dwsmith1983 opened a new pull request, #12018: URL: https://github.com/apache/arrow-rs/pull/12018
# Which issue does this PR close? - Closes #12017 Part of apache/datafusion-comet#6921. # Rationale for this change `ListArrayReader::consume_batch` builds list offsets and validity with a branch per level, and those branches mispredict whenever NULLs, empty lists and values are mixed. Nested lists pay it again at every level. # What changes are included in this PR? - The level scan computes each level's contribution with boolean arithmetic. Offsets are written by index into a pre-sized buffer, and validity bits are packed into a `u64` and appended with `append_word`. - The loop is specialized on whether a parent threshold applies and whether the list is nullable. - An offset that overflows the offset type now returns an error instead of panicking. - A new `ListArray/Int32ListList` bench (no NULLs, half NULLs) covers the nested path. It is in its own commit, so the change can be compared against it. # Are these changes tested? A differential test compares the new scan with a copy of the old loop on seeded random levels: nesting depth 1 to 3, lengths around the 64-bit word boundaries, malformed input, and both `i32` and `i64` offsets. Two round-trip tests read `list<list<int32>>` and a list inside a struct at a batch size of 7. Benchmarks ran on GitHub-hosted runners: the bench commit and this change, each built once, then run in alternating order. Change in time, negative is faster: | Bench | AMD EPYC 9V74 | Neoverse-N2 | |---|---:|---:| | `StringList/no NULLs` | -9.2% | -4.0% | | `StringList/half NULLs` | -18.3% | -12.2% | | `StringList/90pct NULLs` | -19.4% | -10.5% | | `StringList/99pct NULLs` | -12.3% | -5.8% | | `Int32List/no NULLs` | -20.3% | -9.1% | | `Int32List/half NULLs` | -32.2% | -21.1% | | `Int32List/90pct NULLs` | -18.7% | -10.3% | | `Int32List/99pct NULLs` | -13.3% | -5.7% | | `Int32List/no NULLs or empty lists` | -28.8% | -16.2% | | `Int32List/no NULLs, skip and read in runs of 1` | +0.1% | -0.8% | | `Int32List/no NULLs, skip and read in runs of 32` | -12.5% | -3.4% | | `Int32ListList/no NULLs` | -38.3% | -27.5% | | `Int32ListList/half NULLs` | -50.9% | -41.4% | | `Fixed32List/no NULLs` | -20.4% | -6.9% | | `Fixed32List/half NULLs` | -27.4% | -17.4% | | `Fixed32List/90pct NULLs` | -19.7% | -10.7% | | `Fixed32List/99pct NULLs` | -13.5% | -6.1% | Running the two binaries in the opposite order gives the same picture on both machines. `skip and read in runs of 1` moved between -2% and +3% across runs on x86. That bench calls `consume_batch` only five times per iteration, about 5% of its instructions, and callgrind shows those calls run the same instruction count as before with far fewer mispredicts. # Are there any significant user-facing changes? No. -- 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]
