Exupery is now faster than VisualWorks for the bytecode benchmark

Bryce Kampjes bryce at kampjes.demon.co.uk
Sun Apr 10 18:53:57 UTC 2005


stéphane ducasse writes:
 > Hi bryce
 > 
 > I'm not expert but I wanted to know how you plan to deal with mega 
 > morphic methods
 > such as printOn:.
 > 
 > After some benchmarks in visualWorks it seems that they have a cache 
 > with 8 entries.
 > At esug in southampton eliot gave a talk about the tragedy of PIC 
 > explaining that but there were no slides
 > and now I forgot :(.

My PICs only have three entries. My current plan is to defer that
problem until we've got real application benchmarks suffering because
of it. ;-) But megamorphic methods are not that common, printOn: will
only be megamorphic if a lot of classes are all being called from the
same message, chances are most calls of printOn: will only see a
few receivers.

However there are a few options that I've thought about. 

One is to recompile the method with a larger PIC. The plan is for
Exupery to be driven by dynamic feedback to automatically
compile the hotspots. This is one reason why I've used a slow
algorithm for register allocation that generates good code.

Another is to move the type tests into compiled code. So the PIC is
just used to find new senders. If they are called a lot then they
could be slowly inlined into the calling method which means they will
no longer be in the PIC.

Another is to replace the PIC with a local hash lookup. Choose a
better data structure for dealing with large numbers of receivers. A
PIC is just a sequence of dynamicly generated "if class = x then jump
to y" instructions. This is not a great structure for large numbers of
receivers.

Another option is just to ignore them. If the PIC fails then I will
use the interpreters lookup which already uses a hash table. It might
be sensible to disable PICs for frequently called megamorphic calls
so it doesn't flush the code cache.

Without knowing how the megamorphic call fits into the surrounding
code it's hard to say which solution will work best. Once Exupery is
being used seriously then instrumentation should help make this
decision. Instrumentation first to design a set of solutions then to
dynamically choose between them.

The problem of a megamorphic send is really the same as the problem
of generating code for a large case statement. Which means a quick
literature search should find a lot more options.

Bryce



More information about the Squeak-dev mailing list