[gambit-list] Poor compilation of do-loops

Bradley Lucier lucier at math.purdue.edu
Fri Oct 16 12:51:38 EDT 2009


On Thu, 2009-10-15 at 15:57 -0400, Marc Feeley wrote:
> 
> On 2009-10-15, at 12:22 PM, Bradley Lucier wrote:
> 
> > Marc:
> >
> > At the end of this message I suggest a compiler transformation of
> > do-loops that doubles the speed of the sample code.
> 
> Your transformation of nested do loops is not always a win.  It may  
> increase the number of free variables of the inner loop.  See the  
> example below.  In fact the transformation that Gambit uses can be  
> made arbitrarily faster than yours (by increasing the number of free  
> variables).  It is in the worst case a constant factor slower.

So, you're saying that with Gambit's imperfect (to be *very* polite)
register allocator, lambda-lifting loops adds more free variables to the
inner loops, which can slow things down arbitrarily much with certain
loops, which, to my eye, look pretty pathological.  So your way of
generating code is minimax (minimizes the maximum possible delay), while
what I'm suggesting would, I claim, speed up the average loop at the
risk of delaying some convoluted code that only a compiler-writer would
dream up.  (The code looks like a state machine after my transformation,
and I believe that state machines should be compiled into efficient code
by Scheme compilers.)

There are ways to test this hypothesis of "average loop".  One could add
this transformation temporarily and then run the benchmark suite with
and without the transformation.  The source files with '(do ' are:

array1.scm
browse.scm
compiler.scm
destruc.scm
diviter.scm
divrec.scm
gcbench.scm
graphs.scm
matrix.scm
maze.scm
nboyer.scm
perm9.scm
puzzle.scm
ray.scm
sboyer.scm
simplex.scm
string.scm
sumloop.scm
trav1.scm
trav2.scm
triangl.scm

Or, you could release a special beta version of Gambit with the
transformation and let people with numeric codes try it out and reply to
this list with their results.

> 
> So a heuristic would have to be developed to identify the cases where  
> your transformation is a win.  Care to find one?  It doesn't seem easy.

How about "do it if it doesn't increase the number of free variables by
k%", like inlining-limit.

Brad



More information about the Gambit-list mailing list