Achieving high Python performance with code generation (2022) | Hacker News Reader

Achieving high Python performance with code generation (2022)

medium.com

131 pointsPaulHoule94 comments

There's one caveat that I don't see explicitly mentioned in the article - CPython's bytecode "API" is not stable, and availability and behaviour of particular opcodes can vary between two different CPython release versions.

In practice it's stable-ish, but I'd be very afraid of putting it in a critical path like this.

Further, contrary to what you might assume CPython is not memory-safe. Most of the memory-unsafety is difficult to accidentally reach from regular Python code, but it's a distinct possibility if you're emitting bytecode directly. For example, LOAD_CONST is not bounds-checked.

> memory-unsafety is difficult to accidentally reach from regular Python code

Can you give an example of Python (source) code that isn't memory safe?

I assumed Python would be similar to Lua in this respect - the interpreter is memory safe no matter what source code you give it, but when it comes to custom bytecode, all bets are off.

My favourite unsafe one-liner:

    eval((lambda:0).__code__.replace(co_consts=()))

This one is slightly cheat-y because it does modify the code object, just not the bytecode itself.

"Purer" unsafety issues are treated as bugs and patched, but that doesn't stop them from existing periodically. I don't have a specific example on-hand but I bet you can find some in here: https://github.com/search?q=repo%3Apython%2Fcpython+segmenta...

Edit: This one is a decent example (and hasn't been fixed for a long time) https://github.com/python/cpython/issues/74957

> "Purer" unsafety issues are treated as bugs and patched, but that doesn't stop them from existing periodically.

Yeah, the same is true for Lua (search for "segfault" here: https://www.lua.org/bugs.html). The difference is that Lua tends to have far fewer bugs overall than Python, mostly because it's so much simpler.

That was intentional. And intentionally quite a lot of safe thing can be broken.

Whoever opened issue #74957 appeared to have encountered it accidentally.

But my initial point was, if you're writing raw bytecode, you're much more likely to hit memory unsafety issues relative to normal Python code.

Anything using codecs, especially CJK. The amount of scary stuff we found when reimplementing it was... Well, scary

Stable-ish probably turns into full unstable due to rapid changes in the faster cpython work. Lots of bytecode changes have been done.

I encountered this when a coworker got random segfaults trying to run some Cython code. Somehow, he was using an old beta version of the interpreter. After stepping through with GDB (I think it was a call to LOAD_CONST) and finding the offending seemingly benign code, on a hunch, I updated the interpreter, and the random segfault disappeared.

Yep.

If you need to process data fast, just write the component in C that runs as a separate process, and send data to it with pipes.

The most typical alternative to this is that you write the hot code in an unsafe language. And your code already has dozens of dependencies on third-party modules in unsafe languages. So it's something to be aware of, sure, but it's not opening up a whole new surface of vulnerabilities.

I get what you mean, but everyone already knows C is a sharp implement. It's less obvious that writing CPython bytecode has similar risks. (You can also write native python extensions in rust etc., but most people aren't doing that, yet)

I'm not saying it's necessarily a reason to write off the approach, but definitely something people should be aware of.

This isn't really a criticism of this article - at first glance it looks well-written and well-informed. The problem I have with articles like this is that it just doesn't fit my own experience of a decade+ worth of application performance work... I worked on lots of projects where something was slow or under-performing, and it was almost never as simple as some loop or generic function. And, if you are performance bound in the way the author states as a hypothesis, my experience is that you have an architecture problem, not just a problem with a single function. Case in point, a few years ago I worked on a project where the original requirements were stated as needing to process maybe 10,000 images a day. In reality, the need was to process something on the order of 10 million images. Two very different needs. So while there are interesting things to be learned from articles like this, they just don't fit my own observations when it comes to what's necessary to boost the real performance of applications in the wild.

You're not wrong, but despite being complicated, this codegen is less than 200 lines of comment heavy code. This might have been a very light lift in comparison to whatever fundamental architectural changes would be necessary to solve the problem at its root.

Didn't your mother teach you not to prematurely optimize? You'll grow hair on your hands.

What's premature? 50% of their runtime was spent in this one function call

If you have scalability problems, getting something to be twice as quick is unlikely to solve it: you are usually looking for at least an order of magnitude, if not two or more orders of magnitude, or ideally an exponential improvement.

But, for some of the basic stuff in Python, you do get that with external C-based modules.

The code he optimized sped up at least 1-2 orders of magnitude

> ...where it sped up a production stack by nearly 2x

This is a quote from the article. 2x is not even in the ballpark of a single order of magnitude (~ 10x), let alone more than that.

Totally understood, but I've just never found anything that was this simple in any real-world production code. That's not a criticism, it's just sharing a perspective. The only time I can think of that came even close to this was about 20 years ago I worked on a project where for nearly every remote call they were also invoking a function that made an expensive auth call. Yes, the "problem" was in a single function, but there wasn't anything explicitly wrong with the function, rather the overall auth pattern.

I agree. The project I work on right now has some major performance issues, and I'd LOVE if it were just a few bad inner loops that we could re-write.

Instead it's more like death by a million cuts with the end result being a performance nightmare.

Honestly I think the "avoid premature optimization" quote has done more harm than good. Too many people think it means "don't think about performance at all until it's a problem," but by then it's too late and actually a lot of problems combined.

You never inherited a project that opened a db, made a single db call, and closed it again in a loop to process an entire table? I'm jealous! Some people get so used to bad architecture that if you fix it they become suspicious. "What? That call normally takes 10 mins. to run and it just completed in 2 seconds? We need to test this, something must be wrong here!"

Rather than go to all this hassle, I think it’s much easier to use Cython, or even to write C and just wrap it with Cython/Ctypes. Performance is so much better.

I agree, you can also use Rust with PyO3[0] and Maturin[1]. It's far easier than what the author is doing is the article.

[0] -- https://github.com/PyO3/pyo3

[1] -- https://github.com/PyO3/maturin

I've done this and it's a really lovely way to work once the rust stuff clicks!

yes, generating Python bytecode seems to be a horrible idea, and 2x improvements are not great coming from Python.

Apart from Cython and other C/C++ bindings one might also want to look at JIT compilers like Numba (or Jax and Pytorch for number crunching).

The improvement was 2x across the entire application, i.e. this hotspot was 50% of the overall runtime, and his bytecode optimization reduced that to an insignificant %. The improvement to the code he actually optimized was probably at least 2 orders of magnitude.

Typical speed difference between Python and native is around two orders of magnitude (of course for code that actually does computation in Python, not just call numpy etc).

It can actually be way more than that for some applications - I found 1000x for some algorithm heavy use cases.

I don’t find Python ergonomic enough to justify the performance penalty.

Ime 2 orders of magnitude is closer to best case, assuming you have already made reasonable Python-based optimizations. But this problem has two components, function call overhead and conditionals. Moving the original logic into a compiled extension would eliminate a lot of interpreter overhead for function calls, but it would not eliminate the branchy code. His codegen eliminated both.

Nah 2 orders of magnitude is very typical when going from Python to a "fast" language like C++ or Rust.

It's pointless to argue what's "typical" when actual results are incredibly varied and specific to each operation. Also you didn't read the rest of my comment.

They're varied. But 2 orders of magnitude is typical. Sometimes it's 1, sometimes 3. Rarely 0 or 4.

I did read the rest of your comment; I was just not responding to that part.

Or use a language with JIT/AOT in the box, REPL support, some of which even have IDEs all the way back to 1990's.

While it's probably less often used, runtime code generation is a potential technique for optimizing performance in Java.

Elsewhere iirc, V8, which is written in C++, can use runtime code generation for regexes.

Or you could start with mypyc [1] first from mypy and if the results do not please you, then you can use Cython; some folks don't want to learn yet another programming syntax, even though it's Pythonic enough to learn it in a rather short period of time, but still...

https://github.com/python/mypy

Cython can speed up plain Python code. It bypasses the interpreter for everything that is PyObject-based.

(https://github.com/mypyc/mypyc) That's cool!

> Mypyc compiles Python modules to C extensions. It uses standard Python type hints to generate fast code. Mypyc uses mypy to perform type checking and type inference.

> Mypyc can compile anything from one module to an entire codebase. The mypy project has been using mypyc to compile mypy since 2019, giving it a 4x performance boost over regular Python.

The problem isn't simply that repeated function calls are expensive, it's that the comparator logic is very branchy in order to support the different comparator options for their queries, even though any given query will only perform the same comparator for every value. The operation being too dynamic would exist regardless.

He jumps straight from the problem to codegen-based solutions, but I wonder if a simpler loop specialization would yield a big enough chunk of the performance he got. If you hoist the comparator handling higher up into a single branch per query, then have a separate loop for each, you avoid unnecessary branching in your hot loop. You'd have to duplicate logic for every comparator, which is a little ugly, but there were only a few comparators, and that seems a lot more palatable if the alternative is an elaborate codegen solution.

I did byte code-based codegen for one of my projects. It was a maintenance headache. The byte codes are NOT stable across Python releases, so you need to be prepared to tweak your generator and even maintain multiple implementations.

My needs were all static, so I gave up and wrote a codegen that generated Python, with markers in the relevant files to indicate where the codegen output should go. That would not work here.

IMX if you're going to all the trouble of generating linear bytecode, might as well leverage ctypes and go all the way to linear machine code.

The linked-to example uses a query-dependent expression which resists easy pre-compilation. The author says the overhead of building a Python expression as a string then byte compiling it is too high, which would also hold for a ctypes/cffi implementation.

In my case I had a lot of config dictionaries like:

  default_output_args = {
    "tsv": {"sep": "tab", "quoting": "always"},
    "csv": {"sep": "comma", "quoting": "always"},
    "json": {"indent": None, "allow_nan": True},
    ...
  }

and a generic API like:

  def open_writer(destination, format="csv", output_args=None):
     ...

which would let 'format' specify the output format, with the corresponding default arguments, and with the output_args able to override the defaults.

I found the generic API too annoying when I knew I wanted a given format, so I added format-specific APIs with kwargs set to the default values, like:

  def open_csv_writer(destination, sep="tab", quoting="always"):
      ...

  def open_json_writer(destination, indent=None, allow_nan=True):
      ...

And I wanted to keep the generic API and format-specific APIs synchronized, because the generic API is useful too.

My original version processed default_output_args to generate the byte code for the different writer functions, setting up the function definitions correctly.

This is not something which can be done with ctypes.

> resists easy pre-compilation

Right, I was (in pre W^X days; compare Windows' BitBlt) compiling machine code onto the stack and executing it.

I still know people doing on-the-fly query compilation. They control the hardware it runs on, so they don't have to worry about that.

So, I haven't done this particular thing, but I have messed with code that writes code in a couple different production cases, and the number one issue is not any of what he mentions. The number one issue is that it is harder to debug, and harder for someone who comes after you to tell what you're doing.

I had a $work-related project where a certain critical path could be optimized further by generating bytecode (the context was slightly different, it was for the JVM not cpython, and there was a DSL that had already existed before I joined the team which provided model structure and feature semantics, and the system was dealing with a lot of backlog at times so it was business-critical to improve performance on the critical path).

You're spot on, the number one issue is that it becomes harder to debug (and there will be bugs no matter how many eyeballs are on the parser and IR and code generator) and harder to communicate. I'm sure the system was dismantled not long after I and a few others left the team. I did my best to document everything as I went, but I probably could have worked faster without that (and it surely would have been dismantled faster, too).

The question comes down to how much you want that performance, and how much tooling you're willing to build around it. You can make some very custom debugging tools if you're already in there generating byte sequences around chunks of semantics. The mature languages have a lot of similar tools, too, though.

In addition to the other alternatives proposed here, I'm confused why it wouldn't be appropriate to use compile wrapped in a cache. Yeah, you don't want to regularly call it inside the serving path, but calling it once per data type per process seems like it should be fine? It basically just increases amortized startup cost by a tiny amount.

Yeah, and you could run a warmup script on deploy so no actual users pay for it. It's not a rare pattern.

Yeah, I came here to say the same thing. Why not just memoize compile()?

It looks like the compared-to values are hard-coded into the generated function, so you would be calling compile once per unique query per process.

Does hardcoding those values into the generated function actually speed things up? I thought the idea was just to have a distinct function per different control-flow path.

Maybe stop using dynamic languages that were designed for the same kind of use cases as bash scripts for performance-sensitive production workloads? If you have to generate your own bytecode, the language is by definition no longer adequate for your needs.

I don't understand why it's necessary to generate bytecode for this. In Python you can write functions that define other Python functions (i.e., using the normal Python def statement) and return them. Why can't the query object constructor just call a Python function that returns the appropriate Python comparison function based on the query object's attributes?

You don’t understand. That’s not complicated enough! No one will be impressed.

Do what pdonis suggests, but inline the resulting bytecode!

I don't fully understand all the performance tradeoffs in this specific case, but in general, closures don't make things faster. It would be necessary to look up the closed-over value in the nonlocal environment on every iteration of the inner loop, which is at least as slow as the original solution with inline conditionals.

> in general, closures don't make things faster.

Compared to what?

Compared to doing the logic that picks which specific comparison function to call in every iteration of the inner loop? Closures will certainly make things faster compared to that, for the same reason that the method described in the article does.

Compared to generating bytecode by hand? Closures might not make things any faster, but they won't make them any slower either. Generating bytecode by hand is just doing by hand what the Python interpreter does internally when you define a closure using normal Python code. The def statement means the interpreter generates bytecode from the contents of the def block, wraps it in a code object, and attaches that code object to the function that gets returned.

In other words, what the article is doing is generating a closure--just doing it in a way that's much less common than just writing a Python function that returns a function.

> It would be necessary to look up the closed-over value in the nonlocal environment

No, it wouldn't. A Python closure includes cells that store the values of the closed over variables, so as far as the closure function is concerned, they're local variables.

Did someone try to implement a processor that runs Python VM bytecode natively, as it was attempted for Java[1]? I wonder how fast Python would run by replacing a virtual machine with a physical Python machine.

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

A decade ago, https://pycpu.wordpress.com/ was a prototype that turned a small subset of Python bytecode, as well as the specifications for a system to run it, into VHDL/Verilog (via myhdl.org) to run on an FPGA. In theory, I imagine it would be possible to take this approach and transpile something like https://doc.pypy.org/en/latest/interpreter.html to an HDL.

But a more reasonable thing to do would be to look down the road that JIT's and other similar technologies are coming to mainline CPython, see e.g. https://tonybaloney.github.io/posts/python-gets-a-jit.html - and thus it might make sense to have some of the unique semantics of Python opcodes be adopted by specifications like ARM, similar to how ARM created the FJCVTZS opcode to exactly match Javascript's ToInt32 specification:

https://stackoverflow.com/questions/50966676/why-do-arm-chip... -> https://tc39.es/ecma262/#sec-toint32

The problem is that the bytecodes aren't where the work is done, so speeding up the bytecode portion of the VM would get you negligible speedups. The interpreter is a glorified dynamic dispatch mechanism to code that then has to figure out the type of the arguments and then call the relevant routine. Unless the bytecode VM is doing type tracing, the speedup from just a hardware inner loop will get you probably single digit percentage speedup.

But I could see a hardware VM that was a combination of a regular CPU and some of the hot code paths in interpreter as well as operations on primitives of arrays being sped up. The Java processors had the advantage of static types.

> Because this storage system’s query language is more powerful than the underlying one’s, its read operations in general may overfetch and then filter results.

Seems like this is the crux of the problem. Migrating and/or replicating data to an underlying data layer that supports the required query logic probably makes more sense?

Compared to maintaining 200 lines of code?

I'd at least be waiting for the next feature request of "can we just add one more operation to match()" before saying we needed to move our whole storage layer to something else.

Wow that seems massively overcomplicated. Why not just do this comparison in the database layer (what he's calling the X layer, I think, although maybe it's the W layer)?

New Title - Advanced Python: Just Program in C

Advanced Python - Rediscovering Common Lisp.

Ad-hoc, informally specified and bug-ridden (Greenspun's tenth rule applies very much to Python).

I'm not criticizing the article, which humorously draws Dr.Strangelove analogies to these techniques. What I don't understand is that this sort thing has been popular for over 20 years in the Python space.

At least some are doing numeric research right.

"Common Lisp using LLVM and C++ for Molecular Metaprogramming"

https://sungsoo.github.io/2015/06/17/clap.html

A while back I concluded that you could code up most of the examples from

https://www.amazon.com/Paradigms-Artificial-Intelligence-Pro...

in Python without doing anything too out of the ordinary. I just finished

https://www.amazon.com/Lisp-Advanced-Techniques-Common/dp/01...

and came to almost the same conclusion in that most of the macro use in that book is in the syntactic sugar or performance optimization category. If I didn't have a lot of projects in the queue and people demanding my time I'd try coding up the ATN and Prolog examples in Python (sorta kinda did the "CLOS" example in that I built a strange kind of meta-object facility that made "objects" backed by RDF triples)

In Java I did enough hacking on this project

https://github.com/paulhoule/ferocity/blob/main/ferocity0/sr...

to conclude I could create something that people who think "Java Sux" and "Common Lisp Sux" would really hate. If I went forward on that it would be to try "code golf not counting POM file size" by dividing ferocity into layers (like that ferocity0 which is enough to write a code generator that can stub the whole stdlib) so I could use metaprogramming to fight back against the bulkification you get from writing Java as typed S-expressions. (I'm pretty sure type erasure can be dealt with if you aren't interested in JDK 10+ features like var and switch expressions, on the other hand a system like that doesn't have to be able to code generate syntactic sugar sorts of structures because ferocity is all about being able to write syntatic sugar)

With the difference that Python code runs slow as molasses.

I've had very good luck with PyPy speeding up branchy "old AI" code.

Some days I wonder if the popularity of Lisp around MIT was really an attempt to stick Noam Chomsky for biting the hand that feeds them.

The black Swan of Python ecosystem.

Interesting comment, what does Noam Chomsky have to do with Lisp?

Almost every other programming language uses parsing technology related to Chomsky’s generative grammars, Lisp is the conspicuous exception.

Don't forget that Chomksy probably spent a vast amount of time inserting labeled brackets into lists of words to show their syntax!

And it wasn't his choice or fault that they are aren't there.

You can go to several dozen of languages from Python to get better and far more easier performance without having to go to C. C can have performance, but you have to pay with it.

* pay for it

As I look at the comments on this blog post 4 hours after submission, the number of HN readers dismissing it out of hand is really disappointing:

Rather than go to all this hassle...

Just Program in C

Folks, take your dismissiveness elsewhere. It's not the HN spirit. The post is meant to be pedagogical, to teach the concept of codegen if you aren't already familiar with it. It already includes disclaimers about how this technique may be used on any language with a VM, not just Python. It explains why it was the right choice at the employer where the author used it.

So your dismissive comments add nothing.

To anyone who hasn't read the article yet: it's worth reading if you're not already familiar with code gen and want to learn a new tool to add to your programming toolbox. Take note of the caveats the author duly mentions.

An important part of programming is using the right tool for the job. It may make sense to use a hammer instead of pummeling a nail with a screwdriver. Anecdotally, many screwdriver experts don't have other tools in their in their box, and don't consider adding them. Repurposing a tool in a pinch is a useful skill, but it's a temporary solution.

I think the idea that every language is just as useful for task X is just as stupid. Sometimes you're just doing it wrong.

It is a general problem in the Python ecosystem and places that use Python that Python is viewed as the only possible language to solve every problem. While saying just use C is very much unhelpful and not even recommended by most, there are several languages that are just as easy if not much more easy to use as Python and come with many multipliers of performance that you don't even have to try for.

The thing is, I'm genuinely struggling to understand under what circumstances this could be the best solution. The author explains why it's better for his use case than just using inline conditionals (because of performance, though I really wish he'd included benchmarks), but although he asserts that it's also better than using C or C++ or Rust, he doesn't really explain why. Perhaps more importantly, the solution space isn't limited to "do the slow thing", "use C/C++/Rust", and "bytecode generation"; many other alternatives were brought up in this comment thread, some of which seem to provide most or all advantages of bytecode generation while being more maintainable. If the author was aware of these alternatives and rejected them for specific reasons, that would be very interesting to know, but again, the article gives no indication of this.

What I'd like is to understand some set of circumstances such that, if somebody linked me this article and asked me "should I consider doing this in my code?", I could in good conscience say yes.

I think the dismissiveness is because he is genuinely proposing this as a useful solution, even if only for limited circumstances. Whereas in reality there's no way you should do this ever.

If he had presented it as a fun challenge or something and said "but actually just write performance sensitive code in a fast language" then I don't think you'd see these comments.

That’s weird, this article about performance didn’t begin with the design of the experiment and benchmark. In fact, unless I missed something, it was completely omitted. It must not be an article about performance at all, then.

You're being unnecessarily dismissive, but you've got a point. I do think it would have been good to include actual numbers.

In my opinion discussions on performance theory are so subtle and can be so misleading that you really need to model and demonstrate e.g. reduced instruction count, memory reads, or other metrics in order to prove out your claims. Otherwise it’s nearly useless. The Go blog post about performance tuning versus C++ is a great model to follow.

The claim in this article is not 2x, it’s “50% of CPU was consumed by this loop, now it’s ~0%”

I’d love to see a series of improvements and how they impact the machine behavior / speedup....

Just use pypy

I’ve just started using pypy and it is night and day better. It’s truly incredible.

What is your use case? I struggle to see how ~4x faster Python has much value but I guess the effective speedup/value of that speedup depends on what you are doing.

EDIT: By that I meant, if you are trying to make something fast, wouldn't it make more sense to rewrite the critical path in a faster language rather than trying to improve Python's speed?

OP is about a Python app that had a costly inner loop. This could perhaps be improved by switching to a JIT compiled implementation of Python like Pypy, but there are drawbacks and potential dealbreakers too.

Some things aren’t feasible to use another language for, but I see your point.

My use case is MILP optimization. Constructing the model representation(the step necessary before calling some optimizer binary) is very slow in CPython, and Pypy makes development much less painful, since you often need to construct many models to get it right.

Thanks, this is really interesting. How big of a speed up have you been observing?

as other commenter and i had mentions Some cases 100x increase , On many Cases 20x , on Bad cases 4x , on worst cases around 10% slower than python ( In case of some C Extensions ) . On unusable cases some libraries ( those with rust bindings and non-public CPyExt API) PyPy fails to work.

IME, PyPy can get up to 100x faster for many use cases. Most of my Python scripts have a lot of pure-Python code manipulating ints, strs, dicts, etc. (wrangling data between formats and/or doing basic processing), and switching from CPython to PyPy often turns the execution time from minutes into seconds.

You'll likely get much less of a speedup if your program is already optimized around CPython's slowness, e.g., by calling out to libraries like numpy as much as possible. But PyPy lets my simple scripts punch above their weight without any extra circumlocutions.

Most of the case 20x faster not just 4x. 4x faster is mostly bad cases. Worst cases ( a bit slower than python) c-extension for these needing cext, use python.

Why rewrite when you can achieve same without any code changes? PyPy performance rivals golang .

In OP Case this could increase performance by 20x easily.

Reply on news.ycombinator.com