hhhizzz commented on code in PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#discussion_r3718326685
##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -269,39 +269,77 @@ pub(super) fn union_row_selections(left: &[RowSelector],
right: &[RowSelector])
/// Bitwise AND of two mask-backed selections. Longer side's tail passes
through.
pub(super) fn intersect_masks(l: &BooleanBuffer, r: &BooleanBuffer) ->
BooleanBuffer {
if l.len() == r.len() {
- return l & r;
- }
- let common = l.len().min(r.len());
- let head = &l.slice(0, common) & &r.slice(0, common);
- let (longer, longer_len) = if l.len() > r.len() {
- (l, l.len())
- } else {
- (r, r.len())
- };
- let tail = longer.slice(common, longer_len - common);
- let mut builder = BooleanBufferBuilder::new(longer_len);
- builder.append_buffer(&head);
- builder.append_buffer(&tail);
- builder.finish()
+ return combine_equal_masks(l, r, |a, b| a & b);
+ }
+ combine_uneven_masks(l, r, |a, b| a & b)
}
/// Bitwise OR of two mask-backed selections. Longer side's tail passes
through.
pub(super) fn union_masks(l: &BooleanBuffer, r: &BooleanBuffer) ->
BooleanBuffer {
if l.len() == r.len() {
- return l | r;
- }
- let common = l.len().min(r.len());
- let head = &l.slice(0, common) | &r.slice(0, common);
- let (longer, longer_len) = if l.len() > r.len() {
- (l, l.len())
- } else {
- (r, r.len())
- };
- let tail = longer.slice(common, longer_len - common);
- let mut builder = BooleanBufferBuilder::new(longer_len);
- builder.append_buffer(&head);
- builder.append_buffer(&tail);
- builder.finish()
+ return combine_equal_masks(l, r, |a, b| a | b);
Review Comment:
The logical semantics are unchanged, but I think we still have “user-facing
changes” here.
`RowSelection::as_mask()` is public, so callers can observe that
equal-length intersection/union previously returned an offset-zero
`BooleanBuffer`, while this implementation may preserve a non-zero offset. This
also changes the observable `values()`, `inner()`, and `ptr_eq()`
representation.
I don't think this is a breaking API change because `as_mask()` does not
promise normalization and consumers must already honor
`BooleanBuffer::offset()`. Could we clarify the PR wording to say that there
are no public signature or logical-selection changes, while the underlying mask
layout may differ?
##########
parquet/benches/row_selector.rs:
##########
@@ -26,6 +26,21 @@ use std::hint;
/// [`RowSelector`]s per row, so the RLE encoding dominates.
const MASK_RUN_LENGTHS: &[usize] = &[1, 4, 16, 32, 48, 64, 96, 128];
+const MASK_ALGEBRA_ROWS: usize = 3_000_000;
+
+/// Operand length pairs. Unequal lengths pass the longer side's tail through
unchanged,
+/// so the ratio decides how much of the work is the bitwise combine versus
the tail.
+const MASK_ALGEBRA_LENGTHS: &[(&str, usize, usize)] = &[
+ ("equal", MASK_ALGEBRA_ROWS, MASK_ALGEBRA_ROWS),
+ ("tail1", MASK_ALGEBRA_ROWS, MASK_ALGEBRA_ROWS - 1),
+ ("tail1of3", MASK_ALGEBRA_ROWS, MASK_ALGEBRA_ROWS * 2 / 3),
+ ("tail_most", MASK_ALGEBRA_ROWS, 1_000),
+];
+
+/// Bit offsets applied to both operands. Masks come from
[`BooleanBuffer::slice`], so a
+/// non-zero offset is normal, and one that is not byte aligned is the
expensive case.
+const MASK_ALGEBRA_OFFSETS: &[(&str, usize)] = &[("aligned", 0), ("unaligned",
3)];
Review Comment:
Could we include more case where the operands have different relative
offsets?
At the moment both operands use the same offset, so the unaligned case only
exercises the `left_offset % 64 == right_offset % 64` fast path in
`BooleanBuffer::from_bitwise_binary_op`. When the offsets differ, for example
`(3, 5)`, the helper takes the shifting fallback and returns a zero-offset
buffer, so the old implementation does not necessarily pay the extra
normalization copy described in the PR.
Something like `(0, 0)`, `(3, 3)`, `(3, 5)`, and `(3, 67)` would make the
benchmark coverage and the performance claim more precise. Alternatively, the
PR description could narrow “non-byte-aligned operands” to “operands sharing a
non-zero sub-64-bit alignment”.
##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -269,39 +269,77 @@ pub(super) fn union_row_selections(left: &[RowSelector],
right: &[RowSelector])
/// Bitwise AND of two mask-backed selections. Longer side's tail passes
through.
pub(super) fn intersect_masks(l: &BooleanBuffer, r: &BooleanBuffer) ->
BooleanBuffer {
if l.len() == r.len() {
- return l & r;
- }
- let common = l.len().min(r.len());
- let head = &l.slice(0, common) & &r.slice(0, common);
- let (longer, longer_len) = if l.len() > r.len() {
- (l, l.len())
- } else {
- (r, r.len())
- };
- let tail = longer.slice(common, longer_len - common);
- let mut builder = BooleanBufferBuilder::new(longer_len);
- builder.append_buffer(&head);
- builder.append_buffer(&tail);
- builder.finish()
+ return combine_equal_masks(l, r, |a, b| a & b);
+ }
+ combine_uneven_masks(l, r, |a, b| a & b)
}
/// Bitwise OR of two mask-backed selections. Longer side's tail passes
through.
pub(super) fn union_masks(l: &BooleanBuffer, r: &BooleanBuffer) ->
BooleanBuffer {
if l.len() == r.len() {
- return l | r;
- }
- let common = l.len().min(r.len());
- let head = &l.slice(0, common) | &r.slice(0, common);
- let (longer, longer_len) = if l.len() > r.len() {
- (l, l.len())
- } else {
- (r, r.len())
- };
- let tail = longer.slice(common, longer_len - common);
- let mut builder = BooleanBufferBuilder::new(longer_len);
- builder.append_buffer(&head);
- builder.append_buffer(&tail);
- builder.finish()
+ return combine_equal_masks(l, r, |a, b| a | b);
+ }
+ combine_uneven_masks(l, r, |a, b| a | b)
+}
+
+/// Combines two masks of equal length with the bitwise operation `op`.
+///
+/// `BitAnd`/`BitOr` on `&BooleanBuffer` normalise the result to a zero bit
offset,
+/// which costs a second allocation and a shifting copy of the whole mask when
the
+/// operands are not byte aligned. Building the buffer directly keeps the
offset,
+/// as the uneven path does.
+fn combine_equal_masks<F>(l: &BooleanBuffer, r: &BooleanBuffer, op: F) ->
BooleanBuffer
+where
+ F: FnMut(u64, u64) -> u64,
+{
+ BooleanBuffer::from_bitwise_binary_op(
+ l.values(),
+ l.offset(),
+ r.values(),
+ r.offset(),
+ l.len(),
+ op,
+ )
+}
+
+/// Combines two masks of differing lengths with the bitwise operation `op`,
+/// passing the longer side's tail through unchanged.
+///
+/// The longer mask is copied once into a [`MutableBuffer`] and `op` is then
+/// applied in place over the common prefix. This avoids materialising the
+/// prefix into its own buffer and copying both prefix and tail again through a
+/// [`BooleanBufferBuilder`].
+///
+/// Neither the mask offsets nor the prefix length are assumed to be byte
+/// aligned: the copy keeps the longer mask's sub-byte offset so it stays a
+/// plain byte copy, and the offset is carried over to the returned buffer.
+fn combine_uneven_masks<F>(l: &BooleanBuffer, r: &BooleanBuffer, op: F) ->
BooleanBuffer
Review Comment:
Nit: a few names could make the offset arithmetic easier to follow:
- `combine_uneven_masks` -> `combine_unequal_length_masks`
- `bit_offset` -> `offset_within_byte` or `sub_byte_offset`
- `start` / `end` -> `start_byte` / `end_byte`
In particular, `bit_offset` currently looks like the full
`BooleanBuffer::offset()`, but it is specifically `longer.offset() % 8`, which
is an important distinction in this code.
##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -269,39 +269,77 @@ pub(super) fn union_row_selections(left: &[RowSelector],
right: &[RowSelector])
/// Bitwise AND of two mask-backed selections. Longer side's tail passes
through.
pub(super) fn intersect_masks(l: &BooleanBuffer, r: &BooleanBuffer) ->
BooleanBuffer {
if l.len() == r.len() {
- return l & r;
- }
- let common = l.len().min(r.len());
- let head = &l.slice(0, common) & &r.slice(0, common);
- let (longer, longer_len) = if l.len() > r.len() {
- (l, l.len())
- } else {
- (r, r.len())
- };
- let tail = longer.slice(common, longer_len - common);
- let mut builder = BooleanBufferBuilder::new(longer_len);
- builder.append_buffer(&head);
- builder.append_buffer(&tail);
- builder.finish()
+ return combine_equal_masks(l, r, |a, b| a & b);
+ }
+ combine_uneven_masks(l, r, |a, b| a & b)
}
/// Bitwise OR of two mask-backed selections. Longer side's tail passes
through.
pub(super) fn union_masks(l: &BooleanBuffer, r: &BooleanBuffer) ->
BooleanBuffer {
if l.len() == r.len() {
- return l | r;
- }
- let common = l.len().min(r.len());
- let head = &l.slice(0, common) | &r.slice(0, common);
- let (longer, longer_len) = if l.len() > r.len() {
- (l, l.len())
- } else {
- (r, r.len())
- };
- let tail = longer.slice(common, longer_len - common);
- let mut builder = BooleanBufferBuilder::new(longer_len);
- builder.append_buffer(&head);
- builder.append_buffer(&tail);
- builder.finish()
+ return combine_equal_masks(l, r, |a, b| a | b);
+ }
+ combine_uneven_masks(l, r, |a, b| a | b)
+}
+
+/// Combines two masks of equal length with the bitwise operation `op`.
+///
+/// `BitAnd`/`BitOr` on `&BooleanBuffer` normalise the result to a zero bit
offset,
+/// which costs a second allocation and a shifting copy of the whole mask when
the
+/// operands are not byte aligned. Building the buffer directly keeps the
offset,
+/// as the uneven path does.
+fn combine_equal_masks<F>(l: &BooleanBuffer, r: &BooleanBuffer, op: F) ->
BooleanBuffer
+where
+ F: FnMut(u64, u64) -> u64,
+{
+ BooleanBuffer::from_bitwise_binary_op(
+ l.values(),
+ l.offset(),
+ r.values(),
+ r.offset(),
+ l.len(),
+ op,
+ )
+}
+
+/// Combines two masks of differing lengths with the bitwise operation `op`,
+/// passing the longer side's tail through unchanged.
+///
+/// The longer mask is copied once into a [`MutableBuffer`] and `op` is then
+/// applied in place over the common prefix. This avoids materialising the
+/// prefix into its own buffer and copying both prefix and tail again through a
+/// [`BooleanBufferBuilder`].
+///
+/// Neither the mask offsets nor the prefix length are assumed to be byte
+/// aligned: the copy keeps the longer mask's sub-byte offset so it stays a
+/// plain byte copy, and the offset is carried over to the returned buffer.
+fn combine_uneven_masks<F>(l: &BooleanBuffer, r: &BooleanBuffer, op: F) ->
BooleanBuffer
+where
+ F: FnMut(u64, u64) -> u64,
+{
+ let (longer, shorter) = if l.len() > r.len() { (l, r) } else { (r, l) };
+ let common = shorter.len();
+ if common == 0 {
Review Comment:
Is retaining the original backing allocation intentional for the
empty-common-prefix case?
`BooleanBuffer::clone()` is shallow, so if `longer` is a small slice of a
much larger buffer, the result will continue to retain the entire original
allocation. The previous builder path produced a compact copy of the logical
mask.
Avoiding the copy is attractive, but this changes the memory-retention
behavior and could be surprising when the result outlives the input selection.
Could we either document this tradeoff, add a test covering a small slice of a
large buffer, or copy only the logical byte range here?
--
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]
