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 e4fa4882 perf(parquet): encode spaced booleans without compaction
(#1175)
e4fa4882 is described below
commit e4fa4882726348b90e41d8e6bc783e34bd046aca
Author: Minh Vu <[email protected]>
AuthorDate: Fri Aug 14 18:18:51 2026 +0200
perf(parquet): encode spaced booleans without compaction (#1175)
### Rationale for this change
Plain Boolean spaced encoding currently counts valid bits, allocates a
compacted bitmap, copies valid runs into it, and then copies that bitmap
into the encoder buffer.
Short unaligned runs also create bitmap readers and writers for every
copy. This is expensive for common nullable patterns.
### What changes are included in this PR?
- Append valid bitmap runs directly to the existing encoder buffer.
- Accumulate the valid count while encoding instead of scanning validity
first.
- Write short runs directly to avoid unaligned bitmap-copy allocations.
- Keep bulk bitmap copies for longer runs.
- Share bitmap writer initialization between the Boolean input paths.
- Add benchmarks for 1K, 64K, and 1M values across several null
patterns.
- Add tests for bitmap offsets, validity offsets, encoder-buffer
boundaries, and repeated calls.
Apple M1 Pro results for 65,536 values with `-cpu=1`:
| Validity pattern | Before | After | Speedup |
| --- | ---: | ---: | ---: |
| All valid | 6.77 us | 3.00 us | 2.26x |
| 1% null | 224 us | 182 us | 1.23x |
| 10% null | 912 us | 307 us | 2.97x |
| Alternating 50% null | 3.86 ms | 394 us | 9.79x |
| 90% null | 1.16 ms | 95.8 us | 12.1x |
| Clustered nulls | 7.53 us | 3.65 us | 2.06x |
For the short-run patterns:
- 10% null: 847 KB and 13,109 allocations to 23 B and 0 allocations.
- 50% null: 4.20 MB and 65,542 allocations to 14 B and 0 allocations.
- 90% null: 735 KB and 11,469 allocations to 0 B and 0 allocations.
### Are these changes tested?
Yes.
- `go test ./parquet/...`
- `go test -race ./parquet/internal/encoding`
- `go vet -composites=false ./parquet/internal/encoding`
- Cross-compiled the encoding tests for linux/amd64 and linux/s390x.
### Are there any user-facing changes?
No.
---
parquet/internal/encoding/boolean_encoder.go | 117 +++++++------
.../encoding/boolean_encoder_benchmark_test.go | 101 +++++++++++
.../encoding/boolean_encoder_spaced_test.go | 192 +++++++++++++++++++++
3 files changed, 353 insertions(+), 57 deletions(-)
diff --git a/parquet/internal/encoding/boolean_encoder.go
b/parquet/internal/encoding/boolean_encoder.go
index e012b98a..a4111804 100644
--- a/parquet/internal/encoding/boolean_encoder.go
+++ b/parquet/internal/encoding/boolean_encoder.go
@@ -27,45 +27,11 @@ import (
)
const (
- boolBufSize = 1024
- boolsInBuf = boolBufSize * 8
+ boolBufSize = 1024
+ boolsInBuf = boolBufSize * 8
+ scalarBitmapRunLimit = 32
)
-// compressBitmapWithValidity extracts only the valid bits from a source
bitmap,
-// compressing it into a contiguous destination bitmap. Uses SetBitRunReader
for
-// efficient iteration over valid runs.
-func compressBitmapWithValidity(
- srcBitmap []byte,
- srcOffset int64,
- numValues int64,
- validBits []byte,
- validBitsOffset int64,
- numValid int64,
-) []byte {
- if numValid == 0 {
- return []byte{}
- }
-
- // Allocate destination bitmap to hold only valid bits
- dstBitmap := make([]byte, bitutil.BytesForBits(numValid))
- dstWriter := utils.NewBitmapWriter(dstBitmap, 0, int(numValid))
-
- // Use SetBitRunReader to efficiently iterate over valid runs
- reader := bitutils.NewSetBitRunReader(validBits, validBitsOffset,
numValues)
- for {
- run := reader.NextRun()
- if run.Length == 0 {
- break
- }
-
- // Copy this run of valid bits from source to destination
- dstWriter.AppendBitmap(srcBitmap, srcOffset+run.Pos, run.Length)
- }
-
- dstWriter.Finish()
- return dstBitmap
-}
-
// PlainBooleanEncoder encodes bools as a bitmap as per the Plain Encoding
type PlainBooleanEncoder struct {
encoder
@@ -80,12 +46,7 @@ func (PlainBooleanEncoder) Type() parquet.Type {
// Put encodes the contents of in into the underlying data buffer.
func (enc *PlainBooleanEncoder) Put(in []bool) {
- if enc.bitsBuffer == nil {
- enc.bitsBuffer = make([]byte, boolBufSize)
- }
- if enc.wr == nil {
- enc.wr = utils.NewBitmapWriter(enc.bitsBuffer, 0, boolsInBuf)
- }
+ enc.initBitmapWriter()
if len(in) == 0 {
return
}
@@ -100,15 +61,19 @@ func (enc *PlainBooleanEncoder) Put(in []bool) {
}
}
-// PutBitmap encodes boolean values directly from a bitmap without converting
to []bool.
-// This avoids the 8x memory overhead of bool slices.
-func (enc *PlainBooleanEncoder) PutBitmap(bitmap []byte, offset int64, length
int64) {
+func (enc *PlainBooleanEncoder) initBitmapWriter() {
if enc.bitsBuffer == nil {
enc.bitsBuffer = make([]byte, boolBufSize)
}
if enc.wr == nil {
enc.wr = utils.NewBitmapWriter(enc.bitsBuffer, 0, boolsInBuf)
}
+}
+
+// PutBitmap encodes boolean values directly from a bitmap without converting
to []bool.
+// This avoids the 8x memory overhead of bool slices.
+func (enc *PlainBooleanEncoder) PutBitmap(bitmap []byte, offset int64, length
int64) {
+ enc.initBitmapWriter()
if length == 0 {
return
}
@@ -127,6 +92,24 @@ func (enc *PlainBooleanEncoder) PutBitmap(bitmap []byte,
offset int64, length in
}
}
+func (enc *PlainBooleanEncoder) putBitmapScalar(bitmap []byte, offset, length
int64) {
+ enc.initBitmapWriter()
+ for i := int64(0); i < length; i++ {
+ if enc.wr.Pos() == boolsInBuf {
+ enc.wr.Finish()
+ enc.append(enc.bitsBuffer)
+ enc.wr.Reset(0, boolsInBuf)
+ }
+ if bitutil.BitIsSet(bitmap, int(offset+i)) {
+ enc.wr.Set()
+ } else {
+ enc.wr.Clear()
+ }
+ enc.wr.Next()
+ }
+ enc.wr.Finish()
+}
+
// PutSpaced will use the validBits bitmap to determine which values are nulls
// and can be left out from the slice, and the encoded without those nulls.
func (enc *PlainBooleanEncoder) PutSpaced(in []bool, validBits []byte,
validBitsOffset int64) {
@@ -137,24 +120,44 @@ func (enc *PlainBooleanEncoder) PutSpaced(in []bool,
validBits []byte, validBits
// PutSpacedBitmap encodes boolean values directly from a bitmap with validity
information,
// without converting to []bool. This avoids the 8x memory overhead of bool
slices.
-// It compresses the bitmap by extracting only valid (non-null) bits.
+// It appends valid runs directly to the encoder bitmap.
func (enc *PlainBooleanEncoder) PutSpacedBitmap(bitmap []byte, bitmapOffset
int64, numValues int64, validBits []byte, validBitsOffset int64) int64 {
if numValues == 0 {
return 0
}
- // Count the number of valid values to pre-allocate destination bitmap
- numValid := int64(bitutil.CountSetBits(validBits, int(validBitsOffset),
int(numValues)))
- if numValid == 0 {
- return 0
+ numValid := int64(0)
+ reader := bitutils.NewSetBitRunReader(validBits, validBitsOffset,
numValues)
+ for {
+ run := reader.NextRun()
+ if run.Length == 0 {
+ break
+ }
+ // Bitmap copies need word readers for unaligned ranges. Keep
the
+ // scalar path for short runs unless the run is an exact byte
multiple:
+ // when both ranges are byte-aligned, PutBitmap uses a cheaper
byte copy.
+ switch run.Length {
+ case 8, 16, 24:
+ srcOffset := bitmapOffset + run.Pos
+ dstOffset := int64(0)
+ if enc.wr != nil {
+ dstOffset = int64(enc.wr.Pos())
+ }
+ if srcOffset%8 != 0 || dstOffset%8 != 0 {
+ enc.putBitmapScalar(bitmap, srcOffset,
run.Length)
+ } else {
+ enc.PutBitmap(bitmap, srcOffset, run.Length)
+ }
+ default:
+ if run.Length < scalarBitmapRunLimit {
+ enc.putBitmapScalar(bitmap,
bitmapOffset+run.Pos, run.Length)
+ } else {
+ enc.PutBitmap(bitmap, bitmapOffset+run.Pos,
run.Length)
+ }
+ }
+ numValid += run.Length
}
- // Compress bitmap: extract only valid bits
- compressedBitmap := compressBitmapWithValidity(bitmap, bitmapOffset,
numValues, validBits, validBitsOffset, numValid)
-
- // Encode the compressed bitmap
- enc.PutBitmap(compressedBitmap, 0, numValid)
-
return numValid
}
diff --git a/parquet/internal/encoding/boolean_encoder_benchmark_test.go
b/parquet/internal/encoding/boolean_encoder_benchmark_test.go
new file mode 100644
index 00000000..e9d8d491
--- /dev/null
+++ b/parquet/internal/encoding/boolean_encoder_benchmark_test.go
@@ -0,0 +1,101 @@
+// 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_test
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/apache/arrow-go/v18/parquet"
+ "github.com/apache/arrow-go/v18/parquet/internal/encoding"
+)
+
+func BenchmarkPlainBooleanEncoderPutSpacedBitmap(b *testing.B) {
+ patterns := []struct {
+ name string
+ bitmapOffset int
+ valid func(int) bool
+ }{
+ {name: "all_valid", valid: func(int) bool { return true }},
+ {name: "one_percent_null", valid: func(i int) bool { return
i%100 != 0 }},
+ {name: "ten_percent_null", valid: func(i int) bool { return
i%10 != 0 }},
+ {name: "fifty_percent_null", valid: func(i int) bool { return
i%2 != 0 }},
+ {name: "ninety_percent_null", valid: func(i int) bool { return
i%10 == 0 }},
+ {name: "clustered", valid: func(i int) bool { return i%1024 >=
256 }},
+ {
+ name: "eight_valid_eight_null_aligned",
+ valid: func(i int) bool { return i%16 < 8 },
+ },
+ {
+ name: "eight_valid_eight_null_unaligned",
+ bitmapOffset: 1,
+ valid: func(i int) bool { return i%16 < 8 },
+ },
+ {
+ name: "twenty_four_valid_eight_null_aligned",
+ valid: func(i int) bool { return i%32 < 24 },
+ },
+ {
+ name: "twenty_four_valid_eight_null_unaligned",
+ bitmapOffset: 1,
+ valid: func(i int) bool { return i%32 < 24 },
+ },
+ }
+
+ for _, length := range []int{1024, 64 * 1024, 1024 * 1024} {
+ b.Run(fmt.Sprintf("length_%d", length), func(b *testing.B) {
+ for _, pattern := range patterns {
+ b.Run(pattern.name, func(b *testing.B) {
+ bitmap := makeBooleanBitmap(length,
pattern.bitmapOffset, func(i int) bool { return i%3 != 0 })
+ validity := makeBooleanBitmap(length,
0, pattern.valid)
+ expectedValid :=
int64(bitutil.CountSetBits(validity, 0, length))
+ encoder := encoding.NewEncoder(
+ parquet.Types.Boolean,
parquet.Encodings.Plain,
+ false, nil,
memory.DefaultAllocator,
+ ).(encoding.BooleanEncoder)
+ spaced := encoder.(spacedBitmapEncoder)
+
+ b.ReportAllocs()
+ b.SetBytes(int64(length))
+ b.ResetTimer()
+ for b.Loop() {
+ if actual :=
spaced.PutSpacedBitmap(bitmap, int64(pattern.bitmapOffset), int64(length),
validity, 0); actual != expectedValid {
+ b.Fatalf("expected %d
valid values, got %d", expectedValid, actual)
+ }
+ buf, err :=
encoder.FlushValues()
+ if err != nil {
+ b.Fatal(err)
+ }
+ buf.Release()
+ }
+ })
+ }
+ })
+ }
+}
+
+func makeBooleanBitmap(length, offset int, value func(int) bool) []byte {
+ bitmap := make([]byte, bitutil.BytesForBits(int64(length+offset)))
+ for i := range length {
+ if value(i) {
+ bitutil.SetBit(bitmap, offset+i)
+ }
+ }
+ return bitmap
+}
diff --git a/parquet/internal/encoding/boolean_encoder_spaced_test.go
b/parquet/internal/encoding/boolean_encoder_spaced_test.go
new file mode 100644
index 00000000..dde8fe6d
--- /dev/null
+++ b/parquet/internal/encoding/boolean_encoder_spaced_test.go
@@ -0,0 +1,192 @@
+// 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_test
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/apache/arrow-go/v18/parquet"
+ "github.com/apache/arrow-go/v18/parquet/internal/encoding"
+ "github.com/stretchr/testify/assert"
+ "github.com/stretchr/testify/require"
+)
+
+type spacedBitmapEncoder interface {
+ PutSpacedBitmap(bitmap []byte, bitmapOffset, numValues int64, validBits
[]byte, validBitsOffset int64) int64
+}
+
+func TestPlainBooleanEncoderPutSpacedBitmapOffsetsAndBoundaries(t *testing.T) {
+ tests := []struct {
+ name string
+ length int
+ bitmapOffset int
+ validityOffset int
+ valid func(int) bool
+ }{
+ {name: "single value", length: 1, bitmapOffset: 3,
validityOffset: 5, valid: func(int) bool { return true }},
+ {name: "short runs", length: 257, bitmapOffset: 3,
validityOffset: 5, valid: func(i int) bool { return i%10 != 0 }},
+ {name: "alternating", length: 1025, bitmapOffset: 7,
validityOffset: 3, valid: func(i int) bool { return i%2 == 0 }},
+ {name: "long runs", length: 4097, bitmapOffset: 5,
validityOffset: 7, valid: func(i int) bool { return i%256 >= 32 }},
+ {name: "buffer minus one", length: 8191, bitmapOffset: 1,
validityOffset: 2, valid: func(int) bool { return true }},
+ {name: "exact buffer", length: 8192, bitmapOffset: 2,
validityOffset: 3, valid: func(int) bool { return true }},
+ {name: "buffer plus one", length: 8193, bitmapOffset: 3,
validityOffset: 4, valid: func(int) bool { return true }},
+ }
+
+ for _, test := range tests {
+ t.Run(test.name, func(t *testing.T) {
+ bitmap, validity, expected := makeSpacedBooleanInput(
+ test.length, test.bitmapOffset,
test.validityOffset, test.valid,
+ )
+ actual := encodeSpacedBooleanBitmap(
+ t, bitmap, int64(test.bitmapOffset),
int64(test.length),
+ validity, int64(test.validityOffset),
+ )
+ assert.Equal(t, expected, actual)
+ })
+ }
+}
+
+func TestPlainBooleanEncoderPutSpacedBitmapMixedRunLengths(t *testing.T) {
+ const length = 129
+ bitmapOffset := 3
+ validityOffset := 5
+ bitmap, validity, expected := makeSpacedBooleanInput(
+ length, bitmapOffset, validityOffset,
+ func(i int) bool {
+ switch {
+ case i < 17:
+ return true
+ case i < 20:
+ return false
+ case i < 84:
+ return true
+ case i < 89:
+ return false
+ case i < 96:
+ return true
+ default:
+ return false
+ }
+ },
+ )
+
+ actual := encodeSpacedBooleanBitmap(
+ t, bitmap, int64(bitmapOffset), length,
+ validity, int64(validityOffset),
+ )
+ assert.Equal(t, expected, actual)
+}
+
+func TestPlainBooleanEncoderPutSpacedBitmapShortRunBoundary(t *testing.T) {
+ for _, length := range []int{31, 32, 33} {
+ t.Run(fmt.Sprintf("valid_run_%d", length), func(t *testing.T) {
+ bitmapOffset := 1
+ validityOffset := 2
+ bitmap, validity, expected := makeSpacedBooleanInput(
+ length, bitmapOffset, validityOffset, func(int)
bool { return true },
+ )
+ actual := encodeSpacedBooleanBitmap(
+ t, bitmap, int64(bitmapOffset), int64(length),
+ validity, int64(validityOffset),
+ )
+ assert.Equal(t, expected, actual)
+ })
+ }
+}
+
+func TestPlainBooleanEncoderPutSpacedBitmapMultipleCalls(t *testing.T) {
+ encoder := encoding.NewEncoder(
+ parquet.Types.Boolean, parquet.Encodings.Plain,
+ false, nil, memory.DefaultAllocator,
+ ).(encoding.BooleanEncoder)
+ spaced := encoder.(spacedBitmapEncoder)
+
+ var expected []bool
+ for call, length := range []int{31, 9000, 257} {
+ bitmapOffset := call + 1
+ validityOffset := call + 3
+ bitmap, validity, values := makeSpacedBooleanInput(
+ length, bitmapOffset, validityOffset,
+ func(i int) bool { return (i+call)%5 != 0 },
+ )
+ expected = append(expected, values...)
+ actualValid := spaced.PutSpacedBitmap(
+ bitmap, int64(bitmapOffset), int64(length), validity,
int64(validityOffset),
+ )
+ assert.Equal(t, int64(len(values)), actualValid)
+ }
+
+ buf, err := encoder.FlushValues()
+ require.NoError(t, err)
+ defer buf.Release()
+
+ actual := decodeBooleanValues(t, buf.Bytes(), len(expected))
+ assert.Equal(t, expected, actual)
+}
+
+func makeSpacedBooleanInput(
+ length, bitmapOffset, validityOffset int, valid func(int) bool,
+) (bitmap, validity []byte, expected []bool) {
+ bitmap = make([]byte, bitutil.BytesForBits(int64(bitmapOffset+length)))
+ validity = make([]byte,
bitutil.BytesForBits(int64(validityOffset+length)))
+ for i := range length {
+ value := i%3 != 0
+ if value {
+ bitutil.SetBit(bitmap, bitmapOffset+i)
+ }
+ if valid(i) {
+ bitutil.SetBit(validity, validityOffset+i)
+ expected = append(expected, value)
+ }
+ }
+ return
+}
+
+func encodeSpacedBooleanBitmap(
+ t *testing.T, bitmap []byte, bitmapOffset, length int64, validity
[]byte, validityOffset int64,
+) []bool {
+ t.Helper()
+ encoder := encoding.NewEncoder(
+ parquet.Types.Boolean, parquet.Encodings.Plain,
+ false, nil, memory.DefaultAllocator,
+ ).(encoding.BooleanEncoder)
+ spaced := encoder.(spacedBitmapEncoder)
+
+ numValid := spaced.PutSpacedBitmap(bitmap, bitmapOffset, length,
validity, validityOffset)
+ buf, err := encoder.FlushValues()
+ require.NoError(t, err)
+ defer buf.Release()
+
+ return decodeBooleanValues(t, buf.Bytes(), int(numValid))
+}
+
+func decodeBooleanValues(t *testing.T, data []byte, length int) []bool {
+ t.Helper()
+ decoder := encoding.NewDecoder(
+ parquet.Types.Boolean, parquet.Encodings.Plain, nil,
memory.DefaultAllocator,
+ ).(encoding.BooleanDecoder)
+ require.NoError(t, decoder.SetData(length, data))
+
+ values := make([]bool, length)
+ n, err := decoder.Decode(values)
+ require.NoError(t, err)
+ require.Equal(t, length, n)
+ return values
+}
