You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by ze...@apache.org on 2026/09/03 16:50:22 UTC
(arrow-go) branch main updated: perf(arrow/array): SIMD-pack boolean slices into bitmaps (#1283)
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 304ac00c perf(arrow/array): SIMD-pack boolean slices into bitmaps (#1283)
304ac00c is described below
commit 304ac00c5b2e87a7f6c62942f3ca67ba1cacb7a9
Author: Minh Vu <vu...@gmail.com>
AuthorDate: Thu Sep 3 18:50:16 2026 +0200
perf(arrow/array): SIMD-pack boolean slices into bitmaps (#1283)
## Summary
- Add private AVX2 and ARM64 NEON kernels for packing `[]bool` into
Arrow bitmap bytes.
- Keep the existing scalar handling for unaligned prefixes and tails.
- Reuse the SIMD path for BooleanBuilder values and validity bitmap
packing.
- Keep noasm and unsupported architectures on the scalar implementation.
- Expand bitmap coverage across multiple SIMD blocks and offsets.
## Benchmark
Apple M1 Pro. 65,536 pre-reserved values. Representative runs:
| Benchmark | noasm | SIMD |
| --- | ---: | ---: |
| BooleanBuilder / all false | 23.4 us | 3.9 us |
| BooleanBuilder / all true | 22.6 us | 3.9 us |
| BooleanBuilder / alternating | 21.9 us | 4.6 us |
| BooleanBuilder / one in three | 22.6 us | 4.0 us |
The SIMD path is about 4 to 5x faster for this workload, with zero
allocations in both cases.
## Tests
- `go test ./arrow/array -count=1`
- `go test -race ./arrow/array -count=1`
- `go test ./arrow/bitutil ./arrow/compute/... -count=1`
- `go test -tags noasm ./arrow/array -count=1`
- `go vet ./arrow/array ./arrow/bitutil`
- `GOARCH=amd64 go test -c -o /dev/null ./arrow/array`
---
arrow/array/builder.go | 12 ++++++
arrow/array/builder_pack_amd64.go | 47 +++++++++++++++++++++++
arrow/array/builder_pack_amd64.s | 50 +++++++++++++++++++++++++
arrow/array/builder_pack_arm64.go | 47 +++++++++++++++++++++++
arrow/array/builder_pack_arm64.s | 78 +++++++++++++++++++++++++++++++++++++++
arrow/array/builder_pack_noasm.go | 24 ++++++++++++
arrow/array/builder_test.go | 8 ++--
7 files changed, 262 insertions(+), 4 deletions(-)
diff --git a/arrow/array/builder.go b/arrow/array/builder.go
index 48113f43..40e33e1e 100644
--- a/arrow/array/builder.go
+++ b/arrow/array/builder.go
@@ -237,6 +237,14 @@ func (b *builder) unsafeAppendBoolsToBitmap(valid []bool, length int) {
byteOffset++
}
+ packed := packBoolsSIMD(nullBitmap[byteOffset:], valid)
+ for i := 0; i < packed/8; i++ {
+ bitSet := nullBitmap[byteOffset+i]
+ b.nulls += 8 - bits.OnesCount8(bitSet)
+ }
+ valid = valid[packed:]
+ byteOffset += packed / 8
+
for len(valid) >= 8 {
bitSet := packBoolsByte(valid)
nullBitmap[byteOffset] = bitSet
@@ -312,6 +320,10 @@ func packBoolsToBitmap(dst []byte, offset int, values []bool) {
byteOffset++
}
+ packed := packBoolsSIMD(dst[byteOffset:], values)
+ values = values[packed:]
+ byteOffset += packed / 8
+
for len(values) >= 8 {
dst[byteOffset] = packBoolsByte(values)
values = values[8:]
diff --git a/arrow/array/builder_pack_amd64.go b/arrow/array/builder_pack_amd64.go
new file mode 100644
index 00000000..a1660e08
--- /dev/null
+++ b/arrow/array/builder_pack_amd64.go
@@ -0,0 +1,47 @@
+// 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.
+
+//go:build amd64 && !noasm && !appengine
+// +build amd64,!noasm,!appengine
+
+package array
+
+import (
+ "unsafe"
+
+ "golang.org/x/sys/cpu"
+)
+
+//go:noescape
+func _packBoolsAVX2(values, dst unsafe.Pointer, length int)
+
+func packBoolsSIMD(dst []byte, values []bool) int {
+ if !cpu.X86.HasAVX2 {
+ return 0
+ }
+
+ length := len(values) &^ 31
+ if length == 0 {
+ return 0
+ }
+
+ _packBoolsAVX2(
+ unsafe.Pointer(unsafe.SliceData(values)),
+ unsafe.Pointer(unsafe.SliceData(dst)),
+ length,
+ )
+ return length
+}
diff --git a/arrow/array/builder_pack_amd64.s b/arrow/array/builder_pack_amd64.s
new file mode 100644
index 00000000..ac8b31c6
--- /dev/null
+++ b/arrow/array/builder_pack_amd64.s
@@ -0,0 +1,50 @@
+// 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.
+
+//go:build amd64 && !noasm && !appengine
+// +build amd64,!noasm,!appengine
+
+#include "textflag.h"
+
+// func _packBoolsAVX2(values, dst unsafe.Pointer, length int)
+TEXT ·_packBoolsAVX2(SB), NOSPLIT, $0-24
+ MOVQ values+0(FP), DI
+ MOVQ dst+8(FP), SI
+ MOVQ length+16(FP), CX
+
+ // Y1 is zero. The input is a []bool, so comparing it with zero
+ // and inverting the result produces one all-ones byte per true value.
+ VPXOR Y1, Y1, Y1
+
+loop:
+ CMPQ CX, $32
+ JB done
+
+ VMOVDQU (DI), Y0
+ VPCMPEQB Y1, Y0, Y2
+ VPCMPEQB Y1, Y1, Y3
+ VPXOR Y2, Y3, Y2
+ VPMOVMSKB Y2, DX
+ MOVL DX, (SI)
+
+ ADDQ $32, DI
+ ADDQ $4, SI
+ SUBQ $32, CX
+ JMP loop
+
+done:
+ VZEROUPPER
+ RET
diff --git a/arrow/array/builder_pack_arm64.go b/arrow/array/builder_pack_arm64.go
new file mode 100644
index 00000000..d24ce1d3
--- /dev/null
+++ b/arrow/array/builder_pack_arm64.go
@@ -0,0 +1,47 @@
+// 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.
+
+//go:build arm64 && !noasm && !appengine
+// +build arm64,!noasm,!appengine
+
+package array
+
+import (
+ "unsafe"
+
+ "golang.org/x/sys/cpu"
+)
+
+//go:noescape
+func _packBoolsNEON(values, dst unsafe.Pointer, length int)
+
+func packBoolsSIMD(dst []byte, values []bool) int {
+ if !cpu.ARM64.HasASIMD {
+ return 0
+ }
+
+ length := len(values) &^ 31
+ if length == 0 {
+ return 0
+ }
+
+ _packBoolsNEON(
+ unsafe.Pointer(unsafe.SliceData(values)),
+ unsafe.Pointer(unsafe.SliceData(dst)),
+ length,
+ )
+ return length
+}
diff --git a/arrow/array/builder_pack_arm64.s b/arrow/array/builder_pack_arm64.s
new file mode 100644
index 00000000..0fa61a2c
--- /dev/null
+++ b/arrow/array/builder_pack_arm64.s
@@ -0,0 +1,78 @@
+// 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.
+
+//go:build arm64 && !noasm && !appengine
+// +build arm64,!noasm,!appengine
+
+// Each input byte is a Go bool (0 or 1). Masking nonzero values with the bit
+// weights turns each true value into its output bit's weight. VADDV then
+// reduces each group of eight weighted bytes to one Arrow bitmap byte.
+
+#include "textflag.h"
+
+DATA boolBitWeights<>+0(SB)/8, $0x8040201008040201
+GLOBL boolBitWeights<>(SB), (NOPTR+RODATA), $8
+
+// func _packBoolsNEON(values, dst unsafe.Pointer, length int)
+TEXT ·_packBoolsNEON(SB), NOSPLIT, $0-24
+ MOVD values+0(FP), R0
+ MOVD dst+8(FP), R1
+ MOVD length+16(FP), R2
+
+ MOVD $boolBitWeights<>(SB), R3
+ VLD1 (R3), [V4.B8]
+
+loop:
+ CMP $32, R2
+ BLT done
+
+ VLD1 (R0), [V0.B8]
+ ADD $8, R0, R8
+ VLD1 (R8), [V1.B8]
+ ADD $16, R0, R8
+ VLD1 (R8), [V2.B8]
+ ADD $24, R0, R8
+ VLD1 (R8), [V3.B8]
+
+ VCMTST V0.B8, V0.B8, V0.B8
+ VCMTST V1.B8, V1.B8, V1.B8
+ VCMTST V2.B8, V2.B8, V2.B8
+ VCMTST V3.B8, V3.B8, V3.B8
+ VAND V4.B8, V0.B8, V0.B8
+ VAND V4.B8, V1.B8, V1.B8
+ VAND V4.B8, V2.B8, V2.B8
+ VAND V4.B8, V3.B8, V3.B8
+ VADDV V0.B8, V0
+ VADDV V1.B8, V1
+ VADDV V2.B8, V2
+ VADDV V3.B8, V3
+
+ VMOV V0.B[0], R4
+ VMOV V1.B[0], R5
+ VMOV V2.B[0], R6
+ VMOV V3.B[0], R7
+ MOVB R4, (R1)
+ MOVB R5, 1(R1)
+ MOVB R6, 2(R1)
+ MOVB R7, 3(R1)
+
+ ADD $32, R0
+ ADD $4, R1
+ SUB $32, R2
+ B loop
+
+done:
+ RET
diff --git a/arrow/array/builder_pack_noasm.go b/arrow/array/builder_pack_noasm.go
new file mode 100644
index 00000000..4b7553f8
--- /dev/null
+++ b/arrow/array/builder_pack_noasm.go
@@ -0,0 +1,24 @@
+// 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.
+
+//go:build noasm || appengine || (!amd64 && !arm64)
+// +build noasm appengine !amd64,!arm64
+
+package array
+
+func packBoolsSIMD(dst []byte, values []bool) int {
+ return 0
+}
diff --git a/arrow/array/builder_test.go b/arrow/array/builder_test.go
index 2424c139..6773b0aa 100644
--- a/arrow/array/builder_test.go
+++ b/arrow/array/builder_test.go
@@ -70,9 +70,9 @@ func TestBuilder_UnsafeAppendBoolsToBitmap(t *testing.T) {
for _, pattern := range patterns {
for offset := 0; offset < 8; offset++ {
- for length := 1; length <= 33; length++ {
+ for _, length := range []int{1, 2, 3, 7, 8, 15, 16, 31, 32, 33, 63, 64, 65, 127, 128, 129} {
b := &builder{mem: memory.NewGoAllocator()}
- b.init(48)
+ b.init(160)
for i := range b.nullBitmap.Bytes() {
b.nullBitmap.Bytes()[i] = byte(0x5a + i*31)
}
@@ -126,8 +126,8 @@ func TestPackBoolsToBitmap(t *testing.T) {
for _, pattern := range patterns {
for offset := 0; offset < 8; offset++ {
- for length := 0; length <= 33; length++ {
- got := make([]byte, 8)
+ for _, length := range []int{0, 1, 2, 3, 7, 8, 15, 16, 31, 32, 33, 63, 64, 65, 127, 128, 129} {
+ got := make([]byte, 24)
for i := range got {
got[i] = byte(0x5a + i*31)
}