[C++][Parquet] ALP improvements

Describe the enhancement requested

Track the remaining ALP improvements after the initial implementation in #48345.

Accept unsorted and duplicate exception positions while preserving the
optimized patch loop for strictly increasing positions.
Serialize vectors one at a time instead of retaining all encoded vectors
and a separate offset array for the page.
Make ALP vector size configurable through writer properties and encoder
factories.
Cache and reuse a column-chunk preset across pages.
Encode complete vectors as values arrive in Put() / PutSpaced(),
retaining only the unfinished vector instead of buffering the entire page
as raw values until FlushValues().
Support falling back from ALP when ALP would produce a larger page.
Improve EstimatedDataEncodedSize() using observed encoded bytes per value,
including metadata and exception overhead, instead of returning the raw
buffered byte count.

Component(s)

C++, Parquet

apacheGH-55448: [C++][Parquet] Optimize ALP and make vector sizes con…

@mapleFU

We could also improve decoding speed with explicit vectorization.
I made a quick-and-dirty attempt using xsimd here:
https://gist.github.com/pitrou/b52c3af4aa7b8d8b4dd77f4afbf59e70

Benchmark numbers (AVX2):

before:

BM_AlpDecodingFloat/1024          824 ns          824 ns       506872 bytes_per_second=4.62949Gi/s items_per_second=1.24272G/s
BM_AlpDecodingFloat/4096         2742 ns         2741 ns       152919 bytes_per_second=5.56733Gi/s items_per_second=1.49447G/s
BM_AlpDecodingFloat/32768       20420 ns        20417 ns        20591 bytes_per_second=5.97878Gi/s items_per_second=1.60492G/s
BM_AlpDecodingFloat/65536       40767 ns        40712 ns        10150 bytes_per_second=5.99674Gi/s items_per_second=1.60974G/s

BM_AlpDecodingDouble/1024         892 ns          891 ns       468092 bytes_per_second=8.56015Gi/s items_per_second=1.14892G/s
BM_AlpDecodingDouble/4096        2930 ns         2929 ns       142959 bytes_per_second=10.4178Gi/s items_per_second=1.39825G/s
BM_AlpDecodingDouble/32768      21736 ns        21725 ns        19332 bytes_per_second=11.2378Gi/s items_per_second=1.50832G/s
BM_AlpDecodingDouble/65536      43531 ns        43526 ns         9269 bytes_per_second=11.2181Gi/s items_per_second=1.50566G/s

after:

BM_AlpDecodingFloat/1024          378 ns          378 ns      1106542 bytes_per_second=10.0874Gi/s items_per_second=2.70781G/s
BM_AlpDecodingFloat/4096          977 ns          976 ns       426826 bytes_per_second=15.6339Gi/s items_per_second=4.1967G/s
BM_AlpDecodingFloat/32768        6499 ns         6498 ns        64461 bytes_per_second=18.786Gi/s items_per_second=5.04284G/s
BM_AlpDecodingFloat/65536       12610 ns        12606 ns        33576 bytes_per_second=19.3666Gi/s items_per_second=5.19869G/s

BM_AlpDecodingDouble/1024         637 ns          637 ns       660226 bytes_per_second=11.9714Gi/s items_per_second=1.60678G/s
BM_AlpDecodingDouble/4096        1929 ns         1928 ns       218526 bytes_per_second=15.8279Gi/s items_per_second=2.12438G/s
BM_AlpDecodingDouble/32768      13825 ns        13822 ns        30312 bytes_per_second=17.6638Gi/s items_per_second=2.37079G/s
BM_AlpDecodingDouble/65536      27631 ns        27630 ns        15174 bytes_per_second=17.672Gi/s items_per_second=2.3719G/s

cc @mapleFU

@prtkgaur

Also @prtkgaur FYI

ALP's official impl is efficient for SIMD execution, let's just eat it!

By the way 19.3666Gi/s is extremly fast😂

Navigation Menu

Repository navigation

[C++][Parquet] ALP improvements #55448

Describe the enhancement requested

Component(s)

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

[C++][Parquet] ALP improvements #55448

Description

Describe the enhancement requested

Component(s)

Activity

pitrou commented on Nov 10, 2026

pitrou commented on Nov 10, 2026

mapleFU commented on Nov 10, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions