Performance of tail call optimised C++
Share on Mastodon
This series: Lightning talk, Explanation, Performance, Generalisation.
After I wrote a version of tail-call optimised code in C++ I became interested in its performance relative to normal recursion. The tail call version can process arbitrarily large input, but how much do you pay for that in terms of performance?
Recap: there are 4 different versions of our function, called times_two. The first, “hardware”, uses the “*” operator to multiply by 2. The second, “loop” uses a for loop to add up lots of 2s until we get the answer. The third, “recursive”, uses a recursive function to add up 2s. The fourth, “tail_call” is a reimplementation of “recursive”, with a manual version of the tail call optimisation – see the original article for details.
Let’s look first at memory usage. Here is the stack memory usage over time as reported by Massif of calling the four functions for a relatively small input value of 100000:
The recursive function uses way more memory than the others (note the logarithmic scale), because it keeps all those stack frames, and the tail_call version takes much longer than the others (possibly because it puts more strain on Massif?), but keeps its memory usage low. Let’s look at how that affects its performance, for different sizes of input:
For these much larger input values, the recursive and tail_call functions take similar amounts of time, until the recursive version starts using all the physical memory on my computer. At this point, its execution times become huge, and erratic, whereas the tail_call function plods on, working fine.
So the overhead of the infrastructure of the tail call doesn’t have much impact on execution time for large input values, but it’s clear from the barely-visible green line at the bottom that using a for-loop with a mutable loop variable instead of function calls is way, way faster, with my compiler, on my computer, in C++. About 18 times faster, in fact.
And, just in case you were wondering: yes those pesky hardware engineers with their new-fangled “*” operator managed to defeat all comers with their unreasonable execution times of 0 seconds every time (to the nearest 10ms). I suppose that shows you something.