Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

faster Fixnum multiplication in ruby?

using ruby 1.9.2p290 (2011-07-09 revision 32553) [x86_64-linux]

I've been doing a lot of profiling and it's come to my attention that ruby Fixnum multiplication is really slow.

Through some profiling, I've learned that this is (partially) because every call to Fixnum#* involves 6 calls to Kernel#kind_of.

I know you can write C extensions, but these multiplications are spread throughout the code. So, is there anyway to avoid this overhead inside Ruby?

thanks

like image 481
user844942 Avatar asked Aug 22 '12 21:08

user844942


2 Answers

Well, I think I figured it out. I'm using the GSL libray, and it appears that it patches Fixnum#* with code you can see here: https://github.com/romanbsd/rb-gsl/blob/master/lib/gsl/oper.rb#L15

This code includes... wait for it... 6 calls to Kernel#kind_of? in a big ol' 'or' statement.

I'm not going to pretend to totally understand how it works or why it happens, but the code path matches perfectly with the profiler output.

like image 20
user844942 Avatar answered Nov 11 '22 22:11

user844942


I seriously doubt that those measurements are accurate, for several reasons:

  1. You don't state which implementation of Ruby you are using, but ruby-prof is a Ruby profiler. It profiles Ruby code. There is no Ruby implementation I know of where Fixnum#* is Ruby code. In MRI, YARV, MRuby and tinyrb it is C code, in Rubinius it is C++ code, in MacRuby it is Objective-C code, in JRuby and XRuby it is Java code, in RubyGoLightly it is Go code, in IronRuby and Ruby.NET it is C# code, in MagLev and SmallRuby it is Smalltalk code, in Cardinal it is PASM code. ruby-prof can profile Ruby code, it cannot profile C, C++, Objective-C, Java, C#, Go, Smalltalk or PASM. Only Ruby. Therefore, it simply cannot profile Fixnum#*.

  2. There is no need for Fixnum#* to check the class more than once. It knows that self is a Fixnum, because otherwise the call wouldn't have dispatched to the Fixnum#* method in the first place, so it only needs to check the argument. It also needs to check whether the result will fit into a Fixnum or not, but it would do that internally, not by a call to kind_of? (in fact, that doesn't even make sense: in order to be able to call a method on the result of the multiplication, it would first have to construct the result object, and in order to construct the result object, it would already have to know whether it fits into a Fixnum or not).

  3. It wouldn't do that class check by calling kind_of? and going through the entire Ruby method lookup and method dispatch machinery. It's an internal function of the Ruby implementation, it has access to all private internal implementation details, it would just check the class directly or call some internal interpreter function, not the Ruby method kind_of?

  4. I checked the implementation of Fixnum#* in various popular Ruby implementations and didn't find any calls to kind_of?. Unfortunately, you didn't state which Ruby implementation you are using.

    • Rubinius: Fixnum::mul in vm/builtin/fixnum.cpp l. 78–89
    • YARV: fix_mul in numeric.c l. 2596–2640
    • JRuby: org.jruby.RubyFixnum.{op_mul, multiplyFixnum, multiplyOther} in src/org/jruby/RubyFixnum.java l. 472–520 (Here you can clearly see, for example, how the method uses the Java instanceof operator instead of Ruby's kind_of? method to check the class.)
like image 92
Jörg W Mittag Avatar answered Nov 11 '22 21:11

Jörg W Mittag