A very grumpy editor's thoughts on Oracle

Posted Aug 18, 2010 14:28 UTC (Wed) by smurf (subscriber, #17840) [Link]

Posted Aug 27, 2010 16:51 UTC (Fri) by Blaisorblade (guest, #25465) [Link]

That's not partial evaluation - my explanation was confusing. And partial evaluation (p.e.) is still unusable in practice in most cases (PyPy is the only known real-world exception I believe, and it's not really p.e.).

Sorry, I was very unclear - when I wrote "checking the exact class of the target object with a guard", I meant that the inlined code is executed only after checking, at runtime, the class of the receiver. So

  a.method(args);

becomes

  if (a.getClass() == expectedClass)
    call expectedClass_method(a, args);
  else
    //normal call dispatch

and you need profiling data to choose expectedClass. There are few cases in which they are not needed, mostly on final methods or on classes which currently have no subclasses (loading new classes might invalidate this assumption and cause the generated code to be thrown away).

This is a case of run-time algorithm specialisation, and IMHO it's related but different from p.e.

I was a bit sloppy, but the "impossibility" of C++ is actually more an effect of the lack of a virtual machine during C++ execution, in most cases (yes, I know Managed C++, that's the exception).

Profile-guided optimization could be applied to programs in non-VM-based languages - but I don't know of, say, mainstream Linux distributions doing this, even on specific cases.
This is not only due to convenience issues: a good reason is that the profile can be workload-dependent, and you don't necessarily have a gain when you use the wrong profile - I've read examples of this in some paper that I don't remember, but I hope the plausibility is clear enough.
Indeed, in VMs it's interesting the ability to adapt to changes in program behavior.

From my knowledge about p.e., derived from discussions with fellow PhD students and accounts on Wikipedia and PyPy docs (they used p.e., and stopped doing it), general p.e. techniques are well known as being difficult to use, because performance of programs using them is difficult to predict; that's cited as a reason for the invention of MetaML, an environment for staged compilation, where p.e. is explicitly controlled, and for the abandonment of the previous PyPy's JIT compiler [1]. Currently they have reimplemented a form of runtime specialization through tracing JIT compilation, which seems rather different from traditional techniques - in particular, it can't optimize an unmodified RPython program.
See here for a discussion about unpredictable optimizations in general.

The optimization I describe is well-known, except by, say, CPython implementors (and by Ruby implementors up to Ruby 1.8), together with a set of well-known results from the past 30 years (like "don't use reference counting" and other stuff - see these papers).

[1] "performance instability: change a seemingly unrelated bit in your source program, and the performance changes in unexpected ways, which is clearly not desirable". It's not clear whether it's related to p.e., until after reading the paper about MetaML.