Vectorisation: What is it and how does it work?
O(n) is faster than O(1), cache lines, Pandas 2.0 and the consistent rise of the column
This is the 2nd iteration of this article. After finishing the 1st iteration, I left it to stew and edit as the headlines didn’t look good — a 13 min ramble about vectorisation with some loose links to database theory and historical trends.
While waiting to re-draft, I came across several from Polars author Ritchie Vink he explains using a combination of clear concise sentences and simple visuals how Polars achieves what it achieves — because it is not just built with ideas of vectorisation in mind, but built completely around those principles.
The aim for the rest of this article isn’t necessarily to rehash what has been said there, but instead to work back through some ideas and historical context to shed light on how we have come to column (or array) based computing being more ‘mainstream’ and how that has started to perforate the modern day data science tool kit in python.
“I don’t care what your fancy data structure is but I know that an array will beat it”
The above is from out the window because an O(n) algorithm can trump an O(1) algorithm.
I come from a non computer science background, but the wealth of material that universities (particularly American) make available online means I’ve been able to take some of the basic ‘Algorithms’ and ‘Data Structures’ courses. From what I can see, the joint aim could be (probably badly) summarised as:
- use logic to come up with a process that involves the least amount of steps (algorithms)
- organise your data to enable the selection of an algorithm with minimum steps (data structures)
The importance of understanding the core concepts of both is underscored by the legions of companies out there barraging their hopefuls with reams of by Herb Sutter (start at 12:00 for around 20mins if you want to just strip the overview) and the below chart shows it well:
How do we circumvent this? Caching, caching and more caching
Below is the standard image that many people have of a computer’s architecture (), shows how a 4 core CPU is laid out for Intel’s i7 processor — L1 and L2 caches are within each ‘Core’ section:
So how much faster is retrieving data from cache than memory?
For this — a picture is worth a thousand words — or more specifically, an animation. The following link from gaming software optimisation company Overbyte shows just how drastic the relative performance is: unit we have roughly:
- L1: ~1–3x clock cycles
- L2: ~10x clock cycles
- L3: ~40x clock cycles
- Main memory: ~100–300x clock cycles
In other words: if our data is in L1 memory our computer will process it between 30–300x faster than if we fetch it from main memory. Main memory being RAM, not disk. When your CPU can’t find the data in the L1 cache, it searches L2, then L3 and then it goes to main memory with each of these failed searches labelled a ‘cache miss’. The fewer cache misses you have, the faster your code.
So how do I get my data into the caches? Cache Lines
Your CPU does this for you. Based on your code which is translated into the instruction set (lowest level of commands — even assembly is assembled into are the lowest level of data unit that a CPU works with. A cache line will include the data you need, but also the data around that in memory that make up the rest of the cache line — generally a 64 byte contiguous block of memory.
Not only that, but CPUs are built to do clever things to optimise this data fetching from memory. Why? Because it’s slow — so the earlier we can load this data into the cache to be operated on the sooner the bottleneck is fixed between:
- the speed the processor can operate on the data
- the time it takes to make that data available to the processor — in the caches
To do this CPUs implement things like and implement them in the way we store our in memory data.
Moving toward a consistent approach
Polars is based on PyArrow — a python implementation of the . PyArrow works especially well with loading in data from disk in . wrangling with data in spreadsheets, then created and popularised Pandas (utilising NumPy’s vector-friendly .
His career has moved hand in hand with how the modern day ‘data science stack’ (at least in python) has started to move toward a more column orientated in memory data representation. It seems like the championing of the array is set to continue and I personally don’t see it slowing down. Pardon the pun.
on Medium, where people are continuing the conversation by highlighting and responding to this story.
SOCIAL SHARE CARD GENERATOR