Hacker News Reader

Comment by pizlonator | Hacker News Reader

I think the missing piece here is that JavaScriptCore (JSC) and other such systems don't just use inline caching to speed up dynamic accesses; they use them as profiling feedback.

So, anytime you have an IC in interpreter, baseline, or lightly optimized code, then that IC is monitored to see how polymorphic it gets, and that data is fed back into the optimization pipeline.

Just having an IC as a dead-end, where you don't use it for profiling is way less profitable than having an IC that feeds into profiling.

View on HN

Well on dynamic languages the ICs do give a nice order of magnitude speed-up by themselves, since the guard eliminates a whole hashtable (or linear) lookup instead of (in this case) a single memory indirection.

But yeah - on spidermonkey we found that orienting our ICs towards being stable and easy to work with, as opposed to just being fast, ended up leading to a much better design.

This is a nice result though. Negative, but good that they published it.

What would be a good next step is some QEMU-style transformation, pull out basic blocks, profile them for both hotness, and incoming arguments at function starts, and dynamic dispatch targets.. then use that to re-compile the whole thing using method-jit and in particular inlining across call-paths with GVN and DCE applied.

I kind of expect the results to be very positive, just based on intuition.. but it'd be cool to see how it actually turned out.

A minor nitpick: ICs don't give that much benefit in monomorphic languages like scheme.

Couldn't PICs and monomorphization be seen as duals? They are both solving the problem of how to make polymorphic code have fewer branches.

PICs are the core mechanism of monomorphization in the VMs that do it

I was thinking of static monomorphization as in Rust.

But then there isn't a duality.

If your language is static enough, then static devirt is profitable enough that you can stop there.

If your language is dynamic enough, then PICs are the main driver of devirt. (Though all PIC-based systems couple that with static analysis and that static analysis is powerful enough that it can sometimes devirt without the PICs' help.)

I meant "dual" in the analogous sense, not as strict mathematical duals where one could replace the other. That both are solving devirt from opposite ends. I read @bjoli's comment with the analogous connotation.

Your last sentence, would be if Rust used a PIC to optimize calls to dyn Traits?

Apologies if this response seems aggressive - this is just a topic I'm very passionate about :)

I think technically in languages like scheme, the opportunity would be to optimize other sorts of dispatches. The classic dispatch mechanism in scheme is the "assoc" style list-of-pairs lookup.

In this case, the "monomorphization" would be extracting runtime information on the common lookups that are taken. This is doable in a language like scheme, but it requires identifying parts of data structures that are less likely to change over time - where it makes sense to lift them up into hidden types and effectively make them "static".

Imagine if you could designate particular `(list (cons key value) ...)` value as "optimizable" - maybe even with a macro/function call : `(optimizable ((a 1) (b 2) ...))`

This would build a hidden shape for the association's "backbone" and give you back a shaped assoc list, and then you would be able to optimize all uses of `(assoc ...)` on lists of that kind in the same way you optimize shaped objects.

A plumbing exposed version of this would just let you do `(let my-shape (make-shape '(prop1 prop2 ...)))` and later `(my-shape '(1 2 ...))` to build the shape-optimized association list.

It's kind of neat when you realize that almost everything the runtime type-inference regime in a JIT compiler does.. is enable eliding lookups across data structures where we can assume that some part of that data structure is "more static" than other parts.

In JS that data structure is a linked-list-of-hashtables, where the hashtable keys and the linked list backbone are expected to be stable.

But the general idea applies to literally any structure you'd want to do lookups across. If you can extract a 'conserved shape', you can apply this optimization.

Indeed, this was literally the conclusion of the first paper that introduced polymorphic inline caches.

I'll add that the real benefit of ICs isn't just that compiled code is specialized to the seen types, but the fact that deoptimization guards are inserted, which split diamonds in the original general cases so that multiple downstream checks become redundant. So specialization is not just a local simplification but a global simplification to all dominated code in the context of the compilation unit.

https://bibliography.selflanguage.org/pics.html for those following along

SpiderMonkey actually ditched most of the profiling stuff in favor of transpiling the ICs generated at runtime into the IR used by the optimizing compiler, inlining them into the functions when they're used, and then sending the whole thing through the usual optimization pipeline. The technique is surprisingly effective.

I don't know what the best reference to link for this would be, but look up "Warp" or "WarpMonkey" if you're interested.

My understanding is that branch prediction got better in the ‘10s and a bunch of techniques that didn’t work before do now.

The modern VM technique looks almost exactly like what the original PIC papers talked about in the 90s. There are some details that are different, but I'm not sure that the details come down to exploiting changes in branch prediction efficiency. I think the things that changed come mostly down to the fact that the original PIC paper was a first stab by a small team whereas modern VMs involve decades of engineering by larger teams (so everything that could get more complex as a consequence of tuning did get more complex).

So, while it's true that microarches changed in a lot of ways, the overall implications for how you build VMs are not so big.

Are you still using a threaded interpreter main loop? That didn't really come around until the mid 90's and I've been hearing for about ten years now that it's not a clear win anymore due to predictors being able to read through two levels of indirection.

The last time I ran the experiment of having a single jump, it was slower than jump-per-opcode-handler.

It's true that predictors are able to see through multiple levels, but a threaded interpreter gives them plus one level, and that ends up mattering as much as it always did.

Threaded dispatch is absolutely worth it. Wizard's interpreter gets anywhere from 10-35% performance improvement from threaded dispatch.

> that branch prediction got better in the ‘10s and a bunch of techniques that didn’t work before do now.

They got better than they had any right to be, but then we found out that Spectre & Meltdown were vulnerabilities rather than optimizations.

For example, a switch based interpreter was fast as a CGOTO one for a brief period between 2012 and 2018, but suddenly got slower again as the CPUs could no longer rely on branch prediction to do prefetching.

While better predictors allow the speculation window to be larger on average, the the real culprit is that large speculation window. Even if the branch predictor weren't very smart, it will still do well on a program with stable, predictable branches, thus allowing a large speculation window to open up. The vulnerability is that some of those branches guard really important things, like not going out-of-bounds of an array. So a Spectre attack, which works by exploiting a mispredicted branch, is a constructive attack where the gadget is tuned for the branch predictor anyway. The other part of an attack, the windowing gadget, just relies on making a really slow input into a branch. Neither of them would be particularly harder with a dumb predictor.

It sounds like you're describing something similar to what the other JS VMs do

This is unique to SpiderMonkey, as far as I'm aware.

The main thing we're doing differently in SM is that all of our ICs are generated using a simple linear IR (CacheIR), instead of generating machine code directly. For example, a simple monomorphic property access (obj.prop) would be GuardIsObject / GuardShape / LoadSlot. We can then lower that IR directly to MIR for the optimizing compiler.

It gives us a lot of flexibility in choosing what to guard, without having to worry as much about getting out of sync between the baseline ICs and the optimizer's frontend. To a first approximation, our CacheIR generators are the single source of truth for speculative optimization in SpiderMonkey, and the rest of the engine just mechanically follows their lead.

There are also some cool tricks you can do when your ICs have associated IR. For example, when calling a method on a superclass, with receivers of a variety of different subclasses, you often end up with a set of ICs that all 1. Guard the different shapes of the receiver objects, 2. Guard the shared shape of the holder object, then 3. Do the call. When we detect that, we can mechanically walk the IR, collect the different receiver shapes, and generate a single stub-folded IC that instead guards against a list of shapes. The cool thing is that stub folding doesn't care whether it's looking at a call IC, or a GetProp IC, or anything else: so long as the only thing that differs is the a single GuardShape, you can make the transformation.

> The main thing we're doing differently in SM is that all of our ICs are generated using a simple linear IR (CacheIR)

JSC calls this PolymorphicAccess. It’s a mini IR with a JIT that tries to emit optimal code based on this IR. Register allocation and everything, just for a very restricted IR.

It’s been there since I don’t remember when. I wrote it ages ago and then it has evolved into a beast.

Taking a quick look at the JSC code, the main difference is that CacheIR is more pervasive and load-bearing. Even monomorphic cases go through CacheIR.

The main justification for CacheIR isn't that it enables us to do optimizations that can't be done in other ways. It's just a convenient unifying framework.

WarpMonkey doesn't get rid of the profiling stuff - the profiling is inherent in ICs - we keep hitcounts and other information for various paths taken through code (including ICs) and use that to guide compilation later.

Warp's uniqueness is in how it implements the ICs. The design goal when we built baseline JIT in SpiderMonkey was to split the code and data components of ICs. At the time, we were looking at V8 ICs which where basically compiled code blocks with the relevant parameter data (e.g. pointer to the hidden type to compare against) baked into the code.

We wanted to segregate the data from the code - e.g. so that all ShapedGetProp ICs can have a data stub with a pointer to their own shape, but share a pointer to the code. Effectively your ICs end up looking like small linked lists of C++ pure virtual objects (without the vtable indirection and just a single code pointer hanging off of the stub).

Originally the "shared code" was emitted by a bunch of statically defined methods that emitted a fixed bit of assembly (one for each kind of stub). That became unweildy as we added more stubs, so CacheIR was designed. CacheIR was a simple bytecode language that the stubs could express their logic in, which would get compiled down to machine code. The CacheIR bytecode would be a key to the compiled stubcode.

That let stubs generate arbitrary CacheIR for their logic, but still share code between stubs that emitted the same logic.

That led to the idea of Warp, where we noticed that one could build the input for an optimized method-jit compiler just by combining the profiling info that stubs produced, and the CacheIR bytecode for those stubs.

Normally you'd start from bytecode, build an SSA, then do a pass where you apply type information.

With Warp, the design simplifies into stitching together a bunch of CacheIR chunks which already embed the optimization information you care about, and then compiling that.

Ultimately it does the same thing as the other JITs, but it goes about it in a really nice and clean way. It kind of expresses some of the ideas that Maxime Boisvert-Chevalier was exploring in their work with basic block versioning.

Thanks for the more complete explanation!

> Normally you'd start from bytecode, build an SSA, then do a pass where you apply type information.

> With Warp, the design simplifies into stitching together a bunch of CacheIR chunks which already embed the optimization information you care about, and then compiling that.

This is what I meant by ditching most of the profiling stuff; I suppose I should have said "type inference stuff" to be more precise.

> Originally the "shared code" was emitted by a bunch of statically defined methods that emitted a fixed bit of assembly (one for each kind of stub). That became unweildy as we added more stubs, so CacheIR was designed.

I remember all too well :) I worked on the first pass at implementing megamorphic caches into the original stub generators that spit out (macro)assembly directly, before we had CacheIR. So much code duplication...

Ah, sorry for the misinterpretation!

Also, we may have overlapped on the team :)

We talk about this a bit in our CacheIR paper. Search for "IonBuilder".

https://www.mgaudet.ca/s/mplr23main-preprint.pdf

One of the last pieces of really good advice I got before I gave up on writing a programming language myself is that if you instrument the paths that are already expected to be slow, you can get most of the value of instrumentation with a fraction of the cost per call. Because people avoid making the slow calls, and if they don’t the app was going to be slower anyway so why not an extra couple percent? Versus the fast path where the instrumentation may be a quarter or more of runtime.

The answer is always more feedback. I am excited about DNN powered static profilers. The training data will come from the JIT saving the results of their experiments.

That's an exciting direction!

Profile Guided Optimization without Profiles: A Machine Learning Approach

https://www.semanticscholar.org/paper/Profile-Guided-Optimiz...

Very cool!

I've been thinking about what it would look like for something like this to be done for the profiling that you get from ICs, not the profiling you get from branch weights or basic block counts.

They're quite different. Two big differences:

- My best estimate is that speculating on type state (i.e. what you get from ICs) is a value bet only if you're right about 99.9% of the time (or even 99.999% - depends on your compiler/runtime architecture). I think you can get profit from branch weights if they are right less than 99.9% of the time.

- Speculating on type state means having semantically rich profiling information. It's not just a bunch of numbers. You need the profiler to describe a type to you, like: "I expect this access to see objects with fields x, y, z (in that order) and it has a prototype that has fields a, b, c, which then has a prototype with fields e, f, g".

For the .NET JIT, at least, speculation on types seems beneficial even if we're only right maybe 30% of the time.

See eg https://github.com/dotnet/runtime/blob/main/docs/design/core...

(where this is presented as a puzzle)....

Guarded devirtualization is different from the speculation that I'm talking about.

To me, speculation is where the fail path exits the optimized code.

To handle JS's dynamism, guarding is usually not worth it (though JSC has the ability to do that, if the profiling says that the fail path is probable). I believe that most of HotSpot's perf comes from speculation rather than guarded devirt.

> To me, speculation is where the fail path exits the optimized code.

V8 is now doing profile-based guarded inlining for Wasm indirect calls. The guards don't deopt, so it's a form of biasing where the fail path does indeed go through the full indirect call. That means the fail path rejoins, and ultimately, downstream, you don't learn anything, e.g. that there were no aliasing side effects, or anything about the return type of the inlined code.

You can get some of the effect of speculation with tail duplication after biasing, but in order to get the full effect you'd have to tail-duplicate all the way to the end of a function, or even unroll another iteration of the loop. It's possible to do this if you're willing to spend a lot of code space by duplicating a lot of basic blocks.

But the expensive thing about speculation is the deopt path, which is a really expensive OSR transfer and usually throws away optimized code, too. So clearly biasing is a different tradeoff, and I wouldn't be surprised if biasing plus a little bit of tail duplication gets most of the benefit of deoptimization.

Would you mind deep linking to the V8 code that does this?

Which JIT would be the easiest to implement to log this information? A time series LLM should be able to analyze it and give predictions.

Looks like PYPY is the most extensible.

https://rpython.readthedocs.io/en/latest/logging.html

And that the JIT is rebuilt from rpython, so it is fairly open to extension.

I know exactly how I would do that to JavaScriptCore, but that’s maybe mostly due to the fact that I designed most of the bits you’d have to instrument.

Not sure if it’s the easiest overall.

I’m easy to look up if you want to pick my brain about JSC

What a generous offer. I'll spend some time reading your papers first. Thank you.

Ask and ye shall receive:

https://www.sciencedirect.com/science/article/abs/pii/S01641...

It's XGBoost rather than DNN powered, but that might make sense from a runtime throughput perspective.

I think your original post turned me on to static profiling. The same researchers have another paper out, https://www.semanticscholar.org/paper/GraalNN%3A-Context-Sen...

This one is Open Access (thanks ACM!)

While the GraalSP paper is pay walled, there is a paper in Serbian by the same author. https://infom.fon.bg.ac.rs/index.php/infom/article/download/...

Reply on news.ycombinator.com