[erlang-questions] continuation vs. accumulator

[June Kim]

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

Factorial

In non-tail-recursive-style:

fact(1)-> 1;
fact(N)->N*fact(N-1).

In accumulator-passing-style:

fact_aps(1,Acc)->
    Acc;
fact_aps(N,Acc)->
    fact_aps(N-1,N*Acc).
fact_aps(N)->
    fact_aps(N,1).

In continuation-passing-style:

fact_cps(1,K)->
    K(1);
fact_cps(N,K)->
    fact_cps(N-1, fun(X) -> K(X*N) end).
fact_cps(N)->
    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
calls)

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)?