As bad as anything else

2011 07 12

Erlang's Tail Recursion is Not a Silver Bullet

One common belief held by Erlang programmers has to do with tail recursion generally being the best way around when writing code. It's absolutely vital when writing long-running processes (you do not want to go out of memory because of your stack!), I'm not debating that here. However, most sources show how to write Erlang functions by always favoring tail recursive solutions. I know Learn You Some Erlang does fall into the same trap.

Why do I call it a trap? Well, because tail recursion is sometimes vital but body recursion never is, it's kind of normal to always show examples with tail recursion so it becomes absolutely natural to everyone. It's also easier to avoid problems because bad tail recursion often has fewer negative side-effects than bad body recursion (the fibonacci function comes to mind here). However, in some cases, tail recursion is actually slowing your application down The cases where this happens include pretty much every function where you build a list. Now I figure this is somewhat limited given how many possible data structures can be used, but the truth is, lists are everywhere and will almost always be a sizeable portion of the code you write in Erlang.

Let's go with an example, the flush function. The flush function will look at the mailbox and remove messages from there until nothing's left. My version here will accumulate the messages in the order they happened:

tail_flush() -> tail_flush([]).
tail_flush(Acc) ->
    receive
        Msg -> tail_flush([Msg|Acc])
    after 0 -> lists:reverse(Acc)
    end.

This is a rather standard tail recursive function. Here's the body-recursive version:

flush() ->
    receive
        Msg -> [Msg|flush()]
    after 0 -> []
    end.

I think few Erlang programmers would disagree with me if I were to say that flush/0 is much simpler and elegant than tail_flush/0. It's easier to understand and more idiomatic. But here's the thing: the tail recursive one is likely the one we'll see the most in existing code (without proof).

I would dare say that tail recursion is not important here. We can just drop it and go with the simplest way of writing code. In both cases, I basically end up creating a list, which will hold all the values of all messages. In one case, I will be creating a list of N elements to be carried on the stack, in the other case, I'll be having a stack that is about the size of N elements, right? The difference is that the tail recursive version will create a lot of garbage by just dropping the accumulator after reversing it. A step by step explanation to this problem and hypothesis were given by Raimo Niskanen on the Erlang mailing list. Here's the theoretical conclusion:

tail recursion should require a top memory consumption of 2 * size(MsgList) words more than body recursion. This will cause extra garbage collection. Also the lists:reverse/1 is extra work that the body recursive variant avoids. In this case I speculate body recursion wins.

So I decided to test this with a crappy micro-benchmark. I usually do not like to trust micro-benchmarks as they are a bit unreliable if you don't think of everything, but still, this seemed a good proof enough for a blog post:

-module(bench).
-compile(export_all).

main() ->
    L = lists:seq(1,100000),
    F = fun(X) -> X end,
    spawn(fun() -> io:format("Tail:~p~n", [element(1, timer:tc(?MODULE, tail_map, [F, L]))]) end),
    spawn(fun() -> io:format("Body:~p~n", [element(1, timer:tc(?MODULE, body_map, [F, L]))]) end).

tail_map(F, L) ->
    tail_map(F, L, []).

tail_map(_, [], Acc) -> lists:reverse(Acc);
tail_map(F, [H|T], Acc) -> tail_map(F, T, [F(H)|Acc]).

body_map(_, []) -> [];
body_map(F, [H|T]) -> [F(H) | body_map(F, T)].

So each process will iterate (while doing nothing) over a list of 100,000 integers. Fairly simple. Here are the results of a few runs, in microseconds:

Body:9384
Tail:14556
Body:11150
Tail:16260
Body:9419
Tail:14732
Body:11386
Tail:17946
Body:11380
Tail:16512
Body:10885
Tail:16876
Body:9923
Tail:14085

Body recursion is consistently faster. This might have to do with the size of each process and garbage collection. Quick tracing showed that in the case of this benchmark, with the arguments given to the function, the body recursive version had to be garbage collected once, while the tail recursive version had to be garbage collected twice. This would seem to support the theory. But hey, this could be related to some concurrency or allocation of processes and whatnot. So here I'm adding another overly simplistic benchmark, where both calls will run one after the other, in a single process:

main2() ->
    spawn(fun() ->
        L = lists:seq(1,100000),
        F = fun(X) -> X end,
        tail_map(F,L),
        body_map(F,L),
        { {A,_}, {B,_}} = {timer:tc(?MODULE, tail_map, [F, L]), timer:tc(?MODULE, body_map, [F, L])},
        io:format("Tail:~p~nBody:~p~n", [A,B])
    end).

Here I'm running both functions once before the timing. In case I ever need to resize the existing process so everything won't need to be garbage collected as much:

Tail:5329
Body:8648
Tail:5292
Body:6873
Tail:6738
Body:8798
Tail:5718
Body:6818
Tail:5266
Body:8669
Tail:5470
Body:6716
Tail:8108
Body:8952
Tail:5461
Body:6545
Tail:5648
Body:8607
Tail:5424
Body:7153

Aw crap. All my pretty conclusions, gone. Now body recursion is slower than tail recursion. However, not all is lost. What we can see is that body recursion is somewhat stable: running the function once or many times seems to yield very similar performances. In the case of tail recursion, having all the required space allocated beforehand and the GC having done its thing already seems to vastly improve the run time compared to a cold start.

Moreover, if I change the benchmarks a bit so that each of the looping functions runs a few hundred times within their own process, body recursion becomes faster again:

main3() ->
    L = lists:seq(1,100000),
    F = fun(X) -> X end,
    spawn(fun() -> io:format("Tail:~p~n", [element(1, timer:tc(?MODULE, m_tail_map, [F, L, 500]))]) end),
    spawn(fun() -> io:format("Body:~p~n", [element(1, timer:tc(?MODULE, m_body_map, [F, L, 500]))]) end).

m_tail_map(_, _, 0) -> ok;
m_tail_map(F, L, N) ->
    tail_map(F,L),
    m_tail_map(F, L, N-1).

m_body_map(_, _, 0) -> ok;
m_body_map(F, L, N) ->
    body_map(F,L),
    m_body_map(F, L, N-1).

And the results:

Body:2807180
Tail:3577161
Body:2810430
Tail:3644639
Body:2852699
Tail:3611445
Body:2898529
Tail:3699570
Body:3016723
Tail:3711662
Body:3027023
Tail:3712915
Body:2933290
Tail:3623219

What does this mean? Well if I can get ahead of myself and pretend I can trust these results for the general case (which is probably not the smartest thing to do), it'd be that it seems right to believe that tail recursion does require more work. Tracing the main/0 function for garbage collection revealed that it ended up needing more heap space towards the end of its run time when calling lists:reverse/1. On the other hand, body recursion was able to do its thing within the space that was already allocated to it. It seems to be that this memory work is what makes tail recursion be slower for list building, although there are definitely cases where this is false.

This could also mean that using the most idiomatic form of recursion would be what you want to use when you need a lower memory footprint, sometimes more speed and cleaner code when building lists. This is a great property of Erlang: writing idiomatic and clean code often leads to optimal solutions. I would still say that it is very, very unlikely that the type of recursion you use when building lists would be the bottleneck of your application. In any case, to quote Raimo (who is quoting von Siemens), to measure is to know.

If you clicked on the Erlang mailing list link a few paragraphs earlier, you will have seen that Raimo added warnings relevent to this case:

In some other implementation where heap and stack are not in the same memory block the situation changes. I know of no such implementation yet. In the Erjang prototype stack space is limited so all body recursion should be avoided. That might be an unacceptable limitation since it impacts so hard at body recursion.

The measurements in this case were done on a single laptop, with a certain architecture, hardware and a given load on it, on the BEAM virtual machine, which has particular optimizations and a particular way to lay out a process' memory. These results are far from guaranteed to be repeatable in other settings (yay! no scientific proof here!). Measure, measure, measure.

One thing that's to remember no matter what is that writing clean code generally leads to better performances. This is something that many languages can not claim as true, but Erlang certainly can. In the general case, the optimisations in the Erlang VM come from observing idiomatic code in production, and clean one at that. This is why body recursion might be better, and why many other optimizations were made. The best recent example I can think of has to do with synchronous messaging patterns, where mailbox scanning has been optimized a little while ago. Clean code is the best code.