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 ccdb0e09 perf(parquet/internal/encoding): decode RLE booleans directly
into bool slices (#1417)
ccdb0e09 is described below
commit ccdb0e0975f81b7695e545f7fc762abe4ccdda1f
Author: Minh Vu <[email protected]>
AuthorDate: Tue Oct 27 16:49:00 2026 +0100
perf(parquet/internal/encoding): decode RLE booleans directly into bool
slices (#1417)
### Rationale for this change
`RleBooleanDecoder.Decode` staged every value in a `[1024]uint64` buffer
before converting it to `bool`, even for repeated runs that can be
filled directly.
### What changes are included in this PR?
- New `RleDecoder.GetBatchBools`: repeated one-bit runs are written
straight into the `[]bool` destination; bit-packed literal runs are
decoded through the existing word unpacker (`GetBatch`) into a scratch
buffer and then converted.
- `RleBooleanDecoder.Decode` uses it.
### Are these changes tested?
Yes: split-batch, reset, discard and truncated-input coverage for
`GetBatchBools` and the boolean decoder. Decoded values, error status
and decoded counts match `GetBatch` exactly.
`BenchmarkRleBooleanDecoderDecode` on amd64 (pinned, GOMAXPROCS=1, 8
runs, `main` → this PR, allocations unchanged):
| input | change |
|---|---|
| all true / all false | 66–98% faster (e.g. 65536 all_false: 47.6 → 1.2
µs) |
| alternating / short runs, one chunk | ~30% faster |
| alternating / short runs, 257-value chunks | 5–7% faster |
### Are there any user-facing changes?
No API changes; faster decoding of RLE-encoded boolean columns.
---
parquet/internal/encoding/boolean_decoder.go | 36 +++----
.../encoding/boolean_decoder_benchmark_test.go | 45 +++++++++
.../encoding/boolean_decoder_bitmap_test.go | 76 +++++++++++++++
parquet/internal/utils/rle.go | 47 +++++++++
parquet/internal/utils/rle_bools_test.go | 105 +++++++++++++++++++++
5 files changed, 284 insertions(+), 25 deletions(-)
diff --git a/parquet/internal/encoding/boolean_decoder.go
b/parquet/internal/encoding/boolean_decoder.go
index 69c8ce99..89519d9e 100644
--- a/parquet/internal/encoding/boolean_decoder.go
+++ b/parquet/internal/encoding/boolean_decoder.go
@@ -350,33 +350,19 @@ func (dec *RleBooleanDecoder) Discard(n int) (int, error)
{
func (dec *RleBooleanDecoder) Decode(out []bool) (int, error) {
max := shared_utils.Min(len(out), dec.nvals)
-
- var (
- buf [1024]uint64
- n = max
- )
-
- for n > 0 {
- batch := shared_utils.Min(len(buf), n)
- decoded, err := dec.rleDec.GetBatch(buf[:batch])
-
- for i := 0; i < decoded; i++ {
- out[i] = buf[i] != 0
- }
- n -= decoded
- out = out[decoded:]
- if err != nil {
- dec.nvals -= max - n
- return max - n, err
- }
- if decoded != batch {
- dec.nvals -= max - n
- return max - n, io.ErrUnexpectedEOF
- }
+ if max <= 0 {
+ return 0, nil
}
- dec.nvals -= max
- return max, nil
+ decoded, err := dec.rleDec.GetBatchBools(out[:max])
+ dec.nvals -= decoded
+ if err != nil {
+ return decoded, err
+ }
+ if decoded != max {
+ return decoded, io.ErrUnexpectedEOF
+ }
+ return decoded, nil
}
func (dec *RleBooleanDecoder) DecodeToBitmap(out []byte, outOffset int64,
length int) (int, error) {
diff --git a/parquet/internal/encoding/boolean_decoder_benchmark_test.go
b/parquet/internal/encoding/boolean_decoder_benchmark_test.go
index e6064e6b..758f9965 100644
--- a/parquet/internal/encoding/boolean_decoder_benchmark_test.go
+++ b/parquet/internal/encoding/boolean_decoder_benchmark_test.go
@@ -121,3 +121,48 @@ func BenchmarkRleBooleanDecoderDecodeSpacedToBitmap(b
*testing.B) {
}
}
}
+
+func BenchmarkRleBooleanDecoderDecode(b *testing.B) {
+ patterns := []struct {
+ name string
+ value func(int) bool
+ }{
+ {name: "all_true", value: func(int) bool { return true }},
+ {name: "all_false", value: func(int) bool { return false }},
+ {name: "alternating", value: func(i int) bool { return i%2 == 0
}},
+ {name: "short_runs", value: func(i int) bool { return (i/7)%2
== 0 }},
+ }
+
+ for _, size := range []int{64 * 1024, 1024 * 1024} {
+ for _, pattern := range patterns {
+ for _, chunk := range []int{size, 257} {
+ b.Run(fmt.Sprintf("size_%d/%s/chunk_%d", size,
pattern.name, chunk), func(b *testing.B) {
+ values := makeBooleanValues(size,
pattern.value)
+ data := encodeRleBooleanValues(b,
values)
+ out := make([]bool, size)
+ dec :=
encoding.NewDecoder(parquet.Types.Boolean, parquet.Encodings.RLE,
+ nil,
memory.DefaultAllocator).(encoding.BooleanDecoder)
+
+ b.ReportAllocs()
+ b.SetBytes(int64(size))
+ for b.Loop() {
+ if err := dec.SetData(size,
data); err != nil {
+ b.Fatal(err)
+ }
+ for offset := 0; offset < size;
{
+ end := min(size,
offset+chunk)
+ n, err :=
dec.Decode(out[offset:end])
+ if err != nil {
+ b.Fatal(err)
+ }
+ if n != end-offset {
+
b.Fatalf("expected %d booleans, got %d", end-offset, n)
+ }
+ offset = end
+ }
+ }
+ })
+ }
+ }
+ }
+}
diff --git a/parquet/internal/encoding/boolean_decoder_bitmap_test.go
b/parquet/internal/encoding/boolean_decoder_bitmap_test.go
index 44e2768a..fb7d2851 100644
--- a/parquet/internal/encoding/boolean_decoder_bitmap_test.go
+++ b/parquet/internal/encoding/boolean_decoder_bitmap_test.go
@@ -168,3 +168,79 @@ func TestRleBooleanDecoderDecodeToBitmapTruncatedLiteral(t
*testing.T) {
})
}
}
+
+func TestRleBooleanDecoderDecodeInChunks(t *testing.T) {
+ t.Run("empty", func(t *testing.T) {
+ dec := newRleBooleanBitmapDecoder(t, 0, []byte{0, 0, 0, 0})
+ n, err := dec.Decode(nil)
+ require.NoError(t, err)
+ require.Zero(t, n)
+ assert.Zero(t, dec.ValuesLeft())
+ })
+ patterns := []struct {
+ name string
+ values []bool
+ }{
+ {name: "all_true", values: makeBooleanValues(2048, func(int)
bool { return true })},
+ {name: "all_false", values: makeBooleanValues(2048, func(int)
bool { return false })},
+ {name: "alternating", values: makeBooleanValues(2048, func(i
int) bool { return i%2 == 0 })},
+ {name: "short_runs", values: makeBooleanValues(2048, func(i
int) bool { return (i/7)%2 == 0 })},
+ {name: "mixed", values: makeBooleanValues(2048, func(i int)
bool {
+ return i < 23 || i >= 53 && i < 511 || i%5 == 0
+ })},
+ }
+
+ for _, pattern := range patterns {
+ t.Run(pattern.name, func(t *testing.T) {
+ data := encodeRleBooleanValues(t, pattern.values)
+ for _, batchSize := range []int{1, 3, 7, 8, 9, 31, 257,
1024, 4096} {
+ t.Run(fmt.Sprintf("batch_%d", batchSize),
func(t *testing.T) {
+ dec := newRleBooleanBitmapDecoder(t,
len(pattern.values), data)
+ out := make([]bool, len(pattern.values))
+ for i := range out {
+ out[i] = true // verify that
false runs overwrite reused output
+ }
+ for offset := 0; offset < len(out); {
+ end := min(len(out),
offset+batchSize)
+ n, err :=
dec.Decode(out[offset:end])
+ require.NoError(t, err)
+ require.Equal(t, end-offset, n)
+ offset += n
+ }
+ n, err := dec.Decode(nil)
+ require.NoError(t, err)
+ require.Zero(t, n)
+ assert.Equal(t, pattern.values, out)
+ assert.Zero(t, dec.ValuesLeft())
+
+ // Reset must also reset the RLE run
and bit-reader state.
+ require.NoError(t,
dec.SetData(len(pattern.values), data))
+ refilled := make([]bool, len(out))
+ n, err = dec.Decode(refilled)
+ require.NoError(t, err)
+ require.Equal(t, len(out), n)
+ assert.Equal(t, pattern.values,
refilled)
+ })
+ }
+ })
+ }
+}
+
+func TestRleBooleanDecoderDecodeTruncatedLiteral(t *testing.T) {
+ // A literal header advertises 64 bits, but the payload has only 7
bytes.
+ payload := append([]byte{17}, bytes.Repeat([]byte{0xff}, 7)...)
+ data := make([]byte, 4+len(payload))
+ binary.LittleEndian.PutUint32(data[:4], uint32(len(payload)))
+ copy(data[4:], payload)
+
+ dec := newRleBooleanBitmapDecoder(t, 64, data)
+ out := make([]bool, 64)
+ n, err := dec.Decode(out)
+ require.Error(t, err)
+ require.Positive(t, n)
+ require.Less(t, n, 64)
+ assert.Equal(t, 64-n, dec.ValuesLeft())
+ for _, value := range out[:n] {
+ assert.True(t, value)
+ }
+}
diff --git a/parquet/internal/utils/rle.go b/parquet/internal/utils/rle.go
index 57fe6a1a..9b34b350 100644
--- a/parquet/internal/utils/rle.go
+++ b/parquet/internal/utils/rle.go
@@ -239,6 +239,53 @@ func (r *RleDecoder) GetBatch(values []uint64) (int,
error) {
return read, nil
}
+// GetBatchBools decodes repeated one-bit runs directly into booleans.
+// Literal runs use the bulk unpacking path to avoid slow per-bit reads.
+func (r *RleDecoder) GetBatchBools(out []bool) (int, error) {
+ if r.bitWidth != 1 {
+ return 0, errors.New("boolean decoding requires a bit width of
1")
+ }
+
+ read := 0
+ var unpacked [1024]uint64
+ for read < len(out) {
+ remain := len(out) - read
+
+ if r.repCount > 0 {
+ n := min(remain, int(r.repCount))
+ dst := out[read : read+n]
+ if r.curVal != 0 {
+ for i := range dst {
+ dst[i] = true
+ }
+ } else {
+ clear(dst)
+ }
+ r.repCount -= int32(n)
+ read += n
+ } else if r.litCount > 0 {
+ // Packed literals are much faster through the existing
word
+ // unpacker than through the scalar boolean bit reader.
+ n := min(remain, int(r.litCount), len(unpacked))
+ decoded, err := r.r.GetBatch(1, unpacked[:n])
+ for i, value := range unpacked[:decoded] {
+ out[read+i] = value != 0
+ }
+ r.litCount -= int32(decoded)
+ read += decoded
+ if err != nil {
+ return read, err
+ }
+ if decoded != n {
+ return read, nil
+ }
+ } else if !r.Next() {
+ return read, nil
+ }
+ }
+ return read, nil
+}
+
// GetBatchLevels decodes levels directly into values and returns the number
// equal to maxLevel.
func (r *RleDecoder) GetBatchLevels(values []int16, maxLevel int16) (int,
int64, error) {
diff --git a/parquet/internal/utils/rle_bools_test.go
b/parquet/internal/utils/rle_bools_test.go
new file mode 100644
index 00000000..a65221d5
--- /dev/null
+++ b/parquet/internal/utils/rle_bools_test.go
@@ -0,0 +1,105 @@
+// 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 utils_test
+
+import (
+ "bytes"
+ "fmt"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/parquet/internal/utils"
+)
+
+func TestRleDecoderGetBatchBools(t *testing.T) {
+ // 13 false, 19 true, 16 literal bits, 12 true, 8 literal bits.
+ data := []byte{26, 0, 38, 1, 5, 0xa5, 0x3c, 24, 1, 3, 0xaa}
+ const count = 68
+
+ reference := utils.NewRleDecoder(bytes.NewReader(data), 1)
+ want := make([]uint64, count)
+ n, err := reference.GetBatch(want)
+ if err != nil || n != count {
+ t.Fatalf("reference decode: n=%d, err=%v", n, err)
+ }
+
+ for _, chunk := range []int{1, 2, 3, 7, 8, 9, 31, 64, count, count + 3}
{
+ t.Run(fmt.Sprintf("chunk_%d", chunk), func(t *testing.T) {
+ dec := utils.NewRleDecoder(bytes.NewReader(data), 1)
+ got := make([]bool, count)
+ for i := range got {
+ got[i] = true
+ }
+ for pos := 0; pos < count; {
+ end := min(pos+chunk, count)
+ n, err := dec.GetBatchBools(got[pos:end])
+ if err != nil || n != end-pos {
+ t.Fatalf("decode at %d: n=%d, err=%v",
pos, n, err)
+ }
+ pos = end
+ }
+ for i, value := range got {
+ if value != (want[i] != 0) {
+ t.Fatalf("value %d: got %t, want %t",
i, value, want[i] != 0)
+ }
+ }
+ n, err := dec.GetBatchBools(make([]bool, 1))
+ if n != 0 || err != nil {
+ t.Fatalf("exhausted decoder: n=%d, err=%v", n,
err)
+ }
+ dec.Reset(bytes.NewReader(data), 1)
+ n, err = dec.GetBatchBools(make([]bool, count+3))
+ if err != nil || n != count {
+ t.Fatalf("reset decoder: n=%d, err=%v", n, err)
+ }
+ })
+ }
+
+ t.Run("mixed_with_discard", func(t *testing.T) {
+ dec := utils.NewRleDecoder(bytes.NewReader(data), 1)
+ first := make([]bool, 17)
+ n, err := dec.GetBatchBools(first)
+ if err != nil || n != len(first) {
+ t.Fatalf("first batch: n=%d, err=%v", n, err)
+ }
+ if skipped := dec.Discard(13); skipped != 13 {
+ t.Fatalf("discarded %d, want 13", skipped)
+ }
+ rest := make([]bool, count-30)
+ n, err = dec.GetBatchBools(rest)
+ if err != nil || n != len(rest) {
+ t.Fatalf("last batch: n=%d, err=%v", n, err)
+ }
+ for i, value := range first {
+ if value != (want[i] != 0) {
+ t.Fatalf("before discard, value %d", i)
+ }
+ }
+ for i, value := range rest {
+ if value != (want[i+30] != 0) {
+ t.Fatalf("after discard, value %d", i+30)
+ }
+ }
+ })
+}
+
+func TestRleDecoderGetBatchBoolsRejectsNonBooleanWidth(t *testing.T) {
+ dec := utils.NewRleDecoder(bytes.NewReader([]byte{16, 2}), 2)
+ n, err := dec.GetBatchBools(make([]bool, 8))
+ if n != 0 || err == nil {
+ t.Fatalf("invalid width: n=%d, err=%v", n, err)
+ }
+}
