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 d65b0db1 perf(parquet/internal/encoding): expand nullable boolean
bitmaps by byte (#1405)
d65b0db1 is described below
commit d65b0db1606c391ea9cce5677780c8cd6f52eb78
Author: Minh Vu <[email protected]>
AuthorDate: Fri Oct 23 18:57:34 2026 +0200
perf(parquet/internal/encoding): expand nullable boolean bitmaps by byte
(#1405)
## What
Expand nullable boolean bitmaps eight values at a time.
## Why
The dense-null path currently reads and writes each bit individually.
## Implementation
- Use a 256-byte lookup to deposit packed values into valid positions by
byte.
- Keep the sparse-null path unchanged and preserve overlap and
surrounding bits.
- Add offset and null-pattern parity coverage.
## Benchmark
The per-bit and byte paths both include the initial output-buffer copy.
Go 1.26.3, Apple M1 Pro (`darwin/arm64`), `GOMAXPROCS=1`; 10 runs of 150
ms per case.
| Metric | Before | After | Change |
| --- | ---: | ---: | ---: |
| 64 Ki values, 50% null, offset 0 | 204.39 µs/op | 34.70 µs/op |
-83.03% |
| 64 Ki values, 50% null, offset 5 | 203.34 µs/op | 36.82 µs/op |
-81.89% |
| 64 Ki values, 14.3% null, offset 0 | 302.05 µs/op | 37.53 µs/op |
-87.58% |
| 64 Ki values, 14.3% null, offset 5 | 300.81 µs/op | 37.19 µs/op |
-87.64% |
| 1 Mi values, 50% null, offset 0 | 3.336 ms/op | 555.0 µs/op | -83.36%
|
| 1 Mi values, 50% null, offset 5 | 3.337 ms/op | 585.9 µs/op | -82.44%
|
| 1 Mi values, 14.3% null, offset 0 | 5.112 ms/op | 600.6 µs/op |
-88.25% |
| 1 Mi values, 14.3% null, offset 5 | 5.043 ms/op | 597.1 µs/op |
-88.16% |
| Geometric mean, 8 cases | 1.010 ms/op | 146.1 µs/op | -85.53% |
All cases use 0 B/op and 0 allocs/op. Command: `GOMAXPROCS=1 go test
./parquet/internal/encoding -run '^$' -bench
'^BenchmarkSpacedBitmapExpansion$' -benchmem -benchtime=150ms -count=10
-cpu=1`.
---
.../internal/encoding/boolean_bitmap_deposit.go | 90 ++++++++++++++++++++
.../encoding/boolean_bitmap_deposit_test.go | 96 ++++++++++++++++++++++
parquet/internal/encoding/boolean_decoder.go | 2 +-
3 files changed, 187 insertions(+), 1 deletion(-)
diff --git a/parquet/internal/encoding/boolean_bitmap_deposit.go
b/parquet/internal/encoding/boolean_bitmap_deposit.go
new file mode 100644
index 00000000..4d8dce6d
--- /dev/null
+++ b/parquet/internal/encoding/boolean_bitmap_deposit.go
@@ -0,0 +1,90 @@
+// 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 encoding
+
+import "math/bits"
+
+// nibbleBitDeposit deposits up to four packed bits into the set positions of
+// a four-bit mask. The table is only 256 bytes and works on every
architecture.
+var nibbleBitDeposit = func() [256]byte {
+ var table [256]byte
+ for mask := 0; mask < 16; mask++ {
+ for packed := 0; packed < 16; packed++ {
+ source := byte(packed)
+ var deposited byte
+ for bit := uint(0); bit < 4; bit++ {
+ if mask&(1<<bit) != 0 {
+ if source&1 != 0 {
+ deposited |= 1 << bit
+ }
+ source >>= 1
+ }
+ }
+ table[mask<<4|packed] = deposited
+ }
+ }
+ return table
+}()
+
+func depositBitmapByte(packed, valid byte) byte {
+ low := valid & 15
+ high := valid >> 4
+ return nibbleBitDeposit[int(low)<<4|int(packed&15)] |
+
nibbleBitDeposit[int(high)<<4|int((packed>>bits.OnesCount8(low))&15)]<<4
+}
+
+// expandSpacedBitmapByByte expands compacted boolean values in-place.
+// Only valid output bits are touched; nulls and bits outside the range are
+// left unchanged. The compressed bits start at outOffset+nullCount, so source
+// bits for the current output byte are always at or after its destination.
+func expandSpacedBitmapByByte(out []byte, outOffset int64, length, nullCount
int,
+ validBits []byte, validBitsOffset int64) {
+ outputPos := int(outOffset)
+ validPos := int(validBitsOffset)
+ physicalPos := outputPos + nullCount
+
+ for remaining := length; remaining > 0; {
+ destShift := outputPos & 7
+ count := min(remaining, 8-destShift)
+
+ validByte := validBits[validPos>>3] >> (validPos & 7)
+ if (validPos&7)+count > 8 {
+ validByte |= validBits[(validPos>>3)+1] << (8 -
(validPos & 7))
+ }
+ validByte &= byte((1 << count) - 1)
+
+ setBits := bits.OnesCount8(validByte)
+ if setBits != 0 {
+ // Read the full packed source segment before writing
the output
+ // byte, which also makes overlapping
source/destination safe.
+ packed := out[physicalPos>>3] >> (physicalPos & 7)
+ if (physicalPos&7)+setBits > 8 {
+ packed |= out[(physicalPos>>3)+1] << (8 -
(physicalPos & 7))
+ }
+
+ deposited := depositBitmapByte(packed, validByte)
+ mask := validByte << destShift
+ byteIndex := outputPos >> 3
+ out[byteIndex] = (out[byteIndex] &^ mask) | (deposited
<< destShift)
+ physicalPos += setBits
+ }
+
+ outputPos += count
+ validPos += count
+ remaining -= count
+ }
+}
diff --git a/parquet/internal/encoding/boolean_bitmap_deposit_test.go
b/parquet/internal/encoding/boolean_bitmap_deposit_test.go
new file mode 100644
index 00000000..ebb46b70
--- /dev/null
+++ b/parquet/internal/encoding/boolean_bitmap_deposit_test.go
@@ -0,0 +1,96 @@
+// 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 encoding
+
+import (
+ "bytes"
+ "fmt"
+ "math/rand"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+)
+
+func makeSpacedBitmapCase(length, outOffset, validOffset, nullEvery int)
([]byte, []byte, int) {
+ valid := bytes.Repeat([]byte{0xa5}, (validOffset+length+15)/8)
+ out := bytes.Repeat([]byte{0x3c}, (outOffset+length+15)/8)
+ nulls := 0
+ rng := rand.New(rand.NewSource(23))
+ for i := 0; i < length; i++ {
+ isValid := nullEvery == 0 || (nullEvery > 0 && i%nullEvery !=
0) ||
+ (nullEvery == -1 && rng.Intn(2) == 0)
+ bitutil.SetBitTo(valid, validOffset+i, isValid)
+ if !isValid {
+ nulls++
+ }
+ }
+ for i := 0; i < length-nulls; i++ {
+ bitutil.SetBitTo(out, outOffset+nulls+i, rng.Intn(2) == 0)
+ }
+ return out, valid, nulls
+}
+
+func TestExpandSpacedBitmapByByteParity(t *testing.T) {
+ for _, length := range []int{0, 1, 2, 3, 7, 8, 9, 15, 16, 17, 31, 32,
33, 63, 64, 65, 127, 128, 129, 4096} {
+ for outOffset := 0; outOffset < 8; outOffset++ {
+ for validOffset := 0; validOffset < 8; validOffset++ {
+ for _, nullEvery := range []int{0, 1, 2, 3, 7,
9, -1} {
+ out, valid, nulls :=
makeSpacedBitmapCase(length, outOffset, validOffset, nullEvery)
+ want := bytes.Clone(out)
+ got := bytes.Clone(out)
+ expandSpacedBitmapPerBit(want,
int64(outOffset), length, nulls, valid, int64(validOffset))
+ expandSpacedBitmapByByte(got,
int64(outOffset), length, nulls, valid, int64(validOffset))
+ if !bytes.Equal(got, want) {
+ t.Fatalf("length=%d
outOffset=%d validOffset=%d nullEvery=%d nulls=%d: got %x, want %x",
+ length, outOffset,
validOffset, nullEvery, nulls, got, want)
+ }
+ }
+ }
+ }
+ }
+}
+
+var spacedBitmapBenchmarkSink []byte
+
+func BenchmarkSpacedBitmapExpansion(b *testing.B) {
+ for _, length := range []int{64 * 1024, 1024 * 1024} {
+ for _, nullEvery := range []int{2, 7} {
+ for _, offset := range []int{0, 5} {
+ source, valid, nulls :=
makeSpacedBitmapCase(length, offset, offset+1, nullEvery)
+ for _, implementation := range []struct {
+ name string
+ fn func([]byte, int64, int, int,
[]byte, int64)
+ }{
+ {"baseline_per_bit",
expandSpacedBitmapPerBit},
+ {"byte_deposit",
expandSpacedBitmapByByte},
+ } {
+
b.Run(fmt.Sprintf("length_%d/null_every_%d/offset_%d/%s", length, nullEvery,
offset, implementation.name), func(b *testing.B) {
+ out := make([]byte, len(source))
+ b.ReportAllocs()
+ b.SetBytes(int64(length))
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ copy(out, source)
+ implementation.fn(out,
int64(offset), length, nulls, valid, int64(offset+1))
+ }
+ spacedBitmapBenchmarkSink = out
+ })
+ }
+ }
+ }
+ }
+}
diff --git a/parquet/internal/encoding/boolean_decoder.go
b/parquet/internal/encoding/boolean_decoder.go
index a3b51665..69c8ce99 100644
--- a/parquet/internal/encoding/boolean_decoder.go
+++ b/parquet/internal/encoding/boolean_decoder.go
@@ -280,7 +280,7 @@ func decodeSpacedToBitmap(dec BooleanBitmapDecoder, out
[]byte, outOffset int64,
perBitThreshold++
}
if nullCount >= perBitThreshold {
- expandSpacedBitmapPerBit(out, outOffset, length, nullCount,
validBits, validBitsOffset)
+ expandSpacedBitmapByByte(out, outOffset, length, nullCount,
validBits, validBitsOffset)
return length, nil
}
