What are the different techniques to make megamorphic call sites more efficient

Question

Preamble

This is about improving message send efficiency in a JIT compiler. Despite referring to Smalltalk, this question applies to most dynamic JIT-compiled languages.

Problem

Given a message send site, it can be classified as monomorphic, polymorphic or megamorphic. If the receiver of the message send is always of the same type, it is a monomorphic send, as in

10 timesRepeat: [Object new].

where the receiver of new is always Object. For this kind of sends JITs emit monomorphic inline caches.

Sometimes a given send site refers to a few different object types, like:

#(1 'a string' 1.5) do: [:element | element print]

In this case, print is sent to different types of objects. For these cases, JITs usually emit polymorphic inline caches.

Megamorphic message sends occur when a message is sent to not just a few but a lot of different object types in a same place. One of the most prominent examples is this:

Behavior>>#new
    ^self basicNew initialize

Here, basicNew creates the object, then initialize does initialization. You could do:

Object new
OrderedCollection new
Dictionary new

and they will all execute the same Behavior>>#new method. As the implementation of initialize is different in a lot of classes, the PIC will quickly fill. I'm interested in this kind of send sites, knowing they only occur unfrequently (only 1% of sends are megamorphic).

Question

What are the possible and specific optimizations for megamorphic send sites to avoid doing a lookup?

Answer 1

I imagine a few, and want to know more. After a PIC gets full, we'll have to call the lookup (being it full or the global cached one), but to optimize we can:

• Recycle the PIC, throwing away all entries (many entries could be old and not used frequently).
• Call some sort of specific megamorphic lookup (i.e. one that would cache all previously dispatched types in an array accesed by the type hash).
• Inline the containing method (when inlined, the send site may stop being megamorphic)