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