[erlang-questions] Stack space used by "body-recursive calls".

3 views

Skip to first unread message

Kresten Krab Thorup

unread,

Jun 30, 2010, 4:02:35 AM6/30/10

to erlang-q...@erlang.org

One of my challenges in Erjang is that list comprehensions end up chewing stack space. And today I got a glimpse of hope reading this:

According to http://www.erlang.org/doc/efficiency_guide/myths.html

In R12B and later releases, there is an optimization that will in many cases reduces the number of words used on the stack in body-recursive calls, so that a body-recursive list function and tail-recursive function that calls lists:reverse/1<../man/lists.html#reverse-1> at the end will use exactly the same amount of memory. lists:map/2, lists:filter/2, list comprehensions, and many other recursive functions now use the same amount of space as their tail-recursive equivalents.

Can someone tell me, what exactly is the optimization that was done in R12B? It must be something in the runtime system that recognizes these conditions and does something smart; I'd love to be able to be equally smart.

Kresten Krab Thorup, Trifork

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questio...@erlang.org

Björn Gustavsson

unread,

Jul 3, 2010, 5:13:42 AM7/3/10

to Kresten Krab Thorup, erlang-q...@erlang.org

On Wed, Jun 30, 2010 at 10:02 AM, Kresten Krab Thorup <kr...@trifork.com> wrote:
> One of my challenges in Erjang is that list comprehensions end up chewing stack space. And today I got a glimpse of hope reading this:
>
> According to http://www.erlang.org/doc/efficiency_guide/myths.html
>
> In R12B and later releases, there is an optimization that will in many cases reduces the number of words used on the stack in body-recursive calls, so that a body-recursive list function and tail-recursive function that calls lists:reverse/1<../man/lists.html#reverse-1> at the end will use exactly the same amount of memory. lists:map/2, lists:filter/2, list comprehensions, and many other recursive functions now use the same amount of space as their tail-recursive equivalents.
>
> Can someone tell me, what exactly is the optimization that was done in R12B? It must be something in the runtime system that recognizes these conditions and does something smart; I'd love to be able to be equally smart.

No, it's a compiler optimization - stack trimming. List comprehensions and
other body recursive calls used to eat even more stack space before R12.
(The only support that was added to the run-time system was the trim/2
instruction to do the actual stack trimming.)