Revision: 4158 http://trac.macosforge.org/projects/ruby/changeset/4158 Author: lsansonetti@apple.com Date: 2010-05-25 20:58:42 -0700 (Tue, 25 May 2010) Log Message: ----------- split the algo tests into a misc directory + added sudoku test Modified Paths: -------------- MacRuby/trunk/perf/boot.rb MacRuby/trunk/perf/run.rb Added Paths: ----------- MacRuby/trunk/perf/misc/ MacRuby/trunk/perf/misc/ack.rb MacRuby/trunk/perf/misc/ao_bench.rb MacRuby/trunk/perf/misc/fib.rb MacRuby/trunk/perf/misc/mandelbrot.rb MacRuby/trunk/perf/misc/sudoku.rb MacRuby/trunk/perf/misc/tak.rb MacRuby/trunk/perf/perf_misc.rb Removed Paths: ------------- MacRuby/trunk/perf/perf_algo.rb Modified: MacRuby/trunk/perf/boot.rb =================================================================== --- MacRuby/trunk/perf/boot.rb 2010-05-26 02:10:25 UTC (rev 4157) +++ MacRuby/trunk/perf/boot.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -1,14 +1,18 @@ +if ARGV.size < 2 or ARGV.size > 3 + $stderr.puts "Usage: #{__FILE__} <n-iterations> <file.rb> [suite]" + exit 1 +end +N = ARGV[0].to_i +file = ARGV[1] +@suite = ARGV[2] @perf_tests = [] def perf_test(name, &b) - @perf_tests << [name, b] + if @suite == nil or @suite == name + @perf_tests << [name, b] + end end -if ARGV.size != 2 - $stderr.puts "Usage: #{__FILE__} <n-iterations> <file.rb>" - exit 1 -end -N = ARGV[0].to_i -load(ARGV[1]) +load(file) @perf_tests.each do |name, proc| times = [] Added: MacRuby/trunk/perf/misc/ack.rb =================================================================== --- MacRuby/trunk/perf/misc/ack.rb (rev 0) +++ MacRuby/trunk/perf/misc/ack.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -0,0 +1,11 @@ +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 + +perf_test('ack') { ack(3, 9) } Added: MacRuby/trunk/perf/misc/ao_bench.rb =================================================================== --- MacRuby/trunk/perf/misc/ao_bench.rb (rev 0) +++ MacRuby/trunk/perf/misc/ao_bench.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -0,0 +1,288 @@ +module AOBench + # AO render benchmark + # Original program (C) Syoyo Fujita in Javascript (and other languages) + # http://lucille.atso-net.jp/blog/?p=642 + # http://lucille.atso-net.jp/blog/?p=711 + # Ruby(yarv2llvm) version by Hideki Miura + # http://github.com/miura1729/yarv2llvm/blob/a888d8ce6855e70b630a8673d4cfe075a... + # Modified by Tomoyuki Chikanaga + # + + IMAGE_WIDTH = 64 # original value: 256 + IMAGE_HEIGHT = 64 # original value: 256 + NSUBSAMPLES = 2 + NAO_SAMPLES = 6 # original value: 8 + + class Vec + def initialize(x, y, z) + @x = x + @y = y + @z = z + end + + attr_accessor :x, :y, :z + + def vadd(b) + Vec.new(@x + b.x, @y + b.y, @z + b.z) + end + + def vsub(b) + Vec.new(@x - b.x, @y - b.y, @z - b.z) + end + + def vcross(b) + Vec.new(@y * b.z - @z * b.y, + @z * b.x - @x * b.z, + @x * b.y - @y * b.x) + end + + def vdot(b) + @x * b.x + @y * b.y + @z * b.z + end + + def vlength + Math.sqrt(@x * @x + @y * @y + @z * @z) + end + + def vnormalize! + len = vlength + if len > 1.0e-17 + r_len = 1.0 / len + @x *= r_len + @y *= r_len + @z *= r_len + end + self + end + end + + class Sphere + def initialize(center, radius) + @center = center + @radius_2 = radius * radius + end + + def intersect(ray, isect) + rs = ray.org.vsub(@center) + b = rs.vdot(ray.dir) + c = rs.vdot(rs) - @radius_2 + d = b * b - c + if d > 0.0 + t = - b - Math.sqrt(d) + + isect.cross(self, ray, t) + end + nil + end + + def normal_vec(pos) + pos.vsub(@center).vnormalize! + end + end + + class Plane + def initialize(p, n) + @p = p + @n = n + end + + def intersect(ray, isect) + d = -@p.vdot(@n) + v = ray.dir.vdot(@n) + v0 = v + if v < 0.0 + v0 = -v + end + if v0 < 1.0e-17 + return + end + + t = -(ray.org.vdot(@n) + d) / v + + isect.cross(self, ray, t) + nil + end + + def normal_vec(pos) + @n + end + end + + class Ray + def initialize(org, dir) + @org = org + @dir = dir + end + attr_reader :org, :dir + end + + class Isect + def initialize + @t = Float::MAX + @hit = false + @pl = Vec.new(0.0, 0.0, 0.0) + @normal = Vec.new(0.0, 0.0, 0.0) + end + + attr_reader :normal + + def hit? + @hit + end + + def cross(geom, ray, dist) + if 0.0 < dist and dist < @t + @hit = true + @t = dist + @pl = Vec.new(ray.org.x + ray.dir.x * dist, + ray.org.y + ray.dir.y * dist, + ray.org.z + ray.dir.z * dist) + @normal = geom.normal_vec(@pl) + end + nil + end + + def surface(eps) + Vec.new(@pl.x + eps * @normal.x, + @pl.y + eps * @normal.y, + @pl.z + eps * @normal.z) + end + end + + def self.clamp(f) + i = f * 255.5 + if i > 255.0 + i = 255.0 + end + if i < 0.0 + i = 0.0 + end + i.round + end + + def self.otherBasis(basis, n) + basis[2] = Vec.new(n.x, n.y, n.z) + basis[1] = Vec.new(0.0, 0.0, 0.0) + + if n.x < 0.6 and n.x > -0.6 + basis[1].x = 1.0 + elsif n.y < 0.6 and n.y > -0.6 + basis[1].y = 1.0 + elsif n.z < 0.6 and n.z > -0.6 + basis[1].z = 1.0 + else + basis[1].x = 1.0 + end + + basis[0] = basis[1].vcross(basis[2]) + basis[0].vnormalize! + + basis[1] = basis[2].vcross(basis[0]) + basis[1].vnormalize! + end + + class Scene + def initialize + @spheres = Array.new + @spheres[0] = Sphere.new(Vec.new(-2.0, 0.0, -3.5), 0.5) + @spheres[1] = Sphere.new(Vec.new(-0.5, 0.0, -3.0), 0.5) + @spheres[2] = Sphere.new(Vec.new(1.0, 0.0, -2.2), 0.5) + @plane = Plane.new(Vec.new(0.0, -0.5, 0.0), Vec.new(0.0, 1.0, 0.0)) + end + + def ambient_occlusion(isect) + basis = Array.new + AOBench.otherBasis(basis, isect.normal) + + ntheta = NAO_SAMPLES + nphi = NAO_SAMPLES + eps = 0.0001 + occlusion = 0.0 + + p0 = isect.surface(eps) + nphi.times do |j| + ntheta.times do |i| + r = rand + rr = Math.sqrt(1.0 - r) + phi = 2.0 * Math::PI * rand + x = Math.cos(phi) * rr + y = Math.sin(phi) * rr + z = Math.sqrt(r) + + rx = x * basis[0].x + y * basis[1].x + z * basis[2].x + ry = x * basis[0].y + y * basis[1].y + z * basis[2].y + rz = x * basis[0].z + y * basis[1].z + z * basis[2].z + + raydir = Vec.new(rx, ry, rz) + ray = Ray.new(p0, raydir) + + occisect = Isect.new + @spheres[0].intersect(ray, occisect) + @spheres[1].intersect(ray, occisect) + @spheres[2].intersect(ray, occisect) + @plane.intersect(ray, occisect) + if occisect.hit? + occlusion = occlusion + 1.0 + else + 0.0 + end + end + end + + occlusion = (ntheta * nphi - occlusion).to_f / (ntheta * nphi) + + occlusion + end + + def render(w, h, nsubsamples) + cnt = 0 + pixbuf = [] + nsf = nsubsamples.to_f + nsf_2 = nsf * nsf + h.times do |y| + w.times do |x| + rad = 0.0 + + # Subsmpling + nsubsamples.times do |v| + nsubsamples.times do |u| + + cnt = cnt + 1 + wf = w.to_f + hf = h.to_f + xf = x.to_f + yf = y.to_f + uf = u.to_f + vf = v.to_f + + px = (xf + (uf / nsf) - (wf / 2.0)) / (wf / 2.0) + py = -(yf + (vf / nsf) - (hf / 2.0)) / (hf / 2.0) + + eye = Vec.new(px, py, -1.0) + eye.vnormalize! + + ray = Ray.new(Vec.new(0.0, 0.0, 0.0), eye) + + isect = Isect.new + @spheres[0].intersect(ray, isect) + @spheres[1].intersect(ray, isect) + @spheres[2].intersect(ray, isect) + @plane.intersect(ray, isect) + if isect.hit? + rad += ambient_occlusion(isect) + end + end + end + + pixbuf << AOBench.clamp(rad / nsf_2) + end + end + end + end + + def self.test + Scene.new.render(IMAGE_WIDTH, IMAGE_HEIGHT, NSUBSAMPLES) + end +end + +perf_test('ao_bench') { AOBench.test } Added: MacRuby/trunk/perf/misc/fib.rb =================================================================== --- MacRuby/trunk/perf/misc/fib.rb (rev 0) +++ MacRuby/trunk/perf/misc/fib.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -0,0 +1,9 @@ +def fib(n) + if n < 3 + 1 + else + fib(n - 1) + fib(n - 2) + end +end + +perf_test('fib') { fib(37) } Added: MacRuby/trunk/perf/misc/mandelbrot.rb =================================================================== --- MacRuby/trunk/perf/misc/mandelbrot.rb (rev 0) +++ MacRuby/trunk/perf/misc/mandelbrot.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -0,0 +1,32 @@ +def mandelbrot_i(x, y) + cr = y - 0.5 + ci = x + zi = 0.0 + zr = 0.0 + i = 0 + + while true + i += 1 + temp = zr * zi + zr2 = zr * zr + zi2 = zi * zi + zr = zr2 - zi2 + cr + zi = temp + temp + ci + return i if (zi2 + zr2 > 16) + return 0 if (i > 1000) + end +end + +def mandelbrot + y = -39 + while y < 39 + x = -39 + while x < 39 + i = mandelbrot_i(x / 40.0, y/40.0) + x += 1 + end + y += 1 + end +end + +perf_test('mandelbrot') { mandelbrot } Added: MacRuby/trunk/perf/misc/sudoku.rb =================================================================== --- MacRuby/trunk/perf/misc/sudoku.rb (rev 0) +++ MacRuby/trunk/perf/misc/sudoku.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -0,0 +1,62 @@ +class Sudoku + # Sudoku solver + # from http://blog.mmediasys.com/2008/04/24/contributions-speedup-and-less-quirks-f... + + def valid?(state, x, y) + # check in col and row + 0.upto(8) do |i| + return false if i != y and state[x][i] == state[x][y] + return false if i != x and state[i][y] == state[x][y] + end + + # check in box + x_from = (x / 3) * 3 + y_from = (y / 3) * 3 + x_from.upto(x_from + 2) do |xx| + y_from.upto(y_from + 2) do |yy| + return false if (xx != x or yy != y) and state[xx][yy] == state[x][y] + end + end + + true + end + + + def next_state(state, x, y) + @count = @count + 1 + y = 0 and x = x + 1 if y == 9 + return true if x == 9 + + unless state[x][y].zero? + return false unless valid?(state, x, y) + return next_state(state, x, y + 1) + else + 1.upto(9) do |i| + state[x][y] = i + return true if valid?(state, x, y) and next_state(state, x, y + 1) + end + end + + state[x][y] = 0 + false + end + + def test + @count = 0 + start = + [ + [ 0, 0, 0, 4, 0, 5, 0, 0, 1 ], + [ 0, 7, 0, 0, 0, 0, 0, 3, 0 ], + [ 0, 0, 4, 0, 0, 0, 9, 0, 0 ], + [ 0, 0, 3, 5, 0, 4, 1, 0, 0 ], + [ 0, 0, 7, 0, 0, 0, 4, 0, 0 ], + [ 0, 0, 8, 9, 0, 1, 0, 0, 0 ], + [ 0, 0, 9, 0, 0, 0, 6, 0, 0 ], + [ 0, 8, 0, 0, 0, 0, 0, 2, 0 ], + [ 4, 0, 0, 2, 0, 0, 0, 0, 0 ] + ] + next_state(start, 0, 0) + end +end + +perf_test('sudoku') { Sudoku.new.test } Added: MacRuby/trunk/perf/misc/tak.rb =================================================================== --- MacRuby/trunk/perf/misc/tak.rb (rev 0) +++ MacRuby/trunk/perf/misc/tak.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -0,0 +1,11 @@ +def tak(x, y, z) + unless y < x + z + else + tak(tak(x-1, y, z), + tak(y-1, z, x), + tak(z-1, x, y)) + end +end + +perf_test('tak') { tak(18, 9, 0) } Deleted: MacRuby/trunk/perf/perf_algo.rb =================================================================== --- MacRuby/trunk/perf/perf_algo.rb 2010-05-26 02:10:25 UTC (rev 4157) +++ MacRuby/trunk/perf/perf_algo.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -1,355 +0,0 @@ -def fib(n) - if n < 3 - 1 - else - fib(n - 1) + fib(n - 2) - end -end - -perf_test('fib') { fib(37) } - -def tak(x, y, z) - unless y < x - z - else - tak(tak(x-1, y, z), - tak(y-1, z, x), - tak(z-1, x, y)) - end -end - -perf_test('tak') { tak(18, 9, 0) } - -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 - -perf_test('ack') { ack(3, 9) } - -def mandelbrot_i(x, y) - cr = y - 0.5 - ci = x - zi = 0.0 - zr = 0.0 - i = 0 - - while true - i += 1 - temp = zr * zi - zr2 = zr * zr - zi2 = zi * zi - zr = zr2 - zi2 + cr - zi = temp + temp + ci - return i if (zi2 + zr2 > 16) - return 0 if (i > 1000) - end -end - -def mandelbrot - y = -39 - while y < 39 - x = -39 - while x < 39 - i = mandelbrot_i(x / 40.0, y/40.0) - x += 1 - end - y += 1 - end -end - -perf_test('mandelbrot') { mandelbrot } - -module AOBench - # AO render benchmark - # Original program (C) Syoyo Fujita in Javascript (and other languages) - # http://lucille.atso-net.jp/blog/?p=642 - # http://lucille.atso-net.jp/blog/?p=711 - # Ruby(yarv2llvm) version by Hideki Miura - # http://github.com/miura1729/yarv2llvm/blob/a888d8ce6855e70b630a8673d4cfe075a... - # Modified by Tomoyuki Chikanaga - # - - IMAGE_WIDTH = 64 # original value: 256 - IMAGE_HEIGHT = 64 # original value: 256 - NSUBSAMPLES = 2 - NAO_SAMPLES = 6 # original value: 8 - - class Vec - def initialize(x, y, z) - @x = x - @y = y - @z = z - end - - attr_accessor :x, :y, :z - - def vadd(b) - Vec.new(@x + b.x, @y + b.y, @z + b.z) - end - - def vsub(b) - Vec.new(@x - b.x, @y - b.y, @z - b.z) - end - - def vcross(b) - Vec.new(@y * b.z - @z * b.y, - @z * b.x - @x * b.z, - @x * b.y - @y * b.x) - end - - def vdot(b) - @x * b.x + @y * b.y + @z * b.z - end - - def vlength - Math.sqrt(@x * @x + @y * @y + @z * @z) - end - - def vnormalize! - len = vlength - if len > 1.0e-17 - r_len = 1.0 / len - @x *= r_len - @y *= r_len - @z *= r_len - end - self - end - end - - class Sphere - def initialize(center, radius) - @center = center - @radius_2 = radius * radius - end - - def intersect(ray, isect) - rs = ray.org.vsub(@center) - b = rs.vdot(ray.dir) - c = rs.vdot(rs) - @radius_2 - d = b * b - c - if d > 0.0 - t = - b - Math.sqrt(d) - - isect.cross(self, ray, t) - end - nil - end - - def normal_vec(pos) - pos.vsub(@center).vnormalize! - end - end - - class Plane - def initialize(p, n) - @p = p - @n = n - end - - def intersect(ray, isect) - d = -@p.vdot(@n) - v = ray.dir.vdot(@n) - v0 = v - if v < 0.0 - v0 = -v - end - if v0 < 1.0e-17 - return - end - - t = -(ray.org.vdot(@n) + d) / v - - isect.cross(self, ray, t) - nil - end - - def normal_vec(pos) - @n - end - end - - class Ray - def initialize(org, dir) - @org = org - @dir = dir - end - attr_reader :org, :dir - end - - class Isect - def initialize - @t = Float::MAX - @hit = false - @pl = Vec.new(0.0, 0.0, 0.0) - @normal = Vec.new(0.0, 0.0, 0.0) - end - - attr_reader :normal - - def hit? - @hit - end - - def cross(geom, ray, dist) - if 0.0 < dist and dist < @t - @hit = true - @t = dist - @pl = Vec.new(ray.org.x + ray.dir.x * dist, - ray.org.y + ray.dir.y * dist, - ray.org.z + ray.dir.z * dist) - @normal = geom.normal_vec(@pl) - end - nil - end - - def surface(eps) - Vec.new(@pl.x + eps * @normal.x, - @pl.y + eps * @normal.y, - @pl.z + eps * @normal.z) - end - end - - def self.clamp(f) - i = f * 255.5 - if i > 255.0 - i = 255.0 - end - if i < 0.0 - i = 0.0 - end - i.round - end - - def self.otherBasis(basis, n) - basis[2] = Vec.new(n.x, n.y, n.z) - basis[1] = Vec.new(0.0, 0.0, 0.0) - - if n.x < 0.6 and n.x > -0.6 - basis[1].x = 1.0 - elsif n.y < 0.6 and n.y > -0.6 - basis[1].y = 1.0 - elsif n.z < 0.6 and n.z > -0.6 - basis[1].z = 1.0 - else - basis[1].x = 1.0 - end - - basis[0] = basis[1].vcross(basis[2]) - basis[0].vnormalize! - - basis[1] = basis[2].vcross(basis[0]) - basis[1].vnormalize! - end - - class Scene - def initialize - @spheres = Array.new - @spheres[0] = Sphere.new(Vec.new(-2.0, 0.0, -3.5), 0.5) - @spheres[1] = Sphere.new(Vec.new(-0.5, 0.0, -3.0), 0.5) - @spheres[2] = Sphere.new(Vec.new(1.0, 0.0, -2.2), 0.5) - @plane = Plane.new(Vec.new(0.0, -0.5, 0.0), Vec.new(0.0, 1.0, 0.0)) - end - - def ambient_occlusion(isect) - basis = Array.new - AOBench.otherBasis(basis, isect.normal) - - ntheta = NAO_SAMPLES - nphi = NAO_SAMPLES - eps = 0.0001 - occlusion = 0.0 - - p0 = isect.surface(eps) - nphi.times do |j| - ntheta.times do |i| - r = rand - rr = Math.sqrt(1.0 - r) - phi = 2.0 * Math::PI * rand - x = Math.cos(phi) * rr - y = Math.sin(phi) * rr - z = Math.sqrt(r) - - rx = x * basis[0].x + y * basis[1].x + z * basis[2].x - ry = x * basis[0].y + y * basis[1].y + z * basis[2].y - rz = x * basis[0].z + y * basis[1].z + z * basis[2].z - - raydir = Vec.new(rx, ry, rz) - ray = Ray.new(p0, raydir) - - occisect = Isect.new - @spheres[0].intersect(ray, occisect) - @spheres[1].intersect(ray, occisect) - @spheres[2].intersect(ray, occisect) - @plane.intersect(ray, occisect) - if occisect.hit? - occlusion = occlusion + 1.0 - else - 0.0 - end - end - end - - occlusion = (ntheta * nphi - occlusion).to_f / (ntheta * nphi) - - occlusion - end - - def render(w, h, nsubsamples) - cnt = 0 - pixbuf = [] - nsf = nsubsamples.to_f - nsf_2 = nsf * nsf - h.times do |y| - w.times do |x| - rad = 0.0 - - # Subsmpling - nsubsamples.times do |v| - nsubsamples.times do |u| - - cnt = cnt + 1 - wf = w.to_f - hf = h.to_f - xf = x.to_f - yf = y.to_f - uf = u.to_f - vf = v.to_f - - px = (xf + (uf / nsf) - (wf / 2.0)) / (wf / 2.0) - py = -(yf + (vf / nsf) - (hf / 2.0)) / (hf / 2.0) - - eye = Vec.new(px, py, -1.0) - eye.vnormalize! - - ray = Ray.new(Vec.new(0.0, 0.0, 0.0), eye) - - isect = Isect.new - @spheres[0].intersect(ray, isect) - @spheres[1].intersect(ray, isect) - @spheres[2].intersect(ray, isect) - @plane.intersect(ray, isect) - if isect.hit? - rad += ambient_occlusion(isect) - end - end - end - - pixbuf << AOBench.clamp(rad / nsf_2) - end - end - end - end - - def self.test - Scene.new.render(IMAGE_WIDTH, IMAGE_HEIGHT, NSUBSAMPLES) - end -end - -perf_test('ao_bench') { AOBench.test } Added: MacRuby/trunk/perf/perf_misc.rb =================================================================== --- MacRuby/trunk/perf/perf_misc.rb (rev 0) +++ MacRuby/trunk/perf/perf_misc.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -0,0 +1 @@ +Dir.glob(File.join(File.dirname(__FILE__), "misc/*.rb")).each { |x| load x } Modified: MacRuby/trunk/perf/run.rb =================================================================== --- MacRuby/trunk/perf/run.rb 2010-05-26 02:10:25 UTC (rev 4157) +++ MacRuby/trunk/perf/run.rb 2010-05-26 03:58:42 UTC (rev 4158) @@ -14,12 +14,13 @@ exit 1 end else - perf_files << File.join(cwd, "perf_#{arg}.rb") + name, suite = arg.split(':', 2) + perf_files << [File.join(cwd, "perf_#{name}.rb"), suite] end end if perf_files.empty? - perf_files = Dir.glob(File.join(cwd, 'perf_*.rb')) + perf_files = Dir.glob(File.join(cwd, 'perf_*.rb')).map { |x| [x, nil] } end if rubies.empty? @@ -35,10 +36,11 @@ puts '', '-' * 80 booter = File.join(cwd, 'boot.rb') -perf_files.each do |file| +perf_files.each do |file, suite| results = {} + suite ||= '' rubies.each do |ruby| - output = `#{ruby} #{booter} #{n_iterations} #{file}`.strip + output = `#{ruby} #{booter} #{n_iterations} #{file} #{suite}`.strip output.split(/\n/).each do |line| title, times = line.split(/:/) best = times.split(/,/).min @@ -49,7 +51,10 @@ prefix = File.basename(file).scan(/perf_(\w+)\.rb/)[0][0] results.each do |title, res| print "#{prefix}:#{title}".ljust(20) - winner = res.size > 1 ? res.map { |_, best| best }.min : nil + winner = nil + if res.size > 1 + winner = res.map { |_, best| best.to_f }.min.to_s + end res.each do |_, best| s = best.ljust(20) if best == winner