From: Stefan Matthias Aust <sma@3plus4.de>
Date: 2001-05-06T01:11:24+09:00
Subject: [ruby-talk:14710] Why's Ruby so slow in this case?

Sure, Ruby, being interpreted, is slower than a compiled language.
But I didn't expect that it is soo slow!  To practice Ruby, I took the
C source of a simple PBEM strategy game (Russell Wallace's Rainbow's
End to be exact) and rewrote it in Ruby.  That was fun and easy.
However, the following code needs more than 15 minutes to complete
while the original C source runs in less than one second!  

I wonder whether there are some ways to optimize this code other than
to completely change the algorithm.  Or can the Ruby interpreter be
improved?  I'm using Ruby 1.6.4 if that matters.

This method shown below is where all the time is spend.  It generates
a new map (consisting of 35x35 hexagonal fields) for the game using
the following algorithm: In the beginning, all fields are water
fields. One random field is designated as mountain. Now, a loop starts
which first calculates a set of fields which are the shore line and
second picks one random field of that set. That new field gets
assigned a random terrain type and the loop continues until half of
the map became land.

def initmap
  count = $mapsize * $mapsize
  $hexes = (0...count).map{Hex.new}

  $hexes[rand(count)].terrain = Terrain::Mountain
  
  for i in 0...(count / 2 - 1)
    a = []
    for h in 0...count
      if offshore(h) then a << h end
    end
    h = a[rand(a.length)]
    $hexes[h].terrain = 
      case rand(3)
        when 0; Terrain::Plain
        when 1; Terrain::Forest
        when 2; Terrain::Mountain
      end
  end
end

def offshore(h) #private
  if $hexes[h].iswater
    for d in 0..5
      h2 = displace(h, d)
      if h2 >= 0 && !$hexes[h2].iswater
        return true
      end
    end
  end
  false
end

I profiled the code and here's the result.

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 24.65   255.12    255.12   101328     2.52     7.51  Object#displace
 10.64   365.24    110.12   101328     1.09     1.63  Object#onmap
 10.58   474.77    109.53    18949     5.78   156.36  Range#each
  7.01   547.27     72.50   101328     0.72     0.97  Object#even
  5.73   606.56     59.29    92238     0.64     0.90  Object#xytoh
  4.53   653.49     46.93   110044     0.43     0.55  Object#htoy
  4.49   699.92     46.44   110044     0.42     0.55  Object#htox
  4.36   745.02     45.10   116328     0.39     0.50  Hex#iswater
  3.99   786.30     41.28   299016     0.14     0.14  Fixnum#>=
  3.88   826.45     40.15   320307     0.13     0.13  Array#[]
  3.62   863.95     37.50   304378     0.12     0.12  Fixnum#+
  2.65   891.41     27.47   199575     0.14     0.14  Fixnum#<
  2.48   917.11     25.69   220668     0.12     0.12  Fixnum#==
  2.28   940.71     23.61    24975     0.95    38.81  Object#offshore
 ...

BTW, is there a way to profile just a part of a program?  These
numbers are for the complete run of the program.  However I don't
think that the other parts of the program are significant.

Obviously, most time is spent in displace(), a method to find one of
the six neighbor fields of a hex field.  Because the game uses hex
fields, finding a valid neighbor field is somewhat tricky.  Here's
that method

def displace(h, d)
  x, y = htox(h), htoy(h) 
  case d
  when 0
    y -= 1
  when 1
    y -= 1 if even(x)
    x += 1
  when 2
    y += 1 if odd(x)
    x += 1
  when 3
    y += 1
  when 4
    y += 1 if odd(x)
    x -= 1
  when 5
    y -= 1 if even(x)
    x -= 1
  end
  if onmap(x, y)
    xytoh(x, y)
  else
    -1
  end
end

def xytoh(x, y)
  y * $mapsize + x
end

def htox(h)
  h % $mapsize
end

def htoy(h)
  h / $mapsize
end

That method is called quite often, but that's life.  I tried to
optimize it using an offset table

Displacetable_x      = [ 0,  1, 1, 0, -1, -1]

to speed up calculating 

  x = htox(h) + Displacetable_x[d]

but that doesn't really help.  The problem IMHO is that all that tiny
method calls take their time and this sums up.  For example, I don't
really understand why a simple method like

def onmap(x, y) #private
  x >= 0 && x < $mapsize && y >= 0 && y < $mapsize
end

needs more than 1 ms per call!  So this method alone is responsible
for some 2 minutes of execution time.  A similar argument is true for
the other methods.  And why are the "0..5.each" (or is it the
"(0...(count/2)-1).each" call?) calls so expensive?  Replacing them
with "[0, 1, 2, 3, 4, 5].each" also didn't help.

I tried to simulate the onmap() function in Squeak Smalltalk, a
language which is also just interpreted, garbage-collected, 100%
object oriented (and at least as cool as Ruby) and that system needs
just 0.13 s for 100.000 calls

| x y |
MapSize := 35.
x := y := 4.
Time millisecondsToRun: [
  100000 timesRepeat: [
    x >= 0 and: [x < MapSize and: [y >= 0 and: [y < MapSize]]]]]
=> 125

I'd like to understand why Ruby is 100 times slower than the slowest
Smalltalk.  VisualWorks Smalltalk needs just 20ms for 100.000 calls,
BTW.

If it's just the interpreter, wouldn't it be an idea to implement Ruby
on top of Squeak, using that obviously more sophisticated bytecode
interpreter, garbage collector and runtime system?


bye
-- 
Stefan Matthias Aust \/ Truth Until Paradox