continuations to optimize code
Wed Dec 5 15:12:18 CET 2001
Was that a deep recursion?
Here is a theory that might partially explain your speedups.
In the recursive case, you presumably get a big stack. At every garbage collection,
all of the stack is scanned looking for live data. As the stack grows towards
the heap, you could also get more frequent garbage collections than in the
non-recursive case, and you would get fullsweep GCs (forcing copying of all
In the non-recursive case, the root set for the GC is probably small (since the
stack is presumably small). Each GC is presumably fast since the root set is small
and your continuations are already on the older generation heap. Perhaps no
fullsweeps are done, as your output function produces garbage, but only little or
no more live data. Therefore the continuation data will stay on the older generation
heap and not be copied very often.
Just a bunch of guesses, based on unverified assumptions.
Ulf Wiger <> writes:
> On Wed, 5 Dec 2001, Thomas Lindgren wrote:
> >Congratulations on an interesting performance hack!
> >Those are very interesting timing results, because your
> >CPS-transformation builds a closure instead of pushing a stack
> >frame. As far as I can see from the example, the savings then
> >lie in avoiding the tuple. If so, that's remarkable.
> Of course, there's the tiny little chance that I unknowingly
> fixed some obscure bug in the process of rewriting, and that it
> was that bug that accounted for the overhead... (:
> It would be interesting to see if anyone could verify (or refute)
> my theory that CPS-transformation can actually yield significant
> speedups (they don't have to be in the order of 9000x to be
> Ulf Wiger, Senior Specialist,
> / / / Architecture & Design of Carrier-Class Software
> / / / Strategic Product & System Management
> / / / Ericsson Telecom AB, ATM Multiservice Networks
Björn Gustavsson Ericsson Utvecklings AB
+46 8 727 56 87 125 25 Älvsjö
More information about the erlang-questions