Le 18/09/2026 à 16:53, PRATEEK GAUR a écrit :
For Delta encoding, the transposed layout looks highly promising:
Standard Delta encoding forces the CPU to calculate values sequentially,
which slows things down. The FastLanes container fundamentally breaks this
bottleneck by splitting the work into parallel streams. Using its
recommended layout (FL_ORDER), we saw a massive decoding speedup with
virtually no impact on file size.
This begs the question: can an equivalent optimization be implemented
for regular DELTA_BINARY_PACKED?
The main difficulty of DELTA_BINARY_PACKED decoding is the sequential
dependency when accumulating each delta with the previous value.
However, I think the sequential dependency can be broken up:
1. Partial accumulation per miniblock: for each miniblock, build a
cumulated sum of deltas (cum_deltas) with 0 as the start value. A
cumulated sum is inherently sequential, but several cumulated sum
computations can be interleaved (probably 4 or 8 of them) to enable some
parallelism on the CPU. By carefully laying out the arrays of deltas and
cum_deltas, SIMD might even be exploitable.
2. Final accumulation step: for each miniblock, add the previous
miniblock's last value to its cum_deltas, which gives you the final
decoded output. This is an inherently vectorizable sum; the only
sequential dependency is between miniblocks (you need to wait for a
miniblock's last value to start handling the next miniblock), so this
should be quite fast.
Am I missing something?
I will mention I know nothing about Fastlanes; currently I don't really
have the time to read about it, so I have no idea whether other factors
might make it faster or slower, or more or less space-spacing than the
idea above.
However, given that DELTA_BINARY_PACKED is already widespread, a
solution to make its decoding faster sounds better than introducing an
entirely different integer encoding that people won't use before years.
Regards
Antoine.
