From 15da52e7c74d3a0406efdfd469a040a5a226704e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 13 Dec 2016 14:02:34 +0100 Subject: Shorten the tail-recursion myth The myth about tail recursion being faster than body recursion still seems to be alive, but we don't need to spend that much space discussing it as we needed earlier. Shorten the discussion and include a link to to Fred Hebert's excellent blog post. --- system/doc/efficiency_guide/myths.xml | 54 +++++++++++------------------------ 1 file changed, 16 insertions(+), 38 deletions(-) (limited to 'system') diff --git a/system/doc/efficiency_guide/myths.xml b/system/doc/efficiency_guide/myths.xml index d6cb27ddf0..168aa3d35c 100644 --- a/system/doc/efficiency_guide/myths.xml +++ b/system/doc/efficiency_guide/myths.xml @@ -46,44 +46,22 @@ Than Recursive Functions

According to the myth, - recursive functions leave references - to dead terms on the stack and the garbage collector has to copy - all those dead terms, while tail-recursive functions immediately - discard those terms.

- -

That used to be true before R7B. In R7B, the compiler started - to generate code that overwrites references to terms that will never - be used with an empty list, so that the garbage collector would not - keep dead values any longer than necessary.

- -

Even after that optimization, a tail-recursive function is - still most of the times faster than a body-recursive function. Why?

- -

It has to do with how many words of stack that are used in each - recursive call. In most cases, a recursive function uses more words - on the stack for each recursion than the number of words a tail-recursive - would allocate on the heap. As more memory is used, the garbage - collector is invoked more frequently, and it has more work traversing - the stack.

- -

In R12B and later releases, there is an optimization that - in many cases reduces the number of words used on the stack in - body-recursive calls. A body-recursive list function and a - tail-recursive function that calls lists:reverse/1 at - the end will use 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.

- -

So, which is faster? - It depends. On Solaris/Sparc, the body-recursive function seems to - be slightly faster, even for lists with a lot of elements. On the x86 - architecture, tail-recursion was up to about 30% faster.

- -

So, the choice is now mostly a matter of taste. If you really do need - the utmost speed, you must measure. You can no longer be - sure that the tail-recursive list function always is the fastest.

+ using a tail-recursive function that builds a list in reverse + followed by a call to lists:reverse/1 is faster than + a body-recursive function that builds the list in correct order; + the reason being that body-recursive functions use more memory than + tail-recursive functions.

+ +

That was true to some extent before R12B. It was even more true + before R7B. Today, not so much. A body-recursive function + generally uses the same amount of memory as a tail-recursive + function. It is generally not possible to predict whether the + tail-recursive or the body-recursive version will be + faster. Therefore, use the version that makes your code cleaner + (hint: it is usually the body-recursive version).

+ +

For a more thorough discussion about tail and body recursion, + see Erlang's Tail Recursion is Not a Silver Bullet.

A tail-recursive function that does not need to reverse the list at the end is faster than a body-recursive function, -- cgit v1.2.3