Optimization Module

Optimization Module (ruby-optimizer)

"ruby-optimizer" is an extension module which provides functionarity for optimizing methods and blocks.

CVS:

Example 1

This example code shows you tail-recursion and tail 'return' elimination:

require 'optimizer'

def sum_(n, acc)
  if( n > 0 )
    return sum_(n-1, acc + n)
  else
    return acc
  end
end

def sum(n)
  sum_(n, 0)
end

def time(str)
  t1 = Time.now
  begin
    yield
  rescue Exception => e
    print("#{str}: #{e.message}\n")
    #print(e.backtrace.join("\n"),"\n")
    return
  end
  t2 = Time.now
  print("#{str}: #{t2 - t1}\n")
end

time("normal"){
  p sum(ARGV[0].to_i)
}

optimize :sum_
time("optimized"){
  p sum(ARGV[0].to_i)
}

The follows are results:

$ ruby-1.6 sum.rb 1000
500500
normal: 0.014218
500500
optimized: 0.002818

$ ruby-1.6 sum.rb 10000
normal: stack level too deep
50005000
optimized: 0.03651

$ ruby-1.6 sum.rb 100000
normal: stack level too deep
5000050000
optimized: 0.505242

Example 2

The following example shows '!' elimination:

require 'optimizer'

def foo(x)
  if( !(x == 0) )
    x + foo(x - 1)
  else
    x
  end
end

def time(str)
  t1 = Time.now
  begin
    yield
  rescue Exception => e
    print("#{str}: #{e.message}\n")
    #print(e.backtrace.join("\n"),"\n")
    return
  end
  t2 = Time.now
  print("#{str}: #{t2 - t1}\n")
end

time("normal"){
  foo(ARGV[0].to_i)
}

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

$ ruby-1.6 ex1.rb 1000
normal: 0.01492
optimized: 0.010724

$ ruby-1.6 ex1.rb 2000
normal: 0.030962
optimized: 0.019915

Example 3 (Eratosthenes Benchmark)

The following scripts are available at:

http://www.bagley.org/~doug/shootout/bench/sieve/detail.shtml

I quickly hacked ruby's script as follows:

require "optimizer"
NUM = Integer(ARGV.shift || 1)

def foo()
$count = i = j = 0
flags0 = Array.new(8192,1)

NUM.times do
    $count = 0
    flags = flags0.dup
    for i in 2 .. 8192
        next unless flags[i]
        # remove all multiples of prime: i
        (i+i).step(8192, i) do |j|
            flags[j] = nil
        end
        $count += 1
    end
end
end

optimize :foo
foo()

print "Count: ", $count, "\n"

The above script name is `sieve.ruby.optimized'. I got the following result:

$ ruby-1.6 -v
ruby 1.6.7 (2002-08-01) [i686-linux]
$ time ruby-1.6 sieve.ruby 200
Count: nil

real    0m6.223s
user    0m6.190s
sys     0m0.020s

$ time ruby-1.6 sieve.ruby.optmized 200
Count: 1028

real    0m5.745s
user    0m5.710s
sys     0m0.010s


$ perl -v
This is perl, v5.6.0 built for i586-linux
$ time perl sieve.perl 200
Count: 1028

real    0m4.858s
user    0m4.750s
sys     0m0.010s


$ python
Python 1.5.2 (#1, Dec 10 2001, 00:15:29)
$ time python sieve.python 200
Count: 1028

real    0m4.975s
user    0m4.950s
sys     0m0.000s

$ ocaml 
        Objective Caml version 3.04
$ time ocaml sieve.ocaml 200
Count: 1028

real    0m1.059s
user    0m1.040s
sys     0m0.010s

$ guile -v
Guile 1.4
$ time guile -e main -s sieve.guile 200
Count: 1028

real    0m6.307s
user    0m6.200s
sys     0m0.010s

$ sml
Standard ML of New Jersey, Version 110.0.7
$ sml < sieve.smlnj
$ time sml @SMLload=sieve.x86-linux 200
Count: 1028

real    0m0.182s
user    0m0.180s
sys     0m0.000s

ttate@kt.jaist.ac.jp