[erlang-questions] continuation vs. accumulator

June Kim <>
Sun Jul 29 19:29:17 CEST 2007

Why is continuation passing style faster than accumulator passing
style in erlang?


In non-tail-recursive-style:

fact(1)-> 1;

In accumulator-passing-style:


In continuation-passing-style:

    fact_cps(N-1, fun(X) -> K(X*N) end).
    fact_cps(N, fun(X)->X end).

With small numbers, the running time for each style of factorial
calculation is in the order of fact < fact_cps < fact_aps (fact being
the fastest). For example, when N is 30000:

fact       : 2,484,000 us
fact_cps: 2,593,000 us
fact_aps: 2,828,000 us

Of course, fact being non-tail-recursive, it uses a huge amount of
memory (but it didn't reach the point to the page swap).

When the number grows bigger, for instance over 80000, the order is
exactly reversed :  fact_aps<fact_cps<fact (fact_aps being the
fastest). For example, when N is 80000:

fact       : didn't finish until I had to stop the process after 2 mins
fact_cps: 49,281,000 us
fact_aps: 28,250,000 us

(tested on a windows xp machine with 1GB memory -- I tested each
function in an isolated OS process, being worried about garbage
collector getting in between the timer:tc calls for each factorial

This is result was very surprising to me but the previous result was
surprising. Especially, this part: why is fact_cps faster than
fact_aps? fact_cps might be building up a chain of delayed funs in the
memory and I would guess it should be slower than aps.

In addition to that, is there an easy way of measuring the used memory
during a function call in erlang(other than using unix's top or
windows task manager)?

More information about the erlang-questions mailing list