6 ms·

I once was interested what exactly happens when executing python code, asking myself questions like "Why can't I make a fast for loop? Where are the fast intege

by xaedes 6y ago

I once was interested what exactly happens when executing python code, asking myself questions like "Why can't I make a fast for loop? Where are the fast integers? Can't I write fast for loop directly in bytecode, akin to asm?" The python bytecode interpreter mainloop can be found in ceval.c. There is a big switch case for each python bytecode opcode starting at https://github.com/python/cpython/blob/master/Python/ceval.c#L1480 https://github.com/python/cpython/blob/master/Python/ceval.c... One can see even the simplest operations call quite a lot of stuff. I gave up on fast pure cpython after reading ceval.c...

sigwinch28 6y ago
I recall from my days hacking away on the BEAM (the de facto Erlang VM) that it loads code as directly threaded to improve performance. The BEAM loads whole modules at a time, and as part of this process it means that instruction names in the bytecode are essentially replaced with the address of the code which interpret that instruction. This means that once loading is complete there's no big switch statement to visit: the VM jumps directly to the part of its own code which interprets that instruction.
- sigwinch28 6y ago
  Oh wow, my brain was cooked when I wrote that. The BEAM loads bytecode into memory and then goes through the loaded code to directly thread it. It's not an inherent consequence of code loading in general. https://en.wikipedia.org/wiki/Threaded_code#Direct_threading https://en.wikipedia.org/wiki/Threaded_code#Direct_threading
devxpy 6y ago
You should look at numba. In some special cases, you can actually write for loops in pure python that are faster than C loops.
- JesseMeyer 6y ago
  Are you referring to Numba's ability to offload certain loops into a GPU kernel? Otherwise, Clang has access to the same optimizations that Numba has as they both share LLVM as their optimizing compiler. Beyond that, I think a fairer comparison is C w/ OpenMP vs Numba for parallel processing if syntactic brevity is the metric.
basic_bgnr 6y ago
Can you point me toward something that's alternative to switch statement for jumping opcodes. How can we speed things up?
- status_quo69 6y ago
  Do you mean a switch statement in pure-python that avoids certain opcodes, or a way to avoid executing opcodes in the main interpreter switch statement?
- deleted 6y ago
  [deleted]
- deleted 6y ago
  [deleted]
- bjoli 6y ago
  The other comment mentions computed Goto's. I have used those with big success when writing streaming parsers that work per-char (like a typical JSON or csv-parser). I can't remember exactly, but I think switching from a switch statement to computed gotos cut something like 10% from execution time due to better branch predictions in the CPU. That is pretty huge, considering it was a pretty small change to the char dispatch.
ir123 6y ago
Noob question probably, but wouldn't an Enum Map or something similar be more efficient?
- hn_acc_2 6y ago
  It depends on your compiler. But as a general rule, the programmer will have a hard time "outsmarting" the compiler by using different objects or abstractions. Compiler authors have spent many hundreds of combined hours making C code run as fast as possible, and optimizing the switch statement is something they've most certainly done to death. I.e. if your control flow is switch-case-like, use a switch-case.
  - Jasper_ 6y ago
    Not always. Computed gotos can be faster, because it can relax some restrictions that the switch statement can't amke. Most VM implementations, including CPython, use computed gotos for a not insignificant performance improvement. https://github.com/python/cpython/blob/master/Python/ceval.c#L967-L1004 https://github.com/python/cpython/blob/master/Python/ceval.c...
- anon946 6y ago
  For more than a few cases in the switch: If the case values are dense (such as just the integers from 0 to 9), the compiler will turn it into a jump table. https://godbolt.org/z/1Khahr https://godbolt.org/z/1Khahr If too sparse for jump table, then typically will be turned into a binary search tree.
kstrauser 6y ago
Officially, as in I can't point you to this in writing off the top of my head but I've heard Guido say it numerous times, part of the design goal of CPython is to be as understandable and approachable as possible. That code you linked doesn't include stuff like compiling opcodes directly to assembly and then executing them natively, but it is very straightforward. I mean, I'm not a C guru by any stretch but I can look at that and tell immediately how I could go about adding my own opcodes to the VM.
- throwaway894345 6y ago
  Perhaps, but it's unfortunate that so many of Python's design objectives are (in practice if not in theory) so limiting with respect to performance, tooling, package management, maintainability, and other important dimensions of professional software development. Of course, it doesn't mean there aren't companies who can't be successful in spite of these limitations--if you make enough money you can afford to throw money at these problems and make them better (you don't need efficient compute or parallelism if you can afford to pay a team to set up and operate a Spark cluster for you not to mention the cost of the additional VMs and the additional effort to write spark instead of a native language).
  - hn_acc_2 6y ago
    Not sure about the first part...How is Python's approachable design "so limiting" to all those dimensions? Nobody writes performance-critical code in pure python. Not sure how "tooling" is bad, what would you say is limited there? Package management, again, what package management problems are unique to Python? Many people say this but it seems the problems they bring up are not unique to pip or the python ecosystem, same problems are found with rubygems, npm, Maven, etc... Maintainability is a responsibility of developers and not a programming language, and unmaintainable code can easily be written with any language. However I'd argue Python should score positive points for maintainability; one of the languages I feel most comfortable picking up old code from someone else and groking it easily.
    - throwaway894345 6y ago

by xaedes 6y ago

sigwinch28 6y ago

I recall from my days hacking away on the BEAM (the de facto Erlang VM) that it loads code as directly threaded to improve performance. The BEAM loads whole modules at a time, and as part of this process it means that instruction names in the bytecode are essentially replaced with the address of the code which interpret that instruction. This means that once loading is complete there's no big switch statement to visit: the VM jumps directly to the part of its own code which interprets that instruction.

sigwinch28 6y ago
Oh wow, my brain was cooked when I wrote that. The BEAM loads bytecode into memory and then goes through the loaded code to directly thread it. It's not an inherent consequence of code loading in general. https://en.wikipedia.org/wiki/Threaded_code#Direct_threading https://en.wikipedia.org/wiki/Threaded_code#Direct_threading

devxpy 6y ago

You should look at numba. In some special cases, you can actually write for loops in pure python that are faster than C loops.

JesseMeyer 6y ago
Are you referring to Numba's ability to offload certain loops into a GPU kernel? Otherwise, Clang has access to the same optimizations that Numba has as they both share LLVM as their optimizing compiler. Beyond that, I think a fairer comparison is C w/ OpenMP vs Numba for parallel processing if syntactic brevity is the metric.

basic_bgnr 6y ago

Can you point me toward something that's alternative to switch statement for jumping opcodes. How can we speed things up?

status_quo69 6y ago
Do you mean a switch statement in pure-python that avoids certain opcodes, or a way to avoid executing opcodes in the main interpreter switch statement?
deleted 6y ago
[deleted]
deleted 6y ago
[deleted]
bjoli 6y ago
The other comment mentions computed Goto's. I have used those with big success when writing streaming parsers that work per-char (like a typical JSON or csv-parser). I can't remember exactly, but I think switching from a switch statement to computed gotos cut something like 10% from execution time due to better branch predictions in the CPU. That is pretty huge, considering it was a pretty small change to the char dispatch.

ir123 6y ago

Noob question probably, but wouldn't an Enum Map or something similar be more efficient?

hn_acc_2 6y ago
It depends on your compiler. But as a general rule, the programmer will have a hard time "outsmarting" the compiler by using different objects or abstractions. Compiler authors have spent many hundreds of combined hours making C code run as fast as possible, and optimizing the switch statement is something they've most certainly done to death. I.e. if your control flow is switch-case-like, use a switch-case.
- Jasper_ 6y ago
  Not always. Computed gotos can be faster, because it can relax some restrictions that the switch statement can't amke. Most VM implementations, including CPython, use computed gotos for a not insignificant performance improvement. https://github.com/python/cpython/blob/master/Python/ceval.c#L967-L1004 https://github.com/python/cpython/blob/master/Python/ceval.c...
anon946 6y ago
For more than a few cases in the switch: If the case values are dense (such as just the integers from 0 to 9), the compiler will turn it into a jump table. https://godbolt.org/z/1Khahr https://godbolt.org/z/1Khahr If too sparse for jump table, then typically will be turned into a binary search tree.

kstrauser 6y ago

Officially, as in I can't point you to this in writing off the top of my head but I've heard Guido say it numerous times, part of the design goal of CPython is to be as understandable and approachable as possible. That code you linked doesn't include stuff like compiling opcodes directly to assembly and then executing them natively, but it is very straightforward. I mean, I'm not a C guru by any stretch but I can look at that and tell immediately how I could go about adding my own opcodes to the VM.

throwaway894345 6y ago
Perhaps, but it's unfortunate that so many of Python's design objectives are (in practice if not in theory) so limiting with respect to performance, tooling, package management, maintainability, and other important dimensions of professional software development. Of course, it doesn't mean there aren't companies who can't be successful in spite of these limitations--if you make enough money you can afford to throw money at these problems and make them better (you don't need efficient compute or parallelism if you can afford to pay a team to set up and operate a Spark cluster for you not to mention the cost of the additional VMs and the additional effort to write spark instead of a native language).
- hn_acc_2 6y ago
  Not sure about the first part...How is Python's approachable design "so limiting" to all those dimensions? Nobody writes performance-critical code in pure python. Not sure how "tooling" is bad, what would you say is limited there? Package management, again, what package management problems are unique to Python? Many people say this but it seems the problems they bring up are not unique to pip or the python ecosystem, same problems are found with rubygems, npm, Maven, etc... Maintainability is a responsibility of developers and not a programming language, and unmaintainable code can easily be written with any language. However I'd argue Python should score positive points for maintainability; one of the languages I feel most comfortable picking up old code from someone else and groking it easily.
  - throwaway894345 6y ago