Data-Oriented Programming in Python
moderndescartes.com
moderndescartes.com
However it's about the limitations of python's computational model (ie., how it imposes large constant factors on most operations, due to pointer indirection). And how numpy solves that in one case (homogenous arrays).
I was hoping it would include a discussion on the julia solution: a sort of partial static-typing, where type information is use to generate optimised code.
It should be possible for python to follow a similar route: an (optional?) compilation pass which uses type information to eliminate pointer indirection (, etc.).
However I'm not sure how much resistance the actual object model of the VM poses: would you, in effect, just be compiling to a different VM?
The present cpython approach to optimization is hacky and specific, eg.,
sum( a * a for a in range(10) )
These are both long standard tools in scientific Python.
xs: List[Int] = list(range(10))
total : Int = 0
for x in xs:
total += 1
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.,
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).
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.
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.
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.
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.
But apparently it is just what we in R and Python call vectorised functions.
To boil it down:
non-vectorised:
square(2) -> 4
square([2,4]) -> error
square(2) -> 4
square([2,4]) -> [4, 16]
Or am I completely off?
But in the meantime, languages like R or Matlab had figured a solution: write all the heavy-lifting ultra-optimized algorithms in C or Fortran or some equally ugly language that no one but really smart nerds wants to touch, and wrap it in a semantic that makes loops and loading many objects unnecessary, called 'vectorized operations'. In R, for instance, you think you're manipulating mere strings or logicals, but you're in fact manipulating vectors of length 1 and of type 'string', 'logical', etc. But doing operations on vectors or arrays became as seamless as doing them with mere scalars, with hardly any loss in performance. And so the R world thrived, although we were still cautioned to use weird lapply/sapply/rapply magic instead of doing proper loops because something something compiler something something slow blah blah blah.
And so the Python world saw that the R and Matlab world thrived, and wondered if they could do the same. A bunch of really smart nerds sat down with their laptops and wrote a bunch of ultra-optimized algorithms in one of those ugly languages no one else wants to touch, and lo, in the mid-2010s Python had finally achieved feature parity with R and Matlab twenty years ago. Yet the trend showed no sign of slowing, as Python was not only useful for scientific computing, but many other use cases as well (you ever tried to write an interface or webserver in R?), and sometimes researchers have the audacity to want to do several things at once with the computer. And so Python achieved its present ubitquity in data science.
There's trouble in paradise, however. As with R, we were cautioned to avoid doing too many loops because something something you know what I mean, and instead use vectorized operations. And little by little, we had to learn every day a little more of numpy's arcane API, the right magical formulas to invoke in order to avoid losing performance. We had to learn which operations are in-place and which ones create a new array (knowing this could change over multiple versions), which appropriate slicing and indexing to use, which specific functions to call. And the more our use cases deviated from the documentation, the more magic we had to learn. At some point we had to learn obscure methods beginning with an underscore, or even (the horror!) mind whether arrays were ordered C-style and Fortran-style, or even told to use Cython (!), nevermind your desire to absolutely avoid touching these languages in any way. May Allah be with you should you ever want to manipulate sparse data.
Aware that the community had to learn magic whose complexity on par with the ugly languages they'd sworn off, really smart nerds took it upon themselves to... write more magic in order to avoid writing the older magic. And so we got dask, which is as powerful as it is painful to use. We got numba, which seems to work automagically in the official demo snippets and zilch in your own. 'That's because you're using them wrong', the smart people tell you on stackoverflow. 'Teach me how to use them right', you beg. And so your mental spellbook thickens with no end in sight...
Enter Julia. Julia doesn't have that any of the above dillemas, because Julia is fast. Julia doesn't care whether you vectorize or write loops, but you can do either. Julia doesn't force you to declare types, but you can if you really want to. Julia doesn't require you to write advanced magic to do JIT compilation. Julia doesn't see itself as an R or Python competitor: why, Julia loves Python and R, and in fact you can just call one from the other if you feel like it! Go on, just RCall ggplot on an array created with PyCall("numpy"), it just works! Julia was built with parallel computing and HPCs in mind, so no need to fiddle with dask boilerplate when it just works with @macros. Julia knows programmers are afraid of change, so it syntax is really, really close to Python's. Julia has a builtin package manager. Julia lets you use the GPU without having to sacrifice a rooster to Baal every time you want to install CUDA bindings.
Of course Python isn't going anywhere, just like R is still going strong even after Python 'displaced' it. And of course, Julia's ecosystem is smaller (but growing), its documentation is lacking, it doesn't have millions of already answered questions on Stackoverflow...but if you know where the wind blows, you know where the future is headed, and its name rhymes with Java.
That's my experience. I was working on satellite image processing at the time, lots of Python loops in the code. Numba should've made a big difference according to the demos, but when benchmarking it didn't.
Adding a single decorator sounds wonderful and I never found an answer to why it didn't work.
Otherwise it's no better than python.
Generally numba works the same way writing C works: you pass in raw buffers (numpy arrays) and do processing directly on those buffers. That compiles to good LLVM bytecode and is fast.
Is there a way to get it to tell you when it rejects compilation? I don't recall one at the time (this was ~4 years ago) and spent a week and a bit trying to get it to work.
The main culprit seems to lie in the fact that the LLVM JIT compiler isn't great in terms of performance, although it does compile Julia to really efficient native runtime code. For example, you don't have problems like this in LuaJIT: although the JIT does less thorough optimizations than Julia (hence probably slower and more unpredictable runtime performance), it wins in usability by having a really fast non-compiled interpreter path written in assembly (because Mike Pall is a robot from the future). Obviously Lua is quite different in the fact that it's fully dynamically typed while Julia has a static type system, and note in mind that Lua's design had some major flaws as a scientific language (hence most ML researchers moving from LuaTorch to PyTorch.)
https://numba.pydata.org/numba-doc/latest/user/vectorize.htm...
I've had a ton of success using it in statistical and computational geometry applications.
- case 1 : need to make calculations with a specialized library in C (precision arithmetics). Build a bare FFI, later replaced with CFFI.
- case 2 : loop-intensive on very simple calculations, time-constrained development. Identified as horrible performance in python : tried numba didn't work, ended up using cython, worked really well.
- case 3 : optimize numpy-intensive routine for performance. Tried numba, didn't work. Too expensive to recode in cython. Look at numpy C/C++ interfaces, and numpy-friendly C++ alternatives. Also try to trick numpy to function better (do not ever try this, it'll give worse results). Ended up doing nothing as time to develop was the main constraint here.
If you have a lot of time and work on a small program, maybe you can spend the time to optimize. Team producing lots of complicated algorithms and no way to re-develop everything, stick to python, identify perf losses and choose wisely what you'll optimize.
Numba has progressed but is still not a "drop-in decorator" as advertized. Can even give worse performance in some cases. Nevertheless the idea is good and I praise the effort, when it's done it'll be massive !
Not only should it work for case 2 - it should only require a one liner decorator add and no user specified static typing.
I’ve used numba in production for around 6 years now, and never encountered the problems you describe.
I think Numba has a lot of potential and will improve as they fill out remaining language coverage and finalize the API. The idea of a LLVM JIT compiler for python makes a ton of sense.