mbutrovich commented on code in PR #12018:
URL: https://github.com/apache/arrow-rs/pull/12018#discussion_r4587847443
##########
parquet/src/arrow/array_reader/list_array.rs:
##########
@@ -78,6 +78,126 @@ impl<OffsetSize: OffsetSizeTrait>
ListArrayReader<OffsetSize> {
}
}
+/// Computes a list's offsets, its validity bitmap when `nullable`, and the
+/// number of child values it references, from the def/rep levels of its
+/// item reader.
+///
+/// Definition levels identify whether each list boundary contributes a
+/// child slot. For a nullable list, the states are:
+///
+/// - `d >= def_level`: list is present with a child item
+/// - `d == def_level - 1`: list is present but empty
+/// - `d <= def_level - 2`: list is null
+///
+/// Required lists do not have the null state, but still use the same
+/// `d >= def_level` test to distinguish child items from empty lists.
+/// Repetition levels identify list boundaries and whether a child item
+/// belongs directly to this list or to a nested child list.
+///
+/// `parent_threshold` is set when this list is itself a child of another
+/// list; entries with `d < threshold` belong to null/empty parent lists and
+/// are skipped.
+fn build_list_offsets_and_validity<O: OffsetSizeTrait>(
+ def_levels: &[i16],
+ rep_levels: &[i16],
+ def_level: i16,
+ rep_level: i16,
+ parent_threshold: Option<i16>,
+ nullable: bool,
+) -> Result<(Vec<O>, Option<BooleanBuffer>, usize)> {
+ let levels_len = def_levels.len().min(rep_levels.len());
+ // At most one list starts per level, plus the trailing offset
+ let mut offsets = vec![O::default(); levels_len + 1];
+ let mut validity = BooleanBufferBuilder::new(if nullable { levels_len }
else { 0 });
+
+ // Specialize the scan by nullable/parent-threshold mode so the hot loop
+ // does not check these options once per decoded level.
+ let fill = match (parent_threshold.is_some(), nullable) {
+ (false, false) => fill_list_offsets::<O, false, false>,
+ (false, true) => fill_list_offsets::<O, false, true>,
+ (true, false) => fill_list_offsets::<O, true, false>,
+ (true, true) => fill_list_offsets::<O, true, true>,
+ };
+ let (num_lists, num_children) = fill(
+ def_levels,
+ rep_levels,
+ def_level,
+ rep_level,
+ // Only read by the scans specialized with a threshold
+ parent_threshold.unwrap_or(i16::MIN),
+ &mut offsets,
+ &mut validity,
+ );
+
+ // Offsets never decrease, so the last one fitting means they all do
+ offsets[num_lists] = O::from_usize(num_children)
+ .ok_or_else(|| general_err!("offset of {} would overflow list array",
num_children))?;
+ offsets.truncate(num_lists + 1);
+
+ Ok((offsets, nullable.then(|| validity.finish()), num_children))
+}
+
+/// Writes the start offset of each list to `offsets` and, when `NULLABLE`,
+/// its validity bit to `validity`. Returns the number of lists and of child
+/// values. The trailing offset is left to the caller.
+///
+/// The scan does not branch on the level values: every level writes the
+/// current child count to the slot of the next list, and only a list start
+/// advances past that slot, so each list keeps the count from before its own
+/// first level. Validity bits collect in a word that is flushed every 64
lists.
+fn fill_list_offsets<O: OffsetSizeTrait, const HAS_THRESHOLD: bool, const
NULLABLE: bool>(
+ def_levels: &[i16],
+ rep_levels: &[i16],
+ def_level: i16,
+ rep_level: i16,
+ threshold: i16,
+ offsets: &mut [O],
+ validity: &mut BooleanBufferBuilder,
+) -> (usize, usize) {
+ // A list is present (empty or not) from this level up
+ let empty_level = def_level - 1;
+
+ let mut num_lists = 0;
+ let mut num_children = 0;
+ let mut word = 0u64;
+ let mut word_bits = 0;
+
+ for (&d, &r) in def_levels.iter().zip(rep_levels) {
+ // Entries of null/empty parent lists do not belong to this list
+ let keep = !HAS_THRESHOLD || d >= threshold;
+ // A level below this list's rep level starts a new list.
+ let start = keep & (r < rep_level);
+ // `d >= def_level` excludes null/empty lists, which carry no child
+ // value: emptiness is handled by this definition-level guard, not by
+ // the repetition level.
+ //
+ // `r <= rep_level` (not `==`) keeps only direct children: the first
+ // element of each list has `r < rep_level` (it coincides with an
+ // outer/row boundary), so `==` would drop it; continuation entries of
+ // a nested child's own list have `r > rep_level` and are excluded.
+ let child = keep & (d >= def_level) & (r <= rep_level);
+
+ offsets[num_lists] = O::usize_as(num_children);
+ if NULLABLE {
+ // Only a list start may set a bit, as non-starts do not advance
+ word |= ((start & (d >= empty_level)) as u64) << word_bits;
+ word_bits += start as usize;
+ if word_bits == 64 {
+ validity.append_word(word, 64);
+ word = 0;
+ word_bits = 0;
+ }
+ }
+ num_lists += start as usize;
+ num_children += child as usize;
+ }
+
+ if NULLABLE {
+ validity.append_word(word, word_bits);
+ }
+ (num_lists, num_children)
+}
Review Comment:
> I pushed your one-line change in all four loops and dropped the rewrite,
the differential test and both round-trip tests.
Thanks. I checked the codegen with `codegen-units = 1`, which DataFusion and
Comet release builds use, and the four counters are still branchless with the
counter in a register on both x86-64 (`setge`/`setle`/`and`/`add`) and aarch64
(`ccmp`/`cinc`), while `main` keeps two branches per level.
--
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]