continuations to optimize code

Bjorn Gustavsson bjorn@REDACTED
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
live data).

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 <etxuwig@REDACTED> 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
> significant.)
> /Uffe
> -- 
> 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
bjorn@REDACTED      ÄT2/UAB/F/P
			    BOX 1505
+46 8 727 56 87 	    125 25 Älvsjö

More information about the erlang-questions mailing list