# Performance of Dispatch and lists of Rules

The issue outlined here seems to be no longer present in version 10, if you use a Dispatch table! This because a Dispatch table is now an atom.

My question arose when I tried to answer this question by Mr.Wizard

Consider these definitions

Clear @@ Names["x" ~~ DigitCharacter ..]
rules2 = Array[Symbol["x" <> ToString[#]] -> # &, 100000 ];
dRules2 = Dispatch[rules2];


We have

AbsoluteTiming[Symbol["x" <> "100000"] /. dRules2]

{0.000956,100000} (*version 9*)
{0.000022,100000} (*version 10*)

AbsoluteTiming[Symbol["x" <> "100000"] /. rules2]

{0.005132,100000} (*version 9*)
{0.100221,100000} (*first time version 10*)
{0.014408,100000} (*after first time version 10*)


It was to be expected that the dispatch tables are faster. It seems Dispatch tables became faster in V10, but regular replacement by a long list of rules become considerably slower. That is not the point here however, point is that the following breaks the dispatch table in version 9.

Update[x10]
AbsoluteTiming[Symbol["x" <> "100000"] /. dRules2]

 {0.076655,100000} (*version 9*)
{0.000026,100000} (*version 10*)

Update[x10]
AbsoluteTiming[Symbol["x" <> "100000"] /. rules2]

 {0.017523,100000} (*version 9*)
{0.063556,100000} (*version 10*)


Where all the evaluations have slowed down substantially (except there is no "first time delay" in version 10). The version 9 dispatch table is slower than the regular list of rules. I do not expect many people to use Update, but this should still be relevant to many people, as I believe an assignment causes an update. See an example further below.

I found out that updating a variable present in the list of rule causes the expression (list/dispatch table) containing the rules to be rebuilt. This takes a long time.

We can see that the rules get rebuilt from the following examples. Let

rules = {y1 -> 1, y2 -> 2, y3 -> 3};


Then

Trace[y1 /. rules, TraceOriginal -> True]

{y1/. rules,{ReplaceAll},{y1},{rules,{y1->1,y2->2,y3->3}},y1/. {y1->1,y2->2,y3->3},1}


and

Update[y3]
Trace[y1 /. rules, TraceOriginal -> True]

 {y1/. rules,{ReplaceAll},{y1},{rules,{y1->1,y2->2,y3->3},{List},{y1->1},{y2->2},
{y3->3,{Rule},{y3},{3},y3->3},{y1->1,y2->2,y3->3}},y1/. {y1->1,y2->2,y3->3},1}


In the second case we see the Trace is longer. We basically see that the expression rules gets rebuilt. The rule containing y3 gets a little more attention.

An example where this does not happen is the following. Let

blockRules = {HoldComplete[x, 1], HoldComplete[y, 2],
HoldComplete[z, 3], HoldComplete[x, 4]};


Then we have

Equal @@ {Trace[Cases[blockRules, _[x, y_] -> y, 1, 1],
TraceOriginal -> True]
Update[z];
Trace[Cases[blockRules, _[x, y_] -> y, 1, 1],
TraceOriginal -> True]}

True


despite the fact that we updated. HoldComplete prevents the tracking of symbols and therefore the expression does not get rebuilt.

The point is that I find this behaviuor of Dispatch (and also the lists of rules) very troubling. Note that HoldPattern will not save you, it does not have attribute HoldAllComplete, so even lists of rules with this wrapper will get rebuilt. Lists of rules will always contain many symbols, so the risk of updating one is very high I'd say.

To be complete, here is an example using HoldPattern. We have

hPRules = {HoldPattern[y1] -> 1, HoldPattern[y2] -> 2,
HoldPattern[y3] -> 3};
Unequal @@ {Trace[y1 /. hPRules, TraceOriginal -> True], Update[y3];
Trace[y1 /. hPRules, TraceOriginal -> True]}

True


The same happens for assignment. To be really complete, here is another example

Composition[Length,
Flatten] /@ {Trace[y1 /. hPRules, TraceOriginal -> True], y3 = 2;
Trace[y1 /. hPRules, TraceOriginal -> True]}

{7, 18}


Where again our list of rules got rebuilt.

Well I guess the questions are a bit contrived. To share my worries was the main point. But here it is I guess:

In version 9, should we be very careful with Dispatch and lists of Rules? Does anybody know a good way around this?

-
That's a good observation you made on Update, but Update is a rather special command. In my experience, I had at most a dozen cases where I really needed to use Update (i.e. it was crucial). I would think that the general message we should take home from your observation is that it is best to not use l-values (symbols or expressions which can be assigned values) as l.h.s. of rules (also in Dispatch), but I more or less follow this practice in any case. –  Leonid Shifrin May 21 '13 at 20:31
Observe that if you call the dispatch table after the Update and before the substitution the substitution is not slowed down. So perhaps you need to "overload" Update in a such fashion that will also update the rules if a symbol contained in one is updated. –  Spawn1701D May 21 '13 at 20:41
@JacobAkkerboom The usual way HoldPattern is used is to prevent some patterns from evaluation. When wrapped around symbols, it is occasionally ok, but this is arguably not its main use. But if I understand correctly, your observation only affects the speed of rule application, not the result. When I have something like HoldPattern[sym], I usually don't care about the speed so much. So, while I agree that you made an interesting observation, I fail to see how this would affect e.g. code I personally write in the 99.9 percent of cases. So, for me, it is just a good warning. Of course, YMMV. –  Leonid Shifrin May 21 '13 at 21:43
@LeonidShifrin Thanks, I will keep that in mind. I guess I am also focussed on the occurrence of HoldPattern in DownValues (which are not really used by the system, but still). Anyway, you understand correctly. Good night for now! –  Jacob Akkerboom May 21 '13 at 21:57
@JacobAkkerboom Ok, that's an important note (DownValues). You are right in that we may want to understand this issue a bit better. Good night! –  Leonid Shifrin May 21 '13 at 22:14

It turns out there are ways to protect your Dispatch tables in version 9 (again, all of this is not necessary in version 10)! That is, you do not have to make sure that all the symbols in your Dispatch table/list of rules get no assignments or updates made to them until you are done using your Dispatch table.

You simply have to shield them from evaluation and use Unevaluated just before you use them (with Replace etc). Lets have the following definitions

kkkk = 6;
Clear @@ Names["x" ~~ DigitCharacter ..]
rules2 = Array[Symbol["x" <> ToString[#]] -> # &, kkkk];
dRules = Dispatch[rules2];


We then have

Update[x3];
Cases[
Trace[
ReleaseHold@
Hold[Replace][x1,
Apply[Unevaluated, Hold[dRules] /. OwnValues[dRules]]]
,
TraceOriginal -> True
]
,
Dispatch | Rule, Infinity] == {}

True


Indicating no expression with head Dispatch or Rule was ever re-evaluated (check the full Trace if you want).

Avoiding HoldPattern (unnecessary perfectionism?)

Now I will also show how to avoid using HoldPattern. HoldPattern is a bit misleading, as it does not shield from updates. When we shield the Dispatch table from evaluation anyway, we carry the HoldPatterns around for no real reason. It can be convenient to use HoldPattern in the definition of a Dispatch table though. But I have found out this is not strictly necessary. Here is the way to avoid it. Let's have the following definitions as an example to work with.

x6 = 7; (*I show we can avoid this complication*)
stringSymbols = Array["x" <> ToString[#] &, 6];
symbolsCHeld =
Apply[HoldComplete,
List@ToExpression[stringSymbols, InputForm, Hold]][[All, All, 1]]

rulesCHeld =
Apply[HoldComplete,
List @@
MapIndexed[
Function[Null, With[{index = Last[#2]}, Hold[# -> index]],
HoldAll], symbolsCHeld, {2, 2}]][[All, All, 1]]

 HoldComplete[{x1,x2,x3,x4,x5,x6}]
HoldComplete[{x1->1,x2->2,x3->3,x4->4,x5->5,x6->6}]


Now we can make our Dispatch table inside Block as follows. We do this inside Block as this allows the Dispatch table to be built correctly, even though x6 has a value. Note that the code below assigns the returned value to fragileCHeldDispatch.

ReleaseHold@
Hold[Block][symbolsCHeld,
Hold[Set][Hold[fragileCHeldDispatch],
rulesCHeld /. _[yyyy_] ->
Hold[HoldComplete @@ List@Dispatch[yyyy]]]]

HoldComplete[Dispatch[{x1->1,x2->2,x3->3,x4->4,x5->5,x6->6},-DispatchTables-]]


Now, even if I had not set x6 in the beginning, the expression inside the HoldComplete would rebuild when exposed to evaluation. That is a downside of this approach (another being that we have to use Block in this crazy way). Anyway, we now have

Update[x3]
{
Cases[
#
,
Dispatch | Rule, Infinity]
,
Last[#]
} &@

Trace[
ReleaseHold@
Hold[ReplaceAll][Unevaluated[{x1, x2, x3, x4, x5, x6}],
Unevaluated @@ fragileCHeldDispatch]
,
TraceOriginal -> True
]

{{},{1,2,3,4,5,6}}


I hope I can soon use these techniques to provide an elegant answer to Mr.Wizards question.

-