computed-goto interpreter: Prevent the compiler from merging `DISPATCH` calls

[nelhage]

• Work-in-progress test branch here

As a reminder: when compiling the interpreter using computed gotos, we emit a separate copy of the "dispatch" jump (currently goto *opcode_targets[opcode]) for each opcode implementation. The goal here -- as opposed to dispatching once at the top of the loop, and jumping to the top of the loop after each instruction -- is to expose more information to the hardware branch predictor (specifically, I believe, the branch target predictor, which tries to guess the destination of indirect branches).

However, the C compiler doesn't know that! It does, however, see that we've given it a C function containing a few hundred instances of identical DISPATCH code … and may choose to merge them together, replacing one or more instances with a jump into the tail end of a different opcode, thus undoing our careful work!

I suspect we can find a way to prevent the compiler from merging these branches, and thus restore similar branch-target-prediction behavior as in the tail-call interpreter.

The branch above attempts to prevent this merging by adding an empty __asm__ volatile "optimization barrier" to each call site, in the hopes that the compiler treats this as opaque and refuses to merge them. I'm far from certain this is the best approach, but in my testing it seems to be a speedup -- I see 1.03x on pyperformance on my machine (goto-mine is the linked branch with the optimization barrier).

We can also observe the merging a bit more directly by counting the number of DISPATCH sites that remain after optimization, according to debug symbols:

main

$ objdump -S --disassemble=_PyEval_EvalFrameDefault Python/ceval.o | grep -cF 'DISPATCH()'
47

nelhage/computed-goto-nomerge

$ objdump -S --disassemble=_PyEval_EvalFrameDefault Python/ceval.o | grep -cF 'DISPATCH()'
306

For comparison, generated_cases.c.h contains 227 instances on the same commit.

Linked PRs

• gh-129987: Disable GCC SLP autovectorization for the interpreter loop on x86-64 #132295
• gh-129987: Selectively re-enable SLP autovectorization of _PyEval_EvalFrameDefault #132530

[Fidget-Spinner]

Thanks. This makes quite a bit of sense. Just checking: Those numbers are with PGO+LTO/ThinLTO right?

Also what are the specs of the benchmarking machine?

[nelhage]

Just checking: Those numbers are with PGO+LTO/ThinLTO right?

Ah, I should have clarified: these are without PGO or LTO; I was testing without for simplicity while I explored and validated the theory. I'll try to get a PGO+LTO run today.

The benchmarking machine is an Intel i5-13500 Alder Lake running Linux. I wasn't pinning to the P cores, but maybe pyperformance run is smart enough to do so? I'll do an explicit pin when I run a PGO+LTO build.

[Fidget-Spinner]

@nelhage you can use the config file here, it does everything you need https://github.com/python/pyperformance/blob/main/doc/benchmark.conf.sample

You can configure LTO and PGO to be true, then set CPU affinity.

Then run pyperformance compile_all benchmark.conf.sample, which will compile, install and run the thing for you over an hour or so (so you can just walk away and let it run while you do something else).

[nelhage]

Ah-ha, thank you for the pointer! I'll try that.

[Fidget-Spinner]

I also think the commit message saying most of the gains from the tail-calling interpreter were from splitting up the jumps is potentially untrue. From our own benchmarking, tailcalls alone without special calling convention was only a 2-ish% speedup, corroborating with the 3% you got on your machine.

Two big factors come into mind for the other unaccounted 6-9% speedup:

• the preserve_none calling convention which pins registers
• PGO is better able to optimize individual smaller functions, than a gigantic 10000-line switch-case.

[nelhage]

I also think the commit message saying most of the gains from the tail-calling interpreter were from splitting up the jumps is potentially untrue.

Yeah, that commit message was written in a fit of optimism before I'd run the full performance suite. I now agree that this explains some of the difference but no longer believe it's all or even a majority. I toned down my claims in the issue but didn't go back and update the branch.

[Fidget-Spinner]

Thanks, no worries. I'm probably a more hopeless optimist: I sometimes think I sped up the JIT by 20% before I then realize I just forgot to build with release mode on :).

[nelhage]

LTO+PGO using pyperformance compile_all looks fairly comparable -- I see 1.04x vs 1.07x for tail-calls: https://gist.github.com/nelhage/0b1cf340dcf86d42f8c4814338cc883e

Full config and results here.

[Fidget-Spinner]

Very impressive! I'll ask to send a round of benchmarking on on our hardware.

[Fidget-Spinner]

Thanks to Mike, there's benchmark results here for GCC AArch64 and GCC AMD64 https://github.com/faster-cpython/benchmarking-public/tree/main/results/bm-20250210-3.14.0a4+-4603470

In the numbers "vs Base" there's no speedup.

It's possible this change only benefits Clang I think. I have a gut feeling GCC is smarter than Clang at preserving these jumps (or perhaps maybe we could call it not-as-smart, as clang is doing some instruction de-duplication here?).

We're also worried about the fragility of inline assembly and the computed goto interacting, though I don't understand this as well as @colesbury does.

[nelhage]

Interesting (and disappointing) that we don't see results on the other platforms/configurations. I'll investigate the question of whether GCC preserves the jumps better, since that at least should be an easy experiment.

We're also worried about the fragility of inline assembly and the computed goto interacting

Yeah, I agree that my current change feels fragile. Out of curiosity, I looked up what Ruby does, and as best I can tell, on x86, they emit volatile inline assembly with an explicit jmp.

The history of that line is not preserved into git (I believe it dates to YARV subversion), but I speculate it was added for a similar reason to this issue. I'm pretty sure that's technically UB per GCC's extended asm documentation, although I expect it works-in-practice because they also emit the goto and so the compiler infers the correct things about the CFG. I certainly don't feel better about it.

If the tail-call interpreter ends up being adopted on enough of the platforms anyone cares about, I guess it's possible this ends up being a dead-end and not worth much more effort.

[colesbury]

@nelhage - are your results with clang? It wasn't clear to me from this discussion.

I spent a while struggling with this a few years ago in the nogil fork's interpreter, but I mostly focused on GCC. You may already know this, but in case any of this is interesting:

GCC and LLVM combine all the computed gotos into a single instruction in their IRs. For example, the LLVM IR instruction corresponding to computed goto is indirectbr and there is typically one indirectbr per function, not one per goto. The compiler then (hopefully) duplicates the instruction later on, but I'm not sure what pass does this.

GCC has some options that affect this, but YMMV:

• -fno-gcse "When compiling a program using computed gotos, a GCC extension, you may get better run-time performance if you disable the global common subexpression elimination". IIRC, this hurt perf overall because gcse is actually useful.
• --param max-goto-duplication-insns 10000: "To avoid O(N^2) behavior in a number of passes, GCC factors computed gotos early in the compilation process, and unfactors them as late as possible"

See also:

• https://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284: "Computed gotos combined too aggressively"
• https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71785: "Computed gotos are mostly optimized away"

The goal here ... is to expose more information to the hardware branch predictor

The switch interpreter has two sources of overhead compared to computed gotos:

1. An extra direct, unconditional jump to the "top" of the switch
2. A shared indirect jump, which may result in worse branch prediction performance compared to one indirect jump per DISPATCH().

The conventional wisdom focuses on branch prediction performance, but from what I've seen, the extra jump is as important, or more important. I tested this about a year ago on Broadwell (~10 year old Intel) and Zen 4 (recent AMD). From what I remember, the extra direct jmp instruction added 1 cycle per opcode ¹. The sharing of indirect jumps (compared to 1 indirect jump per DISPATCH()) cost ~1 cycle on Broadwell and ~0.25 cycles on Zen 4, presumably due to slightly worse branch prediction. BTBs have gotten really big and branch prediction, including indirect branch prediction, has gotten really good!

In 2015, André Seznec wrote a paper called "Branch prediction and the performance of interpreters — Don't trust folklore", arguing that the "accuracy of indirect branch prediction is no longer critical for interpreters." Seznec is the author of the TAGE (and ITTAGE) predictors, which I think are used on Intel processors since Haswell. The paper doesn't mention GCC's unfortunate habit of merging computed gotos, so I'm a little skeptical of the Python numbers, but I think the overall claim is probably right.

... adding an empty asm volatile "optimization barrier" to each call

GCC and Clang appear to treat the empty __asm__ volatile ("") differently. For example, in https://gcc.godbolt.org/z/Pb51f9Wae, Clang introduces an extra load as if the asm clobbers memory. Not sure what to make of that.

Footnotes

1. I'm actually a bit confused by this, because "zero bubble" taken (conditional) jumps are apparently a thing. ↩

[nelhage]

are your results with clang? It wasn't clear to me from this discussion.

Yes, clang 19.1.6.

I appreciate all the pointers! I did not have all of that context and it's helpful. I am a dabbler more than an expert and figured this topic had to have come up, but didn't have the expertise to find the relevant prior art efficiently.

I can confirm that GCC (at least the one I'm testing with, GCC 14.2.1) does better at keeping the jumps separate, via the same crude objdump test:

$ objdump -S --disassemble=_PyEval_EvalFrameDefault Python/ceval.o| grep -cF 'DISPATCH()'
364

So that explains why GCC didn't show any benefit from this patch, and suggests that opening a bug with clang/LLVM might be a better approach. I'll file that bug and see what they have to say.

The conventional wisdom focuses on branch prediction performance, but from what I've seen, the extra jump is as important, or more important.

Interesting! That makes some sense to me, on reflection.

I arrived at this patch and this line of reasoning because I was comparing the computed-goto interpreter and the tail-call interpreter using perf, and noticed that (at least on the microbenchmark I was studying) the computed-goto interpreter executed slightly fewer instructions but at a significantly worse IPC:

❯ runPcore perf stat ./builds/computed-goto/bin/python3 ubench_unpack.py 100000

 Performance counter stats for './builds/computed-goto/bin/python3 ubench_unpack.py 100000':

          1,129.68 msec task-clock:u                     #    0.985 CPUs utilized
                 0      context-switches:u               #    0.000 /sec
                 0      cpu-migrations:u                 #    0.000 /sec
             1,818      page-faults:u                    #    1.609 K/sec
     <not counted>      cpu_atom/instructions/u                                                 (0.00%)
    12,469,708,578      cpu_core/instructions/u          #    4.47  insn per cycle
     <not counted>      cpu_atom/cycles/u                                                       (0.00%)
     2,790,428,963      cpu_core/cycles/u                #    2.470 GHz
     <not counted>      cpu_atom/branches/u                                                     (0.00%)
     2,781,399,601      cpu_core/branches/u              #    2.462 G/sec
     <not counted>      cpu_atom/branch-misses/u                                                (0.00%)
           587,835      cpu_core/branch-misses/u         #    0.02% of all branches
             TopdownL1 (cpu_core)                 #      0.4 %  tma_backend_bound
                                                  #      0.4 %  tma_bad_speculation
                                                  #     32.5 %  tma_frontend_bound
                                                  #     66.6 %  tma_retiring

❯ runPcore perf stat ./builds/tail-call/bin/python3 ubench_unpack.py 100000

 Performance counter stats for './builds/tail-call/bin/python3 ubench_unpack.py 100000':

            911.65 msec task-clock:u                     #    1.002 CPUs utilized
                 0      context-switches:u               #    0.000 /sec
                 0      cpu-migrations:u                 #    0.000 /sec
             1,816      page-faults:u                    #    1.992 K/sec
     <not counted>      cpu_atom/instructions/u                                                 (0.00%)
    12,829,514,649      cpu_core/instructions/u          #    5.68  insn per cycle
     <not counted>      cpu_atom/cycles/u                                                       (0.00%)
     2,258,460,003      cpu_core/cycles/u                #    2.477 GHz
     <not counted>      cpu_atom/branches/u                                                     (0.00%)
     2,060,476,914      cpu_core/branches/u              #    2.260 G/sec
     <not counted>      cpu_atom/branch-misses/u                                                (0.00%)
           494,661      cpu_core/branch-misses/u         #    0.02% of all branches
             TopdownL1 (cpu_core)                 #      0.4 %  tma_backend_bound
                                                  #      0.4 %  tma_bad_speculation
                                                  #     14.1 %  tma_frontend_bound
                                                  #     85.1 %  tma_retiring

(The ubench_unpack.py script can be found here -- it's a minimized version of pyperformance's bm_unpack_sequence, selected because it showed a substantial divergence between the two interpreters. This is a very small microbenchmark so we shouldn't expect it to be representative, but I was hoping that it would be tractable to analyze and potentially informative)

Based on the branch-misses discrepancy and some other not-necessarily-correct interpretation, I guessed at the "compiler is re-merging branches" theory, and considered it validated by the initial performance numbers. I think the performance gains do suggest it's doing something, but it's possible I'm mistaken about what. Notably, I think I'd expect a larger difference in tma_bad_speculation if branch-predictor accuracy were the issue, although I am far from a uarch/perf counter expert and may be completely mistaken.