CacheIR Heuristic: Stub Reordering
Categories
(Core :: JavaScript Engine, task, P5)
Tracking
()
People
(Reporter: mgaudet, Unassigned)
References
(Blocks 1 open bug)
Details
Copy and pasting from another document, this is an idea that I think could be investigated:
Our inline cache stubs are kept in a linked list. We start at the head of the list, and attempt each stub until we either succeed, or we hit the final stub which is a special fallback stub, which is able to prepend a new stub to the beginning of the chain or and serve a result.
There’s a temporal locality assumption here: Because we prepend stubs at the head of the list, we assume that the most relevant stub is the first one. However, if you had a program that periodically underwent phase-shifts, you could end up in a situation where you are continuously trying ‘the wrong’ stub first.
Because the stubs are a linked list, and we keep track of which stubs we are running, it should be possible to reorder stubs dynamically when situations like this are discovered.
There are few other policies that could be impactful too:
- Dropping a no-longer hitting stub in the prefix of the chain
- Periodically intentionally purging stubs and forcing the chain to be rebuilt (this could be done in a clever way that preserves the actual executable code to minimize overhead).
It could well be that this work isn’t as impactful as I imagine! Aside from instruction cache pollution, which is already endemic, guards are relatively cheap to check and fail, so we may already be well served.
(it may be that you'd want to actually only probabilistically move a stub, with liklihood decreasing proportional to depth in the chain)
|
Reporter | |
Comment 1•8 months ago
|
||
Julian (cc'd) also has an interesting idea for how we could potentially measure the liklihood of this being successful via trace analysis rather than full implementation.
|
||
Comment 2•8 months ago
|
||
With the code generation magic removed, the stub chain can be thought of as a
self-organising list, something that has been widely studied [1]. The goal
would be to reduce the average lookup cost (number of stubs checked) to 1 +
epsilon provided the distribution of types fed to it is skewed enough, at the
same time being able track local changes in the distribution of types.
I wonder also if there is any mileage in having different lists for the same
access in cases where we believe that the list is presented with a sequence of
types that is the interleaving of types from two different type "sources" in
the CFG, and we believe that each source would be better predicted by its own
list than by one list that attempts to track both sources. This might be
implemented using selective tail-duplication at the MIR level.
[1] https://dl.acm.org/doi/10.1145/359997.360000 (free access to article)
|
||
Comment 3•8 months ago
|
||
IIRC, Nathan Henderson (or maybe his undergrad minion Rajan?) played around with this a little as part of his master's and didn't turn up anything useful. I skimmed through the old matrix channel and my inbox and unfortunately couldn't find anything written down.
I believe part of the problem is that most ICs are monomorphic (so any extra code we add to the happy path to support reordering is pure overhead), and a large fraction of the remaining ICs are megamorphic, so there's very limited opportunity for a big payoff from optimizing small-N polymorphic ICs. Also, Warp's compilation model really prefers a single active stub, so we're often better off falling back to a more general IC that will work regardless of phase, instead of trying to keep up with phase shifts.
Actually, removing no-longer-hitting stubs in the prefix of an IC chain might be actively counterproductive. Consider the case where we alternate between two phases: one in which we only see shape A, and one in which we see shapes A and B. If we attach a stub for A, then attach a stub for B, and then remove the stub for B during an A-only phase, we might compile and transpile the A-only IC, in which case we will bail out as soon as we move back to an A-and-B phase.
Description
•