Blazing Fast Merge with Loser Trees - Bryan Boreham, Grafana Labs

Learn how Loser Trees provide 4-8x faster merging of ordered sequences compared to heaps. Explore implementation details, performance gains & real-world usage in Prometheus.

Key takeaways

Loser Trees provide an efficient solution for the K-way merge problem, commonly used in databases for merging ordered sequences
Implementation in Go showed 4-8x performance improvements compared to heap-based approaches, despite having similar O(n log k) complexity
Key performance gains came from:
- Less pointer chasing
- Reduced memory allocation
- Elimination of dynamic dispatch overhead through generics
- Better CPU cache utilization
The algorithm maintains winners/losers in a binary tree structure that can be implemented without pointers using array indexing
Go 1.23 iterators don’t naturally fit the pull-based nature of loser trees, as they are push-based
Memory overhead of the loser tree implementation is relatively small compared to total program memory usage
Devirtualization and profile-guided optimization can further improve performance
Sometimes simpler algorithms with “worse” complexity can perform better due to mechanical sympathy with hardware
Go generics work well for implementing the algorithm but have limitations around parameterized methods
The technique has been successfully implemented in Prometheus and Loki for merging metrics and log data

Blazing Fast Merge with Loser Trees - Bryan Boreham, Grafana Labs

More talks