Optimizing Mathematica's main loop

Question

Good day,

Reading this thread about performance of pattern matching and functions in Mathematica I was impressed by Timo's idea on optimizing the evaluation of expressions:

I have on occasion constructed a Dispatch table of all the functions I need and manually applied it to my starting expression. This provides a significant speed increase over normal evaluation as none of Mathematica's inbuilt functions need to be parsed against my expression.

How exactly should such a Dispatch table be constructed? In which cases would such an approach be recommended? How does it really work? Are there other methods for optimizing of the Main Loop?

No doubt @Timo will provide the definitive answer shortly, but the documentation about [Dispatch](http://reference.wolfram.com/mathematica/ref/Dispatch.html) will make interesting reading while you wait ;) — WReach, Mar 14 '11 at 14:45
I guess you already took a look at the **Parallel Computing**, **Compile**, **GPU Computing**, **Lightweight Grid Client**, etc — Dr. belisarius, Mar 14 '11 at 17:41
@belisarius Yes, of course. The question is about optimizing standard *Mathematica*'s main loop itself. It is inspired by Timo's remark about "significant speed increase over normal evaluation". — Alexey Popkov, Mar 14 '11 at 18:33

score 2 · Accepted Answer · edited Mar 23 '11 at 14:19

To do this, first you need to be able to calculate the dependencies for your symbol(s). There's a package to do that in a back issue of the Mathematica Journal, which is now free online. Here is the URL: http://www.mathematica-journal.com/issue/v6i1/. See the article "Power Programming: Dependency Analysis."

Here's a worked example:

In[1]:= <<"/path/to/DEPEND.MA"

In[2]:= $ContextPath

Out[2]= {DependencyAnalysis`,PacletManager`,WebServices`,System`,Global`}

In[3]:= f[x_]:=x x

In[4]:= g[x_]:=x+1

In[5]:= h[x_]:=f[x]+g[x]

In[6]:= i[x_]:=f[g[x]]

In[7]:= DependsOn[g][[2]]

Out[7]= {Blank,Pattern,Plus,x}

In[8]:= DownValues@@@DependsOn[g][[2]]

Out[8]= {{},{},{},{}}

In[9]:= getDownValues[s_Symbol]:=DownValues[s]

In[10]:= getDownValues[s_HoldForm]:=getDownValues@@s

In[11]:= getDownValues[s_]:={}

In[12]:= hasDownValues[x_]:=getDownValues[x]=!={} 

In[13]:= ruleListEntries[x_List]:=Union[Union@@ruleListEntries/@x,{x}]

In[14]:= ruleListEntries[x_]:=Select[Union[DependsOn[x][[2]],{x}],hasDownValues]

In[15]:= ruleListEntries[f]

Out[15]= {f}

In[16]:= ruleListEntries[g]

Out[16]= {g}

In[17]:= ruleListEntries[h]

Out[17]= {h,f,g}

In[18]:= ruleListEntries[i]

Out[18]= {i,f,g}

In[19]:= dispatch=getDownValues/@ruleListEntries[i]//Flatten//Union//Dispatch

Out[19]= {HoldPattern[f[x_]]:>x x,HoldPattern[g[x_]]:>x+1,HoldPattern[i[x_]]:>f[g[x]]}

In[20]:= i[x]

Out[20]= (1+x)^2

In[21]:= HoldForm[i[x]]//.dispatch

Out[21]= (x+1) (x+1)

I see no way to get the DownValues for the built-in symbols, so this is useful only to the point of reducing an expression to the point of containing only built-ins.

As I understand, this method probably will work properly only if the code does not contain recursive definitions? It would be interesting to know in which cases this method is expected to give substantial increase of performance. — Alexey Popkov, Mar 31 '11 at 11:18

score 2 · Answer 2 · answered Nov 26 '11 at 21:03

How exactly should such a Dispatch table be constructed?

Say you have a graph (network) consisting of n vertices in a loop:

In[1] := rules =
           With[{n = 1000},
             Table[ToString@i -> ToString@Mod[i + 1, n],
               {i, 0, n - 1}]];

You want to traverse the graph by applying these rewrite rules to an initial vertex. You can perform a single step with i /. rules but this is doing a linear search over rules trying to find the Rule with a lhs that matches the expression i. So applying the rules many times is slow:

In[2] := Nest[# /. rules &, 0, 10000] // AbsoluteTiming

Out[2] = {1.7880482, 0}

Mathematica's Dispatch allows us to precompute a hash table that turns the linear lookup into a constant-time lookup:

In[3] := dispatch = Dispatch[rules];

Applying the dispatch table many times obtains the same answer orders of magnitude faster:

In[4] := Nest[# /. dispatch &, 0, 10000] // AbsoluteTiming

Out[4] = {0.0550031, 0}

In which cases would such an approach be recommended?

When:

You are doing many rewrites with the same set of rewrite rules, and
The set of rewrite rules contains at least 30 rules with constant lhs patterns, i.e. composed only from symbols, sequences and literals.

How does it really work?

It just builds a hash table with the constant patterns as keys.

Are there other methods for optimizing of the Main Loop?

The most effective general approach is to rewrite the rules in another language. In particular, languages of the ML family (SML, OCaml and F#) have very efficient pattern match compilers and garbage collectors so they are able to rewrite terms much faster than Mathematica's general purpose rewriter does.

Optimizing Mathematica's main loop

2 Answers2