Improve cache locality in BYTE_STREAM_SPLIT decoding reconstruction
- Dominant language
- Rust
- Stars
- 3.6k
- Forks
- 1.3k
- Avg merge
- 2d 18h
- Merged PRs (30d)
- 169
Description
## Description
In `parquet/src/encodings/decoding/byte_stream_split_decoder.rs`, `BYTE_STREAM_SPLIT` decoding currently reconstructs values using a nested scalar loop over values and byte streams in `join_streams_const` and `join_streams_variable`.
The current implementation iterates value-by-value while performing strided reads across the split byte streams, which results in poor memory locality during reconstruction of the original value layout.
This impacts the `BYTE_STREAM_SPLIT` decoding benchmarks in `parquet/benches/encoding.rs`, particularly for floating-point and fixed-length byte array decoding.
---
## Root Cause
The current reconstruction logic processes values in a scalar, value-major order:
```rust
for i in 0..dst.len() / TYPE_SIZE {
for j in 0..TYPE_SIZE {
dst[i * TYPE_SIZE + j] = sub_src[i + j * stride];
}
}
```
This results in:
* strided memory access patterns across byte streams
* reduced cache locality
* limited compiler vectorization opportunities
* increased memory access overhead during reconstruction
The issue becomes more pronounced for larger fixed-width types such as `f32` and `f64`.
---
## Proposed Solution
Rework the reconstruction logic to process values in contiguous blocks instead of value-by-value scalar iteration.
This improves cache locality by reading contiguous regions from each byte stream before writing reconstructed values back into the destination buffer.
Contributor guide
Research direction
Start in parquet/src/encodings/decoding/byte_stream_split_decoder.rs by reading join_streams_const and join_streams_variable, then run the BYTE_STREAM_SPLIT decoding benchmarks in parquet/benches/encoding.rs. Compare reconstruction performance for floating-point and fixed-length byte array decoding; done means the reconstruction uses contiguous blocks and the affected benchmarks improve without changing decoding results.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100