Optimization module and tail recursion

ruby-talk
1

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

2

“Takaaki Tateishi” ttate@kt.jaist.ac.jp wrote in message
news:200208081557.g78FvQWN029329@smtp16.dti.ne.jp…

Hello,

I introduce an extension module called ruby-optimizer:

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

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:

Great!!! - This ought to become a part of the standard libray at
some point IMO.

Here are is the benchmark for the picture perfect candidate of tail
recursion …

··· 
                                   user      system          total

real
fib(29) 8.773000 0.000000 8.773000 ( 9.254000)
fib_tail(29) 0.000000 0.000000 0.000000 ( 0.015000)
fib_no_rec(15000) 0.391000 0.020000 0.411000 ( 0.429000)
fib_tail(15000) 0.981000 0.040000 1.021000 ( 1.053000)
15000.fib_tail 0.992000 0.050000 1.042000 ( 1.085000)

require ‘optimizer’
require ‘benchmark’
include Benchmark

def fib_tail(n)
__fib_tail (0, 1, n)
end

def __fib_tail(cur, suc, rem)
if rem > 0
__fib_tail(suc, cur + suc, rem - 1)
else
cur
end
end

Class based

class Integer
def fib_tail
__fib(0,1)
end
protected
def __fib(cur,suc)
if self > 0
(self-1).__fib(suc,cur+suc)
else
cur
end
end
end

def fib(n)
if n < 2
n
else
fib(n-1) + fib(n-2)
end
end

def fib_no_rec(n)
if n < 2
n
else
cur ,suc = 0,1
n.times {
tmp = suc
suc = cur + suc
cur = tmp
}
cur
end
end

10.times { |n|
[fib_tail(n), n.fib_tail, fib_no_rec(n)].each {|f|
raise “bad” unless fib(n) == f
}
}

bmbm { |x|
x.report(“fib(29)”) { fib(29) }
x.report(“fib_tail(29)”) { fib_tail(29) }
x.report(“fib_no_rec(15000)”) { fib_no_rec(15000) }
x.report(“fib_tail(15000)”) { fib_tail(15000) }
x.report(“15000.fib_tail”) { 15000.fib_tail }
}

/Christoph

3

At Sat, 10 Aug 2002 22:26:28 +0900,

Great!!! - This ought to become a part of the standard libray at
some point IMO.

Thanks,

Here are is the benchmark for the picture perfect candidate of tail
recursion …

Didn’t you forget to use ‘optimize :__fib_tail’ and ‘instance_optimize :__fib’?
I got the following result:

fib(29) 2.680000 0.070000 2.750000 ( 2.759829)
fib_tail(29) 0.000000 0.000000 0.000000 ( 0.000091)
fib_no_rec(15000) 0.080000 0.020000 0.100000 ( 0.101072)
fib_tail(15000) 0.100000 0.010000 0.110000 ( 0.126680)
15000.fib_tail fib.rb:27:in `__fib’: stack level too deep (SystemStackError)

···

–
Takaaki Tateishi ttate@kt.jaist.ac.jp