This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-go.git
The following commit(s) were added to refs/heads/main by this push:
new a76f844a perf(arrow/bitutil): count offset bits by byte mask (#1397)
a76f844a is described below
commit a76f844aeb4a75423a9c1e58cbd33223d119220a
Author: Minh Vu <[email protected]>
AuthorDate: Thu Oct 22 19:56:05 2026 +0200
perf(arrow/bitutil): count offset bits by byte mask (#1397)
## What
Count unaligned bitmap bits with a byte mask.
## Why
The current path checks leading bits one at a time before word popcount.
## Implementation
- Count the first partial byte with a mask and `bits.OnesCount8`.
- Keep the existing bulk path for the remaining bits.
## Benchmark
Go 1.26.3, Apple M1 Pro (`darwin/arm64`), median of five runs; 0 B/op
and 0 allocs/op.
| Metric | Before | After | Change |
| --- | ---: | ---: | ---: |
| 5 bits, offset 3 | 10.88 ns/op | 2.92 ns/op | -73.2% |
| 8,192 bits, offset 3 | 124.4 ns/op | 80.18 ns/op | -35.5% |
---------
Co-authored-by: Matt Topol <[email protected]>
---
arrow/bitutil/bitutil.go | 30 ++++----
arrow/bitutil/count_set_bits_offset_test.go | 106 ++++++++++++++++++++++++++++
2 files changed, 121 insertions(+), 15 deletions(-)
diff --git a/arrow/bitutil/bitutil.go b/arrow/bitutil/bitutil.go
index da0d98b3..674a0a4d 100644
--- a/arrow/bitutil/bitutil.go
+++ b/arrow/bitutil/bitutil.go
@@ -168,24 +168,24 @@ func BitmapAllSet(buf []byte, offset, n int) bool {
}
func countSetBitsWithOffset(buf []byte, offset, n int) int {
- count := 0
-
- beg := offset
- begU8 := roundUp(beg, uint64SizeBits)
-
- init := min(n, begU8-beg)
- for i := offset; i < beg+init; i++ {
- if BitIsSet(buf, i) {
- count++
- }
+ if n == 0 {
+ return 0
}
- begU64 := BytesForBits(int64(beg + init))
- return count + CountSetBits(buf[begU64:], 0, n-init)
-}
+ byteOffset := offset / 8
+ bitOffset := offset & 7
+ if bitOffset == 0 {
+ return CountSetBits(buf[byteOffset:], 0, n)
+ }
-func roundUp(v, f int) int {
- return (v + (f - 1)) / f * f
+ // Count the partial first byte, then use the word-based path for the
rest.
+ leading := min(n, 8-bitOffset)
+ mask := byte((1<<leading)-1) << bitOffset
+ count := bits.OnesCount8(buf[byteOffset] & mask)
+ if leading == n {
+ return count
+ }
+ return count + CountSetBits(buf[byteOffset+1:], 0, n-leading)
}
func min(a, b int) int {
diff --git a/arrow/bitutil/count_set_bits_offset_test.go
b/arrow/bitutil/count_set_bits_offset_test.go
new file mode 100644
index 00000000..87351bd2
--- /dev/null
+++ b/arrow/bitutil/count_set_bits_offset_test.go
@@ -0,0 +1,106 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bitutil_test
+
+import (
+ "math"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+)
+
+func TestCountSetBitsOffsetByteBoundaries(t *testing.T) {
+ for _, size := range []int{1, 2, 9, 65, 129} {
+ for storageOffset := 0; storageOffset < 8; storageOffset++ {
+ storage := make([]byte, storageOffset+size)
+ bitmap := storage[storageOffset:]
+ for i := range bitmap {
+ bitmap[i] = byte(i*73 + 31)
+ }
+
+ for offset := 0; offset <= len(bitmap)*8; offset++ {
+ available := len(bitmap)*8 - offset
+ for _, n := range []int{0, 1, 2, 3, 7, 8, 9,
15, 16, 31, 32, 63, 64, 65, 127, available} {
+ if n > available {
+ continue
+ }
+ want := 0
+ for i := offset; i < offset+n; i++ {
+ if bitutil.BitIsSet(bitmap, i) {
+ want++
+ }
+ }
+ if got := bitutil.CountSetBits(bitmap,
offset, n); got != want {
+ t.Fatalf("size=%d
storageOffset=%d offset=%d n=%d: got=%d want=%d",
+ size, storageOffset,
offset, n, got, want)
+ }
+ }
+ }
+ }
+ }
+}
+
+func TestCountSetBitsZeroLength(t *testing.T) {
+ for _, tc := range []struct {
+ name string
+ buf []byte
+ }{
+ {"nil", nil},
+ {"empty", []byte{}},
+ {"nonempty", []byte{0xff}},
+ } {
+ t.Run(tc.name, func(t *testing.T) {
+ for _, offset := range []int{0, 1, 8, 64, math.MaxInt} {
+ if got := bitutil.CountSetBits(tc.buf, offset,
0); got != 0 {
+ t.Fatalf("offset=%d: got=%d, want=0",
offset, got)
+ }
+ }
+ })
+ }
+}
+
+var countSetBitsOffsetResult int
+
+func BenchmarkCountSetBitsOffsetByteMask(b *testing.B) {
+ for _, tc := range []struct {
+ name string
+ offset int
+ n int
+ }{
+ {"2-bits-offset-7", 7, 2},
+ {"1-bit-offset-8", 8, 1},
+ {"2-bits-offset-63", 63, 2},
+ {"5-bits-offset-3", 3, 5},
+ {"32-bits-offset-3", 3, 32},
+ {"32-bits-offset-8", 8, 32},
+ {"128-bits-offset-37", 37, 128},
+ {"8192-bits-offset-3", 3, 8192},
+ } {
+ b.Run(tc.name, func(b *testing.B) {
+ bitmap := make([]byte, (tc.offset+tc.n+7)/8)
+ for i := range bitmap {
+ bitmap[i] = byte(i*73 + 31)
+ }
+ b.ReportAllocs()
+ var result int
+ for b.Loop() {
+ result = bitutil.CountSetBits(bitmap,
tc.offset, tc.n)
+ }
+ countSetBitsOffsetResult = result
+ })
+ }
+}
