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

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]:= DeveloperFromPackedArray::punpack1: Unpacking array with dimensions {1000000}. >>

Out[3]= {0.655815, Null}

DeveloperFromPackedArray::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]:= DeveloperFromPackedArray::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.

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_?DeveloperPackedArrayQ :> 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).

• It might even be a dupe of that question, except for your observation about length dependence of unpacking. – Leonid Shifrin May 30 '14 at 15:19
• @Szabolcs Thanks for the accept, that was fast :). I didn't give any explanation for the original behavior, though, so answered only a part of your question. – Leonid Shifrin May 30 '14 at 15:26
• I think only people who've worked on pattern matching at WRI can answer the "why". It's also related to this: stackoverflow.com/a/8701756/695132 i.e. Mma shouldn't unpack a packed array during pattern matching if it's clear that there's no match. Cases always unpacks because it starts searching at the deepest level. It seems ReplaceAll will only unpack everything if there are many replacement rules. The frustrating things about these is that it's so difficult to debug (all I saw originally was that putting the code into a function caused it to slow down). – Szabolcs May 30 '14 at 15:35
• @Szabolcs My guess is that for a large list of rules, optimization needed to decide that there is no need to unpack the packed array is becoming too expensive (because the optimizer has to analyze the list of rules), and so is switched off. Which is why we see unpacking for number of rules >= 10 but not smaller. This can be frustrating, I agree, but I suspect that one can't do much better in general, without significantly extending the current pattern-matcher's implementation. The untyped and very generic nature of pattern-matcher certainly does not help with this sort of problems. – Leonid Shifrin May 30 '14 at 15:41
• @Szabolcs In a sense, this just confirms my general view that packed arrays are a language hack, introduced to alleviate the lack of a real compiler. Packed arrays make it possible for us to work as "human compiler" to speed things up, but they also introduce many corner cases, which their users should be aware of. Had Mathematica had the real compiler, you wouldn't even have to know about packing etc, it would just work. – Leonid Shifrin May 30 '14 at 15:44

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:)
DeveloperFromPackedArray::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.