Shaving 40% off Google’s B-Tree Implementation with Go Generics

There are many reasons to be excited about generics in Go. In this article, I’m going to show how, using Go generics, ScyllaDB achieved a 40% performance gain in an already well-optimized package, the Google B-Tree implementation. (For background, ScyllaDB is a NoSQL database for data-intensive apps that require high performance and low latency. It’s available as open source, enterprise and DBaaS).

A B-Tree is a kind of self-balancing tree. For the purpose of this article, it’s sufficient to say that it is a collection. You can add, remove, get or iterate over its elements. The Google B-Tree is well optimized; measures are taken to make sure memory consumption is correct. There is a benchmark for every exported method, and the benchmark results show that there are zero allocations in the B-Tree code for all operations except cloning. This suggests it would be hard to further optimize using traditional techniques.

The work covered in this article was part of ScyllaDB’s long-standing partnership with the Computer Science Department at the University of Warsaw. We’ve worked on a number of projects together: integrating Parquet, an async userspace filesystem, a Kafka client for Seastar, a system for linear algebra in ScyllaDB and a design for a new Rust driver.

(If you obsess over performance optimizations like this, join us at P99 CONF — a free virtual conference dedicated to all things performance.)

Making Faster B-Trees with Generics

While working on a new ScyllaDB Go Driver with students of the University of Warsaw, we ported the B-tree code to generics. (If you’re not familiar with generics in Go, check out this tutorial.).

The initial result: the generics code is faster by 20 to 30 percent according to the Google benchmarks (here’s the issue we opened). Below is a full benchmark comparison done with benchstat.

👁 Image

This is great, but within those numbers lies a troubling detail. The zero allocations is not something that you would normally see given that the functions accept an interface as a parameter.

👁 Image

For the rest of the article, let’s focus on benchmarking the ReplaceOrInsert function responsible for ingesting data. Consider a simplified benchmark.

👁 Image

The results show even greater improvement: 31 percent vs. 27 percent, and allocations drop from 1 (in the case of the interface-based implementation) to 0 (in the case of generics).

👁 Image

Let’s try to understand what happens here.

The Additional Allocation

The Google benchmarks operate on a B-tree of integers hidden by an Item interface. They use pre-generated random data in a slice. When an Item is passed to the ReplaceOrInsert function, the underlying integer is already on the heap. Technically, we are copying a pointer. This is not the case when a plain integer needs to be converted to an Item interface — the parameter values start “escaping to heap.”

Go has a feature of deciding if a variable you initialized should live in the function’s stack or in the heap. Traditionally, the compiler was very “conservative.” When it saw a function like func bind(v interface{}), anything you wanted to pass as v would have to go to heap first. This is referred to as a variable escaping to the heap. Over the years, the compiler has gotten smarter, and calls to local functions or functions in other packages in your project can be optimized, preventing the variables from escaping. You can check for yourself by running go build -gcflags="-m". in a Go package.

In the following example, Go can figure out that it’s safe to take a pointer to the main function’s stack.

👁 Image

As you can see, the compiler informs us that variables do not escape to heap.

👁 Image

By changing the ToString implementation to

👁 Image

we see that the variables and literal values do start escaping.

👁 Image

In practical examples, when calling a function that accepts an interface as a parameter, the value almost always escapes to heap. When this happens, it not only slows down the function call by the allocation but also increases the garbage collection (GC) pressure. Why is this important? The generics approach enables a truly zero allocation API, with zero GC pressure added. More on this as we continue.

Why Is It Faster?

The B-tree, being a tree, consists of nodes. Each node holds a list of items.

👁 Image

When the Item is a pre-generics plain old interface, the value it holds must live separately somewhere on the heap. The compiler can’t tell the item size. From the runtime perspective, an interface value is an unsafe pointer to data (word), a pointer to its type definition (typ), a pointer to interface definition (ityp) — see definitions in the reflect package. It’s easier to digest than the runtime package. In that case, we have items as a slice of int pointers.

On the other hand, with a generic interface

👁 Image

and a generic type definition

👁 Image

items are a slice of ints. This reduces the number of small heap objects by a factor of 32.

Enough theory. Let’s try to examine a concrete use. For the purpose of this article, I wrote a test program that is a scaled-up version of my benchmark code.

👁 Image

We are adding 100 million integers, and the degree of the B-tree (number of items in a node) is 1k. There are two versions of this program: one uses generics, the other plain old interface. The difference in code is minimal. It’s simply changing btree.New(degree) to btree.New[btree.Int](degree) in line 13. Let’s compare data gathered by running both versions under `/usr/bin/time -l -p`.

Here, using generics solves a version of the N+1 problem for slices of interfaces. Instead of one slice and N integers in heap, we now can have just the slice of ints. The results are profound. The new code behaves better in every way. The wall time duration is down by 40%, context switches are down by 40%, system resources utilization is down by 60% — all thanks to a 99.53% reduction of small heap objects.

Let’s conclude by taking a look at top CPU utilization.

go tool pprof -top cpu.pprof

You can literally see how messy the interface profile is, and how gc starts kicking in killing it… It’s even more evident when we focus on gc.

go tool pprof -focus gc -top cpu.pprof

The generic version spent 0.29s (2.62 percent) in GC while the interface version spent 6.06s accounting for – hold your breath – 32.49% of the total time!

Conclusion

By shifting from an implementation using interfaces to one using generics, we were able to significantly improve performance, minimize garbage collection time, and minimize CPU and other resource utilization, such as heap size. Particularly with heap size, we were able to reduce HeapObjects by 99.53%.

The future of Go generics is bright, especially in the domain of slices.

Join Us at P99 CONF

If you enjoyed diving into this level of Go performance optimization, you will really enjoy the tech talks at P99 CONF, a free virtual conference that will be held Oct. 19-20. P99 CONF is dedicated to engineers who obsess over P99 percentiles and high-performance, low-latency applications. You can see the speaker lineup and register now at p99conf.io.