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?

Answer 1

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.