Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Performance of the Python 3.14 tail-call interpreter

blog.nelhage.com

Post reply on HN
Print view View original

131–140 of 180 posts

Re: Performance of the Python 3.14 tail-call interpreter

#131

Post by SmellTheGlove »

kenjin4096 wrote: post #51

Hello. I'm the author of the PR that landed the tail-calling interpreter in CPython. First, I want to say thank you to Nelson for spending almost a month to get to the root of this issue. Secondly, I want to say I'm extremely embarrassed and sorry that I made such a huge oversight. I, and probably the rest of the CPython team did not expect the compiler we were using for the baseline to have that bug. I posted an apo…

I don’t think you should be embarrassed or apologize. You still did a thing that improved performance - in the near term it worked around a bug that you weren’t even aware of, and long term there are still gains even with that bug fixed. But even if that weren’t the case, the only way anything gets done in software is to rely on abstractions. You can either get things done or know exactly how every last bit of your stack is implemented, but probably not both. It’s a very reasonable trade off.

Smart people go and build things. Other smart people find problems. Nothings broken with that.

Re: Performance of the Python 3.14 tail-call interpreter

#132

Post by sunshowers »

haberman wrote: post #121
kenjin4096 wrote: post #51

Hello. I'm the author of the PR that landed the tail-calling interpreter in CPython. First, I want to say thank you to Nelson for spending almost a month to get to the root of this issue. Secondly, I want to say I'm extremely embarrassed and sorry that I made such a huge oversight. I, and probably the rest of the CPython team did not expect the compiler we were using for the baseline to have that bug. I posted an apo…

I think it's important to note that a primary motivation of the tail call interpreter design is to be less vulnerable to the whims of the optimizer. From my original blog article about this technique ( https://blog.reverberate.org/2021/04/21/musttail-efficient-i... ): > Theoretically, this control flow graph paired with a profile should give the compiler all of the information it needs to generate the most optimal co…

In full agreement with this. There is tremendous value in having code whose performance is robust to various compiler configurations.

Re: Performance of the Python 3.14 tail-call interpreter

#133

Post by csjh »

AlexSW wrote: post #105

I'm struggling to confirm that my intuition of why the compiler optimisation is faster than the naive switch expansion. Is it about the layout of where the assembly instructions end up, and spacing around them? Or the CPU pipelining working better? Or...?

distributing the dispatch instructions lets the predictor pick up on specific patterns within the bytecode - for example, comparison instructions are probably followed by a conditional branch instruction

Re: Performance of the Python 3.14 tail-call interpreter

#134

Post by chowells »

ehsankia wrote: post #123
jraph wrote: post #71

Earlier quoted context omitted.

Reading that you are extremely embarrassed and sorry that you made such a huge oversight, I was imagining you had broken something / worsened CPython's performance. But it's nothing like this. You announced a 10-15% perf improvement but that improvement is more like 1-5% on a non buggy compiler. It's not even like that 10-15% figure is wrong , it's just that it's correct only under very specific conditions, unknowing…

In some way, by indirectly helping fix this bug, they led to a ~10% performance increase for everyone who was using that faulty compiler! That's even better than an optional flag that many people won't know about or use.

That performance regression only hit code that was using a very large number of paths with the same table of computed gotos at the end. That's likely to only be relatively complex interpreters that were affected. So it's not a broad performance improvement. But it is nice to have an example of the compiler's new heuristic failing to prove evidence it needs to be tunable.

Re: Performance of the Python 3.14 tail-call interpreter

#135

Post by codr7 »

kzrdude wrote: post #64
jxjnskkzxxhx wrote: post #54

Earlier quoted context omitted.

I just wanted to say: respect for being able to say "sorry, I made a mistake". I hate the fake it till you make it mentality that seems to be the norm now.

I understand the frustration but I don't think it needed to be said (the part about mentality, the thanks is of course cool), because that's still not the norm. Why do I even bring this message - I want to say that let's not let what we see in the news influence our perception of the real people of the world. Just because fraud and crimes get elevated in the news, does not mean that the common man is a criminal or a…

Divide and conquer; we're supposed to hate each other and trust the state/elite/technology, at least that's the plan.

The real criminals, the people we should keep an eye on, are the plan's designers and implementers.

Re: Performance of the Python 3.14 tail-call interpreter

#136

Post by celeritascelery »

nelhage wrote: post #115
vkazanov wrote: post #7

So, the compiler is tinkering with the way the loop is organised so the whole tail-call interpreter thing is not as effective as announced... Not surprised. 1. CPU arch (and arch version) matters a lot. The problem is 95% about laying out the instruction dispatching code for the branch predictor to work optimally. C was never meant to support this. 2. The C abstract machine is also not low-level enough to express the…

(author here) > The problem is 95% about laying out the instruction dispatching code for the branch predictor to work optimally. A fun fact I learned while writing this post is that that's no longer true! Modern branch predictors can pretty much accurately predict through a single indirect jump, if the run is long enough and the interpreted code itself has stable behavior! Here's a paper that studied this (for both r…

How do you reconcile that with the observation that moving to a computed goto style provides better codegen in zig[1]? They make the claim that using their “labeled switch” (which is essentially computed goto) allows you to have multiple branches which improves branch predictor performance. They even get a 13% speedup in their parser from switch to this style. If modern CPU’s are good at predicting through a single branch, I wouldn’t expect this feature to make any difference.

[1] https://ziglang.org/download/0.14.0/release-notes.html#Code-...

Re: Performance of the Python 3.14 tail-call interpreter

#137

Post by titzer »

jmillikin wrote: post #12
kryptiskt wrote: post #8

This is a very good example of how C is not "close to the machine" or "portable assembly", modern optimizers will do drastic changes to the logic as long as it has no observable effect. As stated in the post: "Thus, we end up in this odd world where clang-19 compiles the computed-goto interpreter “correctly” – in the sense that the resulting binary produces all the same value we expect – but at the same time it produ…

> This is a very good example of how C is not "close to the machine" or > "portable assembly", C is very much "portable assembly" from the perspective of other systems programming languages of the 80s-90s era. The C expression `a += 1` can be trusted to increment a numeric value, but the same expression in C++ might allocate memory or unwind the call stack or do who knows what. Similarly, `a = "a"` is a simple pointe…

Saying that something "is like XY" when you really mean "is like XY, at least in comparison to C++" isn't what most people mean.

C is not a portable assembler.

In C, "a += 1" could overflow, and signed overflow is undefined behavior--even though every individual ISA has completely defined semantics for overflow, and nearly all of them these days do two's complement wraparound arithmetic. With C's notion of undefined behavior, it doesn't even give you the same wraparound in different places in the same program. In fact, wraparound is so undefined that the program could do absolutely anything, and the compiler is not required to even tell you about it. Even without all the C++ abstraction madness, a C compiler can give you absolutely wild results due to optimizations, e.g. by evaluating "a += 1" at compile time and using a different overflow behavior than the target machine. Compile-time evaluation not matching runtime evaluation is one of a huge number of dumb things that C gives you.

Another is that "a += 1" may not even increment the variable. If this occurs as an expression, and not as a statement, e.g. "f(a += 1, a += 1)", you might only get one increment due to sequence points[1]--not to mention that the order of evaluation might be different depending on the target.

C is not a portable assembler.

C is a low-level language where vague machine-like programs get compiled to machine code that may or may not work, depending on whether it violates UB rules or not, and there are precious few diagnostics to tell if that happened, either statically or dynamically.

[1] https://en.wikipedia.org/wiki/Sequence_point

Re: Performance of the Python 3.14 tail-call interpreter

#138

Post by AlexSW »

csjh wrote: post #133
AlexSW wrote: post #105

I'm struggling to confirm that my intuition of why the compiler optimisation is faster than the naive switch expansion. Is it about the layout of where the assembly instructions end up, and spacing around them? Or the CPU pipelining working better? Or...?

distributing the dispatch instructions lets the predictor pick up on specific patterns within the bytecode - for example, comparison instructions are probably followed by a conditional branch instruction

Ah of course! It's improving the branch target predictor. Makes sense, thanks!

Re: Performance of the Python 3.14 tail-call interpreter

#139

Post by igouy »

igouy wrote: post #130
eru wrote: post #14

Earlier quoted context omitted.

I vaguely remember about some benchmarking project that deliberately randomised these compiler decisions, so that they could give you more stable estimates of how well your code actually performed, and not just how well you won or lost the linker lottery.

"Producing wrong data without doing anything obviously wrong!" https://doi.org/10.1145/1508244.1508275

"Producing wrong data without doing anything obviously wrong!"

[pdf]

https://users.cs.northwestern.edu/~robby/courses/322-2013-sp...

Re: Performance of the Python 3.14 tail-call interpreter

#140

Post by Retr0id »

jmillikin wrote: post #102
gpderetta wrote: post #44

Earlier quoted context omitted.

If my misocompile, you mean that it fails the test that a "C expression `a += 1` can be trusted to increment a numeric value", then it is trivial: https://godbolt.org/z/G5dP9dM5q

I was being somewhat terse. The (implied) claim is that the C standard has enough sources of undefined behavior that even a simple integer addition can't be relied upon to actually perform integer addition. But the sources of undefined behavior for integer addition in C are well-known and very clear, and any instruction set that isn't an insane science project is going to have an instruction to add integers. Thus my…

Why are you talking about miscompilation? While the LLVM regression in the featured article makes the code slower, it is not a miscompilation. It is "correct" according to the contract of the C language.
Post reply on HN