The loser tree data structure: How to optimize merges and make your programs run faster

“Okay,” said Bryan Boreham, distinguished engineer at Grafana Labs, as he took to the stage at GopherCon 2023 in September. “Who loves algorithms?”

A room full of software engineers raised their hands in response — and with that, Bryan kicked off his talk at the annual event dedicated to the Go open source programming language. 

GopherCon 2023, which took place in San Diego, Calif. in September, featured Bryan as a speaker alongside other experts within the open source community. In his talk — called “Blazing fast merge with loser trees” — Bryan explored the loser tree data structure (yes, that’s its real name) as a way to optimize sorting and merging operations so your applications run faster.

Here, we recap Bryan’s talk, including how he implemented the loser tree data structure using Go generics to optimize queries in Prometheus, as well as how he’s used loser trees at Grafana Labs to boost the performance of open source projects like Grafana Loki and Grafana Pyroscope. You can also check out Bryan’s complete GopherCon 2023 session on YouTube below.

K-way merges, loser trees, and a love of optimization

In addition to being a distinguished engineer on the cloud databases squad at Grafana Labs, Bryan is a maintainer of the open source Prometheus project. And in both of those roles, he has a passion for optimization.

“I love making computer systems go faster,” Bryan told GopherCon attendees. “It’s basically like a video game for me. I’ll sit there for hours, trying to make my score higher by making the program go faster.”

And this, Bryan explained, is where his journey with loser trees began.

He shared a flamegraph (below) that he used to visualize CPU processing times for Prometheus, calling attendees’ attention to the purple bars, in particular. Those bars indicated a slow execution time — and potential bottleneck — related to a specific package called container/heap. Bryan discovered the lag was the result of the inner loop from container/heap in the Go Standard Library; it was making indirect calls to an interface, which was introducing performance overhead.

Bryan then provided a bit more context around what was happening inside of Prometheus with the container/heap package: it was being used for a k-way merge. In programming, a k-way merge takes multiple sorted lists and merges them into one sorted list. It’s a common operation, especially in databases, but needs to be efficient to avoid a slow-down in performance at scale.

So, Bryan said, he started to look for a solution. In his research, he found that you can accelerate a k-way merge by more quickly identifying the smallest element in the sequence. One way to do this is with a type of tournament tree algorithm that only stores the loser of each game — an algorithm or data structure that’s known (you guessed it) as a loser tree. 

“I couldn’t resist,” Bryan laughed. “I mean, I pictured myself standing on stage at that very moment, because who can resist a talk about something called a loser tree?”

Implementing a loser tree and measuring the results 

Next, Bryan dove into the technical details of how the loser tree data structure works, and how he implemented one in Prometheus, using Go generics, to address that container/heap issue outlined earlier. 

He shared the below example of a basic data structure in Go for a loser tree, walking attendees through different parameters, including value type and sequence type:

As for the results of implementing the loser tree structure? Turns out, it can accelerate k-way  merges pretty significantly, resulting in faster execution times in Prometheus. Bryan confirmed this using benchstat, a Go tool to compute and compare benchmark statistics.

“It’s a synthetic benchmark that was merging 10 elements and then 10,000 and then 100,000, and it showed it was between five to 12 times faster,” Bryan said. 

And while there are some drawbacks to the loser tree — it can require more system memory, for example — Bryan said he was pleased with the results. So much so, in fact, that he has applied the loser tree structure to optimize merges in other systems, including Grafana Loki, the open source log aggregation system. 

The logs that Loki works with are pure sorted sequences; each line of the log is a string, and they are ordered by timestamp. Loki stores logs from all your processes — potentially thousands of them — and when you query the logs, you expect to see all the results merged into a single sequence ordered by timestamp. Bottom line? It’s essentially another k-way merge, which means the loser tree works well as an optimization technique. 

In addition, the loser tree structure has been implemented in Grafana Pyroscope to improve the deduplication of profiles. 

All in all, Bryan said, his experimentation with loser trees and Go generics has been a success. “I had a bit of a voyage with Go generics,” he told attendees at the end of his talk. “It was the first complex code I wrote trying to use generics — and to get the power out of them.” 

Want to learn more about loser trees and Go generics? Watch Bryan’s full GopherCon 2023 talk on YouTube and find all the code from the session on GitHub.