Optimizing your code
Tags: rust, optimization
Published: 2020-01-09 06:57:46

This is the second post about optimization, in the first one I tried to give you the big picture of my ideal workflow and what are the tools I like best when I'm trying to figure out where to start.

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/8o930rr4jv8gjwhfues0.png)

Let's assume we already decided what we want to optimize for, we have our testcases ready and we managed to profile and prepare the benchmarks.

Now we know which are our top 5 codepaths that are using the largest amount of resources or taking the largest amount of time within our program.

## What to do now?

To keep things simple we focus again only on two subsets among the possible optimization targets: **single execution time** and **total number of allocations**.

### Execution time

In order to speed up something we have a number of strategies, here I'm giving you a list in order of expected gains.
#### Check your algorithm
Sometimes you start with a naive implementation that works but has a cubic [complexity](https://en.wikipedia.org/wiki/Computational_complexity) or worse, sometimes you picked a refined [O(ln(n))](https://en.wikipedia.org/wiki/Big_O_notation) algorithm and you forgot to make sure it doesn't have constant overheads that **dwarf** the rest of it for your specific workload. 
Thinking **again** about what you are solving can lead to surprising gains, the best algorithm on paper might not be the right one for you sometimes.
Sometimes having better **cache locality** and more compact code has more impact than using a theoretically optimal algorithm.
#### Find and exploit data parallelism
Most architectures support [SIMD](https://en.wikipedia.org/wiki/SIMD) in a way or another.
-  **rustc** in itself does a fairly decent job if you give it enough context (e.g. using [Iterators](https://doc.rust-lang.org/std/iter/trait.Iterator.html) instead of bare loops), but it can help only up to a point. You may build specialized binaries leveraging `target-cpu` or `target-features` e.g.:
``` sh
$ RUSTFLAGS="-C target-feature=+avx2" cargo build --release
```
- [packed_simd](https://github.com/rust-lang/packed_simd) may help you do more while staying portable.
-  [stdarch](https://github.com/rust-lang/stdarch/) gives you access to the arch-specific intrinsics and the cpu-features detection making fairly straightforward building optimized variants.
-  if you want to drop down to assembly, [nasm-rs](https://crates.io/crates/nasm-rs) and [cc-rs](https://crates.io/crates/cc) let you build everything with some ease. Sadly inline-assembly is **nightly-only**, so there is still some work to be done here to have a great support.

When you are going through this path [cargo-asm](https://github.com/gnzlbg/cargo-asm) helps a lot seeing what is going on and you should look for `cache-misses` and `branch-misprediction` statistics in your profiler if you aren't getting the performance you expect.

Last but not least you should be careful on which instruction sets you are using. Modern `x86_64` provides extremely powerful instructions in the `avx512f` set, but either you use them extensively or you might hit significant slowdowns due the cpu-state change.

#### Find and exploit workload parallelism
Most CPUs come with at least 2 cores and/or 2 or more hardware threads nowadays.

Using threads is the first clear example of throwing in more resources to get more performance: using additional threads usually means you end up using **more memory** and **spend** some cpu cycles on **synchronization**, the [Amdahl's_law](https://en.wikipedia.org/wiki/Amdahl%27s_law) usually models well the theoretical optimum you can reach.

The rust standard library comes with a good set of built-ins you can use, but there is an ecosystem of external crates to help further, among those my favorites are:
- [rayon](https://github.com/rayon-rs/rayon/) makes really easy to split the workload to a pool of workers if you are using [Iterators](https://doc.rust-lang.org/std/iter/trait.Iterator.html).
- [crossbeam](https://github.com/crossbeam-rs/crossbeam) provides a rich set of tools if you want to be more creative.

If your application is doing a good amount of **I/O**, you might want to explore asynchronous programming patterns. Under the hood you might deal with coroutines or threadpools, the API you are facing is still the arguably easy one based around [futures](https://docs.rs/futures/), the best runtimes I know are:
- [tokio](https://crates.io/crates/tokio) is a well established runtime to build your applications and comes with everything you need and some more.
- [async-std](https://github.com/async-rs/async-std) is a newer implementation of similar concepts, you might want to try it if you do not like what **tokio** offers or the other way round.

The asynchronous programming features provided by rust try to be nearly **zero-cost abstractions**, yet you have to deal with an additional **cognitive burden** when using it, so I suggest to not jump on it without considering all the other options.

### Remove slowdowns from the critical path
Once you managed to use the optimal algorithms, simdify lots of code and split the workload over a pool of threads, you will start seeing unexpected impact of your changes:
> Halving time spent in an hot path that comes in the top 5 from `perf report` or equivalent, does **not** map to the expected reduction of the overall execution time.

This happens when we split the workload over multiple threads, once you start doing this you need to pay **additional care** when **profiling** on what is going to run in parallel and what is painfully serial.
- [hawktracer](https://github.com/AlexEne/rust_hawktracer) provides a fairly fast way to collect the information and visualize it in an effective way.
- [cargo instruments](https://github.com/cmyr/cargo-instruments) can also provide good hints on this, but I find it less clear.

## Memory usage
I decided to not focus much on how to reduce the **resident set** or the **peak memory usage** since there isn't much to say: 
- allocate only what you need
- use `with_capacity()` instead of `new()` whenever you know already the maximum size of your container.
- use the smallest datatypes in arrays/tables as long this choice does not have other side effects on performance.

### Total number of allocations
The **number of allocations** is a more interesting problem:
- Using the heap has an **inherent cost** compared to using the stack
- Every time you allocate and deallocate you increase the **risk of fragmenting** the memory, do that often enough and the allocator cannot satisfy your next request.

Within reason you might want to have stack-allocated buffers to use instead of having `Vec`s and `Box`es around, rust makes fairly easy pass around references, even across threads (as shown by [crossbeam scope](https://docs.rs/crossbeam/0.7.3/crossbeam/fn.scope.html))
- [ArrayVec](https://github.com/bluss/arrayvec) is often a boon when you want to convert `Vec`s of known (maximum) size by using a stack-allocated array as storage.
- [SmallVec](https://github.com/servo/rust-smallvec) is another crate offering similar features.

## What next

I provided some pointers on how to optimize, and, as for the previous post, I intentionally avoided making examples to keep the whole thing reasonably compact.

During the next posts I'll start to focus on specific situations that happened while developing [rav1e](https://github.com/xiph/rav1e) and provide some example usage of some of the tools.