8 ms·

Making Ruby Faster

179 points by timr 12y ago

pgz 12y ago
Great article! What I don't understand is why can't they make the compiler inline the function instead inlining manually?
- timr 12y ago
  This is more than just C function inlining -- the Ruby interpreter, when it does a method call, ends up doing a lot of expensive bookkeeping at runtime to maintain its own internal call stack. This optimization allows the interpreter to completely bypass a Ruby method call, which is a big win.
  - pgz 12y ago
    I meant having something like: if (check_cfunc(ci->me, rb_obj_equal)) { return rb_obj_equal(recv, obj); } and trusting the compiler to inline rb_obj_equal (or using inline), although I reckon you don't probably want rb_obj_equal to always be inlined.
    - masklinn 12y ago
      Well inlining this way is an optimisation which the compiler may or may not opt to apply, even after adding inlining hints. By manually inlining it they're introducing a little bit of trivial redundancy but I guess they can be certain there will be no indirect call. Either that, or they never considered the compiler would most likely inline it. Oddly enough, they do it for string comparisons: https://www.omniref.com/ruby/2.1.4/files/vm_insnhelper.c#line=860 https://www.omniref.com/ruby/2.1.4/files/vm_insnhelper.c#lin...
    - timr 12y ago
      Oh, sorry...wasn't clear. The problem with just doing the rb_obj_equal call for everything is that if people override eql? in their Ruby code, you need to call that overridden method, instead. The consequences of this decision mean that the comparison operator needs to be more complex.
    - saraid216 12y ago
      FYI, putting two spaces ahead of each line in a code block will wrap it in a pre-formatted tag. In case you didn't know.
- gsg 12y ago
  They aren't inlining manually. The optimisation works by making more cases fall into an already existing fast path. edit: I might have misunderstood - I should say that the patch doesn't do any inlining. The fast path is indeed the manually inlined body of the function.
jaredcwhite 12y ago
Every tiny little thing like this that gets further optimized in the MRI will result in major performance gains in advanced frameworks/codebases down the road. So this is great news. I'm looking forward to a near-future time when the claim Ruby=Slow! is much harder to make.
- dkarapetyan 12y ago
  There is an inherent overhead to all dynamically typed languages like Ruby and Python, method dispatch. Overcoming this problem is not easy and even JRuby with all the muscle of the JVM JIT is still pretty slow compared to the statically typed equivalent in Java or any other language that doesn't have to pay for method look-ups during run-time. The situation is not hopeless though and projects like Truffle/Graal (https://wiki.openjdk.java.net/display/Graal/Truffle+FAQ+and+Guidelines https://wiki.openjdk.java.net/display/Graal/Truffle+FAQ+and+...) are pushing the boundary of what is possible in terms of performance for dynamically typed languages. There is also PyPy and RPython (http://tratt.net/laurie/blog/entries/fast_enough_vms_in_fast_enough_time http://tratt.net/laurie/blog/entries/fast_enough_vms_in_fast...) which again leverages some neat JIT techniques to make things fast.
  - chrisseaton 12y ago
    This is how Truffle and Graal make Ruby method dispatch fast (linking to my own blog post) http://www.chrisseaton.com/rubytruffle/how-method-dispatch-works-in-jruby-truffle/ http://www.chrisseaton.com/rubytruffle/how-method-dispatch-w....
    - nly 12y ago
      Good article, thanks. It's amazing how such relatively simple techniques get some fancy names.
  - vanderZwan 12y ago
    > There is an inherent overhead to all dynamically typed languages like Ruby and Python, method dispatch I can't claim to fully understand how they pull it off (not being that familiar with compiler internals), but I thought Julia didn't suffer from this problem?
pmontra 12y ago
Almost offtopic because not directly related to symbols performances in Ruby but, coincidence, I was reading a 2011 post from Rubinius site http://rubini.us/2011/02/17/rubinius-what-s-next/ http://rubini.us/2011/02/17/rubinius-what-s-next/ a couple of minutes before seeing this on HN. At almost 50% of the post there is a code snippet that explains why Ruby method calls must be slower than the ones of statically typed languages. It also explains how Rubinius was addressing that 3 years ago. Hopefully they'll optimize that in all language implementations.
- donpdonp 12y ago
  also almost off topic but the lead Rubinius dev just posted a great writeup on rubinius 3.0 which could be a possible future of ruby in general. http://rubini.us/2014/11/12/rubinius-3-0-part-3-the-instructions/ http://rubini.us/2014/11/12/rubinius-3-0-part-3-the-instruct...
  - pmontra 12y ago
    Interesting read. Thank you.
munificent 12y ago
Really neat article, though it makes me wonder why they didn't just remove `sym_equal` entirely and replace all usages of it with `rb_obj_equal`. At the very least, that `#define` needs a comment saying it must have the same identity as `rb_obj_equal` or a perf loss will happen.
- timr 12y ago
  Well, among other things, you can override the object equality check in Ruby -- so you can't simply rely on pointer identity as a check of equality. That said, yeah, it'd be nice if you could just make the assumption that if two objects point to the same memory, they're de facto identical...
  - jrochkind1 12y ago
    You can make that assumption for symbols. And that is in fact what the code was doing -- both before and after optimization. The optimization was about something else, weirder, that was still making string comparison (where you can't just check the pointer) faster even though it ought to be slower. Did you read the article?
    - timr 12y ago
      "The optimization was about something else, weirder, that was still making string comparison (where you can't just check the pointer) faster even though it ought to be slower. Did you read the article?" I'm the author of the article. The optimization here is that the check for plain-old symbol equality is happening without the need for a full ruby method dispatch. You can't make that assumption in the general case, because it's possible to override equality in Ruby, which then requires more work. If you look at the full source code for the method in question, you'll see that it does special checks for Fixnums and Floats and Strings, then a check for the default object equality (i.e. does the comparison use rb_obj_equal?), then, finally, it falls back to a full method call.
    - jenrzzz 12y ago
      Actually, he wrote it!
skratlo 12y ago
Makes me wonder why the C compiler (gcc?) isn't clever enough here and is not inlining all that non-sense. At least I would expect SufficientlySmartCompiler™ to do so. Doing the inline by hand just proves how dark is the age we're living in.
- masklinn 12y ago
  > Makes me wonder why the C compiler (gcc?) isn't clever enough here and is not inlining all that non-sense. There's an indirection through a function pointer (ci->me). The manual optimisation is there to see whether the function pointer matches a baseline pointer, and apply that baseline directly instead of invoking the "generic" dispatch machinery (which involves setting new callframes & al) If you look at the whole function, there's a few special case before that which statically dispatch the case of a comparison between numbers or strings, so here we're in the "general" case and one last optimisation available is to see whether equality has been overridden at all.
  - chrisseaton 12y ago
    People are often confused about how a JIT can be faster than a static compiler - this is a great example of why that can be the case. A dynamic compiler would be able to speculatively inline through the function pointer, where in a static compiler that is not tractable with what we currently know about compilers.
    - gsg 12y ago
      That's not really true - it's just (possibly partial) defunctionalisation. The problem isn't that we don't know how to do it, but that the necessary whole program architecture has various drawbacks. See Stalin and MLton for examples of a static compiler performing such analyses.
      - chrisseaton 12y ago
        Consider the case of a program which applies a processing function to pixels in an image. Which processing function to run depends a command line parameter. How would whole program analysis help you know which function you are going to use? But a JIT will see you keep calling the same function and inline it. Not even profile directed feedback will help you if each time you run the program you use a different function. I know Stalin and MLton but not the research you mention - can you point me at any papers?
mrinterweb 12y ago
My impression was that ruby symbols were defined once and mapped to the same memory space. If I am correct in my assumption, wouldn't it be more efficient to pass the arguments in as pointers and compare the equality of the pointers?
- djur 12y ago
  That's actually what they're doing. VALUE is a typedef for uintptr_t, so rb_obj_equal is just testing whether the pointers are the same.
  - mrinterweb 12y ago
    Thanks for looking into that, Matt. It has been a long time since I did any real C programming, and I could not believe that they would be passing by value for this kind of equality check. The word "VALUE" is a little deceiving considering that it is actually a uintptr_t.
    - riffraff 12y ago
      it's not, really, VALUE may alternatively contain an immediate value or a pointer, i.e. a couple bits are used for type tagging and the rest is used to hold an int/float/nil/boolean. and avoid an extra struct.
    - stormbrew 12y ago
      It is uintptr_t in size, but it's actually a bit more complicated than that. If the 'value' is a fixnum, the low bit is set to 1 and the bottom 31 or 63 bits of the integer are shifted to the left and stored directly in the VALUE [1]. And then there's a few other bit patterns (all with the low bit set to zero) that also mean embedded values [2], including symbols, where they're actually an index into a string table rather than an actual object pointer. So a lot of the time, VALUE is anything but a misnomer. Also, the name for this pattern is tagged pointer. It's one of the most notable things ruby borrowed from emacs lisp [3]. Also, the entire point of symbols is that they don't need to be dereferenced (or strcmp'd) to compare them. That's not the slow part of symbol comparison. [1] https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#L234 https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#... [2] https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#L383 https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#... [3] https://www.gnu.org/software/emacs/manual/html_node/elisp/Object-Internals.html https://www.gnu.org/software/emacs/manual/html_node/elisp/Ob...
kazinator 12y ago
Though optimizations in an interpreter are valiant efforts, the way to optimize the language is to develop a compiler. There are good reasons not to start doing hairy optimizations in the interpreter, like that it establishes the semantics which is helpful when compiled and interpreted semantics differ, and that interpreter optimizations will become moot once you have a compiler. About this Ruby optimization: one thing that stands out is that there doesn't appear to be any way to turn it off. If such a hard-coded interpreter optimization breaks, the only way to try something without the optimization is to revert to a build of the interpreter which didn't have it. That may not be possible, so then you may have to build the current interpreter, but with that change reverted. Compilers usually have switches for selecting various optimizations. Of course, a similar switch in an interpreter has a run-time impact: a "do this optimization" flag has to be checked each time there is an opportunity to do that optimization.
- jeffreyrogers 12y ago
  Mike Pall, the writer of the LuaJIT interpreter/compiler, suggests that a good interpreter can get a large portion of the gains you'd get from a compiler. At one point the LuaJIT interpreter (not the regular Lua interpreter) was within about a factor 2 of the JIT. I think the JIT has since improved, but you can still get significant benefits from simply improving the interpreter. (I don't have a reference for this and can't look it up now, so maybe someone else can help me on this... I do, however, remember reading something by Mike Pall that said this. I think it was on Lambda The Ultimate.) Of course, the best thing to do is to optimize the interpreter and then JIT compile the CPU intensive stuff.
  - strmpnk 12y ago
    Twiddling around with the radio buttons on this page show some interesting performance ratios: http://luajit.org/performance_x86.html http://luajit.org/performance_x86.html
  - riffraff 12y ago
    "LuaJIT's interpreter (!) beats V8's JIT compiler in 6 out of 8 benchmarks and is not too far off in another one" http://lambda-the-ultimate.org/node/3851?a=1#comment-57761 http://lambda-the-ultimate.org/node/3851?a=1#comment-57761
cliffordheath 12y ago
"Symbols are this unique, quasi-string construct" - not even a little bit unique. Interned atoms were a core feature in the very first Lisp interpreters, and the idea has been copied in many languages since.
cliffordheath 12y ago
"Symbols are this unique, quasi-string construct" - not even a little bit unique. Interned atoms were a core feature in the very first Lisp interpreters, and the idea has been copied in many languages since.

179 points by timr 12y ago

pgz 12y ago

Great article! What I don't understand is why can't they make the compiler inline the function instead inlining manually?

timr 12y ago
This is more than just C function inlining -- the Ruby interpreter, when it does a method call, ends up doing a lot of expensive bookkeeping at runtime to maintain its own internal call stack. This optimization allows the interpreter to completely bypass a Ruby method call, which is a big win.
- pgz 12y ago
  I meant having something like: if (check_cfunc(ci->me, rb_obj_equal)) { return rb_obj_equal(recv, obj); } and trusting the compiler to inline rb_obj_equal (or using inline), although I reckon you don't probably want rb_obj_equal to always be inlined.
  - masklinn 12y ago
    Well inlining this way is an optimisation which the compiler may or may not opt to apply, even after adding inlining hints. By manually inlining it they're introducing a little bit of trivial redundancy but I guess they can be certain there will be no indirect call. Either that, or they never considered the compiler would most likely inline it. Oddly enough, they do it for string comparisons: https://www.omniref.com/ruby/2.1.4/files/vm_insnhelper.c#line=860 https://www.omniref.com/ruby/2.1.4/files/vm_insnhelper.c#lin...
  - timr 12y ago
    Oh, sorry...wasn't clear. The problem with just doing the rb_obj_equal call for everything is that if people override eql? in their Ruby code, you need to call that overridden method, instead. The consequences of this decision mean that the comparison operator needs to be more complex.
  - saraid216 12y ago
    FYI, putting two spaces ahead of each line in a code block will wrap it in a pre-formatted tag. In case you didn't know.
gsg 12y ago
They aren't inlining manually. The optimisation works by making more cases fall into an already existing fast path. edit: I might have misunderstood - I should say that the patch doesn't do any inlining. The fast path is indeed the manually inlined body of the function.

jaredcwhite 12y ago

Every tiny little thing like this that gets further optimized in the MRI will result in major performance gains in advanced frameworks/codebases down the road. So this is great news. I'm looking forward to a near-future time when the claim Ruby=Slow! is much harder to make.

dkarapetyan 12y ago
There is an inherent overhead to all dynamically typed languages like Ruby and Python, method dispatch. Overcoming this problem is not easy and even JRuby with all the muscle of the JVM JIT is still pretty slow compared to the statically typed equivalent in Java or any other language that doesn't have to pay for method look-ups during run-time. The situation is not hopeless though and projects like Truffle/Graal (https://wiki.openjdk.java.net/display/Graal/Truffle+FAQ+and+Guidelines https://wiki.openjdk.java.net/display/Graal/Truffle+FAQ+and+...) are pushing the boundary of what is possible in terms of performance for dynamically typed languages. There is also PyPy and RPython (http://tratt.net/laurie/blog/entries/fast_enough_vms_in_fast_enough_time http://tratt.net/laurie/blog/entries/fast_enough_vms_in_fast...) which again leverages some neat JIT techniques to make things fast.
- chrisseaton 12y ago
  This is how Truffle and Graal make Ruby method dispatch fast (linking to my own blog post) http://www.chrisseaton.com/rubytruffle/how-method-dispatch-works-in-jruby-truffle/ http://www.chrisseaton.com/rubytruffle/how-method-dispatch-w....
  - nly 12y ago
    Good article, thanks. It's amazing how such relatively simple techniques get some fancy names.
- vanderZwan 12y ago
  > There is an inherent overhead to all dynamically typed languages like Ruby and Python, method dispatch I can't claim to fully understand how they pull it off (not being that familiar with compiler internals), but I thought Julia didn't suffer from this problem?

pmontra 12y ago

Almost offtopic because not directly related to symbols performances in Ruby but, coincidence, I was reading a 2011 post from Rubinius site http://rubini.us/2011/02/17/rubinius-what-s-next/ http://rubini.us/2011/02/17/rubinius-what-s-next/ a couple of minutes before seeing this on HN. At almost 50% of the post there is a code snippet that explains why Ruby method calls must be slower than the ones of statically typed languages. It also explains how Rubinius was addressing that 3 years ago. Hopefully they'll optimize that in all language implementations.

donpdonp 12y ago
also almost off topic but the lead Rubinius dev just posted a great writeup on rubinius 3.0 which could be a possible future of ruby in general. http://rubini.us/2014/11/12/rubinius-3-0-part-3-the-instructions/ http://rubini.us/2014/11/12/rubinius-3-0-part-3-the-instruct...
- pmontra 12y ago
  Interesting read. Thank you.

munificent 12y ago

Really neat article, though it makes me wonder why they didn't just remove `sym_equal` entirely and replace all usages of it with `rb_obj_equal`. At the very least, that `#define` needs a comment saying it must have the same identity as `rb_obj_equal` or a perf loss will happen.

timr 12y ago
Well, among other things, you can override the object equality check in Ruby -- so you can't simply rely on pointer identity as a check of equality. That said, yeah, it'd be nice if you could just make the assumption that if two objects point to the same memory, they're de facto identical...
- jrochkind1 12y ago
  You can make that assumption for symbols. And that is in fact what the code was doing -- both before and after optimization. The optimization was about something else, weirder, that was still making string comparison (where you can't just check the pointer) faster even though it ought to be slower. Did you read the article?
  - timr 12y ago
    "The optimization was about something else, weirder, that was still making string comparison (where you can't just check the pointer) faster even though it ought to be slower. Did you read the article?" I'm the author of the article. The optimization here is that the check for plain-old symbol equality is happening without the need for a full ruby method dispatch. You can't make that assumption in the general case, because it's possible to override equality in Ruby, which then requires more work. If you look at the full source code for the method in question, you'll see that it does special checks for Fixnums and Floats and Strings, then a check for the default object equality (i.e. does the comparison use rb_obj_equal?), then, finally, it falls back to a full method call.
  - jenrzzz 12y ago
    Actually, he wrote it!

skratlo 12y ago

Makes me wonder why the C compiler (gcc?) isn't clever enough here and is not inlining all that non-sense. At least I would expect SufficientlySmartCompiler™ to do so. Doing the inline by hand just proves how dark is the age we're living in.

masklinn 12y ago
> Makes me wonder why the C compiler (gcc?) isn't clever enough here and is not inlining all that non-sense. There's an indirection through a function pointer (ci->me). The manual optimisation is there to see whether the function pointer matches a baseline pointer, and apply that baseline directly instead of invoking the "generic" dispatch machinery (which involves setting new callframes & al) If you look at the whole function, there's a few special case before that which statically dispatch the case of a comparison between numbers or strings, so here we're in the "general" case and one last optimisation available is to see whether equality has been overridden at all.
- chrisseaton 12y ago
  People are often confused about how a JIT can be faster than a static compiler - this is a great example of why that can be the case. A dynamic compiler would be able to speculatively inline through the function pointer, where in a static compiler that is not tractable with what we currently know about compilers.
  - gsg 12y ago
    That's not really true - it's just (possibly partial) defunctionalisation. The problem isn't that we don't know how to do it, but that the necessary whole program architecture has various drawbacks. See Stalin and MLton for examples of a static compiler performing such analyses.
    - chrisseaton 12y ago
      Consider the case of a program which applies a processing function to pixels in an image. Which processing function to run depends a command line parameter. How would whole program analysis help you know which function you are going to use? But a JIT will see you keep calling the same function and inline it. Not even profile directed feedback will help you if each time you run the program you use a different function. I know Stalin and MLton but not the research you mention - can you point me at any papers?

mrinterweb 12y ago

My impression was that ruby symbols were defined once and mapped to the same memory space. If I am correct in my assumption, wouldn't it be more efficient to pass the arguments in as pointers and compare the equality of the pointers?

djur 12y ago
That's actually what they're doing. VALUE is a typedef for uintptr_t, so rb_obj_equal is just testing whether the pointers are the same.
- mrinterweb 12y ago
  Thanks for looking into that, Matt. It has been a long time since I did any real C programming, and I could not believe that they would be passing by value for this kind of equality check. The word "VALUE" is a little deceiving considering that it is actually a uintptr_t.
  - riffraff 12y ago
    it's not, really, VALUE may alternatively contain an immediate value or a pointer, i.e. a couple bits are used for type tagging and the rest is used to hold an int/float/nil/boolean. and avoid an extra struct.
  - stormbrew 12y ago
    It is uintptr_t in size, but it's actually a bit more complicated than that. If the 'value' is a fixnum, the low bit is set to 1 and the bottom 31 or 63 bits of the integer are shifted to the left and stored directly in the VALUE [1]. And then there's a few other bit patterns (all with the low bit set to zero) that also mean embedded values [2], including symbols, where they're actually an index into a string table rather than an actual object pointer. So a lot of the time, VALUE is anything but a misnomer. Also, the name for this pattern is tagged pointer. It's one of the most notable things ruby borrowed from emacs lisp [3]. Also, the entire point of symbols is that they don't need to be dereferenced (or strcmp'd) to compare them. That's not the slow part of symbol comparison. [1] https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#L234 https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#... [2] https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#L383 https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#... [3] https://www.gnu.org/software/emacs/manual/html_node/elisp/Object-Internals.html https://www.gnu.org/software/emacs/manual/html_node/elisp/Ob...

kazinator 12y ago

Though optimizations in an interpreter are valiant efforts, the way to optimize the language is to develop a compiler. There are good reasons not to start doing hairy optimizations in the interpreter, like that it establishes the semantics which is helpful when compiled and interpreted semantics differ, and that interpreter optimizations will become moot once you have a compiler. About this Ruby optimization: one thing that stands out is that there doesn't appear to be any way to turn it off. If such a hard-coded interpreter optimization breaks, the only way to try something without the optimization is to revert to a build of the interpreter which didn't have it. That may not be possible, so then you may have to build the current interpreter, but with that change reverted. Compilers usually have switches for selecting various optimizations. Of course, a similar switch in an interpreter has a run-time impact: a "do this optimization" flag has to be checked each time there is an opportunity to do that optimization.

jeffreyrogers 12y ago
Mike Pall, the writer of the LuaJIT interpreter/compiler, suggests that a good interpreter can get a large portion of the gains you'd get from a compiler. At one point the LuaJIT interpreter (not the regular Lua interpreter) was within about a factor 2 of the JIT. I think the JIT has since improved, but you can still get significant benefits from simply improving the interpreter. (I don't have a reference for this and can't look it up now, so maybe someone else can help me on this... I do, however, remember reading something by Mike Pall that said this. I think it was on Lambda The Ultimate.) Of course, the best thing to do is to optimize the interpreter and then JIT compile the CPU intensive stuff.
- strmpnk 12y ago
  Twiddling around with the radio buttons on this page show some interesting performance ratios: http://luajit.org/performance_x86.html http://luajit.org/performance_x86.html
- riffraff 12y ago
  "LuaJIT's interpreter (!) beats V8's JIT compiler in 6 out of 8 benchmarks and is not too far off in another one" http://lambda-the-ultimate.org/node/3851?a=1#comment-57761 http://lambda-the-ultimate.org/node/3851?a=1#comment-57761

cliffordheath 12y ago

"Symbols are this unique, quasi-string construct" - not even a little bit unique. Interned atoms were a core feature in the very first Lisp interpreters, and the idea has been copied in many languages since.

cliffordheath 12y ago