C vs Rust vs Go: performance analysis

DISCLAIMER: In this article I will compare C, Rust and Go performance against one specific algorithm. This in not how performance tests should be conducted! If you are interested in more comprehensive comparison please refer to more reliable tests https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/gcc-rust.html, https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/rust-go.html

The Problem

In one of my previous jobs I got a task: “For given image find popular colors in that image, so users can browse images by it’s colors”.

For example, for following image:

Solution might find:

Of course, designed solution should work as fast as possible.

The Solution

Problem of finding dominant colors can be solved in may ways. At first I decided to use k-means. As I soon find out, k-means are really slow :( Fortunately I stumble upon great article by Matt Nedrich https://spin.atomicobject.com/2016/12/07/pixels-and-palettes-extracting-color-palettes-from-images/ Matt presents few possible ways to extract palette from image. One of the methods, histogram, is very simple in terms of computations so I decided to go with that approach.

In simple histogram method you divide 3D color space to fixed number of clusters. For example you can divide space into 8 clusters by cutting them in the middle of each axis:

Then, for each pixel in the image, we assign pixel to it’s cluster. After that we calculate cluster averages and we got up to 8 possible colors.

Obvious optimization

Histogram algorithm iterates over every pixel in the image. So it will take more time to process larger image than small one. Time complexity will be proportional to size of the image:

O(n) = n

Problem with that kind of solution is that you cannot estimate time if you don’t know size of an input image. So it is impossible to ensure appropriate response time. What’s more there is not much to do with that unless you are willing to sacrifice quality of the palette.

Simple solution to that problem is to ignore image size and pick some big, but constant number of pixels from image. If you choose large enough sample from image results might still be good enough for your problem. In that case time complexity may be defined as constant:

O(n) = 1

Implementation

Constant complexity is the best what we can get from algorithms point of view. Of course even constant complexity might not be fast enough in real life scenario. Our actual complexity is not in fact 1, it’s actually C * 1. Where C is some constant, which will depend a lot from programing language we choose.

This is where three languages comes to play. I have implemented histogram algorithm in C, Rust and Go:

C: https://gitlab.com/marekm4/dominant_color/blob/master/color.c#L15

Rust: https://github.com/marekm4/dominant_color/blob/master/src/lib.rs#L20

Go: https://github.com/marekm4/color-extractor/blob/master/color_extractor.go#L35

If you want to test algorithm in action you checkout demo page: https://color-extractor-demo.herokuapp.com/

Let’s run some tests

For the purpose of the test I will run each implementation 100,000 times on Intel Core i7–7500U processor. Only computation part will be tested, image loading will be omitted. Sample scenario will look similar to this:

for i in 0..100000 {
    dominant_color::get_colors(&image.raw_pixels());
}

Before running test I expected that C and Rust will have similar result and Go will be slightly slower, but not much. What I saw astonished me:

C     14s
Rust  21s
Go   370s

Go was more that 10 times slower than C and Rust! I ran tests few times to make sure that it isn’t some random error.

Problem with Go

Of course there were something wrong with Go implementation. Algorithm is strait forward and all three implementations were returning the same results. So my hypothesis was that it must be somehow connected with the way that Go is accessing pixels data. And in fact this was only significant difference between C/Rust and Go implementation.

C and Rust are using single, raw block of memory. So when you need to take 15th pixel from image you just access it by image[15]. But Go have special struct for dealing with images https://golang.org/pkg/image/#Image When you need a pixel form image in Go you use .At(x, y int) method. For some reason At method doesn’t perform as efficient as accessing memory directly.

To verify my hypothesis I changed Go implementation. After loading file to image struct I copied it to Go array and pass this array to algorithm. So test setup look similar to this:

for i := 0; i < 100000; i++ {
   color_extractor.ExtractColors(width, height, image)
}

Final results

After changing Go implementation to use array instead of image struct I ran Go tests again:

C    14s
Rust 21s
Go   34s

That’s much better :) Although Go implementation is still slower than C or Rust. the results are on the same scale.

Conclusions

All three languages are pretty fast and it was fun to play with them. In both C and Rust it was easy to write efficient code without any extra optimizations. On the other hand, both Rust and Go implementation was fast in terms of developer productivity. In terms of implementing efficient algorithms Rust seems to be in sweet spot. It doesn’t hide things between inefficient abstractions, yet still you can be as productive as in Go.