Blazing Fast Merge with Loser Trees
summary
Implements a k‑way merge using a Loser Tree in Go, using generics to eliminate indirect calls and storing leaf values to avoid repeated sequence lookups. Benchmarks show 5–12× faster microbenchmark versus container/heap, memory rises (about 6 MB extra for 100k series), and a generic fallback using a comparison function is generics vs function‑pointer ~2× slower because the call doesn’t inline. Applied in production systems (Prometheus PR 12878, Grafana Loki PR 8351) with real workloads yielding ~30% faster Loki queries, so the structure is practical and effective.
AI-written summary · about
chapters (19)
- 0:00Introduction
- 1:10Optimizing algorithms like a game
- 2:36Heap bottleneck in Prometheus
- 5:04K-way merge problem
- 6:30Loser tree introduction
- 8:24How loser trees work
- 12:44Complexity of loser trees
- 14:51Go generics implementation
- 18:30Node storage and inner loop
- 20:21Benchmarking loser trees
- 23:16Adapting loser trees for Loki
- 25:28Go generics limitations
- 27:14Function pointers with loser trees
- 28:19Performance trade-offs
- 29:44Loser trees in production
- 31:29Visualizing loser trees
- 32:15Why loser trees beat heaps
- 33:21Lessons from Go generics
- 33:44Loser tree code
