mbutrovich commented on code in PR #11879:
URL: https://github.com/apache/arrow-rs/pull/11879#discussion_r4516242565
##########
arrow-buffer/src/builder/boolean.rs:
##########
@@ -186,18 +200,17 @@ impl BooleanBufferBuilder {
#[inline]
pub fn resize(&mut self, len: usize) {
match len.checked_sub(self.len) {
- Some(delta) => self.advance(delta),
+ Some(delta) => self.advance_zeroed(delta),
None => self.truncate(len),
}
}
/// Appends a boolean `v` into the buffer
#[inline]
pub fn append(&mut self, v: bool) {
- self.advance(1);
- if v {
- unsafe { bit_util::set_bit_raw(self.buffer.as_mut_ptr(), self.len
- 1) };
- }
+ let index = self.len;
+ self.advance_zeroed(1);
+ self.buffer.as_slice_mut()[index / 8] |= u8::from(v) << (index & 7);
}
Review Comment:
`append` now reads and writes the byte twice for every value, including
`false`, which `main` never writes. Cross-compiled for x86_64, the loop does
this for each value:
```asm
cmp rdi, r13
jae .LBB0_12 ; bounds check
and byte ptr [rax + rdi], dl ; clear the padding
mov rsi, qword ptr [r15 + 24] ; reload the buffer length
cmp rdi, rsi
jae .LBB0_18 ; second bounds check
mov rax, qword ptr [r15 + 16] ; reload the buffer pointer
or byte ptr [rax + rdi], r14b ; set the bit
```
The next `append` reads the same byte, so each value waits for the previous
one's store to reach the next load. I measured a version with a single
read-modify-write per value in #12137, and on the bot's CPUs it cost a lot
whenever the values were predictable:
| Case | Xeon Platinum 8581C | Neoverse-V2 |
|---|---|---|
| `append`, all false | 0.37x | 0.67x |
| `append`, all true | 0.88x | 0.86x |
| `append`, random | 1.95x | 2.25x |
Speedup is `main` time over the branch's time. The numbers come from
https://github.com/apache/arrow-rs/pull/12137#issuecomment-6745382116 and
https://github.com/apache/arrow-rs/pull/12137#issuecomment-6745307055. This PR
does two writes per value, so I'd expect it to do no better. On an Apple M5 Max
with thin LTO, this PR measured 0.70x on all false and 0.72x on all true (the
"Local benchmarks" section of #12137). Apple silicon didn't predict the bot's
results, though, so a bot run on this PR would settle it.
Could we keep `main`'s `append` as it is and clear the padding in `advance`
only when something may have dirtied it? See the next comment.
##########
arrow-buffer/src/builder/boolean.rs:
##########
@@ -147,6 +147,20 @@ impl BooleanBufferBuilder {
self.len = new_len;
}
+ /// Advances the buffer with zeroed bits, clearing the padding at the old
end.
+ #[inline]
+ fn advance_zeroed(&mut self, additional: usize) {
+ if additional == 0 {
+ return;
+ }
+
+ let old_len = self.len;
+ self.advance(additional);
+
+ let keep_mask = (1_u8 << (old_len & 7)) - 1;
+ self.buffer.as_slice_mut()[old_len / 8] &= keep_mask;
+ }
Review Comment:
`advance_zeroed` adds a write and a bounds check to every call, which also
costs `append_slice`. On the M5 Max, many calls of 1 to 7 values measured 0.61x
to 0.64x, and calls of 8 values measured 0.78x to 0.81x (same section of
#12137).
Only `set_bit` and `as_slice_mut` can set the padding bits. A flag lets
every append skip the clear until one of them has run:
- Add a `padding_dirty: bool` field. `set_bit` does `self.padding_dirty |=
index >= self.len`, and `as_slice_mut` sets it to `true`.
- `advance` calls the clear only when the flag is set, and the clear resets
it. `append`, `append_slice`, `append_n(_, false)`, `resize`, and `append_word`
all go through `advance`. `append_word` would need to call `advance` instead of
resizing on its own. That fixes the public `advance` too. Its docs don't
promise zeroed bits, but `BooleanBuilder::append_null` and `append_nulls` call
it
([`boolean_builder.rs#L83-L95`](https://github.com/apache/arrow-rs/blob/30c5c3287cd5b99ca9aa0e46c18e0d8e09c4e2a2/arrow-array/src/builder/boolean_builder.rs#L83-L95)).
- Mark the clear `#[cold]` and `#[inline(never)]`. `#[cold]` puts the clean
case on the fall-through path. `#[inline(never)]` keeps `advance` small. With
only `#[cold]`, LLVM still inlined the clear, and under thin LTO with 16
codegen units `append_slice` stopped inlining into its callers. Short
`append_slice` calls then measured 0.86x to 0.91x on the Xeon.
https://github.com/apache/arrow-rs/blob/32fbb333e4c577ad0b03ab4ddb3c7e936cd6ec7b/arrow-buffer/src/builder/boolean.rs#L136-L180
has that version. On the Xeon
(https://github.com/apache/arrow-rs/pull/12137#issuecomment-6747325134), short
and 8-value `append_slice` calls measured 0.97x to 1.00x. Per-value `append`
measured 1.01x on all true, 0.83x on all false, 0.91x on mostly true, and 0.82x
on random. All false came out at 0.86x and 0.83x in two runs, and that's the
cost of loading and testing the flag on every value. The other per-value cases
moved by up to 10% between runs whose loops differed only in out-of-line code,
so I'd read them as layout noise until an aligned run says otherwise.
If you go this way, could you add `advance` to the test's operations? The
test in #12137 covers it, along with `append_packed_range` and
`extend_trusted_len`.
--
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]
