Zero-Overhead Metaprogramming

I saw this talk at FCRC/PLDI. It's both very impressive and very well-presented. What follows is what I gathered from the talk; I haven't read the paper but it's on my reading list. The basic idea is that the old notion of a polymorphic inline cache can be nicely generalized to erase away metaprogramming like method_missing or descriptors.

PIC is a way to speed up method dispatch. Normally, if you call a method foo in your program, but you don't know the class of the object you're calling foo on, you need to go look up the appropriate code to run in a virtual table or similar data structure. This is slow, because you might do this lookup very often. PIC means caching this lookup in the code that calls foo—basically adding an instruction like

    if (obj.class == CACHED_CLASS) CACHED_CODE()

The reason this helps is that we can do the test quickly, and the branch predictor will predict it very well; then our JIT can inline CACHED_CODE, perhaps optimize it against the other code nearby, and now we have nearly-optimal machine code. After "warm-up", in other words, we've dynamically inferred the type of obj and have optimized our machine code to take that into account.

Now on to meta-programming. Suppose instead of calling a method on an object we are instead instantiating a class object which is dynamically determined. PIC isn't exactly applicable, because it's not like the type of the class object is in question (the class object's class is probably Class or something). Instead, this paper proposes caching the identity of the class object, and the caching the initialization code and optimizing around it. You could do the same for things that override method_missing and similar, to cache all the decisions those overrides are making and then allowing the JIT to inline the code.

Their evaluation suggests that this method works really well, almost eliminating all of the overhead from meta-programming. This isn't too surprising: we know that even dynamic features are usually used in very "static" ways, that JITs are really good at finding these ways, and that after warming up JITs can usually optimize away all that dynamism to get very fast code.

I am kicking myself for never having thought of this, despite having read several of the PIC papers. I am not a big believer in meta-programming, but this work is simple, extremely useful in practice, and also deepens our understanding of a technique both theoretically and practically.

I'm very curious how your workflow is for putting together this paper! I put together https://github.com/Hoverbear/acm-pandoc-paper for my own purposes but there is some work to be done.

Meta question - anyone know if this was autogenerated from latex, and if so how?

What about compile-time metaprogramming such as found in D and C++. That's zero-overhead (discounting possible template bloat) and requires no special techniques at all. Well, besides knowing how to write compile-time code, that is.

It is my understanding that Graal -- one of the two JITs used in the paper -- will be available for use with "stock OpenJDK HotSpot" as a plugin (as opposed to a special HotSpot build), starting in Java 9. At least, that's the plan[1]. Is that correct?

[1]: http://openjdk.java.net/jeps/243

Off topic, but does anyone know how the author generated this web version of the paper? It looks like as though they've automatically generated it from the LaTeX source of the PDF. It looks brilliant, and much easier to read in the browser.

Haven't read it fully, but the first thing that popped in my head - wouldn't Apple benefit from this? There was one very detailed article on how their object method lookup changed over the years, but can't find it right now (Objective C).

Why does the partial evaluation approach result in larger performance variance than meta-tracing in the reported results?