Performance of Dispatch and lists of Rules

Question

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?

Answer 1

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.