I thought I’d share a useful little trick with the list. I’ve put
together a little library (27 lines for the actual implementation) that
can convert any function into a partially tail-recursive function,
without any alteration required, using a single command.
I ran a few tests on this (included with the library) to show the time
it took to step through my sample recursive function, which stepped
forward through the fibonacci sequence, returning the Nth number (where
N was chosen in advance). Tests were run separately for each one.
N = 10000
Recursive: 0.101 seconds, 22.2 MB RAM (VSZ for process, measured on
final return)
Tail Recursive: 0.132 seconds, 3.44 MB RAM
N = 15000
Recursive: 0.216 seconds, 35.6 MB RAM
Tail Recursive: 0.204 seconds, 3.71 MB RAM
N = 30000
Recursive: 0.984 seconds, 87.5 MB RAM
Tail Recursive: 0.465 seconds, 4.50 MB RAM
N = 100000
Recursive: 79.8 seconds, 579 MB RAM (warning: time is misleading due to
swapping)
Tail Recursive: 2.70 seconds, 8.49 MB RAM
As you can see, benefits in terms of memory begin immediately. Benefits
in terms of processing time take a while to realise, at about a depth
of 15000 in this example. The technique works by aliasing the method to
a random name, replacing it with a method that handles the tail
recursion, and relying on the other function to call it again.
There are a few restrictions:
- The last action of the function must be to recurse or return the
final value - The function must not spawn threads internally (this should work in
threaded applications though).
Other than that, just define your method and call:
tail_recurse :my_method, max_depth
The max_depth factor is used because the library uses a continuation
internally (which is slow) so it is much faster to recurse to a fixed
depth (15 in the tests above) rather than using full tail recursion.
This will default to one, but increasing it will usually improve
performance. For examples of use, see the demonstration included with
the library.
Here’s the library itself:
require ‘thread’
class Module
def tail_recurse(meth, recurse_depth = 1)
random_name = (rand((16 ** 10) / 2) + 16 ** 10).to_s(16).to_sym;
# Create a randomly named alias of our original method
alias_method random_name, meth.to_sym
# Create a new method in the place of the old one
define_method meth.to_sym do |*args|
return_val = nil
if Thread.current[random_name]
# This has been called from the recursive function
Thread.current[random_name][:count] += 1 # Add one to the
period counter
if Thread.current[random_name][:count] % recurse_depth == 0
# Save our arguments and jump back using the continuation
Thread.current[random_name][:args] = args
Thread.current[random_name][:continuation].call
else
# Recurse another level
return_val = send(random_name, *args)
end
else
# This is a new call. Set up for recursion.
Thread.current[random_name] = {}
Thread.current[random_name][:count] = 0
Thread.current[random_name][:args] = args
callcc {|cont| Thread.current[random_name][:continuation] =
cont}
return_val = send(random_name,
*Thread.current[random_name][:args])
end
# Clear out the recursion information
Thread.current[random_name] = nil
return return_val
end
end
end
This is an example that will compare recursive and tail recursive
performance.
if $0 == FILE
class Fibonacci
def fib_tail(a, b, depth)
if depth == 1
#system('ps u -p ’ + Process.pid.to_s)
return b
else
return fib_tail(b, a+b, depth - 1)
end
end
tail_recurse :fib_tail, 15 # Partially tail recurse (15 levels
deep)
def fib_recursive(a, b, depth)
if depth == 1
#system('ps u -p ' + Process.pid.to_s)
return b
else
return fib_recursive(b, a+b, depth - 1)
end
end
end
fib = Fibonacci.new
depth = ARGV.shift
depth ||= 15000
depth = depth.to_i
puts “Normal recursive: #{depth} deep”
start_time = Time.now
val1 = fib.fib_recursive(1,1,depth)
difference = Time.now - start_time
puts “Took #{difference} seconds”
puts “Tail recursive: #{depth} deep”
start_time = Time.now
val2 = fib.fib_tail(1,1,depth)
difference = Time.now - start_time
puts “Took #{difference} seconds”
if val1 == val2
puts “Values Matched”
else
puts “ERROR: Values different”
puts “Recursive:”
puts val1
puts “Tail Recursive:”
puts val2
end
end