3 ms·

That snippet as a whole could be optimized. Individual components would be trickier though. To be clear, you aren't suggesting something as seemingly straightfo

by 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.
  - mlthoughts2018 6y ago
    Also note Python has built in support for contiguous, homogeneously typed arrays. This is the “array.array” class. Of course in practice you should use NumPy for this, but array.array is there too.

by hansvm 6y ago

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.
- mlthoughts2018 6y ago
  Also note Python has built in support for contiguous, homogeneously typed arrays. This is the “array.array” class. Of course in practice you should use NumPy for this, but array.array is there too.