neilconway opened a new pull request, #11408: URL: https://github.com/apache/arrow-rs/pull/11408
# Which issue does this PR close? - N/A # Rationale for this change This PR makes several related optimizations when decoding definition and repetition levels: * `DefinitionLevelDecoderImpl::read_def_levels` counts how many definition levels have the maximum value. That was previously done with `filter(|x| **x == self.max_level).count()`, which does not vectorize well: levels are `i16` but `count` returns `usize`, so we can look at many levels at once (e.g., 8 with ARM NEON registers), but we then need to widen those comparison results to sum them into 64-bit `usize` counters. It is more efficient to sum into `u16` counters first and then aggregate the partial sums. We count chunks of <= `u16::MAX` levels at a time, to avoid overflowing the `u16` counters. We introduce a helper `count_levels_eq` that does this. * `RepetitionLevelDecoderImpl::count_records` looks for 0s in the repetition levels to identify when new records start. That was previously done one level at a time, stopping once the requested # of records has been reached. That means the loop can stop at any level, which is hard to vectorize. Instead, use `count_levels_eq` to count 0s in chunks of 32 levels at a time; once we reach or exceed the requested # of records, we go back and precisely count the last chunk. * `DefinitionLevelBufferDecoder::read_def_levels` reads the definition levels of a nested column and builds a null mask with one bit per level. When every level is at the maximum (no nulls, empty lists, or null lists), we can append an all-valid run instead of building the null-mask bit-by-bit. `arrow_reader` benchmarks, Apple M4 Max / AMD EPYC (x86): - `ListArray` cases: -12% to -29% / -12% to -26% - `Int32List`, skip and read in runs of 32: -24% / -24% - `Int32List`, skip and read in runs of 1: -3% to +4% / -2% to +1% - optional struct with optional data: -51% / -70% with no NULLs, -10% / -10% with half NULLs # What changes are included in this PR? See above. # Are these changes tested? Yes; existing tests pass, new tests added. # Are there any significant user-facing changes? No functional changes. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
