ReplaceAll performance problem: packed arrays on the LHS are unpacked when the RHS is too long

Question

The following is one of the most mysterious performance problems I encountered and came up while extending the booleval function mentioned here. I am looking for a workaround since the whole purpose of writing booleval was to increase performance.

The problem

ReplaceAll will unpack packed arrays that appear on its left-hand-side if the right-hand-side contains more than rules.

Example:

In[1]:= On["Packing"]

In[2]:= AbsoluteTiming[
 Range[1000000] /. {x -> 0, a -> 1, b -> 2, c -> 3, d -> 4, e -> 5, 
    f -> 6, g -> 7, h -> 8, i -> 9(*,j -> 10*)};
 ]

Out[2]= {0.003741, Null}

Up to here it works fine. Now let's uncomment the last rule to have 11 rules in total.

In[3]:= AbsoluteTiming[
 Range[1000000] /. {x -> 0, a -> 1, b -> 2, c -> 3, d -> 4, e -> 5, 
    f -> 6, g -> 7, h -> 8, i -> 9, j -> 10};
 ]

During evaluation of In[3]:= Developer`FromPackedArray::punpack1: Unpacking array with dimensions {1000000}. >>

Out[3]= {0.655815, Null}

Developer`FromPackedArray::punpack1: Unpacking array with dimensions {1000000}. >>

This was very frustrating to debug when I encoutered a performance problem because performance was only bad when I put my code in a function. Originally I had code similar to this:

Unevaluated[Range[1000000]] /. {x -> 0, a -> 1, b -> 2, c -> 3, d -> 4, e -> 5, f -> 6, g -> 7, h -> 8, i -> 9, j -> 10}

The Unevaluated prevents unpacking without preventing ReplaceAll from working. I orignally needed Unevaluated for reasons unrelated to this problem.

Now let's put this into a function:

In[46]:= 
ClearAll[fun]
fun[arg_] := Unevaluated[arg] /. {x -> 0, a -> 1, b -> 2, c -> 3, d -> 4, e -> 5, f -> 6, g -> 7, h -> 8, i -> 9, j -> 10}

In[48]:= AbsoluteTiming[fun[Range[1000000]];]

During evaluation of In[48]:= Developer`FromPackedArray::punpack1: Unpacking array with dimensions {1000000}. >>

Out[48]= {0.608700, Null}

Now the problem is back, but only if the packed array is passed to the function as an argument, not if it's part of the function definition.

Question

Why does ReplaceAll unpack like this? More importantly, is there a workaround for the unpacking that I can apply in booleval? The Unevaluated workaround won't work when I package up the code as a function.

Answer 1

The part about a workaround can, I think, be solved by the same trick as I very recently suggested here - prepend an idle rule:

AbsoluteTiming[
   Range[1000000] /. {
      arr_?Developer`PackedArrayQ :> arr, 
      x -> 0, a -> 1, b -> 2, c -> 3, d -> 4, e -> 5, 
      f -> 6, g -> 7, h -> 8, i -> 9, j -> 10};
]

(* {0.001131, Null} *)

This will only work for ReplaceAll though (and not Replace, Cases etc).

Answer 2

As for the reason: I can't comment on the motivation for this, obviously, but it seems to be the case that replacement using a hash table (Dispatch object) is not possible with a packed array. We can see this from the fact that the threshold for unpacking is only four rules, rather than eleven, when we specify Dispatch explicitly on the right-hand side:

On["Packing"];

Range[10] /. Dispatch[{x -> 0, a -> 1, b -> 2, c -> 3}];
(* (emits message:)
   Developer`FromPackedArray::punpack1: Unpacking array with dimensions {10}. *)

Why, you might ask, is the threshold now four, rather than one (or two)? Well, Dispatch doesn't actually create a hash table for short rule lists, presumably since the overhead of doing so is not justified by the gain in performance:

Dispatch[{x -> 0, a -> 1, b -> 2, c -> 3}]
(* -> Dispatch[{x -> 0, a -> 1, b -> 2, c -> 3}, -DispatchTables-] *)

Dispatch[{x -> 0, a -> 1, b -> 2}]
(* -> {x -> 0, a -> 1, b -> 2} *)

So, the workaround would seem to be anything that prevents ReplaceAll from automatically converting the list of rules into a hash table. Apart from splitting the rules into shorter groups or inserting unhashable rules (as in Leonid's answer), I don't know how one might accomplish this, as there is nothing obviously appropriate in the SystemOptions[], or for that matter anywhere else that I was able to find.