[erlang-questions] continuation vs. accumulator
Sun Jul 29 19:29:17 CEST 2007
Why is continuation passing style faster than accumulator passing
style in erlang?
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