Add some of MRI's benchmarks

18 files changed, 636 insertions, 16 deletions

diff --git a/.gitignore b/.gitignore
index 3657b105d..e3f434432 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,8 +2,8 @@
 *.bak
 *.d
 *.o
-benchmark/**/*.dat
-benchmark/*.pdf
+/benchmark/**/*.dat
+/benchmark/*.pdf
 *.orig
 *.pdb
 *.rej
diff --git a/benchmark/bm_so_ackermann.rb b/benchmark/bm_so_ackermann.rb
new file mode 100644
index 000000000..7db5be905
--- /dev/null
+++ b/benchmark/bm_so_ackermann.rb
@@ -0,0 +1,19 @@
+#!/usr/bin/ruby
+# -*- mode: ruby -*-
+# $Id: ackermann-ruby.code,v 1.4 2004/11/13 07:40:41 bfulgham Exp $
+# http://www.bagley.org/~doug/shootout/
+
+def ack(m, n)
+    if m == 0 then
+        n + 1
+    elsif n == 0 then
+        ack(m - 1, 1)
+    else
+        ack(m - 1, ack(m, n - 1))
+    end
+end
+
+NUM = 9
+ack(3, NUM)
+
+
diff --git a/benchmark/bm_so_array.rb b/benchmark/bm_so_array.rb
new file mode 100644
index 000000000..2b8fce8f9
--- /dev/null
+++ b/benchmark/bm_so_array.rb
@@ -0,0 +1,23 @@
+#!/usr/bin/ruby
+# -*- mode: ruby -*-
+# $Id: ary-ruby.code,v 1.4 2004/11/13 07:41:27 bfulgham Exp $
+# http://www.bagley.org/~doug/shootout/
+# with help from Paul Brannan and Mark Hubbart
+
+n = 9000 # Integer(ARGV.shift || 1)
+
+x = Array.new(n)
+y = Array.new(n, 0)
+
+n.times{|bi|
+  x[bi] = bi + 1
+}
+
+(0 .. 999).each do |e|
+  (n-1).step(0,-1) do |bi|
+    y[bi] += x.at(bi)
+  end
+end
+# puts "#{y.first} #{y.last}"
+
+
diff --git a/benchmark/bm_so_binary_trees.rb b/benchmark/bm_so_binary_trees.rb
new file mode 100644
index 000000000..8250fba31
--- /dev/null
+++ b/benchmark/bm_so_binary_trees.rb
@@ -0,0 +1,62 @@
+# The Computer Language Shootout Benchmarks
+# http://shootout.alioth.debian.org
+#
+# contributed by Jesse Millikan
+
+# disable output
+alias puts_orig puts
+def puts str
+  # disable puts
+end
+
+def item_check(tree)
+ if tree[0] == nil
+  tree[1]
+ else
+  tree[1] + item_check(tree[0]) - item_check(tree[2])
+ end
+end
+
+def bottom_up_tree(item, depth)
+ if depth > 0
+  item_item = 2 * item
+  depth -= 1
+  [bottom_up_tree(item_item - 1, depth), item, bottom_up_tree(item_item, depth)]
+ else
+  [nil, item, nil]
+ end
+end
+
+max_depth = 14 # ARGV[0].to_i
+min_depth = 4
+
+max_depth = min_depth + 2 if min_depth + 2 > max_depth
+
+stretch_depth = max_depth + 1
+stretch_tree = bottom_up_tree(0, stretch_depth)
+
+puts "stretch tree of depth #{stretch_depth}\t check: #{item_check(stretch_tree)}"
+stretch_tree = nil
+
+long_lived_tree = bottom_up_tree(0, max_depth)
+
+min_depth.step(max_depth + 1, 2) do |depth|
+ iterations = 2**(max_depth - depth + min_depth)
+
+ check = 0
+
+ for i in 1..iterations
+  temp_tree = bottom_up_tree(i, depth)
+  check += item_check(temp_tree)
+
+  temp_tree = bottom_up_tree(-i, depth)
+  check += item_check(temp_tree)
+ end
+
+ puts "#{iterations * 2}\t trees of depth #{depth}\t check: #{check}"
+end
+
+puts "long lived tree of depth #{max_depth}\t check: #{item_check(long_lived_tree)}"
+
+undef puts
+alias puts puts_orig
diff --git a/benchmark/bm_so_concatenate.rb b/benchmark/bm_so_concatenate.rb
new file mode 100644
index 000000000..873214de7
--- /dev/null
+++ b/benchmark/bm_so_concatenate.rb
@@ -0,0 +1,18 @@
+#!/usr/bin/ruby
+# -*- mode: ruby -*-
+# $Id: strcat-ruby.code,v 1.4 2004/11/13 07:43:28 bfulgham Exp $
+# http://www.bagley.org/~doug/shootout/
+# based on code from Aristarkh A Zagorodnikov and Dat Nguyen
+
+STUFF = "hello\n"
+i = 0
+while i<10
+  i += 1
+  hello = ''
+  4_000_000.times do |e|
+    hello << STUFF
+  end
+end
+# puts hello.length
+
+
diff --git a/benchmark/bm_so_exception.rb b/benchmark/bm_so_exception.rb
new file mode 100644
index 000000000..deb003a59
--- /dev/null
+++ b/benchmark/bm_so_exception.rb
@@ -0,0 +1,61 @@
+#!/usr/bin/ruby
+# -*- mode: ruby -*-
+# $Id: except-ruby.code,v 1.4 2004/11/13 07:41:33 bfulgham Exp $
+# http://www.bagley.org/~doug/shootout/
+
+$HI = 0
+$LO = 0
+NUM = 250000 # Integer(ARGV[0] || 1)
+
+
+class Lo_Exception < Exception
+  def initialize(num)
+    @value = num
+  end
+end
+
+class Hi_Exception < Exception
+  def initialize(num)
+    @value = num
+  end
+end
+
+def some_function(num)
+  begin
+    hi_function(num)
+  rescue
+    print "We shouldn't get here, exception is: #{$!.type}\n"
+  end
+end
+
+def hi_function(num)
+  begin
+    lo_function(num)
+  rescue Hi_Exception
+    $HI = $HI + 1
+  end
+end
+
+def lo_function(num)
+  begin
+    blowup(num)
+  rescue Lo_Exception
+    $LO = $LO + 1
+  end
+end
+
+def blowup(num)
+  if num % 2 == 0
+    raise Lo_Exception.new(num)
+  else
+    raise Hi_Exception.new(num)
+  end
+end
+
+
+i = 1
+max = NUM+1
+while i < max
+  i += 1
+  some_function(i+1)
+end
diff --git a/benchmark/bm_so_lists.rb b/benchmark/bm_so_lists.rb
index f8d26797a..e8f4a2a5f 100644
--- a/benchmark/bm_so_lists.rb
+++ b/benchmark/bm_so_lists.rb
@@ -40,7 +40,7 @@ end
 
 i = 0
 while i<NUM
-  i+=1
+  i += 1
   result = test_lists()
 end
 
diff --git a/benchmark/bm_so_mandelbrot.rb b/benchmark/bm_so_mandelbrot.rb
index dd1d75ba1..76331c64b 100644
--- a/benchmark/bm_so_mandelbrot.rb
+++ b/benchmark/bm_so_mandelbrot.rb
@@ -3,7 +3,8 @@
 #
 #  contributed by Karl von Laudermann
 #  modified by Jeremy Echols
-size = 1000 # ARGV[0].to_i
+
+size = 600 # ARGV[0].to_i
 
 puts "P4\n#{size} #{size}"
 
@@ -14,9 +15,6 @@ byte_acc = 0
 bit_num = 0
 
 count_size = size - 1               # Precomputed size for easy for..in looping
-def id(x)
-  x
-end
 
 # For..in loops are faster than .upto, .downto, .times, etc.
 for y in 0..count_size
@@ -40,23 +38,18 @@ for y in 0..count_size
       end
     end
 
-#    byte_acc = (byte_acc << 1) | (escape ? 0b0 : 0b1)
-    byte_acc = (byte_acc * 2) | (escape ? 0b0 : 0b1)
-#    byte_acc = (byte_acc * 2) + (escape ? 0b0 : 0b1)
-#    byte_acc = (byte_acc * 2) + 1
-
+    byte_acc = (byte_acc << 1) | (escape ? 0b0 : 0b1)
     bit_num += 1
 
     # Code is very similar for these cases, but using separate blocks
     # ensures we skip the shifting when it's unnecessary, which is most cases.
     if (bit_num == 8)
-#      print byte_acc.chr
+      print byte_acc.chr
       byte_acc = 0
       bit_num = 0
     elsif (x == count_size)
       byte_acc <<= (8 - bit_num)
-#      byte_acc = byte_acc << (8 - bit_num)
-#      print byte_acc.chr
+      print byte_acc.chr
       byte_acc = 0
       bit_num = 0
     end
diff --git a/benchmark/bm_so_matrix.rb b/benchmark/bm_so_matrix.rb
new file mode 100644
index 000000000..e2c5c8e55
--- /dev/null
+++ b/benchmark/bm_so_matrix.rb
@@ -0,0 +1,48 @@
+#!/usr/bin/ruby
+# -*- mode: ruby -*-
+# $Id: matrix-ruby.code,v 1.4 2004/11/13 07:42:14 bfulgham Exp $
+# http://www.bagley.org/~doug/shootout/
+
+n = 60 #Integer(ARGV.shift || 1)
+
+size = 40
+
+def mkmatrix(rows, cols)
+    count = 1
+    mx = Array.new(rows)
+    (0 .. (rows - 1)).each do |bi|
+        row = Array.new(cols, 0)
+        (0 .. (cols - 1)).each do |j|
+            row[j] = count
+            count += 1
+        end
+        mx[bi] = row
+    end
+    mx
+end
+
+def mmult(rows, cols, m1, m2)
+    m3 = Array.new(rows)
+    (0 .. (rows - 1)).each do |bi|
+        row = Array.new(cols, 0)
+        (0 .. (cols - 1)).each do |j|
+            val = 0
+            (0 .. (cols - 1)).each do |k|
+                val += m1.at(bi).at(k) * m2.at(k).at(j)
+            end
+            row[j] = val
+        end
+        m3[bi] = row
+    end
+    m3
+end
+
+m1 = mkmatrix(size, size)
+m2 = mkmatrix(size, size)
+mm = Array.new
+n.times do
+    mm = mmult(size, size, m1, m2)
+end
+# puts "#{mm[0][0]} #{mm[2][3]} #{mm[3][2]} #{mm[4][4]}"
+
+
diff --git a/benchmark/bm_so_nbody.rb b/benchmark/bm_so_nbody.rb
new file mode 100644
index 000000000..d6c5bb9e6
--- /dev/null
+++ b/benchmark/bm_so_nbody.rb
@@ -0,0 +1,148 @@
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org
+#
+# Optimized for Ruby by Jesse Millikan
+# From version ported by Michael Neumann from the C gcc version,
+# which was written by Christoph Bauer.
+
+SOLAR_MASS = 4 * Math::PI**2
+DAYS_PER_YEAR = 365.24
+
+def _puts *args
+end
+
+class Planet
+ attr_accessor :x, :y, :z, :vx, :vy, :vz, :mass
+
+ def initialize(x, y, z, vx, vy, vz, mass)
+  @x, @y, @z = x, y, z
+  @vx, @vy, @vz = vx * DAYS_PER_YEAR, vy * DAYS_PER_YEAR, vz * DAYS_PER_YEAR
+  @mass = mass * SOLAR_MASS
+ end
+
+ def move_from_i(bodies, nbodies, dt, i)
+  while i < nbodies
+   b2 = bodies[i]
+   dx = @x - b2.x
+   dy = @y - b2.y
+   dz = @z - b2.z
+
+   distance = Math.sqrt(dx * dx + dy * dy + dz * dz)
+   mag = dt / (distance * distance * distance)
+   b_mass_mag, b2_mass_mag = @mass * mag, b2.mass * mag
+
+   @vx -= dx * b2_mass_mag
+   @vy -= dy * b2_mass_mag
+   @vz -= dz * b2_mass_mag
+   b2.vx += dx * b_mass_mag
+   b2.vy += dy * b_mass_mag
+   b2.vz += dz * b_mass_mag
+   i += 1
+  end
+
+  @x += dt * @vx
+  @y += dt * @vy
+  @z += dt * @vz
+ end
+end
+
+def energy(bodies)
+  e = 0.0
+  nbodies = bodies.size
+
+  for i in 0 ... nbodies
+    b = bodies[i]
+    e += 0.5 * b.mass * (b.vx * b.vx + b.vy * b.vy + b.vz * b.vz)
+    for j in (i + 1) ... nbodies
+      b2 = bodies[j]
+      dx = b.x - b2.x
+      dy = b.y - b2.y
+      dz = b.z - b2.z
+      distance = Math.sqrt(dx * dx + dy * dy + dz * dz)
+      e -= (b.mass * b2.mass) / distance
+    end
+  end
+  e
+end
+
+def offset_momentum(bodies)
+  px, py, pz = 0.0, 0.0, 0.0
+
+  for b in bodies
+    m = b.mass
+    px += b.vx * m
+    py += b.vy * m
+    pz += b.vz * m
+  end
+
+  b = bodies[0]
+  b.vx = - px / SOLAR_MASS
+  b.vy = - py / SOLAR_MASS
+  b.vz = - pz / SOLAR_MASS
+end
+
+BODIES = [
+  # sun
+  Planet.new(0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0),
+
+  # jupiter
+  Planet.new(
+    4.84143144246472090e+00,
+    -1.16032004402742839e+00,
+    -1.03622044471123109e-01,
+    1.66007664274403694e-03,
+    7.69901118419740425e-03,
+    -6.90460016972063023e-05,
+    9.54791938424326609e-04),
+
+  # saturn
+  Planet.new(
+    8.34336671824457987e+00,
+    4.12479856412430479e+00,
+    -4.03523417114321381e-01,
+    -2.76742510726862411e-03,
+    4.99852801234917238e-03,
+    2.30417297573763929e-05,
+    2.85885980666130812e-04),
+
+  # uranus
+  Planet.new(
+    1.28943695621391310e+01,
+    -1.51111514016986312e+01,
+    -2.23307578892655734e-01,
+    2.96460137564761618e-03,
+    2.37847173959480950e-03,
+    -2.96589568540237556e-05,
+    4.36624404335156298e-05),
+
+  # neptune
+  Planet.new(
+    1.53796971148509165e+01,
+    -2.59193146099879641e+01,
+    1.79258772950371181e-01,
+    2.68067772490389322e-03,
+    1.62824170038242295e-03,
+    -9.51592254519715870e-05,
+    5.15138902046611451e-05)
+]
+
+init = 200_000 # ARGV[0]
+n = Integer(init)
+
+offset_momentum(BODIES)
+
+puts "%.9f" % energy(BODIES)
+
+nbodies = BODIES.size
+dt = 0.01
+
+n.times do
+  i = 0
+  while i < nbodies
+    b = BODIES[i]
+    b.move_from_i(BODIES, nbodies, dt, i + 1)
+    i += 1
+  end
+end
+
+puts "%.9f" % energy(BODIES)
diff --git a/benchmark/bm_so_nested_loop.rb b/benchmark/bm_so_nested_loop.rb
new file mode 100644
index 000000000..a0513f8c4
--- /dev/null
+++ b/benchmark/bm_so_nested_loop.rb
@@ -0,0 +1,24 @@
+#!/usr/bin/ruby
+# -*- mode: ruby -*-
+# $Id: nestedloop-ruby.code,v 1.4 2004/11/13 07:42:22 bfulgham Exp $
+# http://www.bagley.org/~doug/shootout/
+# from Avi Bryant
+
+n = 16 # Integer(ARGV.shift || 1)
+x = 0
+n.times do
+    n.times do
+        n.times do
+            n.times do
+                n.times do
+                    n.times do
+                        x += 1
+                    end
+                end
+            end
+        end
+    end
+end
+# puts x
+
+
diff --git a/benchmark/bm_so_nsieve_bits.rb b/benchmark/bm_so_nsieve_bits.rb
new file mode 100644
index 000000000..6f958ee44
--- /dev/null
+++ b/benchmark/bm_so_nsieve_bits.rb
@@ -0,0 +1,43 @@
+#!/usr/bin/ruby
+#coding: us-ascii
+#
+# The Great Computer Language Shootout
+# http://shootout.alioth.debian.org/
+#
+# nsieve-bits in Ruby
+# Contributed by Glenn Parker, March 2005
+
+CharExponent = 3
+BitsPerChar = 1 << CharExponent
+LowMask = BitsPerChar - 1
+
+def sieve(m)
+  items = "\xFF" * ((m / BitsPerChar) + 1)
+  masks = ""
+  BitsPerChar.times do |b|
+    masks << (1 << b).chr
+  end
+
+  count = 0
+  pmax = m - 1
+  2.step(pmax, 1) do |p|
+    if items[p >> CharExponent][p & LowMask] == 1
+      count += 1
+      p.step(pmax, p) do |mult|
+	a = mult >> CharExponent
+	b = mult & LowMask
+	items[a] -= masks[b] if items[a][b] != 0
+      end
+    end
+  end
+  count
+end
+
+n = 9 # (ARGV[0] || 2).to_i
+n.step(n - 2, -1) do |exponent|
+  break if exponent < 0
+  m = 2 ** exponent * 10_000
+  count = sieve(m)
+  printf "Primes up to %8d %8d\n", m, count
+end
+
diff --git a/benchmark/bm_so_object.rb b/benchmark/bm_so_object.rb
new file mode 100644
index 000000000..e8607c719
--- /dev/null
+++ b/benchmark/bm_so_object.rb
@@ -0,0 +1,56 @@
+#!/usr/bin/ruby
+# -*- mode: ruby -*-
+# $Id: objinst-ruby.code,v 1.4 2004/11/13 07:42:25 bfulgham Exp $
+# http://www.bagley.org/~doug/shootout/
+# with help from Aristarkh Zagorodnikov
+
+class Toggle
+    def initialize(start_state)
+        @bool = start_state
+    end
+
+    def value
+        @bool
+    end
+
+    def activate
+        @bool = !@bool
+        self
+    end
+end
+
+class NthToggle < Toggle
+    def initialize(start_state, max_counter)
+        super start_state
+        @count_max = max_counter
+        @counter = 0
+    end
+
+    def activate
+        @counter += 1
+        if @counter >= @count_max
+            @bool = !@bool
+            @counter = 0
+        end
+        self
+    end
+end
+
+n = 1500000 # (ARGV.shift || 1).to_i
+
+toggle = Toggle.new 1
+5.times do
+    toggle.activate.value ? 'true' : 'false'
+end
+n.times do
+    toggle = Toggle.new 1
+end
+
+ntoggle = NthToggle.new 1, 3
+8.times do
+    ntoggle.activate.value ? 'true' : 'false'
+end
+n.times do
+    ntoggle = NthToggle.new 1, 3
+end
+
diff --git a/benchmark/bm_so_partial_sums.rb b/benchmark/bm_so_partial_sums.rb
new file mode 100644
index 000000000..630b45cb8
--- /dev/null
+++ b/benchmark/bm_so_partial_sums.rb
@@ -0,0 +1,31 @@
+n = 2_500_000 # (ARGV.shift || 1).to_i
+
+alt = 1.0 ; s0 = s1 = s2 = s3 = s4 = s5 = s6 = s7 = s8 = 0.0
+
+1.upto(n) do |d|
+  d = d.to_f ; d2 = d * d ; d3 = d2 * d ; ds = Math.sin(d) ; dc = Math.cos(d)
+
+  s0 += (2.0 / 3.0) ** (d - 1.0)
+  s1 += 1.0 / Math.sqrt(d)
+  s2 += 1.0 / (d * (d + 1.0))
+  s3 += 1.0 / (d3 * ds * ds)
+  s4 += 1.0 / (d3 * dc * dc)
+  s5 += 1.0 / d
+  s6 += 1.0 / d2
+  s7 += alt / d
+  s8 += alt / (2.0 * d - 1.0)
+
+  alt = -alt
+end
+
+if false
+  printf("%.9f\t(2/3)^k\n", s0)
+  printf("%.9f\tk^-0.5\n", s1)
+  printf("%.9f\t1/k(k+1)\n", s2)
+  printf("%.9f\tFlint Hills\n", s3)
+  printf("%.9f\tCookson Hills\n", s4)
+  printf("%.9f\tHarmonic\n", s5)
+  printf("%.9f\tRiemann Zeta\n", s6)
+  printf("%.9f\tAlternating Harmonic\n", s7)
+  printf("%.9f\tGregory\n", s8)
+end
diff --git a/benchmark/bm_so_random.rb b/benchmark/bm_so_random.rb
new file mode 100644
index 000000000..a66b9e8e6
--- /dev/null
+++ b/benchmark/bm_so_random.rb
@@ -0,0 +1,20 @@
+# from http://www.bagley.org/~doug/shootout/bench/random/random.ruby
+
+IM = 139968.0
+IA = 3877.0
+IC = 29573.0
+
+$last = 42.0
+
+def gen_random(max)
+  (max * ($last = ($last * IA + IC) % IM)) / IM
+end
+
+N = 3_000_000
+
+i = 0
+while i<N
+  i +=1
+  gen_random(100.0)
+end
+# "%.9f" % gen_random(100.0)
diff --git a/benchmark/bm_so_sieve.rb b/benchmark/bm_so_sieve.rb
new file mode 100644
index 000000000..43dc30264
--- /dev/null
+++ b/benchmark/bm_so_sieve.rb
@@ -0,0 +1,24 @@
+# from http://www.bagley.org/~doug/shootout/bench/sieve/sieve.ruby
+num = 500
+count = i = j = 0
+flags0 = Array.new(8192,1)
+k = 0
+while k < num
+  k += 1
+  count = 0
+  flags = flags0.dup
+  i = 2
+  while i<8192
+    i += 1
+    if flags[i]
+      # remove all multiples of prime: i
+      j = i*i
+      while j < 8192
+        j += i
+        flags[j] = nil
+      end
+      count += 1
+    end
+  end
+end
+count
diff --git a/benchmark/bm_so_spectralnorm.rb b/benchmark/bm_so_spectralnorm.rb
new file mode 100644
index 000000000..6b9720668
--- /dev/null
+++ b/benchmark/bm_so_spectralnorm.rb
@@ -0,0 +1,50 @@
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org/
+# Contributed by Sokolov Yura
+
+def eval_A(i,j)
+	return 1.0/((i+j)*(i+j+1)/2+i+1)
+end
+
+def eval_A_times_u(u)
+        v, i = nil, nil
+	(0..u.length-1).collect { |i|
+                v = 0
+		for j in 0..u.length-1
+			v += eval_A(i,j)*u[j]
+                end
+                v
+        }
+end
+
+def eval_At_times_u(u)
+	v, i = nil, nil
+	(0..u.length-1).collect{|i|
+                v = 0
+		for j in 0..u.length-1
+			v += eval_A(j,i)*u[j]
+                end
+                v
+        }
+end
+
+def eval_AtA_times_u(u)
+	return eval_At_times_u(eval_A_times_u(u))
+end
+
+n = 500 # ARGV[0].to_i
+
+u=[1]*n
+for i in 1..10
+        v=eval_AtA_times_u(u)
+        u=eval_AtA_times_u(v)
+end
+vBv=0
+vv=0
+for i in 0..n-1
+        vBv += u[i]*v[i]
+        vv += v[i]*v[i]
+end
+
+str = "%0.9f" % (Math.sqrt(vBv/vv)), "\n"
+# print str
diff --git a/benchmark/plot.gpl b/benchmark/plot.gpl
index 639674d68..21a55dd3d 100644
--- a/benchmark/plot.gpl
+++ b/benchmark/plot.gpl
@@ -1,5 +1,5 @@
 set yrange [0:]
-set terminal pdf
+set terminal pdf font 'Sans, 3'
 set xtics rotate by -45
 set style histogram errorbars gap 2 lw 1
 set style fill solid border -1