apache / apache/arrow-rs

Improve cache locality in BYTE_STREAM_SPLIT decoding reconstruction

Open
#10,006 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.