Ruby doesn’t implement tail call optimization, so a while ago I tried to figure out how I could fake it:
It was extremely slow (see the benchmark at the end of this post) since it has to build backtraces for each exception, but hey: It worked! I was proud; very proud. Well, until I discovered this awesome snippet:
Magical stuff. Fast and sweet. My (failed) attempt was sent to /dev/null immediately…
The Ruby Programming Language arrives
A few months later, I received my copy of The Ruby Programming Language and started reading it. Suddenly, on page 151:
The Ruby Programming Language, page 151, 5.5.4 redo:
redostatement restarts the current iteration of a loop or iterator. This is not the same thing as
nexttransfers control to the end of a loop or block so that the next iteration can begin, whereas
redotransfers control back to the top of the loop or block so that the iteration can start over. If you come to Ruby from a C-like language, then
redois probably a new control structure for you.
I’ve used Ruby for a long time, still I’ve never heard of redo… Here’s an example from the book:
So I started thinking: The reason I used raise/rescue in my implementation was because I needed the
retry-keyword… Maybe… What if?
redo statement restarts the currentiteration of a loop or iterator”, so it only throws a LocalJumpError. However, don’t forget that we’re dealing with Ruby:
Native Support in 1.9.2
It turns out that there’s yet another way to achive tail call optimization in Ruby: Ruby 1.9.2 actually ships with native support, but it’s disabled by default. You can either enable it through a compile-flag or by specifying the compile options at runtime (thanks a lot to Roman Semenenko for showing me this trick!):
Notice that the compile options will only be used for the code you pass into InstructionSequence, not any regular code. Also be aware of that these tail call optimization are considered experimental and there might be bugs related to them (like #4082). However, they perform pretty good (see the TCO-graph below).
So, how fast is it? Take a look below:
- You can zoom by marking in any of the graphs.
- When you un-tick a graph, mark in the lower graph to zoom in.
- Un-tick everything else than “Redo” and “Iterative” and notice how close they are to each other.
- Look how bad “Rescue” performs,
- and how early “Regular” fails.
- All the code is available at GitHub