The CPython Bytecode Compiler Is Dumb
nullprogram.com
nullprogram.com
For example, it's hard to optimize even local variable dataflow in python since it's part of the API : you can inspect the local frame of your caller, so you have a problem as soon as your function contains a single call. And no you can't know statically what is the call target since it can be replaced dynamically.
So either you perform the optimization anyway and then have to try to support reconstructing values correctly to support introspection, or you just do that generically with OSR and use the simple introspection on the interpeter.
Either way, there are not a lot of "simple optimization" when the language is so dynamic.
E.G: I have no problem putting a few annotation telling Python I'm not going to and allow to override builtins in my program and it's dependancies.
We could make sure those markers can only be set in __main__, and crashes with very explicit errors in the unlikely event anything down there decide to do otherwise.
Indeed, many dynamic features are rarely used. They are handy from time to time, but I won't miss them for many codes.
Things like monkey patching and stack inspection are the excetion rather than the rule. You may very well be able to safely disable many feature at some local level, or in prod but not dev, etc.
Right now, the swing is in general to statically-typed languages that are more convenient to use, but I've thought there's room for a new dynamic scripting language that is still dynamically typed, but is written from the beginning to focus on speed. You can see some of the ideas in Julia or LuaJIT, but you pay a penalty on what can be dynamic.
One of the ideas I've had is more like the "pledge" feature that OpenBSD recently introduced. Rather than stating up front "I will not use this feature", you initialize your program, do all the dynamic stuff, then push the "OK, now I'm done being dynamic" button. After that, the program "freezes" into place, and calling a function with a new type of argument it has never seen before or something becomes an error.
My reasoning here is that the dynamic scripting languages tend not to use their dynamism evenly. The vast bulk of "dynamic" behavior is all done in an informal initialization phase, but then, for the bulk of the program's execution, you continue to pay for all the dynamism because the interpreter has to constantly follow the dynamic chains of functions, or even if the code is JIT'ed, the JIT has to be written to handle functions suddenly getting the "wrong" type, which at the very least means you pay for a check the static programs don't need to pay for, and generally, you may have to pay more. You set up the dynamism once at the start of the program, but pay for the ability to be dynamic later billions and trillions and so on of times over the course of the program.
(Don't just think about how poorly this would work if bodged onto Python or Javascript or something, because I know such an attempt would absolutely be a disaster. That's why I'm hypothesizing someone sitting down and designing this language from scratch with these ideas in mind, so it'll have the correct affordances and paved cow paths and such to make this work. While you're at it, give your new dynamic scripting language a solid concurrency story, since none of the current ones have one, since they all grotesquely predate that as a concern. I think there's a hole in the programming language landscape here right now. Another way to think of this is "write a dynamic scripting language that is designed to have a good, simple JIT".)
(Actually, for all the languages there are, I think there's several holes in the programming language landscape right now. You'd think everything would be covered, but it really isn't.)
I'm sorry but I think I'm missing something here - what sort of penalty are you paying in terms of dynamicness? Can you be more specific?
Regardless, Perl, Python, and Ruby have simply absurd amounts of dynamicness; you can dynamically add operator overloads to the super-superclass of some object you have in hand, or write new metaclasses then create new classes from them, or stick new implementations of __setattr__ in the middle of a class chain, etc., and the interpreter is ready for you to do it, at great runtime cost. For that sort of thing, the JIT will just give up, generally. You'll note that a lot of these things are things you don't generally have a need to do, which is precisely the thing I'm suggesting be exploited more. My understanding is that Julia is not this dynamic. (For those who may be inclined to jump to the "defense" of Julia, bear in mind I'm citing this as a good thing.)
Another way of looking at my suggestion is to forbid all the things that blow out the JITs, but giving the JIT a phase it is allowed to depend on, which will take some work because, again, simply retrofitting that on to an existing language will be a nightmare in all sorts of ways. You want some deep integration into the language for this. None of the current scripting languages were designed with JITs in mind; JITs are always laboriously wrapped around them years after the fact. What if you went the other way around? (You may get Julia in that case; what if you add the ability to have a pre-pledge phase in too, though?)
(Another idea: What if you write a language, or possibly language family, for truly heterogeneous computing models? What would a language that natively has a concept of CPU vs. GPU code look like? Some sort of explicit, visible management of shared data? We also see embryonic use cases where we want a low-power, cheap CPU that's still a CPU, to do some low-power basic maintenance cases, but has a high-power CPU friend that can be turned on if necessary. If there was a language that afforded such management, would we see more of that thing in cell phones and such? There's a lot of interesting places for programming languages to be created, but we tend to see so much of "it's ${some existing language}, with some slight twist, and no standard library".)
Julia is designed along these lines - its JIT compiler is really just does AOT compilation at runtime. JavaScript JITs tend to work along the lines of:
1. Interpret (and gather profiling data including type information)
2. JIT compile hot code, making assumptions based on profiling data
3. Deoptimize (fall back to the interpreter) if an assumption is broken
This is why Julia code tends to contain many more explicit types than code in other dynamic languages. Compared to other JIT-compiled dynamic languages, Julia trades-off some dynamism for compiler simplicity.
I'm proposing that you could probably get back a lot of that dynamicness if you could explicitly say "OK, I'm done being dynamic now", because in general, even Python programs that do things like introspect databases and dynamically create classes on the fly based on that still have a distinct initialization phase. Reifying that into something the interpreter/compiler (honestly, in this language design, that distinction barely matters...) understands might let you have both worlds.
In practice Chez Scheme is fast, though I guess not quite up to LuaJIT's level even though Lua seems less designed for efficiency than Scheme. (E.g. Lua tables ought to be more expensive than Scheme vectors, and people use metatables a lot where Schemers might use macros...)
We could even come up with names for those two phases. We could call the first phase "compile time" or "preprocessor/macro evaluation time", and the second phase "run time" :)
You shouldn't have to!
The VM should be able to work this all out for you. One person puts the effort into improving the VM rather than everyone has to work around in their program.
Do you want to break all assumptions a Smalltalk JIT managed to reach about a live object?
Just send it a become: message.
It's really a combination of dynamicism and desire for approachability of the codebase: the cpython codebase is not beautiful, but it's definitely approachable, there is very little use of tricks or complex macros and the average Python developer can jump around and find things.
This seems like the sort of thing that should be absolutely not relied upon outside of debugging/profiling and other special circumstances. At least in my experience, I've had to write this sort of thing a few times and it's always been a last resort (and mainly for those purposes I mentioned).
Not only is it problematic because it disallows compiler optimizations, it also seems like it would enforce an unchangable set of local vars.
> Don’t count on your operator overloads to work here, though.
> by keeping these variables around, debugging is more straightforward
The transformations the author is suggesting are not in general legal. Missing operator overloads and inconsistent debugging states aren’t something to gloss over - they’re showing you your optimisations are just wrong!
You would need a sophisticated deoptimisation system with frame states, like JVMs or V8 has, to make them legal.
The Python compiler isn’t dumb - it’s correct.
https://twitter.com/chrisgseaton/status/619885182104043520
Try doing something like that at compile time.
Edit: I have seen Guile's optimizer/peval turn 30 lines of messy (to human eyes) code to a single atom result. This is actually rather simple as long as you van reason enough about the code and it has no side effects. The hard part is developing heuristics to not have it impact compile time too much
My PhD defence committee was impressed, so that was good enough for me.
In Ruby almost no code is refentially transparent so just simple PE is not enough. You need to speculate in some complex ways and writing that to be practical is not easy.
I might have gotten it wrong for guile as well :) sorry to sound so dismissive. I would love to read your thesis!
> I wonder if the code I’m writing is putting undue constraints on the bytecode compiler and limiting its options
If that's what you're wondering while writing Python, then you probably shouldn't be writing Python.
I certainly basically mentally execute code to some extent as I write it. Is there a way to program that doesn't do something like that?
The only thing you can do is run your code and get an empirical answer to the question 'Is it fast enough'.
Most common instructions in modern CPU cores are decoded directly into the corresponding micro-operation(s), without involving the microcode ROM. Only the most complex instructions, involving many micro-operations, will use the microcode decoder. Also, there are often several copies of the simpler instruction decoder, so the CPU can decode several instructions in a single cycle, while there's normally a single copy of the complex (microcode-using) instruction decoder.
A good resource if you want to read more is part 3 of https://www.agner.org/optimize/ which describes the decoder (and other parts) of several families of x86 processors.
(I too execute the code in my head, but these days usually a couple layers above x86 ASM, in my own mental "bytecode" that tracks how expensive are some of programming language's operations and stdlib functions.)
An example - some code I was working with gave subtly different results on two processors. It turned out this was because one of them implemented FMA - Fused Multiply Add.
https://en.wikipedia.org/wiki/Multiply%E2%80%93accumulate_op...
It wasn't particularly painful to find this, but if you were attempting to debug this kind of problem without considering lower level issues, you'd spend a whole lot of time banging your head against a wall.
I think if you're talking micro-code fusing then Intel does guarantee it has exactly the same semantics as a separate multiply and add.
Interesting fact - I believe modern Intel architectures actually only have fused multiply add. If you do just a multiply it'll do a fused multiply and add zero.
Logic and relational programming (Prolog, SQL) comes pretty close. "Here's some rules about the data. Execute."
I remember university classes in Prolog. Solving logical puzzles tended to be declarative, but trying to write any actual program involved shifting to the mindset that you're dealing with a regular programming language with a built-in DFS engine underneath (the same way programming in JS involves learning you have a hidden event loop running in the background). For practical use of SQL, you need to be able to choose between equivalent queries based on how the database engine actually turns them into lookups.
Maybe 30 years ago. It's really not so important nowadays. Computers are fast.
> For practical use of SQL, you need to be able to choose between equivalent queries based on how the database engine actually turns them into lookups.
Maybe there are some cases where you need to, but there are also million-dollar businesses that have succeeded while only ever writing their SQL queries as naively as possible. The notion that all non-toy practical uses need to understand such low-level details is just utterly false.
Citation needed. Given engineering staff sizes and the amount of performance problems RDBMSes have, that seems highly doubtful.
But in regards to "Is there a way to program that doesn't do something like that?", I would say relational is that way.
You must be psychic if you can figure out what the DB engine is going to do without running it.
Bitmap scan, parallel index scan, merge join, nested loop join, etc. I always have to try and see.
You don't necessarily have to know whether an index scan is going to be parallelized or whether the CBO is going to switch to a loop because its heuristics think your result set is likely tiny to think about things like "is this data being accessed via the right indexes? Is the data likely in memory or not? Will my joins, given my consistency level, impose locks or concurrency considerations on the tables I expect?"
- Guess what I think is going to happen
- EXPLAIN ANALYZE
- Ohhh, it did [thing]. Lemme tweak if I can convince it to do [other thing] that should work better
- <Repeat>
Also, the author points out in the first sentence that they are subject to external constraints that require Python.
As a long time Pythonista, I find the article quite balanced actually.
It's tough to optimize a language where any thread can change the internal variables of any other thread at any time. Python has gratuitous dynamism. Rarely does code muck with the state of another thread, but it can, and the code has to handle the worst case. There's no such thing as a thread-local variable in Python.
Why is this different from Java, where the JVM can assume that local variables cannot be changed by other threads?
That is, in the absence of special cases, which I believe include `volatile` and function calls. (Any other special cases?)
You can easily pass the address of a thread_local variable around. Threads can easily muck around with objects from multiple threads. Hell that's even true with Java too.
The reason threading is weird on Python is due to the GIL. Optimizing for threads is tough because Python explicitly avoids defining a threading model & assumes all implementations have something like the GIL. That doesn't mean no optimization is possible.
1. Python doesn't have thread-local variables 2. Python's memory model around threading is what prevents any optimization.
Both are clearly incorrect. For example, take Java. You have the same behaviour as Python: your VM won't crash & your code won't even generate a panic. Java clearly has thread-local variables & an optimizing compiler.
Python's inhibition around optimizing is partially around the guarantees they make around APIs that do self introspection but mainly around keeping the interpreter simple. For a counterpoint see PyPy, Cython, JPython, IronPython etc which optimize Python just fine. They mostly trip over module extensions being tied directly to the non-standardized CPython module API & that API is tied intimately to implementation decisions of CPython.
- Don't check. Programs will crash if a thread-local variable is passed outside the thread (C, C++)
- Naive interpreter. Everything works, slowly, because the worst case code is used for everything. (CPython)
- Really clever just-in-time recompilation when what seemed to be thread-local suddenly gets accessed from another thread. (PyPy, Java?)
- Compile time checking to prevent this. (Rust)
- No threads (classic Javascript)
- Explicit shared areas into which only certain types can be placed (ECMAscript 2018)
The default python interpreter does absolutely nothing to make it's execution thread-safe, and that appears to be a deliberate decision on their part to keep the complexity of the interpreter down.
For example, a single list can safely be extended (as in `l += [1]`) concurrently from several threads.
The GIL just means that only one of those threads will be executing pure-Python code at any time. But they're still normal threads.
These are distinct from eg Spectre because the point isn't isolation breaking, it's leakage. But at least a few years ago there was always a question of "are side channel attacks real", and I think we're pretty clearly over that question now.
The amount of brainpower that has gone into making JavaScript fast is amazing.
Most noteworthy one is Unladen Swallow from Google:
https://www.python.org/dev/peps/pep-3146/
And Dropbox's now dead Pyston.
While both are pretty dynamic, Python has a rich ecosystem of C-extensions, which exposes a lot of interpreter details to developers, making moving away from the CPython implementation much harder or straight impossible if compatibility is required.
Pyston was better supported, but I think just too ambitious - IIRC it was initially intended to be a full rewrite and to be compatible with C-extensions.
You have a point though, no company can replace javascript , the cost is straightly forbidden. But Python as mainly a backend language at the time, it can be more realistically replaced, with newer more performant alternatives like Golang, and to some extent node.js.
But it has its own stronghold, which is data/ml land stuff. However, that community has gotten around with Python in its own way, either they are tolering the slowness because that happens behind the scene, or they are bypassing the performance bottleneck to c-extensions.
So in the end, I guess people love complaining about Python's performance, including myself, but it never reaches the break point where they said enough is enough.
However, compatibility is certainly not:
Scipy/scikit-learn/pandas/matplotlib/h5py aren't supported, and all the packages depends on them, which makes it not an option for probably the most important segment of python's user base.
Hundred of millions have been poured at chrome, ie and firefox. The best specialists in the world in the field of interpretters and JIT worked on them. For years.
The Python projects were mostly personnal initiatives approved by the companies.
What we want instead is:
- general concurrency
- access to any (garbage collected) JS variable/object from any thread.
- a garbage collector that works across all threads.
- no global locking of threads by the runtime system
I think JS is making the right call here: a small subset just to engage the extra cores.
It really is, and it really makes me sad that the manpower wasn't instead invested in a better underlying language.
If only Eich had been allowed to implement a Scheme for Netscape Navigator! I really dislike Scheme (it's under-specified, and has some poor design decisions like a single namespace), but having a homoiconic language available within every browser in the world would have been amazing. The manager who squashed that is single-handedly responsible for setting back the development of computing by at least twenty years (and more likely thirty, since I predict that it'll be at least another decade before we're able to escape the JavaScript rut).
Not that I disagree with the patch being rejected, only that this is an example of the compiler's philosophy
Philosophy aside, that is a fine reason to reject the patch unless you can convince the reviewer (and the committee) that you are in the right (you very well may be).
And I think that's ok. Python wants to be simple and straightforward and performance was never a goal.
If you need performance don't use Python, or write a python library in C/C++/Rust and do the heavy lifting there.
Also, just want to also say Python reviewers are great. They're very good at explaining issues with patches & are willing to collaborate on improving a patch when necessary. There's a long list of backlog issues because there is simply not enough review to go around, not because of a lack of quality. Highly recommend CPython to people who want to get involved in contributing to an open source project, even just testing patches helps
My assumption of possible speedups (from past experience) is roughly.
Python -5x-> Perl -2x-> C#/F# -5x-> C++ -2x-> Rust
Rust is usually a lot faster than C++, because in my data wrangling I often need a lot of string operations that are much easier to do with zero-allocation in Rust than in C++. While you can write the same in C++ it becomes very hard to manage without the borrow checker.
I don't like Perl, so I basically never use that, and I find it's easier to write something that works in Rust than in C++. So usually I'll pick F# or Rust, depending on how fast it needs to be and how easy it needs to be to write it. F# is super nice for writing and Ionide code completion is just miles ahead of Rust code completion at this point. Being forgetful I barely need to look anything up in F#, but in Rust I always need to look at the docs. This will probably improve in the future (I hope). If Rust code completion becomes amazing I think I won't even start in Python anymore. (Pandas is the only thing that pulls me back into Python usually).
If you start writting a C++ process first, you will take a lot of time.
Python allow you to have a good idea of how the thing works. And if, eventually, you find out that it's not fast enough (even with pypy, numpy, a few lines of cython, etc), you may rewrite it in C++. But the rewrite is going to be much, much faster to do, because you know now what's up, and can just translate it to C++ and focus on its gotchas.
My recent example is processing around 10m chess games to get statistics on all positions that occurred inside them (above an occurrence threshold). This required parsing the games in chess notation, using a chess library to simulate the moves to get positions, and counting how often each position occurred, in which matches, etc. My first try was with Python. After I realized it's unbearably slow, I tried using PyPy, running multiple processes for each core, etc., and in the end my approximation was that the job would finish in a couple of hours. I tried more optimizations and nothing helped. And there's no number crunching to use numpy for. Then I wrote the same script in Rust, and it ran in a couple of minutes, finishing well before the original Python script would have finished, had I left it to run. I arguably didn't save time by using Python here.
Because it was easy in Python.
It was easy to write the same script in Rust, then, because you already got the Python version working.
def foo():
a=1
return a
print(foo.__code__.co_nlocals)
print(foo.__code__.co_varnames)
CPython's compilation pipeline just has a fairly straightforward peephole optimiser: https://github.com/python/cpython/blob/master/Python/peephol...
It's acceptable to have different compilation modes for different levels/fidelities of debugging introspection.
No there's no such thing called Python language specification. Every implementation of Python is based on CPython. This also leads to the sad fact that every non-CPython implementation has to provide C API that's compatible with CPython if they want to be adopted widely.
Not quite true - there are notes in the documentation that call out parts of CPython's behaviour as "implementation-specific".
These are quite rare though. I seem to recall the suggestion being made that MicroPython shouldn't call itself "an implementation of Python" simply because its internal string encoding is UTF-8.
> This also leads to the sad fact that every non-CPython implementation has to provide C API that's compatible with CPython if they want to be adopted widely.
A specification for the C API wouldn't necessarily help with this. The problem for alternative implementations is that the C API is closely tied to CPython internals - there is no reason that having a specification would change that.
Designing and specifying a more abstracted API would be useful - but I don't see it happening.
In a document like this, that means "doing whatever CPython does in a way that we are not bothering to commit to documentation" (and that any other implementation will have to reverse engineer and implement).
I'm pretty sure the same concepts could be applied to CPython.
So, yes, something like this isn't optimized:
def foo(): return [1024][0]
But it's also pretty unlikely to see something like that in actual code. One could argue that that's just an example of a /type/ of a more general case, but I think you'd find that the more general case can't be safely optimized because Python is insanely dynamic. So e.g.
def foo(): return SomeArrayLikeThing(1024)[0]
can't be optimized because not only might the behavior be very different from a typical Python array, the behavior could very easily not be determined until the exact moment when that code is run.
IOW, the things the author points out are things that, in practice, end up being so narrow and rare that there's no real point in trying to optimize them.
Unfortunately it seems to be incomplete - and even if support for exceptions etc were added, I suspect some of Python's more highly dynamic features (e.g. inspection of stack frame objects) would be extremely difficult to support in a compatible way.
I think supporting such niche dynamic features would be essential - I've found the Python community to be strongly against the idea of changing (or removing) such features in the pursuit of increased performance.
Lots of high profile python developers not so against a version of python that was less dynamic and more performant.
Anyone know of someone taking this idea further?
[1] http://code.activestate.com/recipes/277940-decorator-for-bin... - it's old, for Python2.4
But you need to be aware that optimization passes are costly, and with a dynamic language this adds to the overall performance, unlike as with static languages where the optimizer may spend seconds, but run-time is unaffected.
"python -OO -m compileall mydir"
But it's merely skipping comments and names
After all PyPy's selling point is that it does optimise, isn't it?
> To be clear: This isn’t to say CPython is bad, or even that it should necessarily change. In fact, as I’ll show, dumb bytecode compilers are par for the course. In the past I’ve lamented how the Emacs Lisp compiler could do a better job, but CPython and Lua are operating at the same level. There are benefits to a dumb and straightforward bytecode compiler: the compiler itself is simpler, easier to maintain, and more amenable to modification (e.g. as Python continues to evolve). It’s also easier to debug Python (pdb) because it’s such a close match to the source listing.
timeit.timeit(setup='x = range(10000); l = lambda n: n + 1', stmt='map(l, x)', number=1000)
timeit.timeit(setup='x = range(10000)', stmt='[n+1 for n in x]', number=1000)
Although dropping the inlined function runs slower still (1.6s):
timeit.timeit(setup='x = range(10000); l = lambda n: n + 1', stmt='[l(n) for n in x]', number=1000)
On 3.6 the map version runs in 0.00067 seconds, because it doesn't actually do anything, it just constructs a generator object.
The general point is well taken. My favorite bit of trivia like this is the fast matrix transpose: `zip(*matrix)`, which does everything in pure c, and is also likely the shortest way to do the transpose in python.
Yeah. map is usually faster if you already have a function to invoke (especially if that function is a builtin or in C). If you have an expression and have to wrap it in a lambda to get it in map, it's going to be way slower than the listcomp because all things considered CPython's function calls are expensive.