Blazing Fast Merge with Loser Trees
summary
Implements a loser tree k‑way merge in Go using Go generics to remove interface dispatch and speed the inner loop; replaces heap-based merging and gets about 4–8× faster on a Prometheus postings benchmark while using ~4.5MB extra for 100k items. Integrates into Loki for logs (30% end-to-end improvement, one component 4× faster). Problems: push‑style go1.23 iterators force heavy allocations, and Go’s current devirtualization/profile‑guided optimization is incomplete so performance depends on compiler support.
AI-written summary · about
chapters (19)
- 0:00Introduction
- 1:07Algorithms in real systems
- 2:58Heap performance bottleneck
- 6:37K-way merge problem
- 8:27Loser tree algorithm
- 13:28Complexity and performance
- 15:38Generics implementation
- 21:21Core loop
- 23:10Benchmarking in Prometheus
- 26:05Log merging in Loki
- 28:35Generics limitations
- 31:54Loki with function params
- 32:59Compiler optimizations
- 35:50Go 1.23 iterators
- 37:15Rewriting with iterators
- 40:24Benchmarking iterator version
- 41:50Loki performance
- 42:32Summary
- 43:19Q&A
