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

41–50 of 180 posts

Re: Performance of the Python 3.14 tail-call interpreter

#41

Post by jmillikin »

eru wrote: post #35
TinkersW wrote: post #30

Earlier quoted context omitted.

a+=1 will not produce any surprising results, signed integer overflow is well defined on all platforms that matter. And we all know about the looping behavior, it isn't surprising. The only surprising part would be if the compiler decides to use inc vs add, not that it really matters to the result.

> a+=1 will not produce any surprising results, signed integer overflow is well defined on all platforms that matter. I'm not sure what you are talking about? There's a difference between how your processor behaves when given some specific instructions, and what shenanigans your C compiler gets up to. See eg https://godbolt.org/z/YY69Ezxnv and tell me where the ADD instruction shows up in the compiler output. Feel fr…

I don't think "dead-code elimination removes dead code" adds much to the discussion.

If you change the code so that the value of `a` is used, then the output is as expected: https://godbolt.org/z/78eYx37WG

Re: Performance of the Python 3.14 tail-call interpreter

#42

Post by MaulingMonkey »

jmillikin wrote: post #25
eru wrote: post #20

Earlier quoted context omitted.

I know that for 'int a' the statement 'a += 1' can give rather surprising results. And you made a universal statement that 'a += 1' can be trusted. Not just that it can sometimes be trusted. In C++ the code you gave above can also be trusted as far as I can tell. At least as much as the C version.

I'll expand my point to be clearer. In C there is no operator overloading, so an expression like `a += 1` is easy to understand as incrementing a numeric value by 1, where that value's type is one of a small set of built-in types. You'd need to look further up in the function (and maybe chase down some typedefs) to see what that type is, but the set of possible types generally boils down to "signed int, unsigned int,…

    error: could not convert 'true' from 'bool' to 'std::string' {aka 'std::__cxx11::basic_string'}
I don't think anyone's claiming C nor C++'s dumpster fires have signed integer overflow at the top of the pile of problems, but when the optimizer starts deleting security or bounds checks and other fine things - because of signed integer overflow, or one of the million other causes of undefined behavior - I will pray for something as straightforward as a core dump, no matter where EIP has gone.

Signed integer overflow UB is the kind of UB that has a nasty habit of causing subtle heisenbugfuckery when triggered. The kind you might, hopefully, make shallow with ubsan and good test suite coverage. In other words, the kind you won't make shallow.

Re: Performance of the Python 3.14 tail-call interpreter

#43

Post by pjmlp »

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…

Systems languages that predated C already could do that, that is the typical myth.

Re: Performance of the Python 3.14 tail-call interpreter

#44

Post by gpderetta »

jmillikin wrote: post #19
eru wrote: post #15

Earlier quoted context omitted.

> The C expression `a += 1` can be trusted to increment a numeric value, [...] Have you heard of undefined behaviour?

Show me a C compiler that miscompiles the following code and I'll concede the point: uint32_t add_1(uint32_t a) { a += 1; return a; }

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

Re: Performance of the Python 3.14 tail-call interpreter

#45

Post by gpderetta »

jmillikin wrote: post #25
eru wrote: post #20

Earlier quoted context omitted.

I know that for 'int a' the statement 'a += 1' can give rather surprising results. And you made a universal statement that 'a += 1' can be trusted. Not just that it can sometimes be trusted. In C++ the code you gave above can also be trusted as far as I can tell. At least as much as the C version.

I'll expand my point to be clearer. In C there is no operator overloading, so an expression like `a += 1` is easy to understand as incrementing a numeric value by 1, where that value's type is one of a small set of built-in types. You'd need to look further up in the function (and maybe chase down some typedefs) to see what that type is, but the set of possible types generally boils down to "signed int, unsigned int,…

Counterexample: https://godbolt.org/z/z3jqjPT6o

Re: Performance of the Python 3.14 tail-call interpreter

#46

Post by cb321 »

While some people here are citing 10% as "large" and 1% as "normal", there are optimizations like partial inlining of doubly recursive Fibonacci that can reduce the actual work (and so also time) exponentially (factors >10X for double-digit arguments or 1000s of %, technically exponential in the difference of the recursion depth, not the problem size [1]).

C compilers can also be very finicky about their code inlining metrics. So, whether that enormous speed-up is realized can be very sensitive to the shape of your code.

So, while part of the problem is definitely that CPUs have gotten quite fancy/complex, another aspect is that compilers "beyond -O0 or -O1" have also gotten fancy/complex.

The article here, while good & worth reading, is also but one of many examples of how two complex things interacting can lead to very surprising results (and this is true outside of computing). People have a rather strong tendency to oversimplify -- no matter how many times this lesson shows up.

EDIT: Also, the article at least uses two CPUs, Intel & Apple M1 and two compilers (gcc & clang), but there are realistic deployment scenarios across many more generations/impls of Intel, AMD, and ARM and probably other compilers, too. So, it only even samples a small part of the total complexity. Also, if you want to be more scientific, esp. for differences like "1.01X" then time measurements should really have error bars of some kind (either std.dev of the mean or maybe better for a case like this std.dev of the min[2]) and to minimize those measurement errors you probably want CPU core affinity scheduling in the OS.

[1] https://stackoverflow.com/questions/360748/computational-com...

[2] https://github.com/c-blake/bu/blob/main/doc/tim.md

Re: Performance of the Python 3.14 tail-call interpreter

#47

Post by jmillikin »

pjc50 wrote: post #36
jmillikin wrote: post #12

Earlier quoted context omitted.

> 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…

> The phrase "C is portable assembly" isn't a claim that each statement gets compiled directly to equivalent machine code. Weasel words. Like a "self driving car" that requires a human driver with constant attention willing to take over within a few hundred milliseconds. People advocate for C and use it in a way that implies they think it can achieve specific machine outcomes, and it usually does .. except when it do…

As a general rule if you're reading a technical discussion and every single participant is using a particular phrase in a way that doesn't make sense to you then you should probably do a quick double-check to make sure you're on the same page.

For example, in this discussion about whether C is "portable assembly", you might be tempted to think back to the days of structured programming in assembly using macros. I no longer remember the exact syntax, but programs could be written to look like this:

  .include "some-macro-system.s"
  .include "posix-sym.s"

  .func _start(argc, argv) {
    .asciz message "Hello, world!"
    .call3 _write STDOUT message (.len message)
    .call1 _exit 0
  }
Assembly? Definitely! Portable? Eh, sort of! If you're willing to restrict yourself to DOS + POSIX and write an I/O abstraction layer then it'll probably run on i386/SPARC/Alpha/PA-RISC.

But that's not really what people are discussing, is it?

When someone says "C is portable assembly" they don't mean you can take C code and run it through a platform-specific macro expander. They don't mean it's literally a portable dialect of assembly. They expect the C compiler to perform some transformations -- maybe propagate some constants, maybe inline a small function here and there. Maybe you'd like to have named mutable local variables, which requires a register allocator. Reasonable people can disagree about exactly what transformations are legal, but at that point it's a matter of negotiation.

Anyway, now you've got a language that is more portable than assembler macros but still compiles more-or-less directly to machine code -- not completely divorced from the underlying hardware like Lisp (RIP Symbolics). How would you describe it in a few words? "Like assembly but portable" doesn't seem unreasonable.

Re: Performance of the Python 3.14 tail-call interpreter

#48

Post by IshKebab »

jmillikin wrote: post #19
eru wrote: post #15

Earlier quoted context omitted.

> The C expression `a += 1` can be trusted to increment a numeric value, [...] Have you heard of undefined behaviour?

Show me a C compiler that miscompiles the following code and I'll concede the point: uint32_t add_1(uint32_t a) { a += 1; return a; }

That will be inline by any C compiler and then pretty much anything can happen to the 'a += 1'.

Re: Performance of the Python 3.14 tail-call interpreter

#49

Post by xmcqdpt2 »

jmillikin wrote: post #41
eru wrote: post #35

Earlier quoted context omitted.

> a+=1 will not produce any surprising results, signed integer overflow is well defined on all platforms that matter. I'm not sure what you are talking about? There's a difference between how your processor behaves when given some specific instructions, and what shenanigans your C compiler gets up to. See eg https://godbolt.org/z/YY69Ezxnv and tell me where the ADD instruction shows up in the compiler output. Feel fr…

I don't think "dead-code elimination removes dead code" adds much to the discussion. If you change the code so that the value of `a` is used, then the output is as expected: https://godbolt.org/z/78eYx37WG

The parent example can be made clearer like this: https://godbolt.org/z/MKWbz9W16

Dead code elimination only works here because integer overflow is UB.

Re: Performance of the Python 3.14 tail-call interpreter

#50

Post by jmillikin »

MaulingMonkey wrote: post #42
jmillikin wrote: post #25

Earlier quoted context omitted.

I'll expand my point to be clearer. In C there is no operator overloading, so an expression like `a += 1` is easy to understand as incrementing a numeric value by 1, where that value's type is one of a small set of built-in types. You'd need to look further up in the function (and maybe chase down some typedefs) to see what that type is, but the set of possible types generally boils down to "signed int, unsigned int,…

error: could not convert 'true' from 'bool' to 'std::string' {aka 'std::__cxx11::basic_string '} I don't think anyone's claiming C nor C++'s dumpster fires have signed integer overflow at the top of the pile of problems, but when the optimizer starts deleting security or bounds checks and other fine things - because of signed integer overflow, or one of the million other causes of undefined behavior - I will pray for…

For context, I did not pick that type signature at random. It was in actual code that was shipping to customers. If I remember correctly there was some sort of bool -> int -> char -> std::string path via `operator()` conversions and constructors that allowed it to compile, though I can't remember what the value was (probably "\x01").

---

My experience with the C/C++ optimizer is that it's fairly timid, and only misbehaves when the input code is really bad. Pretty much all of the (many, many) bugs I've encountered and/or written in C would have also existed if I'd written directly in assembly.

I know there are libraries out there with build instructions like "compile with -O0 or the results will be wrong", but aside from the Linux kernel I've never encountered developers who put the blame on the compiler.

Post reply on HN