3 ms·

Cython offers the type of targeted compilation options you suggest. Also numba offers them in a more opinionated way that requires less overhead than Cython. T

by mlthoughts2018 6y ago

Cython offers the type of targeted compilation options you suggest. Also numba offers them in a more opinionated way that requires less overhead than Cython. These are both long standard tools in scientific Python.

mjburgess 6y ago
My hope is that there's some easy, non-trivial, improvements in just basic type awareness, eg., xs: List[Int] = list(range(10)) total : Int = 0 should permit an optimised, for x in xs: total += 1 (almost?) as fast as the equivalent sum. Python hasn't had typing for long enough for this thought to have percolated deeply, ie., I believe at the moment it is just unconsidered rather than infeasible. I suspect that there's a few cases that can be hard coded into the VM that will make a big difference. eg., namedtuple/dataclass, List[String], Dict[String, String], etc.,
- mlthoughts2018 6y ago
  Unfortunately what you suggest just isn’t conceptually possible (by design) in Python, and would require removing many of the language features that make Python successful for a wide set of use cases. Type hinting (eg List[Int]) has no control over the actual byte layout, it’s just purely metadata. Nothing stops someone from changing xs[4] to be some complex object in your example, regardless of the type hint, so at a pure CPython level it’s fundamentally impossible to benefit from static typing & optimization purely on the basis of type hinting. This is why Cython and numba play that role. They change the location of type metadata - it’s not mere runtime metadata, rather it is compile-time static type annotation in the real sense, for either ahead of time compilation (Cython) or just in time compilation (numba).
  - mjburgess 6y ago
    I'm not convinced. The compiler can emit different byte-code. The proposal includes adding a compiler-aware phase to processing type "hints" (here now, actual static types). If you type code "xs: List[Int]" and try to change xs[4], the compiler (phase) would have to reject your code. This isn't "removing features" as typing is optional. And as long as a lists in "successfully compiled python program" express the same API, it doesnt matter that their implementations differ.
    - mlthoughts2018 6y ago
      > “ If you type code "xs: List[Int]" and try to change xs[4], the compiler (phase) would have to reject your code.” This just can’t work - because lists are mutable, so code that mutates them must be valid and permitted by any such compiler. Similarly, values are dynamically typed, so the value of the assignment might be an int or might not, and it cannot be decided until runtime (and this inability to prove at compile time can’t cause the program to fail to compile, it’s Python). Additionally, Python only has infinite precision ints, so it would be quite hard to get anything useful out of this, unless you wholesale switch to using ctypes or something, but then just use Cython and it will be way easier. I’m not convinced this could ever be anything more than a super limited toy.
- hansvm 6y ago
  That snippet as a whole could be optimized. Individual components would be trickier though. To be clear, you aren't suggesting something as seemingly straightforward as shoving lists of integers into contiguous memory, right? With native big integers, integer subclasses, and whatnot I'd imagine that'd get thorny in a hurry.
  - mjburgess 6y ago
    cutting down on the pointer indirection would be a start total is known Int, so there is no need to run-time look up `+=` (which python does). xs is known List[Int] so there is no need to use an iterator protocol to obtain sequential elements (ie., it can be known to be sequential in memory). The problem is that if python were statically typed in a way which matched its semantics, everything would be profoundly polymorphic. Almost nothing is monomorphized. Lot's and lot's of trivial optimisations are available if the core team is happy to add time to the compiler phase.
    - hansvm 6y ago
      > total is known Int, so there is no need to run-time look up `+=` (which python does). Total is known Int or any valid subclass. You can do a bit better for this particular example since it's possible to determine that it falls back to the built-in range (assuming that hasn't been shadowed or otherwise monkeyed with), but any language with operator overloading and without sealed classes has to do _something_ here. It doesn't have to be as expensive as a blind run-time lookup per se, but it's not totally trivial either. > xs is known List[Int] Same problem here with list subclasses (though once it was verified it was the built-in list you might have optimization opportunities that fit within the language's semantics -- I'm not 100% certain it isn't possible to redefine the thing you're iterating over in a way that might inhibit optimizations) > cutting down on the pointer indirection would be a start Even the problem of List[Int] being an array of pointers rather than an array of integers is kind of hard to cut back on when you consider that integers can consume unbounded space. There are some things that can be done and still preserve a pythonic look and feel (as evidenced by many cython projects), but I think optimizing pure python is hard, especially when trying to make small changes that benefit most code (like changing how the interpreter handles lists of integers) rather than examining the effects of larger chunks of code.

mjburgess 6y ago

My hope is that there's some easy, non-trivial, improvements in just basic type awareness, eg., xs: List[Int] = list(range(10)) total : Int = 0 should permit an optimised, for x in xs: total += 1 (almost?) as fast as the equivalent sum. Python hasn't had typing for long enough for this thought to have percolated deeply, ie., I believe at the moment it is just unconsidered rather than infeasible. I suspect that there's a few cases that can be hard coded into the VM that will make a big difference. eg., namedtuple/dataclass, List[String], Dict[String, String], etc.,

mlthoughts2018 6y ago
Unfortunately what you suggest just isn’t conceptually possible (by design) in Python, and would require removing many of the language features that make Python successful for a wide set of use cases. Type hinting (eg List[Int]) has no control over the actual byte layout, it’s just purely metadata. Nothing stops someone from changing xs[4] to be some complex object in your example, regardless of the type hint, so at a pure CPython level it’s fundamentally impossible to benefit from static typing & optimization purely on the basis of type hinting. This is why Cython and numba play that role. They change the location of type metadata - it’s not mere runtime metadata, rather it is compile-time static type annotation in the real sense, for either ahead of time compilation (Cython) or just in time compilation (numba).
- mjburgess 6y ago
  I'm not convinced. The compiler can emit different byte-code. The proposal includes adding a compiler-aware phase to processing type "hints" (here now, actual static types). If you type code "xs: List[Int]" and try to change xs[4], the compiler (phase) would have to reject your code. This isn't "removing features" as typing is optional. And as long as a lists in "successfully compiled python program" express the same API, it doesnt matter that their implementations differ.
  - mlthoughts2018 6y ago
    > “ If you type code "xs: List[Int]" and try to change xs[4], the compiler (phase) would have to reject your code.” This just can’t work - because lists are mutable, so code that mutates them must be valid and permitted by any such compiler. Similarly, values are dynamically typed, so the value of the assignment might be an int or might not, and it cannot be decided until runtime (and this inability to prove at compile time can’t cause the program to fail to compile, it’s Python). Additionally, Python only has infinite precision ints, so it would be quite hard to get anything useful out of this, unless you wholesale switch to using ctypes or something, but then just use Cython and it will be way easier. I’m not convinced this could ever be anything more than a super limited toy.
hansvm 6y ago
That snippet as a whole could be optimized. Individual components would be trickier though. To be clear, you aren't suggesting something as seemingly straightforward as shoving lists of integers into contiguous memory, right? With native big integers, integer subclasses, and whatnot I'd imagine that'd get thorny in a hurry.
- mjburgess 6y ago
  cutting down on the pointer indirection would be a start total is known Int, so there is no need to run-time look up `+=` (which python does). xs is known List[Int] so there is no need to use an iterator protocol to obtain sequential elements (ie., it can be known to be sequential in memory). The problem is that if python were statically typed in a way which matched its semantics, everything would be profoundly polymorphic. Almost nothing is monomorphized. Lot's and lot's of trivial optimisations are available if the core team is happy to add time to the compiler phase.
  - hansvm 6y ago
    > total is known Int, so there is no need to run-time look up `+=` (which python does). Total is known Int or any valid subclass. You can do a bit better for this particular example since it's possible to determine that it falls back to the built-in range (assuming that hasn't been shadowed or otherwise monkeyed with), but any language with operator overloading and without sealed classes has to do _something_ here. It doesn't have to be as expensive as a blind run-time lookup per se, but it's not totally trivial either. > xs is known List[Int] Same problem here with list subclasses (though once it was verified it was the built-in list you might have optimization opportunities that fit within the language's semantics -- I'm not 100% certain it isn't possible to redefine the thing you're iterating over in a way that might inhibit optimizations) > cutting down on the pointer indirection would be a start Even the problem of List[Int] being an array of pointers rather than an array of integers is kind of hard to cut back on when you consider that integers can consume unbounded space. There are some things that can be done and still preserve a pythonic look and feel (as evidenced by many cython projects), but I think optimizing pure python is hard, especially when trying to make small changes that benefit most code (like changing how the interpreter handles lists of integers) rather than examining the effects of larger chunks of code.