5 ms·

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

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.

titzer 2y ago
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.
- sitkack 2y ago
  https://bibliography.selflanguage.org/pics.html https://bibliography.selflanguage.org/pics.html for those following along
kannanvijayan 2y ago
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.
- bjoli 2y ago
  A minor nitpick: ICs don't give that much benefit in monomorphic languages like scheme.
  - sitkack 2y ago
    Couldn't PICs and monomorphization be seen as duals? They are both solving the problem of how to make polymorphic code have fewer branches.
    - pizlonator 2y ago
      PICs are the core mechanism of monomorphization in the VMs that do it
      - sitkack 2y ago
        I was thinking of static monomorphization as in Rust.
        pizlonator 2y ago
        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.)
        sitkack 2y ago
        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?
  - kannanvijayan 2y ago
sitkack 2y ago
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.
- pizlonator 2y ago
  That's an exciting direction!
  - sitkack 2y ago
    Profile Guided Optimization without Profiles: A Machine Learning Approach https://www.semanticscholar.org/paper/Profile-Guided-Optimization-without-Profiles%3A-A-Rotem-Cummins/0eb3a393cc4c6590e6314d6d5207859179e21e2f https://www.semanticscholar.org/paper/Profile-Guided-Optimiz...
    - pizlonator 2y ago
      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".
      - andyayers 2y ago
        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/coreclr/jit/GuardedDevirtualization.md https://github.com/dotnet/runtime/blob/main/docs/design/core... (where this is presented as a puzzle)....
mintplant 2y ago
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.
- hinkley 2y ago
  My understanding is that branch prediction got better in the ‘10s and a bunch of techniques that didn’t work before do now.
  - pizlonator 2y ago
    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.
    - hinkley 2y ago
      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.
      - pizlonator 2y ago
        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.
hinkley 2y ago
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.

titzer 2y ago

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.

sitkack 2y ago
https://bibliography.selflanguage.org/pics.html https://bibliography.selflanguage.org/pics.html for those following along

kannanvijayan 2y ago

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.

bjoli 2y ago
A minor nitpick: ICs don't give that much benefit in monomorphic languages like scheme.
- sitkack 2y ago
  Couldn't PICs and monomorphization be seen as duals? They are both solving the problem of how to make polymorphic code have fewer branches.
  - pizlonator 2y ago
    PICs are the core mechanism of monomorphization in the VMs that do it
    - sitkack 2y ago
      I was thinking of static monomorphization as in Rust.
      - pizlonator 2y ago
        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.)
        sitkack 2y ago
        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?
- kannanvijayan 2y ago

sitkack 2y ago

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.

pizlonator 2y ago
That's an exciting direction!
- sitkack 2y ago
  Profile Guided Optimization without Profiles: A Machine Learning Approach https://www.semanticscholar.org/paper/Profile-Guided-Optimization-without-Profiles%3A-A-Rotem-Cummins/0eb3a393cc4c6590e6314d6d5207859179e21e2f https://www.semanticscholar.org/paper/Profile-Guided-Optimiz...
  - pizlonator 2y ago
    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".
    - andyayers 2y ago
      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/coreclr/jit/GuardedDevirtualization.md https://github.com/dotnet/runtime/blob/main/docs/design/core... (where this is presented as a puzzle)....

mintplant 2y ago

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.

hinkley 2y ago
My understanding is that branch prediction got better in the ‘10s and a bunch of techniques that didn’t work before do now.
- pizlonator 2y ago
  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.
  - hinkley 2y ago
    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.
    - pizlonator 2y ago
      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.

hinkley 2y ago

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.