quick/fast integer multiplication in ruby?

Question

Hi there,

I am trying to make a quick/efficient Mandelbrot implementation in Ruby. A long long time ago, one way to speed it up was using fixed point integers instead of floats.

So i made the following benchmark, comparing float and integer raising to a square, using multiplication or square ** operand.

require 'benchmark'

Benchmark.bmbm(10) do |x|  
  x.report("float-multip") do
    for z in 0..100000 
      zf = z.to_f
      y = zf*zf
    end
  end  

  x.report("float-square") do
    for z in 0..100000 
      zf = z.to_f
      y = zf**2
    end
  end  

  x.report("int-multip") do
    zo = 0
    for zi in 0..100000 
      y2 = zo*zo
      zo += 1
    end
  end   

  x.report("int-multip") do
    for zi in 0..100000 
      y2 = zi**2
    end
  end  
end

and this generates the following output:

Rehearsal ------------------------------------------------
float-multip   0.125000   0.000000   0.125000 (  0.125000)
float-square   0.125000   0.000000   0.125000 (  0.125000)
int-multip     0.250000   0.000000   0.250000 (  0.250000)
int-multip     0.282000   0.000000   0.282000 (  0.282000)
--------------------------------------- total: 0.782000sec

                   user     system      total        real
float-multip   0.110000   0.000000   0.110000 (  0.110000)
float-square   0.125000   0.000000   0.125000 (  0.125000)
int-multip     0.219000   0.016000   0.235000 (  0.235000)
int-multip     0.265000   0.015000   0.280000 (  0.282000)

which clearly shows the the Fixnum multiplication is almost twice as slow as floating point.

I have two questions:

• Can anyone explain this? A reason I can imagine is that Fixnum multiplication is slower because of the internal checking whether or not it needs to be converted to a Bignum.
• secondly is there than a quick integer multiplication for ruby?

Answer 1

I can't explain your tables. But I can explain mine (ruby 1.8.7):

                   user     system      total        real
float-multip   0.600000   0.000000   0.600000 (  0.612311)
float-square   0.650000   0.000000   0.650000 (  0.649399)
int-multip     0.450000   0.010000   0.460000 (  0.457004)
int-multip     0.690000   0.000000   0.690000 (  0.692879)

Whoops. Integer multiplication beats floating point ones.

Since your processor is 5 times slower than mine (I increased the number of repeats in your benchmark in ten times), there must be something not ruby-concerned.

** operation probably used floating-point arithmetic(exp(x*ln(2)), so it is as slow as other floating-point operations.

Answer 2

1.8.6 is just slower in this area. 1.8.7 does a little better and 1.9.1 does better still. I couldn't say why but rvm agrees with you and Pavel that 1.8.6 is oddly slow.

1.8.6: 
Rehearsal ------------------------------------------------
float-multip   0.140000   0.000000   0.140000 (  0.141560)
float-square   0.150000   0.000000   0.150000 (  0.146286)
int-multip     0.220000   0.000000   0.220000 (  0.223255)
int-multip     0.180000   0.000000   0.180000 (  0.183850)
--------------------------------------- total: 0.690000sec

1.8.7:
Rehearsal ------------------------------------------------
float-multip   0.090000   0.000000   0.090000 (  0.092346)
float-square   0.080000   0.000000   0.080000 (  0.080335)
int-multip     0.070000   0.000000   0.070000 (  0.068012)
int-multip     0.080000   0.000000   0.080000 (  0.081713)
--------------------------------------- total: 0.320000sec

1.9.1:
Rehearsal ------------------------------------------------
float-multip   0.070000   0.000000   0.070000 (  0.065532)
float-square   0.080000   0.000000   0.080000 (  0.081620)
int-multip     0.060000   0.000000   0.060000 (  0.065371)
int-multip     0.070000   0.000000   0.070000 (  0.065761)
--------------------------------------- total: 0.280000sec

Answer 3

A couple of things come to mind. You do not specify what Ruby implementation you are using. Since you run Ruby 1.8.6 on Windows, I am going to assume that you are using MRI installed via the Windows One-Click Installer.

This is kind of a worst-case scenario:

1. MRI is the slowest of all the Ruby implementations
2. MRI on Windows is even slower than MRI on Linux or OSX
3. The One-Click Installer uses the pre-compiled binaries from Ruby-Lang.Org, which are compiled with Microsoft Visual C++ 6.0 from 1996, and thus are even slower than MRI on Windows compiled with Microsoft Visual C++ 10.0 or GCC 4.x or even GCC 3.x.

Here's a couple of tips that you could try to improve performance:

• use the RubyInstaller project, which uses interpreters compiled with GCC 3.x instead of MSVC6,
• maybe recompile the interpreter yourself (it's not that hard with the Rakefiles provided by the RubyInstaller project) with GCC 4.x and/or different optimization options (RubyInstaller is compiled with moderate optimization options and for generic 386 CPUs),
• use a newer version of MRI than 1.8.6,

• use a different implementation of Ruby:

  • YARV is significantly faster than MRI (unfortunately, it only implements Ruby 1.9, so you might have to change your code),
  • JRuby is significantly faster than YARV in a lot of scenarios, and it implements both Ruby 1.8 and Ruby 1.9 (it also has a -fast commandline option, which is slightly incompatible with Ruby, but improves performance, including arithmetic performance) and
  • IronRuby might also be faster than YARV, depending on the workload.

In the latter two cases you might want to revise your benchmarks a bit. Both eventually can compile Ruby code to native machine code, but it might take a while. JRuby for example compiles to JVM bytecode after a method has been executed 20 times and HotSpot Server compiles JVM bytecode to native machine code after it has executed 20000 times. Also, compilation itself takes time, so the program needs to run a while to gain back that cost through improved performance.

In particular, Charles Oliver Nutter, one of the JRuby lead developers, said that depending on the workload, JRuby might take up to 5-15 seconds to ramp up to full speed. Your benchmarks are about 100x too fast (here's a sentence you don't hear every day ...).