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/iceberg-go.git
The following commit(s) were added to refs/heads/main by this push:
new 2e69b8adb perf(internal): avoid quadratic packing with large lookback
(#2363)
2e69b8adb is described below
commit 2e69b8adb8f0db0ecdd7a48cf4280737f4704fe6
Author: Minh Vu <[email protected]>
AuthorDate: Thu Nov 5 21:12:15 2026 +0100
perf(internal): avoid quadratic packing with large lookback (#2363)
* perf(internal): avoid quadratic packing with large lookback
Signed-off-by: Minh Vu <[email protected]>
* test(internal): compare indexed packing with linear across weight
transitions
* fix(internal): correct reverse iterator test declaration
* test(internal): use integer range in packing test
---------
Signed-off-by: Minh Vu <[email protected]>
---
internal/packing_indexed.go | 26 ++--
internal/packing_large_lookback_test.go | 216 ++++++++++++++++++++++++++++++++
internal/utils.go | 4 +-
3 files changed, 237 insertions(+), 9 deletions(-)
diff --git a/internal/packing_indexed.go b/internal/packing_indexed.go
index 9f54a0faa..ea4567ce1 100644
--- a/internal/packing_indexed.go
+++ b/internal/packing_indexed.go
@@ -23,13 +23,14 @@ import (
)
// Large FIFO plans spend most of their time searching the open bins.
-// Index only when there are enough items to amortize the tree and ring buffer.
-// Smaller plans, largest-bin-first packing, and potentially overflowing
-// weights keep the existing linear implementation.
+// For small plans, index only after there are enough items to amortize it.
+// Large plans use the indexed first-fit path even with a very large lookback;
+// otherwise every new bin searches thousands of open bins. Division avoids
+// overflow when callers use a practically unbounded lookback.
func (s *SlicePacker[T]) shouldUseIndexedFIFO(itemCount int) bool {
return !s.LargestBinFirst &&
- s.Lookback >= 32 && s.Lookback <= 8192 &&
- itemCount >= 2*s.Lookback &&
+ s.Lookback >= 32 &&
+ (itemCount/s.Lookback >= 2 || itemCount >= 16_384) &&
s.TargetWeight >= 0 && s.TargetWeight <= math.MaxInt64/2
}
@@ -96,7 +97,8 @@ func indexedFIFOPackingIterator[T any](
input iter.Seq[T], targetWeight int64, lookback int, weightFunc func(T)
int64,
) iter.Seq[[]T] {
capacity := lookback + 1
- bins := make([]Bin[T], capacity)
+ // Small or easy-to-pack inputs do not need a lookback-sized ring.
+ bins := make([]Bin[T], 0, min(capacity, 32))
var weights packingWeightIndex
head, openBins := 0, 0
@@ -140,7 +142,11 @@ func indexedFIFOPackingIterator[T any](
}
slot := (head + openBins) % capacity
- bins[slot] = Bin[T]{targetWeight: targetWeight}
+ if slot == len(bins) {
+ bins = append(bins, Bin[T]{targetWeight:
targetWeight})
+ } else {
+ bins[slot] = Bin[T]{targetWeight: targetWeight}
+ }
bins[slot].Add(item, weight)
if indexed {
weights.update(slot, weight)
@@ -148,6 +154,12 @@ func indexedFIFOPackingIterator[T any](
openBins++
if safeToIndex && !indexed && openBins == 32 {
+ // Only allocate the full ring once indexing
becomes worthwhile.
+ if cap(bins) < capacity {
+ expanded := make([]Bin[T], capacity)
+ copy(expanded, bins)
+ bins = expanded
+ }
weights = newPackingWeightIndex(capacity)
for i := range openBins {
j := (head + i) % capacity
diff --git a/internal/packing_large_lookback_test.go
b/internal/packing_large_lookback_test.go
new file mode 100644
index 000000000..a4d9f40a7
--- /dev/null
+++ b/internal/packing_large_lookback_test.go
@@ -0,0 +1,216 @@
+// 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 internal
+
+import (
+ "fmt"
+ "math"
+ "math/rand"
+ "reflect"
+ "slices"
+ "testing"
+)
+
+func TestLargeLookbackIndexedSelection(t *testing.T) {
+ tests := []struct {
+ name string
+ count int
+ lookback int
+ target int64
+ largest bool
+ want bool
+ }{
+ {"small existing indexed plan", 64, 32, 128, false, true},
+ {"old indexed boundary", 16_384, 8192, 128, false, true},
+ {"past old limit", 16_384, 8193, 128, false, true},
+ {"large lookback", 24_000, 10_000, 128, false, true},
+ {"effectively unbounded", 16_384, math.MaxInt, 128, false,
true},
+ {"below large plan cutoff", 16_383, math.MaxInt, 128, false,
false},
+ {"small input", 8000, 10_000, 128, false, false},
+ {"largest bin first", 24_000, 10_000, 128, true, false},
+ {"negative target", 24_000, 10_000, -1, false, false},
+ {"overflowing target", 24_000, 10_000, math.MaxInt64, false,
false},
+ {"zero lookback", 24_000, 0, 128, false, false},
+ }
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ packer := SlicePacker[int]{
+ TargetWeight: tt.target,
+ Lookback: tt.lookback,
+ LargestBinFirst: tt.largest,
+ }
+ if got := packer.shouldUseIndexedFIFO(tt.count); got !=
tt.want {
+ t.Fatalf("shouldUseIndexedFIFO(%d) = %t, want
%t", tt.count, got, tt.want)
+ }
+ })
+ }
+}
+
+func TestLargeLookbackPackingMatchesLinear(t *testing.T) {
+ tests := []struct {
+ name string
+ count int
+ lookback int
+ mode string
+ }{
+ {"old index limit", 16_384, 8193, "large"},
+ {"many open bins", 20_000, 10_000, "mixed"},
+ {"unbounded lookback", 16_384, math.MaxInt, "large"},
+ {"fall back after negative weight", 16_384, 8193, "negative"},
+ {"fall back after oversized weight", 16_384, 8193, "oversized"},
+ {"single bin, no eager ring", 16_384, math.MaxInt, "single"},
+ }
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ items := make([]int, tt.count)
+ weights := make([]int64, tt.count)
+ rng := rand.New(rand.NewSource(42))
+ for i := range items {
+ items[i] = i
+ switch tt.mode {
+ case "mixed":
+ weights[i] = int64(1 + rng.Intn(128))
+ case "single":
+ weights[i] = 0
+ default:
+ weights[i] = int64(65 + i%64)
+ }
+ }
+ if tt.mode == "negative" {
+ weights[tt.count/2] = -1
+ }
+ if tt.mode == "oversized" {
+ weights[tt.count/2] = math.MaxInt64
+ }
+ weight := func(index int) int64 { return weights[index]
}
+ packer := SlicePacker[int]{TargetWeight: 128, Lookback:
tt.lookback}
+ want := slices.Collect(PackingIterator(
+ slices.Values(items), 128, tt.lookback, weight,
false))
+ if got := packer.Pack(items, weight);
!reflect.DeepEqual(got, want) {
+ t.Fatalf("Pack differs from linear first-fit
(%d items, lookback %d)",
+ tt.count, tt.lookback)
+ }
+
+ reversed := func(yield func(int) bool) {
+ for _, item := range slices.Backward(items) {
+ if !yield(item) {
+ return
+ }
+ }
+ }
+ wantEnd := slices.Collect(PackingIterator(
+ reversed, 128, tt.lookback, weight, false))
+ slices.Reverse(wantEnd)
+ for _, bin := range wantEnd {
+ slices.Reverse(bin)
+ }
+ if got := packer.PackEnd(items, weight);
!reflect.DeepEqual(got, wantEnd) {
+ t.Fatalf("PackEnd differs from linear first-fit
(%d items, lookback %d)",
+ tt.count, tt.lookback)
+ }
+ })
+ }
+}
+
+var largeLookbackPackingBenchmarkSink [][]int64
+
+// This compares the original linear fallback with SlicePacker's selected
+// implementation on the same input. Both modes must return the same bins.
+func BenchmarkSlicePackerLargeLookback(b *testing.B) {
+ for _, tc := range []struct {
+ count int
+ lookback int
+ }{
+ {16_384, 8193},
+ {24_000, 10_000},
+ {24_000, 1_000_000},
+ } {
+ b.Run(fmt.Sprintf("files=%d/lookback=%d", tc.count,
tc.lookback), func(b *testing.B) {
+ items := make([]int64, tc.count)
+ for i := range items {
+ items[i] = int64(65 + i%64)
+ }
+ weight := func(item int64) int64 { return item }
+ packer := SlicePacker[int64]{TargetWeight: 128,
Lookback: tc.lookback}
+ for _, mode := range []string{"linear", "indexed"} {
+ b.Run(mode, func(b *testing.B) {
+ b.ReportAllocs()
+ b.ReportMetric(float64(tc.count),
"files/op")
+ b.ResetTimer()
+ for range b.N {
+ if mode == "linear" {
+
largeLookbackPackingBenchmarkSink = slices.Collect(PackingIterator(
+
slices.Values(items), 128, tc.lookback, weight, false))
+ } else {
+
largeLookbackPackingBenchmarkSink = packer.Pack(items, weight)
+ }
+ }
+ if
len(largeLookbackPackingBenchmarkSink) != tc.count {
+ b.Fatalf("expected %d bins, got
%d", tc.count, len(largeLookbackPackingBenchmarkSink))
+ }
+ })
+ }
+ })
+ }
+}
+
+func TestIndexedPackingMatchesLinearAcrossWeightTransitions(t *testing.T) {
+ const count = 512
+ for _, lookback := range []int{32, 33, 64, 128} {
+ for seed := range int64(4) {
+ t.Run(fmt.Sprintf("lookback=%d/seed=%d", lookback,
seed), func(t *testing.T) {
+ rng := rand.New(rand.NewSource(seed))
+ items := make([]int, count)
+ weights := make([]int64, count)
+ for i := range items {
+ items[i] = i
+ if i < 160 {
+ weights[i] = int64(65 +
rng.Intn(64))
+ } else {
+ weights[i] =
int64(rng.Intn(129))
+ }
+ }
+ weights[255] = -1
+ weights[383] = math.MaxInt64
+ weight := func(i int) int64 { return weights[i]
}
+ packer := SlicePacker[int]{TargetWeight: 128,
Lookback: lookback}
+
+ want :=
slices.Collect(PackingIterator(slices.Values(items), 128, lookback, weight,
false))
+ if got := packer.Pack(items, weight);
!reflect.DeepEqual(got, want) {
+ t.Fatal("indexed packing differs from
linear first-fit")
+ }
+
+ reversed := func(yield func(int) bool) {
+ for _, item := range
slices.Backward(items) {
+ if !yield(item) {
+ return
+ }
+ }
+ }
+ wantEnd :=
slices.Collect(PackingIterator(reversed, 128, lookback, weight, false))
+ slices.Reverse(wantEnd)
+ for _, bin := range wantEnd {
+ slices.Reverse(bin)
+ }
+ if got := packer.PackEnd(items, weight);
!reflect.DeepEqual(got, wantEnd) {
+ t.Fatal("indexed reverse packing
differs from linear first-fit")
+ }
+ })
+ }
+ }
+}
diff --git a/internal/utils.go b/internal/utils.go
index c5de79771..842c98d3b 100644
--- a/internal/utils.go
+++ b/internal/utils.go
@@ -209,7 +209,7 @@ type SlicePacker[T any] struct {
func (s *SlicePacker[T]) Pack(items []T, weightFunc func(T) int64) [][]T {
if s.shouldUseIndexedFIFO(len(items)) {
return
slices.Collect(indexedFIFOPackingIterator(slices.Values(items),
- s.TargetWeight, s.Lookback, weightFunc))
+ s.TargetWeight, min(s.Lookback, len(items)),
weightFunc))
}
return slices.Collect(PackingIterator(slices.Values(items),
s.TargetWeight,
@@ -228,7 +228,7 @@ func (s *SlicePacker[T]) PackEnd(items []T, weightFunc
func(T) int64) [][]T {
var packed [][]T
if s.shouldUseIndexedFIFO(len(items)) {
packed = slices.Collect(indexedFIFOPackingIterator(reversed,
- s.TargetWeight, s.Lookback, weightFunc))
+ s.TargetWeight, min(s.Lookback, len(items)),
weightFunc))
} else {
packed = slices.Collect(PackingIterator(reversed,
s.TargetWeight, s.Lookback, weightFunc,
s.LargestBinFirst))
