>E.g. speculatively even looking near call sites by method name

That is devious and fantastic.

> But to get the most performance out of this you're likely to need to be prepared to do some very basic JIT.

Yeah. But the attractive targets here are places where you can't have a JIT: embedded systems and iOS.

When you spend a few years speculating about what it would take to efficiently compile Ruby as statically as possible (I love Ruby, but I hate moving parts), devious becomes second nature...

The idea of speculatively looking at method names comes from testing that to create vtables ahead of time for Ruby classes, to avoid hash tables in the common-case.

As it turns out, most method on most Ruby classes are the ones inherited from Object or other standard classes, and the number of classes is usually fairly constrained, so again speculatively looking at method names in the compile-time available source and allocating sparse vtables for the most common names results in relatively little waste.

And it reduces typical method lookup to a vtable lookup for common methods, with expensive method dispatch becoming much more rare. There's the tradeoff between theoretical horrible blowup in vtable waste from apps dynamically adding tons of methods and tons of classes, with a unique vtable slot required for each method name across all classes, vs. falling back to doing hash-table lookups all the way up the inheritance chain for "unusual" method names ones you reach certain thresholds for waste.

You do incur the cost of propagating vtable changes down the inheritance tree when methods are dynamically redefined in other places than leaves, but it is fairly rare to see apps where this happens at a very high rate, and the number of subclasses usually fairly small, so it is likely to be quite cheap. Doing it that way is something I first saw in a technical report by (now) prof. Michael Franz from '93 or '94 on "Protocol Extension" for Oberon.

You can probably also get some decent gains by adding heuristics to give preference to names that appears to be used in loops when picking names for the vtables to reduce the need of any JIT'ing.

That's interesting; Apple's Objective-C runtime has a fast vtable for its most common methods and uses a more expensive lookup for the rest. Doing a static analysis to find other commonly-used methods is like the next step up from there.

Out of interest, are you actually working on something like this for MRI? As you say, Ruby is in desperate need of optimization.

No, I've been off-and-on, toying with writing a "as static as possible" Ruby compiler (see http://www.hokstad.com/compiler) - it's been about two years since I last posted an update, but I have one new part complete and another one mostly complete. Just holding off posting for a bit longer because I want to have a bit of a buffer (3-4 complete parts) before I get peoples hope of regular posts up again...

What is there uses vtable's exclusively - I effective punted on the slow path (and so on adding methods at runtime) completely, but keep track of how much of the vtable allocations is wasted space. If/when I get there, the goal is to use various mechanisms like this to determine when to fall back on a slow path, and couple both with polymorphic inline caching when suitable.

EDIT:

I don't see MRI as very interesting to work on, largely because interpreters aren't much fun, and ironically given the amount of time I spend using Ruby, I prefer compilers to be as static as possible. I also prefer my compilers to be bootstrapped in their target language. Hence my "ideal" Ruby compiler would be written in pure Ruby, do a ton of static analysis, with minimal fallback to JIT when users user features that are too dynamic to analyse fully ahead of time

E.g. there's a ton of annoying uses of eval() in Ruby code where a more complete meta-programming API would make it trivial for a compiler to do full ahead of time static analysis, so one big thing an AOT Ruby compiler really need to do is to provide a library of compiler specific meta-programming facilities with a fallback that uses eval() as needed, and either convince people to use it, or provide monkey-patches for a number of popular projects. Some of these uses don't even need eval() in the first places, but uses it just as a quick shortcut because it's simpler...

Just to make clear, I'm not sure when or even if my compiler project will ever get to a state where it's even remotely useable to compile Ruby. I started it out without even having decided to compiler Ruby, mostly to write about various parts of the process of writing a compiler that I find interesting. I find compiling Ruby as incredibly fascinating from a theoretical point of view because of the complexity involved, but unfortunately working on it takes a lot more time and effort than thinking about the problems.

I see. Sounds like an interesting project.

Sure, MRI is boring, but it's the best implementation right now (though some may argue that JRuby is better), and it's in desperate need of VM innovations.

Any new compiler/VM starting from scratch will be years away from being available for use in production environments. By the time it's finished, we'll all be using Go. (Sigh.)

I think we need both. MRI can keep getting better, as can JRuby (which is an amazing feat, but to me, running on top of the JVM makes it a non-starter) or Rubinius, but they're fundamentally side-stepping the really hard problems.

E.g. nothing will stop MRI from having to interpret thousands of lines of code each time because it can't draw a line between runtime and compile time, while for an ahead of time compiler for Ruby, finding a pragmatic line between what needs to be executed at runtime vs. compile time is essential (consider for example the tendency to do stuff like getting the list of files in a directory and require all of them in turn).

We do need both. But some of the things you mention (like constructing vtables) could be applied to MRI's VM model without writing a compiler from scratch. Frankly, I would much rather have large performance improvements now than in 2-3 years.

(I agree about JRuby. I also wonder why Rubinius, which showed so much promise at the beginning, has stagnated. Is it simply the lack of developers?)

I agree the performance increase would be great, but I think it needs to come gradually to MRI. E.g. trying to do anything fancy with the old AST-based interpreter would've been pretty pointless. After YARV, it is probably starting to get more attractive, but at the same time they've added method caching which gives a decent amount of the benefits. A vtable will still get faster, but it might not be the most immediately expedient way of speeding things up vs. e.g. Sasadas latest project of adding a generational gc.

Regarding Rubinius, writing compilers for dynamic languages is hard. Most textbooks you'll find cover techniques most suitable for statically typed languages (the best resource I know for starting to catch up on compiling dynamic languages is actually the Self papers). So you need more than an unusual level of interest in writing compilers to be likely to try to tackle a language like Ruby which is tricky even for dynamic languages (e.g. my favorite pet problem to meditate on: What constitutes 'compile time' vs. 'runtime' for ahead of time compiled Ruby?), and even more to actually persevere until you start getting proper results where you can get decent results in days with a simpler language.

It's made worse because of Ruby's horrendous grammar. And I mean that from a compiler writers perspective - as a developer I love to use Ruby to a large extent because the complexities of the grammar means it reads and writes better 95% of the time. But MRI's bison based parser was 6k-7k lines with ugly parser/lexer interplay last time I checked... There are full compilers substantially smaller than that for other languages...

To me, these complexities are part of what makes it fascinating. I firmly believe you can parse Ruby fully with a much, much simpler parser for example. A lot of the ugliness can be abstracted away, and C parser code is rarely good examples of succint code.

I did start playing with MRI years ago, specifically the parser, actually, and started chopping out redundant pieces, but got frustrated and bored with it. That's part of the problem - it's one thing to play around with a toy compiler like I've done, and another entirely to put in the effort to push a major change to MRI through to production quality given the number of years of accumulated history encapsulated in it. Doing the latter as a hobby is a daunting task.

Just a note on Rubinius: The PyPy guys seem to have done pretty well at this. I don't know how similar they are to Rubinius; PyPy reduces to a RPython as an initial step, whereas I believe Rubinius compiles to LLVM's LI.

To tell me to "just use" it seems a bit glib considering that it's apparently nowhere being ready for production (the current code even has failng tests), let alone available as a swap-in replacement for Ruby.

That said: It looks like a really interesting project. I do wish they would phrase the project description as a "Ruby VM" instead of a separate programming language, through. There should not be any need to fork the entire language just to provide better performance.

I know it is still very alpha.

I just wanted to raise your attention to it, but you are right, it would be better to have a proper Ruby compiler available instead.

I would love to have a higher-level-than-C language to work with on embedded systems, and Clojure seems good.

However my applications run on systems with very limited resources (and a Harvard-ish architecture, e.g separate data/program memories) and I wonder how far tools like ClojureC could go with regard to these constraints.

re: JIT on iOS I've heard of people compiling their own JavaScriptCore (to use Ejecta), is this still an issue? Embedded systems is another story, I'd be far more concerned about Clojure's assumptions about GC.

The JavaScriptCore they are compiling is without the JIT.

You still can't have memory pages marked write+execute, which is what you need for a JIT.