Making Ruby Faster
omniref.com
omniref.com
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.
Of course, the best thing to do is to optimize the interpreter and then JIT compile the CPU intensive stuff.
But there is a fundamental thing that a pure interpreter cannot avoid: compiling the source every time your application runs. This leads to long loading times.
For long lived applications this is not a big problem, but for short lived programs this can be killing. Currently `ls` in a directory with 10k files takes "0m0.008s", `git status` on the same directory takes "0m0.020s". You can barely warm up your interpreter in that time.
Also any cross-language comparison should be done very accurately - because we are talking about different language semantics and different benchmark implementations.
If you prefer apples to apples, quoting Mike Pall again[0]
"the LJ1 JIT compiler is not much faster than the LJ2 interpreter, sometimes it's worse".
A compiler that only beats interpretation by 2:1 is either a poor compiler or something else is going on, like most of the work actually being done by subroutines that cannot be whose performance is not being affected by the compilation (Because, for instance, they are written in C and intrinsic in the language run-time).
There do not have to be explicit calls to such functions. For instance, compiled arithmetic that is heavy on large bignums will probably not be much faster than its interpreted version, because cycles are actually spent in processing the arrays of bignum digits (or "limbs"), which is done in some bignum library code. The code being compiled looks innocuous; it just has formulas like (a+b)*c, but these turn into bignum library calls. Since the bignum library is written in C and compiled, the calls run equally fast whether called by interpreted or compiled code. That's where most of the time is spent, and so compiling the interpreted code makes no difference overall, even if 90% or more of the time spent there is knocked out by the compiler. (Amdahl's Law.)
Now check out performance graphs of LuaJIT2 compiler+interpreter vs interpreter modes[1].
Anything remotely computationally expensive is 2x faster with compiler and you can go up to 28x for integer number crunching.
I do believe that original point "a good interpreter can get a large portion of the gains you'd get from a compiler" can't be correct simply because it is too broad and ill-defined. What are the gains you expect from the compiler? How can "large portion" be defined? All of these really depend on many things: from the language itself to concrete design decisions in compiler/interpreter.
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...
Sure, but we aren't talking Ruby semantics here, we're talking C. I don't see why it's useful to still have a sym_equal identifier that's just an alias for rb_obj_equal.
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.
That's exactly what #define does. It replaces all usages and gives the token the same identity as the other token. As a C programmer first and foremost, it looks reasonable to me.
First class functions are super useful in C, but I think it's pretty rare to rely on their identity at runtime. If you are doing that, also aliasing the same function by another name seems like a recipe for confusion.
`sym_equal` only makes 2 appearances in the whole codebase (to be bound to `Symbol#==` and `Symbol#===` in string.c), so there's not a whole lot of room for confusion.
Also, this is Ruby core! Smart people do what works and makes sense to them and don't spend a lot of time worrying about how clear it is to us unwashed masses.
It's perfectly valid to question using a macro to rename a function instead of just renaming calls, especially if the renamed function is only called twice. It also would've been more pragmatic to mention in the code that rb_obj_equal is being used due to an optimization in opt_eq_func, as it's not obvious.
There might be reasons for using a macro in this case, like wanting to underline the fact that symbols are being compared, but I strongly suspect the author was just focused on changing the implementation of sym_equal to be better, and didn't think of the option of throwing it away.
Exuberant ctags will find the #define that goes with sym_equal and make it quick to locate. Upon seeing that sym_equal is #define'd to rb_obj_equal, it will be clear that they're identical at the C level. It may not be obvious why it's a #define, but a cautious programmer would be on alert that changing it back to a separate function would likely have some kind of implications.
Perhaps the ideal solution would be a large refactor to make the whole system as self-explanatory and surprise-free as possible. While waiting for that, this #define looks like a reasonable and low-risk bug-fix.
The situation is not hopeless though and projects like Truffle/Graal (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...) which again leverages some neat JIT techniques to make things fast.
JS engines have done a fair bit around dispatch, but ultimately much of that is similar to what was done in Self over twenty years ago.
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?
Many modern JIT compilers use multiple techniques for aggressive specialization of code sections that meet optimization heuristics (whether tracing-based or otherwise), thus carefully written JavaScript (under V8 and others), Lua (under LuaJIT) and Python (under PyPy and others) can be quite fast. On these platforms there are usually implicit or explicit language subsets and coding styles required to get maximum performance out of the compiler (as with Julia: it is possible to write slow code in any language). For example, ASM.js is an optimization-friendly, explicit subset of JavaScript.
[1] U. Hölzle, C. Chambers, and D. Ungar, “Debugging optimized code with dynamic deoptimization,” presented at the PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, New York, New York, USA, 1992, pp. 32–43.
It is quite common to cache methods (selectors) or just re-write them in the C subset, when optimizing code.
When you deal with sloppy inefficient code, almost any language is going to be considered slow.
I remember trying to make a paint program with Turbo Pascal 3.0 back in the DOS days, it was slow until I learned better algorithms in drawing things and how to write directly to video memory instead of using built in commands like plot.
This optimization allows the interpreter to completely bypass a Ruby method call, which is a big win.
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.
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.
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#lin...
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.
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#...
[2] https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#...
[3] https://www.gnu.org/software/emacs/manual/html_node/elisp/Ob...
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.
http://rubini.us/2014/11/12/rubinius-3-0-part-3-the-instruct...
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.
See Stalin and MLton for examples of a static compiler performing such analyses.
I know Stalin and MLton but not the research you mention - can you point me at any papers?
The classic paper on defunctionalisation is Reynolds' "Definitional Interpreters for Higher-Order Programming Languages". There's also a huge whack of papers at http://mlton.org/References, some of which go into MLton's compilation strategy (I don't remember which ones to point you at, though).
By using a #define to alias another name to that same function pointer, it hits the same fast path.
The equality method can't be inlined because ruby is a dynamic language and eql? can be redefined.