Making Rust as Fast as Go

Go is garbage collected, rust is not. That means rust is faster than go, right? No! Not always.

Let’s take an example that I stumbled across while playing around with an algorithm that calculates Levenshtein edit distances. I wanted to compare the performance of the same algorithm in a bunch of different languages. Two of these languages were rust and go.

To my surprise, the go version was faster than the rust version. A lot faster. My initial reaction was that I must have implemented the rust version incorrectly. Maybe I was doing some unsafe (but fast) things in go that rust wouldn’t let me do. To account for this, I laid out some ground rules:

1. The more idiomatic the better. Rust, for example, promises zero cost abstractions so we should lean on this & write safe code
2. No static global variables. This means that containers need to be heap allocated & dynamically sized. We don’t know how big the inputs will be!
3. Memory access should be safe. Don’t eliminate bounds checks
4. Assume that text is utf8 encoded

In short, this should be code that you’d happily ship to prod. Here’s what I ended up with:

func EditDistance(source, target string) int {
	if len(source) == 0 {
		return len(target)
	}

	if len(target) == 0 {
		return len(source)
	}

	sourceChars := []rune(source)
	targetChars := []rune(target)

	cache := make([]int, len(target)+1)
	for i := 0; i < len(target)+1; i++ {
		cache[i] = i
	}

	for i, sourceChar := range sourceChars {
		nextDist := i + 1
		for j, targetChar := range targetChars {
			currentDist := nextDist

			distIfSubstitute := cache[j]
			if sourceChar != targetChar {
				distIfSubstitute++
			}

			distIfInsert := currentDist + 1
			distIfDelete := cache[j+1] + 1

			nextDist = min(distIfDelete, min(distIfInsert, distIfSubstitute))

			cache[j] = currentDist
		}

		cache[len(target)] = nextDist
	}

	return cache[len(target)]
}

pub fn levenshtein_distance(source: &str, target: &str) -> usize {
    if source.is_empty() {
        return target.len();
    }

    if target.is_empty() {
        return source.len();
    }

    let mut cache: Vec<usize> = (0..=target.chars().count()).collect();

    for (i, source_char) in source.chars().enumerate() {
        let mut next_dist = i + 1;

        for (j, target_char) in target.chars().enumerate() {
            let current_dist = next_dist;

            let mut dist_if_substitute = cache[j];
            if source_char != target_char {
                dist_if_substitute += 1;
            }

            let dist_if_insert = current_dist + 1;
            let dist_if_delete = cache[j + 1] + 1;

            next_dist = std::cmp::min(
                dist_if_substitute,
                std::cmp::min(dist_if_insert, dist_if_delete),
            );

            cache[j] = current_dist;
        }

        cache[target.len()] = next_dist;
    }

    cache[target.len()]
}

Even with the playing field levelled, go still outperformed rust by 50%. For the dataset I was using to benchmark the programs, the go version to 1.5 seconds and rust 3 seconds.

This was bizarre. As far as I could tell, these programs were identical besides the fact that the go runtime needs to spend precious cycles collecting garbage. That means it should be slower, right?

I took the question to my coworkers, who had some good suggestions. Theories included escape analysis , string allocation, and the rust implementation being wrong. The last one was true but the performance gap remained once I fixed it (I have tests now!).

The winning suggestion ended up being to switch the allocator in the rust program to jemalloc . This was the default allocator used by rust binaries in the past, but it was removed in favour of using the system allocator instead in late 2018 . Read #36963 to get the full rationale for this change.

To change the allocator, you simply add the following to the start of your program:

extern crate jemallocator;

#[global_allocator]
static ALLOC: jemallocator::Jemalloc = jemallocator::Jemalloc;

This made a huge difference. On my machine, this dropped the execution time from 3 seconds to about 1.8 seconds. Let’s take a look at the flamegraphs (generated with flamegraph-rs/flamegraph ) to see the change:

This means that the time spend allocating has dropped from about 40% to 20%. Keep in mind this is for the full benchmark, including all the setup code, but it gives us a good sense of what changed.

I’m not sure why the change was so severe. I tried searching for things like “macos allocator slow” but didn’t find anything. If you have some information here, please let me know!

Why doesn’t go suffer from the slow system allocator on macos? Two things come to mind. The first is that go uses a custom allocator . I assume that this is also faster than the macos system allocator. The second is that while this program does spend a lot of time allocating and freeing memory, there are barely any objects in the heap at any given moment. EditDistance only allocates one object on the heap ( cache ), meaning that the time spent garbage collecting is probably negligible.

So the answer is:

1. The macos allocator is slow
2. Go uses a custom allocator, which is faster than the one that ships with macos

What’s the lesson here? If you’re writing a rust program that does a lot of allocation, consider using a non-system allocator if you need some more performance. Don’t make the mistake of extrapolating beyond that simple point, though. This is a “microbenchmark”, and the results are tightly coupled to the very contrived scenario I’ve concocted.

Check out the whole github repo. It has implementations in several languages, as well as scripts to benchmark + test them.