zeroshade commented on code in PR #1397:
URL: https://github.com/apache/arrow-go/pull/1397#discussion_r4339808081
##########
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
Review Comment:
gofmt changes this to `mask := byte((1<<leading)-1) << bitOffset`; that is
exactly what the Lint job is failing on.
##########
arrow/bitutil/count_set_bits_offset_test.go:
##########
@@ -0,0 +1,83 @@
+// 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 (
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+)
+
+func TestCountSetBitsOffsetByteBoundaries(t *testing.T) {
+ for _, size := range []int{1, 2, 9, 65, 129} {
Review Comment:
Please add nil and empty buffers with `n == 0` and offsets past the end (for
example 1, 8, 64 and `math.MaxInt`). Removing the new length-0 early return
still passes this test, but `CountSetBits(nil, 1, 0)` then panics.
##########
arrow/bitutil/count_set_bits_offset_test.go:
##########
@@ -0,0 +1,83 @@
+// 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 (
+ "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)
+ }
+ }
+ }
+ }
+ }
+}
+
+var countSetBitsOffsetResult int
+
+func BenchmarkCountSetBitsOffsetByteMask(b *testing.B) {
+ for _, tc := range []struct {
+ name string
+ offset int
+ n int
+ }{
+ {"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 i := 0; i < b.N; i++ {
Review Comment:
Nit: please use `for b.Loop()`; go.mod already requires Go 1.26. These tests
could also live in `bitutil_test.go` rather than a new file.
##########
arrow/bitutil/count_set_bits_offset_test.go:
##########
@@ -0,0 +1,83 @@
+// 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 (
+ "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)
+ }
+ }
+ }
+ }
+ }
+}
+
+var countSetBitsOffsetResult int
+
+func BenchmarkCountSetBitsOffsetByteMask(b *testing.B) {
+ for _, tc := range []struct {
+ name string
+ offset int
+ n int
+ }{
+ {"5-bits-offset-3", 3, 5},
Review Comment:
Could you include `{offset: 7, n: 2}`, `{offset: 8, n: 1}` and `{offset: 63,
n: 2}`? Pinned runs showed those about 38%, 25% and 19% slower than `main`
(non-overlapping ranges), so the tradeoff should be visible in the benchmark.
--
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]
