mbutrovich opened a new pull request, #12137: URL: https://github.com/apache/arrow-rs/pull/12137
# Which issue does this PR close? - Closes #12136. Supersedes #11879. The test here is adapted from that PR. # Rationale for this change #11879 clears the padding in an extra write before each append, which costs `append` a second write and bounds check per value. This PR clears the padding in the write each append already does. `append` also stops [branching on the value](https://github.com/apache/arrow-rs/blob/30c5c3287cd5b99ca9aa0aec57509d076eb07347/arrow-buffer/src/builder/boolean.rs#L183-L188). # What changes are included in this PR? - `append` masks out the bit and the padding above it and sets the bit in one write. - `append_slice` masks the padding in its write to the first byte. Later bytes come zeroed from the resize. - `advance` clears the padding before it grows, which fixes `append_n(_, false)`, `resize`, and `append_word`. # Are these changes tested? `test_append_false_with_dirty_padding` sets the padding bits with `set_bit`, then appends `false` with each append method. The first commit adds per-value `append` cases to the `boolean_buffer_builder` and `null_buffer_builder` benchmarks. TODO: benchmark bot results. On an Apple M5 Max, `append` on random values is 1.68x faster than `main` in the `bench` profile and 5.12x faster with thin LTO and `codegen-units = 1`. Constant values are 0.96x to 1.04x and 1.08x to 1.15x. Many short `append_slice` calls are 0.94x to 0.98x, and per-value `NullBufferBuilder` appends with nulls are 0.97x to 0.99x. <details><summary>Local benchmarks</summary> The baseline is `main` at 30c5c3287c. #11879 was rebased onto the same commit and measured in a separate run, in which `main` matched within 3%. Runs with `-C llvm-args=-align-all-functions=7 -C llvm-args=-align-all-nofallthru-blocks=7` on both sides matched within 3%. `NullBufferBuilder` passes a constant to `append`, so it gains nothing from the removed branch, and each null now writes its byte. The all-valid case builds no bitmap and doesn't reach the changed code, so it shows each run's noise. TODO: drag in `boolean-padding-local-bench.png` TODO: drag in `boolean-padding-local-lto.png` </details> <details><summary>Generated code for <code>append</code></summary> `append` inlined into a loop over a `&[bool]`, from the capacity check to the byte store. Built with rustc 1.99.1 in release mode with `codegen-units = 1`. aarch64-apple-darwin, `main`: ```asm str x25, [x21, #32] ; len += 1 tbz w24, #0, LBB0_2 ; v == false: skip the write ldr x8, [x21, #16] and x9, x23, #0x7 lsl w9, w22, w9 ; 1 << bit lsr x10, x23, #3 ldrb w11, [x8, x10] orr w9, w11, w9 strb w9, [x8, x10] ``` aarch64-apple-darwin, #11879: ```asm str x26, [x21, #32] ; len += 1 lsr x0, x25, #3 cmp x0, x22 b.hs LBB0_15 ; bounds check ldr x8, [x21, #16] and x9, x25, #0x7 ldrb w10, [x8, x0] lsl w9, w23, w9 ; -1 << bit bic w9, w10, w9 strb w9, [x8, x0] ; first write: clear padding ldr x1, [x21, #24] ; reload buffer length cmp x0, x1 b.hs LBB0_14 ; second bounds check and w8, w25, #0x7 ldr x9, [x21, #16] ; reload buffer pointer lsl w8, w24, w8 ; v << bit add x20, x20, #1 ldrb w10, [x9, x0] ; reload the byte just stored orr w8, w10, w8 strb w8, [x9, x0] ; second write: set bit ``` aarch64-apple-darwin, this PR: ```asm str x25, [x21, #32] ; len += 1 ldr x8, [x21, #16] lsr x9, x24, #3 ldrb w10, [x8, x9] and x11, x24, #0x7 lsl w12, w22, w11 ; -1 << bit bic w10, w10, w12 ; clear bit and padding lsl w11, w23, w11 ; v << bit orr w10, w10, w11 strb w10, [x8, x9] ; one write ``` x86_64-unknown-linux-gnu, `main`: ```asm mov qword ptr [r15 + 32], rbx # len += 1 test bpl, bpl je .LBB0_12 # v == false: skip the write mov rax, qword ptr [r15 + 16] mov ecx, r12d and cl, 7 mov dl, 1 shl dl, cl # 1 << bit shr r12, 3 or byte ptr [rax + r12], dl ``` x86_64-unknown-linux-gnu, #11879: ```asm mov qword ptr [r15 + 32], rbx # len += 1 mov rdi, r12 shr rdi, 3 cmp rdi, r13 jae .LBB0_12 # bounds check mov rax, qword ptr [r15 + 16] and r12b, 7 mov dl, -1 mov ecx, r12d shl dl, cl not dl and byte ptr [rax + rdi], dl # first write: clear padding mov rsi, qword ptr [r15 + 24] # reload buffer length cmp rdi, rsi jae .LBB0_18 # second bounds check mov ecx, r12d shl r14b, cl # v << bit mov rax, qword ptr [r15 + 16] # reload buffer pointer or byte ptr [rax + rdi], r14b # second write: set bit ``` x86_64-unknown-linux-gnu, this PR: ```asm mov qword ptr [r15 + 32], rbx # len += 1 mov rax, qword ptr [r15 + 16] mov rdx, r12 and r12b, 7 mov dil, -1 mov ecx, r12d shl dil, cl shr rdx, 3 not dil and dil, byte ptr [rax + rdx] # clear bit and padding shl r13b, cl # v << bit or r13b, dil mov byte ptr [rax + rdx], r13b # one write ``` </details> # Are there any significant user-facing changes? `advance` now documents that the new bits are `false`. -- 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]
