You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iceberg.apache.org by at...@apache.org on 2026/09/21 16:22:10 UTC
(iceberg-go) branch main updated: perf: optimize FIFO packing for lookback one (#2033)
This is an automated email from the ASF dual-hosted git repository.
laskoviymishka 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 630e13005 perf: optimize FIFO packing for lookback one (#2033)
630e13005 is described below
commit 630e13005310eeddc1d17a0ba472655a3dd3be0a
Author: Minh Vu <vu...@gmail.com>
AuthorDate: Mon Sep 21 18:22:05 2026 +0200
perf: optimize FIFO packing for lookback one (#2033)
* perf(internal): reuse FIFO packing storage with one-bin lookback
Signed-off-by: Minh Vu <vu...@gmail.com>
* perf(internal): rotate FIFO lookback-one bins in place
Signed-off-by: Minh Vu <vu...@gmail.com>
---------
Signed-off-by: Minh Vu <vu...@gmail.com>
---
internal/utils.go | 15 ++++-
internal/utils_fifo_test.go | 151 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 164 insertions(+), 2 deletions(-)
diff --git a/internal/utils.go b/internal/utils.go
index 5f7d2a4c2..53fa0e220 100644
--- a/internal/utils.go
+++ b/internal/utils.go
@@ -138,8 +138,19 @@ func PackingIterator[T any](itr iter.Seq[T], targetWeight int64, lookback int, w
return maxBin
}
- var out Bin[T]
- out, bins = bins[0], bins[1:]
+ out := bins[0]
+ if lookback == 1 {
+ // Keep the two-bin buffer for the next FIFO eviction.
+ if len(bins) == 2 {
+ bins[0] = bins[1]
+ bins[1] = Bin[T]{}
+ } else {
+ bins[0] = Bin[T]{}
+ }
+ bins = bins[:len(bins)-1]
+ } else {
+ bins = bins[1:]
+ }
return out
}
diff --git a/internal/utils_fifo_test.go b/internal/utils_fifo_test.go
new file mode 100644
index 000000000..bbaa2b66a
--- /dev/null
+++ b/internal/utils_fifo_test.go
@@ -0,0 +1,151 @@
+// 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_test
+
+import (
+ "reflect"
+ "slices"
+ "strconv"
+ "testing"
+
+ "github.com/apache/iceberg-go/internal"
+)
+
+func TestPackingFIFOSingleLookback(t *testing.T) {
+ tests := []struct {
+ name string
+ weights []int64
+ target int64
+ want [][]int
+ wantEnd [][]int
+ }{
+ {name: "empty", target: 10, wantEnd: [][]int{}},
+ {name: "single", weights: []int64{7}, target: 10, want: [][]int{{0}}, wantEnd: [][]int{{0}}},
+ {name: "one bin", weights: []int64{3, 3, 4}, target: 10, want: [][]int{{0, 1, 2}}, wantEnd: [][]int{{0, 1, 2}}},
+ {
+ name: "repeated evictions", weights: []int64{6, 7, 8, 9, 10}, target: 10,
+ want: [][]int{{0}, {1}, {2}, {3}, {4}}, wantEnd: [][]int{{0}, {1}, {2}, {3}, {4}},
+ },
+ {
+ name: "exact fits", weights: []int64{6, 4, 10, 5, 5}, target: 10,
+ want: [][]int{{0, 1}, {2}, {3, 4}}, wantEnd: [][]int{{0, 1}, {2}, {3, 4}},
+ },
+ {
+ name: "different directions", weights: []int64{1, 2, 3, 4, 5}, target: 8,
+ want: [][]int{{0, 1, 2}, {3}, {4}}, wantEnd: [][]int{{0, 1}, {2, 3}, {4}},
+ },
+ {
+ name: "oversized and zero", weights: []int64{12, 1, 9, 15, 0, 10}, target: 10,
+ want: [][]int{{0}, {1, 2}, {3}, {4, 5}}, wantEnd: [][]int{{0}, {1, 2}, {3}, {4, 5}},
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ items := make([]int, len(tt.weights))
+ for i := range items {
+ items[i] = i
+ }
+ original := slices.Clone(items)
+ weight := func(i int) int64 { return tt.weights[i] }
+ packer := internal.SlicePacker[int]{TargetWeight: tt.target, Lookback: 1}
+
+ if got := packer.Pack(items, weight); !reflect.DeepEqual(got, tt.want) {
+ t.Fatalf("Pack() = %v, want %v", got, tt.want)
+ }
+ if got := packer.PackEnd(items, weight); !reflect.DeepEqual(got, tt.wantEnd) {
+ t.Fatalf("PackEnd() = %v, want %v", got, tt.wantEnd)
+ }
+ if !slices.Equal(items, original) {
+ t.Fatalf("packing changed input: got %v, want %v", items, original)
+ }
+ })
+ }
+}
+
+func TestPackingFIFOSingleLookbackEarlyStop(t *testing.T) {
+ for _, itemCount := range []int{1, 100} {
+ t.Run(strconv.Itoa(itemCount), func(t *testing.T) {
+ consumed := 0
+ input := func(yield func(int) bool) {
+ for i := range itemCount {
+ consumed++
+ if !yield(i) {
+ return
+ }
+ }
+ }
+ weightCalls := 0
+ weight := func(int) int64 {
+ weightCalls++
+
+ return 1
+ }
+ yielded := 0
+ for bin := range internal.PackingIterator(input, 1, 1, weight, false) {
+ yielded++
+ if !slices.Equal(bin, []int{0}) {
+ t.Fatalf("first bin = %v, want [0]", bin)
+ }
+
+ break
+ }
+ wantConsumed := min(itemCount, 2)
+ if yielded != 1 || consumed != wantConsumed || weightCalls != wantConsumed {
+ t.Fatalf("yielded=%d consumed=%d weightCalls=%d; want 1, %d, %d",
+ yielded, consumed, weightCalls, wantConsumed, wantConsumed)
+ }
+ })
+ }
+}
+
+var fifoPackingBenchmarkSink [][]int64
+
+func BenchmarkSlicePackerFIFO(b *testing.B) {
+ for _, lookback := range []int{1, 10, 64} {
+ for _, workload := range []string{"single", "mixed", "small"} {
+ for _, method := range []string{"Pack", "PackEnd"} {
+ b.Run(method+"/lookback="+strconv.Itoa(lookback)+"/"+workload, func(b *testing.B) {
+ items := make([]int64, 4096)
+ for i := range items {
+ switch workload {
+ case "single":
+ items[i] = 65 + int64(i%64)
+ case "mixed":
+ items[i] = 1 + int64((i*73)%128)
+ case "small":
+ items[i] = 1 + int64(i%8)
+ }
+ }
+ packer := internal.SlicePacker[int64]{TargetWeight: 128, Lookback: lookback}
+ pack := packer.Pack
+ if method == "PackEnd" {
+ pack = packer.PackEnd
+ }
+ weight := func(v int64) int64 { return v }
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ fifoPackingBenchmarkSink = pack(items, weight)
+ }
+ })
+ }
+ }
+ }
+}