Ruby doesn’t do tail call optimization. That sucks. However, quite a few month ago I managed to fake it:
RunAgain = Class.new(Exception) def fib(i, n = 1, result = 0) if i == -1 result else raise RunAgain end rescue RunAgain i, n, result = i - 1, n + result, n retry end
It was extremely slow (see benchmark at the end of this post) since it has to build backtrace for each raise, but at least it worked! I was proud; very proud. Until I discovered this snippet:
class Class # Sweet stuff! def tailcall_optimize( *methods ) methods.each do |meth| org = instance_method( meth ) define_method( meth ) do |*args| if Thread.current[ meth ] throw( :recurse, args ) else Thread.current[ meth ] = org.bind( self ) result = catch( :done ) do loop do args = catch( :recurse ) do throw( :done, Thread.current[ meth ].call( *args ) ) end end end Thread.current[ meth ] = nil result end end end end end class TCOTest # tail-recursive factorial def fact( n, acc = 1 ) if n < 2 then acc else fact( n-1, n*acc ) end end # length of factorial def fact_size( n ) fact( n ).size rescue $! end end t = TCOTest.new # normal method puts t.fact_size( 10000 ) # => stack level too deep # enable tail-call optimization class TCOTest tailcall_optimize :fact end # tail-call optimized method puts t.fact_size( 10000 ) # => 14808
Not only was it faster, you could also drop it in wherever you want. Sweet stuff, indeed. 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: The
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:
puts "Please enter the first word you think of" words = %w(apple banana cherry) response = words.collect do |word| # Control returns here when redo is executed print word + "> " # Prompt the user response = gets.chop # Get a response if response.size == 0 # If user entered nothing word.upcase! # Emphasize the prompt with uppercase redo # And skip to the top of the block end response # Return the response end
So I started thinking: The reason I used raise/rescue in my implementation was because I needed the
retry-keyword… Maybe… What if?
def fib(i, n = 1, result = 0) if i == -1 result else i, n, result = i - 1, n + result, n redo end end fib(10000)
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:
### Everything is possible in Ruby! define_method(:acc) do |i, n, result| if i == -1 result else i, n, result = i - 1, n + result, n redo end end def fib(i) acc(i, 1, 0) end fib(10000) # Yeah!
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.