A tail calling interpreter for Python (already landed in CPython)
(blog.reverberate.org)122 points by phsilva 4 days ago
122 points by phsilva 4 days ago
This is a great summary. When Mike wrote the message you linked, his conclusion was that you have to drop to assembly to get reasonable code for VM interpreters. Later we developed the "musttail" technique which was able to match his assembly language sequences using C. This makes C a viable option for VM interpreters, even if you want best performance, as long as your compiler supports musttail.
> they are able to perform more/better optimizations when looking at normal-sized functions rather than massive blocks
It's not the size of the function that is the primary problem, it is the fully connected control flow that gums everything up. The register allocator is trying to dynamically allocate registers through each opcode's implementation, but it also has to connect the end of every opcode with the beginning of every opcode, from a register allocation perspective.
The compiler doesn't understand that every opcode has basically the same set of "hot" variables, which means we benefit from keeping those hot variables in a fixed set of registers basically all of the time.
With tail calls, we can communicate a fixed register allocation to the compiler through the use of function arguments, which are always passed in registers. When we pass this hot data in function arguments, we force the compiler to respect this fixed register allocation, at least at the beginning and the end of each opcode. Given that constraint, the compiler will usually do a pretty good job of maintaining that register allocation through the entire function.
I feel like using calling conventions to massage the compiler's register allocation strategy is a hack. If the problem is manual control over register allocation, then the ideal solution should be... well, exactly that and no more? An annotation for local variables indicating "always spill this" (for cold-path locals) or "never spill this or else trigger a build error" (for hot-path locals). Isn't that literally why the "register" keyword exists in C? Why don't today's C compilers actually use it?
Unfortunately, most discussion of direct threaded interpreters confuses the implementation techniques (e.g. computed gotos) with the concepts (tail calls, or duality between calls and returns and data and codata, depending on your point of view). What is presented here is conceptually a direct threaded interpreter. It's just implemented in a way that is more amenable to optimization by the compiler technology in use.
(More here: https://noelwelsh.com/posts/understanding-vm-dispatch/)
Recent discussion: https://news.ycombinator.com/item?id=42999672
Do check out the articles in the top most comment.. about how tail call optimization gets you faster interpreters.
It completely eliminates the overhead of function calls in the generated machine code while you still your code modularly using functions.
To read about the basics of tail calls optimization:
https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
See also this little bit of discussion about a week back: https://news.ycombinator.com/item?id=42999672
This does NOT mean Python will get Tail Call Optimization, as Guido cannot be shown The Light, and has decided.
It is not an optimization ; it changes program semantics - converts programs that will run out of stack eventually regardless of the amount of available memory (and raise exceptions an the process, for example, which a program might rely on. Either way, semantics are changed)
It should only be called Tail Call Elimination.
By that standard, any optimization that changes scaling in any dimension changes semantics, which, well, I’m not saying its wrong, but I would say it is exactly what people looking for optimization want.
I disagree.
An optimization that speeds a program by x2 has the same effect as running on a faster CPU. An optimization that packs things tighter into memory has the same effect as using more memory.
Program semantics are usually referred to as “all output given all input, for any input configuration” but ignoring memory use or CPU time, provided they are both finite (but not limited).
TCE easily converts a program that will halt, regardless of available memory, to one that will never halt, regardless of available memory. That’s a big change in both theoretical and practical semantics.
I probably won’t argue that a change that reduces an O(n^5) space/time requirement to an O(1) requirement is a change in semantics, even though it practically is a huge change. But TCE changes a most basic property of a finite memory Turing machine (halts or not).
We don’t have infinite memory Turing machines.
edited: Turing machine -> finite memory Turing machine.
> By that standard, any optimization that changes scaling in any dimension changes semantics
That doesn't follow. This isn't like going from driving a car to flying an airplane. It's like going from driving a car to just teleporting instantly. (Except it's about space rather than time.)
It's a difference in degree (optimization), yes, but by a factor of infinity (O(n) overhead to 0 overhead). At that point it's not unreasonable to consider it a difference in kind (semantics).
The important thing is whether theres a garuntee of it happening in particular circumstance or not. Like with python referencing counting theoretically finalizers should be called after you lose all references to a file (assuming no cycles) but you cant rely on it.
Python dicts were in insert sort order for 3.6 but this only became a garuntee as opposed to an implementation choice that could be changed at anyvtime with python3.7
> converts programs that will run out of stack eventually regardless of the amount of available memory (and raise exceptions an the process, for example, which a program might rely on
That's probably one of the more frustrating things about Python. Each release it gets all sorts of questionable new syntax (including the very strange pattern matching "feature" that kind of sucks compared to something like Erlang or Scala), but we never get real useful quality of life improvements for basic functional programming like TCO or multi line lambdas
Python has always been unashamedly imperative, with some functional features entering by slipping through the cracks. The pattern matching thing seemed ok to me when I tried it, but I haven't used it except briefly, since I'm still mostly on Python 3.9. Interestingly, Python has been losing users to Rust. I don't entirely understand that, other than everyone saying how Rust's tooling is so much better.
> Python has been losing users to Rust. I don't entirely understand that, other than everyone saying how Rust's tooling is so much better.
Not to rust, but to Go and C++ for myself. The biggest motivating factor is deployment ease. It is so difficult to offer a nice client install process when large virtual environments are involved. Static executables solve so many painpoints for me in this arena. Rust would probably shine here as well.
If its for some internal bespoke process, I do enjoy using Python. For tooling shipped to client environments, I now tend to steer clear of it.
I'm largely still a Python user, but when I've used it, rust overall gross way more thoughtfully and consistently designed— both in the core language features and in the stdlib.
Python's thirty years of evolution really shows at this point.
> we never get real useful quality of life improvements for basic functional programming like TCO or multi line lambdas
A lambda can be as big of an expression as you want, including spanning multiple lines; it can't (because it is an expression) include statements, which is only different than lambdas in most functional languages in that Python actually has statements.
Guido is no longer BDFL though, it's the steering committee that decides.
the steering committee seems way less conservative than Guido, right?
Looking at python from the outside a lot of changes since GvR stepped down seem like stuff he'd not have been fond of.
I think this is a change longer in the making than that. Back when I started working with Python in the mid--late 2000s, the Zen was holy and it seemed very unlikely to ever see multiple ways to do "one thing".
The Python community has since matured and realised that what they previously thought of as "one thing" were actually multiple different things with small nuances and it makes sense to support several of them for different use cases.
Any examples? The biggest change since Guido stepped down has been the addition of pattern matching, which he was strongly in favour of.
Moreover, Guido is in favour of ongoing addition of major new features (like pattern matching), worrying that without them Python would become a “legacy language”:
https://discuss.python.org/t/pep-8012-frequently-asked-quest...
Ah, you’re correct. My comment was mainly meant as a tongue in cheek remark to point out that this definition of tailcall is wholly separate from Python function objects and merely an implementation detail.
Will Python ever get fast? Or even _reasonably_ fast?
The answer is no, it will not. Instead they'll just keep adding more and more syntax. And more and more ways to do the same old things. And they'll say that if you want "fast" then write a native module that we can import and use.
So then what's the point? Is Python really just a glue language like all the rest?
VWWHFSfQ, you may already know this, but: I recommend this talk by Armin Ronacher (Flask creator) on how Python's implementation internals contribute to the difficulties of making Python faster.
https://www.youtube.com/watchv=qCGofLIzX6g
One case study Ronacher gets into is the torturous path taken through the Python interpreter (runtime?) when you evaluate `__add__`. Fascinating stuff.
Your link is broken, here's a working one: https://www.youtube.com/watch?v=qCGofLIzX6g
Python is fast enough for a whole set of problems AND it is a pretty, easy to read and write language. I do think it can probably hit pause on adding more syntax but at least everything it adds is backwards compatible. You won’t be writing a 3D FPS game engine in Python but you definitely can do a whole lot of real time data processing, batch processing, scientific computing, web and native applications, etc. before you need to start considering a faster interpreter.
If your only metric for a language is speed then nothing really beats hand crafted assembly. All this memory safety at runtime is just overhead. If you also consider language ergonomics, Python suddenly is not a bad choice at all.
> If your only metric for a language is speed then nothing really beats hand crafted assembly
Only if you know the micro-architecture of the processor you are running on at great depth and can schedule the instructions accordingly. Modern compilers and vms can do crazy stuff at this level.
> Python is fast enough for a whole set of problems AND it is a pretty, easy to read and write language.
It is definitely easy to read. But speed is debatable. It is slow enough for my workload to start wondering about moving to pypy.
Will your program ever be fast if you don’t learn the microarchitecture of your CPU first? :)
PyPy is a valid option and one I would explore if it fits what you are doing.
everything it adds is by default backwards compatible, because old programs didn't use it, because it wasn't there yet, and so won't break.
Python's problem is that the non-new stuff is not always backwards compatible. It happens way too often that A new python version comes out and half the python programs on my system just stop working.
It was, once.
Nowadays (for about 12 years already I think) there is nothing much stackless about it.
The concept was nice. Stackless and greenlets.. yess. But the way they rewrote C stack just killed caches. Even a naive reimplementation just using separate mmapped stacks and wrapping the whole coro concept under then-Python's threading module instantly gained like 100x speedup on context switch loads like serving small stuff over HTTP.
Edit: Though at this point it didn't much differ from ye olde FreeBSD N:M pthread implementation. Which ended badly if anyone can remember.
I guess I'm wondering what is the point of tail-call optimizations, or even async/await when it's all super slow and bounded by the runtime itself? There are basically no improvements whatsoever to the core cpython runtime. So really what is all this for? Some theoretical future version of Python that can actually use these features in an optimal way?
This TCO is in how the CPython interpreter works, not in making Python itself tail recursive. Some of the C code in the interpreter has been reorganized to put some calls into tail position where the C compiler turns them into jumps. That avoids some call/return overhead and makes the interpreter run a little faster. It's still interpreting the same language with the same semantics.
The JIT will improve - you can also use PyPy to get speedups on programs that don't use a ton of C extensions.
Also, free-threading is coming so we'll have threads soon.
I don't know if Python can every really be fast as by design, objects are scattered all over memoryand even things like iterating a list, you're chasing pointers to PyObject all over the place - it's just not cache friendly.
How does this differ from direct threading interpreters?
It seems like it solves the same problem (saving the function call overhead) and has the same downsides (requires non-standard compiler extensions)
EDIT: it seems the answer is that compilers do not play well with direct-threaded interpreters and they are able to perform more/better optimizations when looking at normal-sized functions rather than massive blocks
http://lua-users.org/lists/lua-l/2011-02/msg00742.html