Hi everyone, @Divjot Arora - can you try the link again?
@Antoine Pitrou - I went through the doc again and trimmed it down. I removed two sections to make it more concise: 1) Comparing the performance at O2 vs O3. 2) Details about the memory store bandwidth at various output buffers. I've made those edits. Please let me know if this version is much easier to parse. Best, Prateek On Tue, Sep 29, 2026 at 7:15 AM Divjot Arora via dev <[email protected]> wrote: > Hey Prateek, > > I am not able to access > https://docs.google.com/document/d/1L2pfrHfAZG4vKTHc-OD8p9alIUD-sUFg due > to > permissions. > > -- Div > > On Tue, Sep 29, 2026 at 3:54 PM PRATEEK GAUR <[email protected]> wrote: > > > Hi Antoine, > > > > The doc was a little large as I tried to build on things step by step. > And > > then I tried to explain why on certain hardware we didn't see any > benefit. > > I'll try to trim down the content across those sections and see if I can > > still explain things with less verbosity. > > > > Best, > > > > Prateek > > > > On Tue, Sep 29, 2026 at 12:38 AM Antoine Pitrou <[email protected]> > > wrote: > > > > > > > > Hello Prateek, > > > > > > I've tried several times to read and parse your sentences. They all > look > > > like AI-generated gibberish to me. > > > > > > Can I ask you to rephrase this as a human (no, please don't delegate > > > this to a LLM)? > > > > > > Similarly, the descriptions for your PRs are all AI-generated. Please > > > reformulate like a human talking to a human. > > > > > > Thank you > > > > > > Antoine. > > > > > > > > > > > > Le 18/09/2026 à 20:12, PRATEEK GAUR a écrit : > > > > Hi Antoine, > > > > > > > > You hit the nail on the head. Your intuition about breaking the > > > sequential > > > > dependency using a > > > > vectorized prefix sum (a log-step scan) is exactly right. > > > > > > > > In fact, I completely agree that optimizing the existing format is > > > crucial > > > > for immediate impact. > > > > I dug into this recently and actually have three draft PRs open > against > > > > Parquet C++ (under > > > > issue #51268) that do exactly what you are suggesting. > > > > > > > > Specifically, PR #51295 [3] implements the exact log-step SIMD scan > you > > > > described. Combined with > > > > batched miniblock unpacking (PR #51250) [2], it yields about a 2.15x > > > > speedup on narrow 32-bit > > > > pages on Graviton4. > > > > > > > > With that said: even when compared against this newly optimized, > > > vectorized > > > > DELTA_BINARY_PACKED baseline, the FastLanes transposed layout > > (FL_ORDER) > > > is > > > > still roughly > > > > 2x faster on top of that. (Also the document introduces interleaved > > > layout > > > > in addition to FL_ORDER). > > > > > > > > The difference comes down to how much work the CPU has to do: > > > > > > > > 1. Vectorized DELTA_BINARY_PACKED (Software): Because the values are > > > stored > > > > sequentially, the > > > > CPU has to execute a log-depth tree of cross-lane shifts and adds to > > > > accumulate the totals > > > > within the vector. > > > > > > > > 2. FastLanes FL_ORDER (Layout): By rearranging the bits on disk so > > that a > > > > lane gets its own > > > > contiguous run of values, the decoder requires zero cross-lane > > > > communication. It just issues > > > > standard, vertical SIMD ADDs, advancing 32 independent dependency > > chains > > > > perfectly in parallel. > > > > > > > > So you are absolutely right that we can (and should!) make the > existing > > > > DELTA_BINARY_PACKED > > > > much faster right now. But the benchmark data shows that solving the > > > > dependency chain at the > > > > layout level still extracts about twice (more on hardware that Kosta > > > tried > > > > on) as much performance > > > > as solving it in software. > > > > > > > > So my thinking is : > > > > 1) We should definitely optimize the DELTA_BINARY_PACKED. > > > > 2) In addition we should give serious thought to interleaving + > > fl_order > > > > 3) PFOR can use both sequential bit packing or fl_order/interleave > > based > > > on > > > > a flag. > > > > > > > > Thanks, > > > > Prateek > > > > > > > > [1] https://github.com/apache/arrow/pull/51249 > > > > [2] https://github.com/apache/arrow/pull/51250 > > > > [3] https://github.com/apache/arrow/pull/51295 (not yet stacked on > top > > > of > > > > #51249) > > > > > > > > On Fri, Sep 18, 2026 at 10:25 AM Antoine Pitrou <[email protected]> > > > wrote: > > > > > > > >> > > > >> 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. > > > >> > > > >> > > > >> > > > > > > > > > > > > > > > >
