From: Takaaki Tateishi <ttate@...>
Date: 2002-08-09T00:57:40+09:00
Subject: optimization module and tail recursion

Hello,

I introduce an extension module called ruby-optimizer:

  http://www.ruby-lang.org/en/raa-list.rhtml?name=Optimization+Module

The implementation is rough and I don't exactly understand how to construct
a node tree. However, today I've successfuly optimize tail recursion
automatically using the module. In this mail, I introduce a script 'fact.rb'
and its result. The script has two versions of the factorial function which
is defined as follows:

require 'optimizer'

# Trivial
def fact1(n)
  if n == 1
    return 1
  else
    return n * fact1(n - 1)
  end
end

# Tail recursion version
# Reference: http://www.shugo.net/article/cmagazine/3rd/   (Japanese)
def fact2_(prod, count, max)
  if( count > max )
    prod
  else
    fact2_(count * prod, count + 1, max)
  end
end

def fact2(n)
  fact2_(1,1,n)
end

'fact1' is a trivial implementation, and 'fact2'('fact2_') is another
implementation which has tail recursion. I use the following method to
measure time:

def time(str)
  t1 = Time.now
  begin
    yield
  rescue SystemStackError,RuntimeError
    print(str, ":", $!.message,"\n")
    return
  end
  t2 = Time.now
  print("#{str}: #{t2 - t1}\n")
end

and execute the following code:

time("fact1"){ fact1(ARGV[0].to_i) }
time("fact2"){ fact2(ARGV[0].to_i) }

optimize :fact2_
time("optimized fact2"){ fact2(ARGV[0].to_i) }

'optimize' optimize a given method. I obtained interesting result:

$ ruby-1.7 -I. fact.rb 1000
fact1: 0.043627
fact2: 0.040168
optimized fact2: 0.019668

$ ruby-1.7 -I. fact.rb 3000
fact1:stack level too deep
fact2: 0.162616
optimized fact2: 0.130709

$ ruby-1.7 -I. fact.rb 10000
fact1:stack level too deep
fact2:stack level too deep
optimized fact2: 1.331363

$ ruby-1.7 -I. fact.rb 30000
fact1:stack level too deep
fact2:stack level too deep
optimized fact2: 13.069898

I welcome your idea,
Thanks,
-- 
Takaaki Tateishi <ttate@kt.jaist.ac.jp>