15 ms·
The CPython Bytecode Compiler Is Dumb
- obl 8y agoThere is a reason why basically every attempt to make this kind of language fast has to support some form of on-stack replacement. 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.
- sametmax 8y agoYou could support markers stating "I swear this part is never going to use those dynamic features", disabling them for you and others. 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.
- pishpash 8y agoHow can you know the builtins and the libraries you call don't use these features, to make such guarantees? I suspect it's rather more common than it appears.
- sametmax 8y agoYou can't at first, but you don't need to. You just write normal code, with regular unit tests. Once you are satisfy, you can start playing with optimization and see if things break or get faster. 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.
- coredog64 8y agoOne of the event workers for Django monkey patches ‘socket’. A colleague and I discovered that an hour into debugging why something was misbehaving when we switched workers.
- jerf 8y ago"You could support markers stating "I swear this part is never going to use those dynamic features", disabling them for you and others." 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.)
- Sukera 8y ago> You can see some of the ideas in Julia or LuaJIT, but you pay a penalty on what can be dynamic. 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?
- chrisseaton 8y ago> You could support markers stating "I swear this part is never going to use those dynamic features" 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.
- pjmlp 8y agoYet Smalltalk, Common Lisp, Dylan managed to do it. Do you want to break all assumptions a Smalltalk JIT managed to reach about a live object? Just send it a become: message.
- masklinn 8y agoYeah the dynamicism part is probably not a good argument there (JITs were built for Self, after all). 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.
- mschaef 8y ago> 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, 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.
- beagle3 8y agoIt hasn’t been updated in 5 years, and IIRC Python2 only - but Russell Power’s “Falcon” was an attempt to solve these issues that showed a lot of promise. https://github.com/rjpower/falcon https://github.com/rjpower/falcon
- bakery2k 8y agoThanks for this - I hadn't seen it before. Looks like an implementation of the core Python interpreter designed to work more like the reference interpreter for Lua. 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.
- jsmeaton 8y agoHave you seen this twitter thread? https://twitter.com/mitsuhiko/status/1091802711908106240?s=21 https://twitter.com/mitsuhiko/status/1091802711908106240?s=2... Lots of high profile python developers not so against a version of python that was less dynamic and more performant.
- pizlonator 8y agoFast bytecode-based implementations of dynamic languages, like JavaScriptCore, do optimizations after the bytecode is generated. The bytecode is just the common frame of reference for profiling and OSR.
- bakery2k 8y agoLuaJIT is the same, as is V8 (at least with Ignition & TurboFan). The article's assumption that fewer instructions = faster does not necessarily apply to these implementations, but is approximately correct for CPython (because it's a simple bytecode interpreter).
- chrisseaton 8y agoThe author hints at the problem > 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.
- nickysielicki 8y ago+1. I'm reminded of a tweet of yours from a few years back! https://twitter.com/chrisgseaton/status/619885182104043520 https://twitter.com/chrisgseaton/status/619885182104043520 Try doing something like that at compile time.
- TeMPOraL 8y agoCommon Lisp does that for breakfast :).
- bjoli 8y ago... I am not sure I am impressed. The rules for partially evaluating eval are the same for partially evaluating any code. I am just not sure anybody else bothered something like that with eval. 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
- chrisseaton 8y ago> I am not sure I am impressed 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.
- ChrisSD 8y agoI think CPython is quite clear about not optimising python code, no? I think both the docs and python programmers quickly disabused me of that notion (although this was some years ago so I guess things could have changed). After all PyPy's selling point is that it does optimise, isn't it?
- kbumsik 8y agoOf course he does not intend to criticize it, but to show what the dumb compiler is. > 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.
- hermitdev 8y agoRight, the CPython runtime is first trying to be correct (IMHO is also correct). Very few optimizations are made by the compiler/interpreter. This has long been known by Python devs, and exploited by specifically using APIs known to be written in C/C++. e.g. using 'map' instead of a list comprehension. Map was generally faster (at least in the 2.x days) than an equivalent list comprehension.
- joshuamorton 8y agoJust FYI this specific wisdom you're suggesting is exactly backwards, or at least could be depending how how you read it. timeit.timeit(setup='x = range(10000); l = lambda n: n + 1', stmt='map(l, x)', number=1000) provides approximately 1.2 seconds to do that. The same with a listcomp: timeit.timeit(setup='x = range(10000)', stmt='[n+1 for n in x]', number=1000) runs in a half second. 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) The second is the fastest because you drop the overhead of the function call, which does stack pushes and pops, and instead do them locally. The last is the slowest because it does the stack pushes and pops, as well as loads extra globals, which is slow. 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.
- aboutruby 8y agoSome people are working on optimizing ruby "bytecode" (what the VM interprets): https://developers.redhat.com/blog/2019/02/19/register-transfer-language-for-cruby https://developers.redhat.com/blog/2019/02/19/register-trans... I'm pretty sure the same concepts could be applied to CPython.
- tambourine_man 8y agoJavaScript is really lucky. Imagine having you pet language’s execution being continuously optimized for decades by the likes of Apple, Google, Microsoft and Mozilla. The amount of brainpower that has gone into making JavaScript fast is amazing.
- hsaliak 8y agoThe best part is that they cannot afford to stop doing that.
- tambourine_man 8y agoYeah, but I think we are in the diminishing returns phase, already. I hope I'm wrong, though.
- tanilama 8y agoWell, there are multiple attempts in Python's history to make it faster, yet failed. Most noteworthy one is Unladen Swallow from Google: https://www.python.org/dev/peps/pep-3146/ 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.
- bakery2k 8y agoUnladen Swallow had a small fraction of the resources that Google allocated to V8, though. I think it was only worked on by a few interns. 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.
- tanilama 8y agoPyston as far as I was tracking, it seems to be mainly 2 devs from Dropbox, hardly that better off. 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.
- yegle 8y ago> Unless the Python language specification is specific about this case 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.
- bakery2k 8y ago> Every implementation of Python is based on CPython. 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.
- kazinator 8y ago> there are notes in the documentation that call out parts of CPython's behaviour as "implementation-specific" 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).
- gjenks 8y agoClosest thing to a spec is the Python Language Reference: https://docs.python.org/3/reference/ https://docs.python.org/3/reference/ which is actually pretty good.
- abecedarius 8y agoGuido himself said "Python is about having the simplest, dumbest compiler imaginable." Even a subset of this dumbest thing turned out to be a lot to cover when I dug into it at https://codewords.recurse.com/issues/seven/dragon-taming-with-tailbiter-a-bytecode-compiler https://codewords.recurse.com/issues/seven/dragon-taming-wit...
- saagarjha 8y agoEven the Java compiler is pretty stupid: it’s HotSpot doing amazing things under the hood that makes it fast.
- kccqzy 8y agoThe local variable elimination optimization breaks introspection features. def foo(): a=1 return a Then we can inspect the local variables: print(foo.__code__.co_nlocals) print(foo.__code__.co_varnames) On a related note, I believe it was also a deliberate decision to keep the name of all local variables during compilation. This is of course very different from C.
- greglindahl 8y agoActually, C compilers with -O0 keep all of the local variables, for debugging purposes. O0 is deliberately bad. And if you file bugs complaining about debugging at higher optimization levels, well, if you want loop fusion and splitting for high performance, you're going to lose some debugging.
- aasasd 8y agoI wonder if Python could similarly have opt-in optimization (‘-Osomething’) for those who are sure it won't break anything. Though I guess the standard lib might get in the way immediately.
- masklinn 8y agoCPython already has -O and -OO, they just don't do much that's useful (and are mostly detrimental): -O will skip asserts and set __debug__ to False, -OO will also remove docstrings. CPython's compilation pipeline just has a fairly straightforward peephole optimiser: https://github.com/python/cpython/blob/master/Python/peephole.c https://github.com/python/cpython/blob/master/Python/peephol...
- greglindahl 8y agoYou're describing opt-in pessmisation, not opt-in optimization.
- kccqzy 8y agoNo that's qualitatively different. There's no way for a piece of C code to look at the local variables of another C function. But in Python you can do that. What you mean is that C compilers keep the local variables on the stack, and do not eliminate loads/stores so that a debugger can see what the variables are and a debugger can read DWARF information to figure out names of variables. There is no way for code itself to learn these except for implementing DWARF parsing yourself.
- dbrueck 8y agoSeems like part of the problem is that there might not be much overlap between the types of things he points out that aren't optimized - which are obscure and useless - and what could "legally" be optimized. 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.
- Animats 8y agoWell, yes. It's a naive interpreter. The source is translated to the obvious bytecode. At run time, everything is a CObject, including integers and floats. Everything which you'd expect to be a dict really is a dict. So you spend a lot of run time checking the types of objects, dispatching, and looking up variables. There's a bit of memoization, I think, to cut down some of the lookups. 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.
- deleted 8y ago[deleted]
- bakery2k 8y ago> any thread can change the internal variables of any other thread at any time 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?)
- deleted 8y ago[deleted]
- mkl 8y agoAm I missing something, or does your first question answer itself? The question asserts a specific difference. (I don't remember how it works in Java to know if the assertion is correct.)
- bakery2k 8y agoAs I understand it, the JVM can assume that local variables are not modified by other threads. My question is why can't CPython make the same assumption?
- __s 8y agoIndeed, a patch I created in 2010 for the peepholer to optimize 'a,b=b,a' was rejected with one particular reason being "changing order of execution starts to venture into territory that we've stayed away from (on purpose)." https://bugs.python.org/issue10648 https://bugs.python.org/issue10648 Not that I disagree with the patch being rejected, only that this is an example of the compiler's philosophy
- isatty2 8y agoI know you don't disagree with the patch being rejected, but I have to say that the reviewer gave you a firm example in which your patch changes expected behavior. 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).
- carlmr 8y agoBeing in the right is very much a matter of taste. Python has always erred on the side o less optimization and more obvious behavior. So something that optimizes for performance while introducing subtle possibilities for bugs would likely be accepted by the C++, but not the Python commitee. 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.
- __s 8y agoYes, I agree that the patch was wrong in that it shouldn't optimize NAME/GLOBAL. I was unaware of those semantics when I wrote it. However that doesn't apply to FAST, the most common LOAD/STORE ops. The other reasons are why the patch wouldn't be accepted if it were fixed 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
- alsadi 8y agoSome optimizations can be enabled "python -OO -m compileall mydir" But it's merely skipping comments and names
- thegeomaster 8y agoPython's slowness has been a very real problem for me. It's a great language to write data-wrangling scripts in, but when there's a little bit more data, it's terribly slow. And then you have to rewrite your script in a faster language, like C++ or Rust. I've observed speedups on the order of 20x this way. Which means that I could've saved myself a lot of time by writing them in another language at the start.
- carlmr 8y ago>And then you have to rewrite your script in a faster language, like C++ or Rust. I've observed speedups on the order of 20x this way. 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).
- nerpderp82 8y agoAn F# like language hosted within Rust would be a dream. With a GC and stack allocation, optional lifetime annotations when you want to remove the GC overhead.
- carlmr 8y agoI think with the newer versions of F# you can do some manual memory management if needed.
- 8y ago
- andrewf 8y agoThis [1] is a bytecode optimizer for Python - it takes the bytecode from CPython's compiler, and outputs bytecode with a few select optimizations. Anyone know of someone taking this idea further? [1] http://code.activestate.com/recipes/277940-decorator-for-bindingconstants-at-compile-time/ http://code.activestate.com/recipes/277940-decorator-for-bin... - it's old, for Python2.4
- joejev 8y agoI work on a library for doing Python bytecode transformations like this, but with a more abstract API. Here is a similar transformation with this library, which works with Python 3: https://github.com/llllllllll/codetransformer/blob/master/codetransformer/transformers/constants.py https://github.com/llllllllll/codetransformer/blob/master/co...
- rurban 8y agoThat's why php7 is now 2x faster. Just by simple escape analysis, optimizing to stack-allocation and omitting unnecessary refcounting. 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.
- jnwatson 8y agoThe optimization is a one time cost at load time that Python already caches anyway.
- rawmodz 8y ago"...in this case for my wife’s photo blog". Stunning bird photographs, really exceptional. And nice work on that responsive static album generator. Now time to continue reading about CPython byte code...
- fijal 8y agoIf you want to see an advanced Python compiler, have a look at PyPy. While CPython bytecode compiler is "dump", it's as smart as it can be. You can do crazy stuff with speculative replacing of bytecodes with guards and type-specific bytecodes, but then you might as well create a full just in time compiler. It's incredibly hard to create optimizations on bytecode level without changing semantics, which Python rightly stayed away from.
- sevensor 8y agoAs the article points out, CPython is dumb on purpose, which benefits transparency, maintainability, and development. I've always appreciated this -- it's obvious when you're doing something expensive in Python because you know the interpreter is going to do pretty much what you'd expect it to.