The FastLanes Unified Transport Layout · blog.dave.tf
Written by<br>David Anderson
on August 8, 2026
The FastLanes Unified Transport Layout
UTL comes from FastLanes, and is designed to make delta decoding very data-parallel. However the paper explains the layout in a way I find confusing, so I’m going to try my own explanation here.
I’m going to assume that you know what delta encoding is, as well as the basics of SIMD computing.
Basic delta encoding/decoding is a fundamentally sequential problem, because computing each value requires first computing all previous values. The parts of FastLanes we’re interested for this post aim to add parallelism to the problem, so that we can use SIMD to make delta encoding and (especially) decoding very fast.
Preliminaries: vector registers
SIMD ISAs come with a dedicated set of wide vector registers. On modern systems they vary in size from 128 bits (SSE, Arm’s Neon) up to 512 bits (AVX-512), and can be sliced up into lanes of different sizes. Instructions execute the same operation on all lanes in parallel. Here’s a 64-bit vector register (very small by modern standards), decomposed into 8-bit, 16-bit and 32-bit lanes.
FastLanes designs its algorithms around a virtual 1024-bit SIMD register size, larger than any mainstream ISA can handle. This is because it’s easy to implement an algorithm designed for wide registers using narrower registers: just implement each wide operation as several narrower ones.
On the flip side, it’s very hard to take an algorithm designed for narrow SIMD widths and make them fast with wider registers, because you’re likely to end up with data dependencies between different lanes of the same register. Such dependencies completely kill performance, so you really want to avoid ending up in this situation.
So, the FastLanes algorithms we’re looking at all work with 1024-bit registers, with lanes of 16x64b, 32x32b, 64x16b or 128x8b. Algorithms that are efficient on a 1024-bit register will be just as efficient on real-world machines and their 128/256/512-bit registers.
Lane-parallel delta decoding
Let’s start with an array of 1024 64-bit integers that we want to delta-encode.
As I said above, this is a fundamentally sequential algorithm: keep the first value, and make every subsequent value be the delta from the previous. Every value requires touching the previous value to compute the difference, which in SIMD would mean reaching over to a neighbour lane.
For our 1024-bit SIMD registers, we’d need 16 independent delta streams that we can compute simultaneously. If we’re willing to store more than one base value, we can do that by breaking up our 1024 values into 16 chunks:
The layout in memory hasn’t changed yet, this is just a bit of wrapping to visualize the 16 chunks as rows.
Now, imagine processing this 2D array one column at a time. Each column is 16x64b values, exactly one 1024-bit register. Furthermore, if you look down each row, the values within the row are still in the right order for delta-encoding. In other words, if we store the entire first column as the base values, the 16 rows become 16 independent data streams that can be computed simultaneously. Exactly what we need!
One wrinkle is that the values for each column are still scattered all over the place in memory. SIMD load/store instructions want those values to be contiguous. We can solve that easily by thinking of this array as a 16x64 matrix, and transposing it:
Now, we can process this array in chunks of 16 values, which fits neatly in our 1024-bit SIMD register and lets us blow through 16 delta encoding streams simultaneously.
Width agnostic layout
The transposition above works well, but the ideal split and transposition depends on the element size. The layout above is perfect for 64-bit values, but if we switch to 32-bit values we’re once again in trouble: now a row of 16 values is only 512 bits, half the size of our SIMD register. And it gets even worse if we consider 16-bit and 8-bit values!
You could say “who cares” and just do different transpositions for different data types: use rows of 32 for 32-bit values, rows of 64 for 16-bit, and 128 for 8-bit. That would work, but it means that two columns with different data types end up with values in different orders. That’s going to be a nightmare both for filtering values during query execution, and for stitching together coherent results to return.
Ideally, we want to find a single permutation of our input array that can make full use of our 1024-bit registers, regardless of the element size. And, well, that’s exactly what the UTL permutation is.
To see how and why it works, let’s derive it one step at a time.
32-bit values
We already have a permutation that works well for 64-bit values above, 64 rows of 16 columns. Let’s start with that, reduce the element size to 32 bits,...