The Rust Performance Book

First published in November 2020

Written by Nicholas Nethercote and others

Source code

Introduction

Performance is important for many Rust programs.

This book contains many techniques that can improve the performance—speed and memory usage—of Rust programs. The Compile Times section also contains some techniques that will improve the compile times of Rust programs. Some techniques only require changing build configurations, but many require changing code.

Some techniques are entirely Rust-specific, and some involve ideas that can be applied (often with modifications) to programs written in other languages. The General Tips section also includes some general principles that apply to any programming language. Nonetheless, this book is mostly about the performance of Rust programs and is no substitute for a general purpose guide to profiling and optimization.

This book also focuses on techniques that are practical and proven: many are accompanied by links to pull requests or other resources that show how the technique was used on a real-world Rust program.

This book is deliberately terse, favouring breadth over depth, so that it is quick to read. It links to external sources that provide more depth when appropriate.

This book is aimed at intermediate and advanced Rust users. Beginner Rust users have more than enough to learn and these techniques are likely to be an unhelpful distraction to them.

Benchmarking

Benchmarking typically involves comparing the performance of two or more programs that do the same thing. Sometimes this might involve comparing two or more different programs, e.g. Firefox vs Safari vs Chrome. Sometimes it involves comparing two different versions of the same program. This latter case lets us reliably answer the question “did this change speed things up?”

Benchmarking is a complex topic and a thorough coverage is beyond the scope of this book, but here are the basics.

First, you need workloads to measure. Ideally, you would have a variety of workloads that represent realistic usage of your program. Workloads using real-world inputs are best, but microbenchmarks and stress tests can be useful in moderation.

Second, you need a way to run the workloads, which will also dictate the metrics used. Rust’s built-in benchmark tests are a simple starting point, but they use unstable features and therefore only work on Nightly Rust. Criterion is a more sophisticated alternative. Custom benchmarking harnesses are also possible. For example, rustc-perf is the harness used to benchmark the Rust compiler.

When it comes to metrics, there are many choices, and the right one(s) will depend on the nature of the program being benchmarked. For example, metrics that make sense for a batch program might not make sense for an interactive program. Wall-time is an obvious choice in many cases because it corresponds to what users perceive. However, it can suffer from high variance. In particular, tiny changes in memory layout can cause significant but ephemeral performance fluctuations. Therefore, other metrics with lower variance (such as cycles or instruction counts) may be a reasonable alternative.

Summarizing measurements from multiple workloads is also a challenge, and there are a variety of ways to do it, with no single method being obviously best.

Good benchmarking is hard. Having said that, do not stress too much about having a perfect benchmarking setup, particularly when you start optimizing a program. A mediocre setup is far better than no setup. Keep an open mind about what you are measuring, and over time you can make benchmarking improvements as you learn about the performance characteristics of your program.

Build Configuration

The right build configuration will maximize the performance of your Rust program without any changes to its code. But you should check your program’s performance after applying any of the following changes, because they can sometimes worsen performance.

Release Builds

The single most important Rust performance tip is simple but easy to overlook: make sure you are using a release build rather than a debug build when you want high performance. This is most often done by specifying the --release flag to Cargo.

A release build typically runs much faster than a debug build. 10-100x speedups over debug builds are common!

Debug builds are the default. They are produced if you run cargo build, cargo run, or rustc without any additional options. Debug builds are good for debugging, but are not optimized.

Consider the following final line of output from a cargo build run.

Finished dev [unoptimized + debuginfo] target(s) in 29.80s

The [unoptimized + debuginfo] indicates that a debug build has been produced. The compiled code will be placed in the target/debug/ directory. cargo run will run the debug build.

Release builds are more optimized than debug builds. They also omit some checks, such as debug assertions and integer overflow checks. Produce one with cargo build --release, cargo run --release, or rustc -O. (Alternatively, rustc has multiple other options for optimized builds, such as -C opt-level.) This will typically take longer than a debug build because of the additional optimizations.

Consider the following final line of output from a cargo build --release run.

Finished release [optimized] target(s) in 1m 01s

The [optimized] indicates that a release build has been produced. The compiled code will be placed in the target/release/ directory. cargo run --release will run the release build.

See the Cargo profile documentation for more details about the differences between debug builds (which use the dev profile) and release builds (which use the release profile).

Link-time Optimization

Link-time optimization (LTO) is a whole-program optimization technique that can improve runtime performance by 10-20% or more, at the cost of increased build times. For any individual Rust program it is easy to see if the runtime versus compile-time trade-off is worthwhile.

The simplest way to try LTO is to add the following lines to the Cargo.toml file and do a release build.

[profile.release]
lto = true

This will result in “fat” LTO, which optimizes across all crates in the dependency graph.

Alternatively, use lto = "thin" in Cargo.toml to use “thin” LTO, which is a less aggressive form of LTO that often works as well as “fat” LTO without increasing build times as much.

See the Cargo LTO documentation for more details about the lto setting, and about enabling specific settings for different profiles.

Codegen Units

The Rust compiler splits your crate into multiple codegen units to parallelize (and thus speed up) compilation. However, this might cause it to miss some potential optimizations. If you want to potentially improve runtime performance at the cost of larger compile time, you can set the number of units to one:

[profile.release]
codegen-units = 1

Example.

Be wary that the codegen unit count is a heuristic and thus a smaller count can actually result in a slower program.

Using CPU Specific Instructions

If you do not care that much about the compatibility of your binary on older (or other types of) processors, you can tell the compiler to generate the newest (and potentially fastest) instructions specific to a certain CPU architecture.

For example, if you pass -C target-cpu=native to rustc, it will use the best instructions for your current CPU:

$ RUSTFLAGS="-C target-cpu=native" cargo build --release

This can have a large effect, especially if the compiler finds vectorization opportunities in your code.

As of July 2022, on M1 Macs there is an issue where using -C target-cpu=native doesn’t detect all the CPU features. You need to use -C target-cpu=apple-m1 instead.

If you are unsure whether -C target-cpu=native is working optimally, compare the output of rustc --print cfg and rustc --print cfg -C target-cpu=native to see if the CPU features are being detected correctly in the latter case. If not, you can use -C target-feature to target specific features.

Abort on panic!

If you do not need to catch or unwind panics, you can tell the compiler to simply abort on panics. This might reduce binary size and increase performance slightly:

[profile.release]
panic = "abort"

Profile-guided Optimization

Profile-guided optimization (PGO) is a compilation model where you compile your program, run it on sample data while collecting profiling data, and then use that profiling data to guide a second compilation of the program. Example.

It is an advanced technique that takes some effort to set up, but is worthwhile in some cases. See the rustc PGO documentation for details.

Linting

Clippy is a collection of lints to catch common mistakes in Rust code. It is an excellent tool to run on Rust code in general. It can also help with performance, because a number of the lints relate to code patterns that can cause sub-optimal performance.

Given that automated detection of problems is preferable to manual detection, the rest of this book will not mention performance problems that Clippy detects by default.

Basics

Once installed, it is easy to run:

cargo clippy

The full list of performance lints can be seen by visiting the lint list and deselecting all the lint groups except for “Perf”.

As well as making the code faster, the performance lint suggestions usually result in code that is simpler and more idiomatic, so they are worth following even for code that is not executed frequently.

Conversely, some non-performance lint suggestions can improve performance. For example, the ptr_arg style lint suggests changing various container arguments to slices, such as changing &mut Vec<T> arguments to &mut [T]. The primary motivation here is that a slice gives a more flexible API, but it may also result in faster code due to less indirection and better optimization opportunities for the compiler. Example.

Disallowing Types

In the following chapters we will see that it is sometimes worth avoiding certain standard library types in favour of alternatives that are faster. If you decide to use these alternatives, it is easy to accidentally use the standard library types in some places by mistake.

You can use Clippy’s disallowed_types lint, added in Rust 1.55, to avoid this problem. For example, to disallow the use of the standard hash tables (for reasons explained in the Hashing section) add a clippy.toml file to your code with the following lines.

disallowed-types = ["std::collections::HashMap", "std::collections::HashSet"]

Then add the following declaration to your Rust code.

#![warn(clippy::disallowed_types)]

This is necessary because disallowed_types is (at the time of writing) a “nursery” (under development) lint. This may change in the future.

Profiling

When optimizing a program, you also need a way to determine which parts of the program are “hot” (executed frequently enough to affect runtime) and worth modifying. This is best done via profiling.

Profilers

There are many different profilers available, each with their strengths and weaknesses. The following is an incomplete list of profilers that have been used successfully on Rust programs.

• perf is a general-purpose profiler that uses hardware performance counters. Hotspot and Firefox Profiler are good for viewing data recorded by perf. It works on Linux.
• Instruments is a general-purpose profiler that comes with Xcode on macOS.
• AMD μProf is a general-purpose profiler. It works on Windows and Linux.
• flamegraph is a Cargo command that uses perf/DTrace to profile your code and then displays the results in a flame graph. It works on Linux and all platforms that support DTrace (macOS, FreeBSD, NetBSD, and possibly Windows).
• Cachegrind & Callgrind give global, per-function, and per-source-line instruction counts and simulated cache and branch prediction data. They work on Linux and some other Unixes.
• DHAT is good for finding which parts of the code are causing a lot of allocations, and for giving insight into peak memory usage. It can also be used to identify hot calls to memcpy. It works on Linux and some other Unixes. dhat-rs is an experimental alternative that is a little less powerful and requires minor changes to your Rust program, but works on all platforms.
• heaptrack and bytehound are heap profiling tools. They work on Linux.
• counts supports ad hoc profiling, which combines the use of eprintln! statement with frequency-based post-processing, which is good for getting domain-specific insights into parts of your code. It works on all platforms.
• Coz performs causal profiling to measure optimization potential, and has Rust support via coz-rs. It works on Linux.

Debug Info

To profile a release build effectively you might need to enable source line debug info. To do this, add the following lines to your Cargo.toml file:

[profile.release]
debug = 1

See the Cargo documentation for more details about the debug setting.

Unfortunately, even after doing the above step you won’t get detailed profiling information for standard library code. This is because shipped versions of the Rust standard library are not built with debug info. To remedy this, you can build your own version of the compiler and standard library, following these instructions, and adding the following lines to the config.toml file:

[rust]
debuginfo-level = 1

This is a hassle, but may be worth the effort in some cases.

Symbol Demangling

Rust uses a mangling scheme to encode function names in compiled code. If a profiler is unaware of this scheme, its output may contain symbol names beginning with _ZN or _R, such as _ZN3foo3barE or _ZN28_$u7b$$u7b$closure$u7d$$u7d$E or _RMCsno73SFvQKx_1cINtB0_3StrKRe616263_E

Names like these can be manually demangled using rustfilt.

Inlining

Entry to and exit from hot, uninlined functions often accounts for a non-trivial fraction of execution time. Inlining these functions can provide small but easy speed wins.

There are four inline attributes that can be used on Rust functions.

• None. The compiler will decide itself if the function should be inlined. This will depend on the optimization level, the size of the function, etc. If you are not using link-time optimization, functions will never be inlined across crates.
• #[inline]. This suggests that the function should be inlined, including across crate boundaries.
• #[inline(always)]. This strongly suggests that the function should be inlined, including across crate boundaries.
• #[inline(never)]. This strongly suggests that the function should not be inlined.

Inline attributes do not guarantee that a function is inlined or not inlined, but in practice, #[inline(always)] will cause inlining in all but the most exceptional cases.

Simple Cases

The best candidates for inlining are (a) functions that are very small, or (b) functions that have a single call site. The compiler will often inline these functions itself even without an inline attribute. But the compiler cannot always make the best choices, so attributes are sometimes needed. Example 1, Example 2, Example 3, Example 4, Example 5.

Cachegrind is a good profiler for determining if a function is inlined. When looking at Cachegrind’s output, you can tell that a function has been inlined if (and only if) its first and last lines are not marked with event counts. For example:

      .  #[inline(always)]
      .  fn inlined(x: u32, y: u32) -> u32 {
700,000      eprintln!("inlined: {} + {}", x, y);
200,000      x + y
      .  }
      .  
      .  #[inline(never)]
400,000  fn not_inlined(x: u32, y: u32) -> u32 {
700,000      eprintln!("not_inlined: {} + {}", x, y);
200,000      x + y
200,000  }

You should measure again after adding inline attributes, because the effects can be unpredictable. Sometimes it has no effect because a nearby function that was previously inlined no longer is. Sometimes it slows the code down. Inlining can also affect compile times, especially cross-crate inlining which involves duplicating internal representations of the functions.

Harder Cases

Sometimes you have a function that is large and has multiple call sites, but only one call site is hot. You would like to inline the hot call site for speed, but not inline the cold call sites to avoid unnecessary code bloat. The way to handle this is to split the function always-inlined and never-inlined variants, with the latter calling the former.

For example, this function:

#![allow(unused)]
fn main() {
fn one() {};
fn two() {};
fn three() {};
fn my_function() {
    one();
    two();
    three();
}
}

Would become these two functions:

#![allow(unused)]
fn main() {
fn one() {};
fn two() {};
fn three() {};
// Use this at the hot call site.
#[inline(always)]
fn inlined_my_function() {
    one();
    two();
    three();
}

// Use this at the cold call sites.
#[inline(never)]
fn uninlined_my_function() {
    inlined_my_function();
}
}

Example 1, Example 2.

Hashing

HashSet and HashMap are two widely-used types. The default hashing algorithm is not specified, but at the time of writing the default is an algorithm called SipHash 1-3. This algorithm is high quality—it provides high protection against collisions—but is relatively slow, particularly for short keys such as integers.

If profiling shows that hashing is hot, and HashDoS attacks are not a concern for your application, the use of hash tables with faster hash algorithms can provide large speed wins.

• rustc-hash provides FxHashSet and FxHashMap types that are drop-in replacements for HashSet and HashMap. Its hashing algorithm is low-quality but very fast, especially for integer keys, and has been found to out-perform all other hash algorithms within rustc. (fxhash is an older, less well maintained implementation of the same algorithm and types.)
• fnv provides FnvHashSet and FnvHashMap types. Its hashing algorithm is higher quality than rustc-hash’s but a little slower.
• ahash provides AHashSet and AHashMap. Its hashing algorithm can take advantage of AES instruction support that is available on some processors.

If hashing performance is important in your program, it is worth trying more than one of these alternatives. For example, the following results were seen in rustc.

• The switch from fnv to fxhash gave speedups of up to 6%.
• An attempt to switch from fxhash to ahash resulted in slowdowns of 1-4%.
• An attempt to switch from fxhash back to the default hasher resulted in slowdowns ranging from 4-84%!

If you decide to universally use one of the alternatives, such as FxHashSet/FxHashMap, it is easy to accidentally use HashSet/HashMap in some places. You can use Clippy to avoid this problem.

Some types don’t need hashing. For example, you might have a newtype that wraps an integer and the integer values are random, or close to random. For such a type, the distribution of the hashed values won’t be that different to the distribution of the values themselves. In this case the nohash_hasher crate can be useful.

Hash function design is a complex topic and is beyond the scope of this book. The ahash documentation has a good discussion.

Heap Allocations

Heap allocations are moderately expensive. The exact details depend on which allocator is in use, but each allocation (and deallocation) typically involves acquiring a global lock, doing some non-trivial data structure manipulation, and possibly executing a system call. Small allocations are not necessarily cheaper than large allocations. It is worth understanding which Rust data structures and operations cause allocations, because avoiding them can greatly improve performance.

The Rust Container Cheat Sheet has visualizations of common Rust types, and is an excellent companion to the following sections.

Profiling

If a general-purpose profiler shows malloc, free, and related functions as hot, then it is likely worth trying to reduce the allocation rate and/or using an alternative allocator.

DHAT is an excellent profiler to use when reducing allocation rates. It works on Linux and some other Unixes. It precisely identifies hot allocation sites and their allocation rates. Exact results will vary, but experience with rustc has shown that reducing allocation rates by 10 allocations per million instructions executed can have measurable performance improvements (e.g. ~1%).

Here is some example output from DHAT.

AP 1.1/25 (2 children) {
  Total:     54,533,440 bytes (4.02%, 2,714.28/Minstr) in 458,839 blocks (7.72%, 22.84/Minstr), avg size 118.85 bytes, avg lifetime 1,127,259,403.64 instrs (5.61% of program duration)
  At t-gmax: 0 bytes (0%) in 0 blocks (0%), avg size 0 bytes
  At t-end:  0 bytes (0%) in 0 blocks (0%), avg size 0 bytes
  Reads:     15,993,012 bytes (0.29%, 796.02/Minstr), 0.29/byte
  Writes:    20,974,752 bytes (1.03%, 1,043.97/Minstr), 0.38/byte
  Allocated at {
    #1: 0x95CACC9: alloc (alloc.rs:72)
    #2: 0x95CACC9: alloc (alloc.rs:148)
    #3: 0x95CACC9: reserve_internal<syntax::tokenstream::TokenStream,alloc::alloc::Global> (raw_vec.rs:669)
    #4: 0x95CACC9: reserve<syntax::tokenstream::TokenStream,alloc::alloc::Global> (raw_vec.rs:492)
    #5: 0x95CACC9: reserve<syntax::tokenstream::TokenStream> (vec.rs:460)
    #6: 0x95CACC9: push<syntax::tokenstream::TokenStream> (vec.rs:989)
    #7: 0x95CACC9: parse_token_trees_until_close_delim (tokentrees.rs:27)
    #8: 0x95CACC9: syntax::parse::lexer::tokentrees::<impl syntax::parse::lexer::StringReader<'a>>::parse_token_tree (tokentrees.rs:81)
  }
}

It is beyond the scope of this book to describe everything in this example, but it should be clear that DHAT gives a wealth of information about allocations, such as where and how often they happen, how big they are, how long they live for, and how often they are accessed.

Box

Box is the simplest heap-allocated type. A Box<T> value is a T value that is allocated on the heap.

It is sometimes worth boxing one or more fields in a struct or enum fields to make a type smaller. (See the Type Sizes chapter for more about this.)

Other than that, Box is straightforward and does not offer much scope for optimizations.

Rc/Arc

Rc/Arc are similar to Box, but the value on the heap is accompanied by two reference counts. They allow value sharing, which can be an effective way to reduce memory usage.

However, if used for values that are rarely shared, they can increase allocation rates by heap allocating values that might otherwise not be heap-allocated. Example.

Unlike Box, calling clone on an Rc/Arc value does not involve an allocation. Instead, it merely increments a reference count.

Vec

Vec is a heap-allocated type with a great deal of scope for optimizing the number of allocations, and/or minimizing the amount of wasted space. To do this requires understanding how its elements are stored.

A Vec contains three words: a length, a capacity, and a pointer. The pointer will point to heap-allocated memory if the capacity is nonzero and the element size is nonzero; otherwise, it will not point to allocated memory.

Even if the Vec itself is not heap-allocated, the elements (if present and nonzero-sized) always will be. If nonzero-sized elements are present, the memory holding those elements may be larger than necessary, providing space for additional future elements. The number of elements present is the length, and the number of elements that could be held without reallocating is the capacity.

When the vector needs to grow beyond its current capacity, the elements will be copied into a larger heap allocation, and the old heap allocation will be freed.

Vec growth

A new, empty Vec created by the common means (vec![] or Vec::new or Vec::default) has a length and capacity of zero, and no heap allocation is required. If you repeatedly push individual elements onto the end of the Vec, it will periodically reallocate. The growth strategy is not specified, but at the time of writing it uses a quasi-doubling strategy resulting in the following capacities: 0, 4, 8, 16, 32, 64, and so on. (It skips directly from 0 to 4, instead of going via 1 and 2, because this avoids many allocations in practice.) As a vector grows, the frequency of reallocations will decrease exponentially, but the amount of possibly-wasted excess capacity will increase exponentially.

This growth strategy is typical for growable data structures and reasonable in the general case, but if you know in advance the likely length of a vector you can often do better. If you have a hot vector allocation site (e.g. a hot Vec::push call), it is worth using eprintln! to print the vector length at that site and then doing some post-processing (e.g. with counts) to determine the length distribution. For example, you might have many short vectors, or you might have a smaller number of very long vectors, and the best way to optimize the allocation site will vary accordingly.

Short Vecs

If you have many short vectors, you can use the SmallVec type from the smallvec crate. SmallVec<[T; N]> is a drop-in replacement for Vec that can store N elements within the SmallVec itself, and then switches to a heap allocation if the number of elements exceeds that. (Note also that vec![] literals must be replaced with smallvec![] literals.) Example 1, Example 2.

SmallVec reliably reduces the allocation rate when used appropriately, but its use does not guarantee improved performance. It is slightly slower than Vec for normal operations because it must always check if the elements are heap-allocated or not. Also, If N is high or T is large, then the SmallVec<[T; N]> itself can be larger than Vec<T>, and copying of SmallVec values will be slower. As always, benchmarking is required to confirm that an optimization is effective.

If you have many short vectors and you precisely know their maximum length, ArrayVec from the arrayvec crate is a better choice than SmallVec. It does not require the fallback to heap allocation, which makes it a little faster. Example.

Longer Vecs

If you know the minimum or exact size of a vector, you can reserve a specific capacity with Vec::with_capacity, Vec::reserve, or Vec::reserve_exact. For example, if you know a vector will grow to have at least 20 elements, these functions can immediately provide a vector with a capacity of at least 20 using a single allocation, whereas pushing the items one at a time would result in four allocations (for capacities of 4, 8, 16, and 32). Example.

If you know the maximum length of a vector, the above functions also let you not allocate excess space unnecessarily. Similarly, Vec::shrink_to_fit can be used to minimize wasted space, but note that it may cause a reallocation.

String

A String contains heap-allocated bytes. The representation and operation of String are very similar to that of Vec<u8>. Many Vec methods relating to growth and capacity have equivalents for String, such as String::with_capacity.

The SmallString type from the smallstr crate is similar to the SmallVec type.

The String type from the smartstring crate is a drop-in replacement for String that avoids heap allocations for strings with less than three words’ worth of characters. On 64-bit platforms, this is any string that is less than 24 bytes, which includes all strings containing 23 or fewer ASCII characters. Example.

Note that the format! macro produces a String, which means it performs an allocation. If you can avoid a format! call by using a string literal, that will avoid this allocation. Example. std::format_args and/or the lazy_format crate may help with this.

Hash tables

HashSet and HashMap are hash tables. Their representation and operations are similar to those of Vec, in terms of allocations: they have a single contiguous heap allocation, holding keys and values, which is reallocated as necessary as the table grows. Many Vec methods relating to growth and capacity have equivalents for HashSet/HashMap, such as HashSet::with_capacity.

Cow

Sometimes you have some borrowed data, such as a &str, that is mostly read-only but occasionally needs to be modified. Cloning the data every time would be wasteful. Instead you can use “clone-on-write” semantics via the Cow type, which can represent both borrowed and owned data.

Typically, when starting with a borrowed value x you wrap it in a Cow with Cow::Borrowed(x). Because Cow implements Deref, you can call non-mutating methods directly on the data it encloses. If mutation is desired, Cow::to_mut will obtain a mutable reference to an owned value, cloning if necessary.

Cow can be fiddly to get working, but it is often worth the effort. Example 1, Example 2, Example 3, Example 4.

clone

Calling clone on a value that contains heap-allocated memory typically involves additional allocations. For example, calling clone on a non-empty Vec requires a new allocation for the elements (but note that the capacity of the new Vec might not be the same as the capacity of the original Vec). The exception is Rc/Arc, where a clone call just increments the reference count.

clone_from is an alternative to clone. a.clone_from(&b) is equivalent to a = b.clone() but may avoid unnecessary allocations. For example, if you want to clone one Vec over the top of an existing Vec, the existing Vec’s heap allocation will be reused if possible, as the following example shows.

#![allow(unused)]
fn main() {
let mut v1: Vec<u32> = Vec::with_capacity(99);
let v2: Vec<u32> = vec![1, 2, 3];
v1.clone_from(&v2); // v1's allocation is reused
assert_eq!(v1.capacity(), 99);
}

Although clone usually causes allocations, it is a reasonable thing to use in many circumstances and can often make code simpler. Use profiling data to see which clone calls are hot and worth taking the effort to avoid.

Sometimes Rust code ends up containing unnecessary clone calls, due to (a) programmer error, or (b) changes in the code that render previously-necessary clone calls unnecessary. If you see a hot clone call that does not seem necessary, sometimes it can simply be removed. Example 1, Example 2, Example 3.

to_owned

ToOwned::to_owned is implemented for many common types. It creates owned data from borrowed data, usually by cloning, and therefore often causes heap allocations. For example, it can be used to create a String from a &str.

Sometimes to_owned calls can be avoided by storing a reference to borrowed data in a struct rather than an owned copy. This requires lifetime annotations on the struct, complicating the code, and should only be done when profiling and benchmarking shows that it is worthwhile. Example.

Reusing Collections

Sometimes you need to build up a collection such as a Vec in stages. It is usually better to do this by modifying a single Vec than by building multiple Vecs and then combining them.

For example, if you have a function do_stuff that produces a Vec that might be called multiple times:

#![allow(unused)]
fn main() {
fn do_stuff(x: u32, y: u32) -> Vec<u32> {
    vec![x, y]
}
}

It might be better to instead modify a passed-in Vec:

#![allow(unused)]
fn main() {
fn do_stuff(x: u32, y: u32, vec: &mut Vec<u32>) {
    vec.push(x);
    vec.push(y);
}
}

Sometimes it is worth keeping around a “workhorse” collection that can be reused. For example, if a Vec is needed for each iteration of a loop, you could declare the Vec outside the loop, use it within the loop body, and then call clear at the end of the loop body (to empty the Vec without affecting its capacity). This avoids allocations at the cost of obscuring the fact that each iteration’s usage of the Vec is unrelated to the others. Example 1, Example 2.

Similarly, it is sometimes worth keeping a “workhorse” collection within a struct, to be reused in one or more methods that are called repeatedly.

Using an Alternative Allocator

Another option for improving the performance of allocation-heavy Rust programs is to replace the default (system) allocator with an alternative allocator. The exact effect will depend on the individual program and the alternative allocator chosen, but large improvements in speed and very large reductions in memory usage have been seen in practice. The effect will also vary across platforms, because each platform’s system allocator has its own strengths and weaknesses. The use of an alternative allocator can also affect binary size.

One popular alternative allocator for Linux and Mac is jemalloc, usable via the tikv-jemallocator crate. To use it, add a dependency to your Cargo.toml file:

[dependencies]
tikv-jemallocator = "0.4.0"

Then add the following somewhere in your Rust code:

#[global_allocator]
static GLOBAL: tikv_jemallocator::Jemalloc = tikv_jemallocator::Jemalloc;

tikv-jemallocator is a fork of the jemallocator crate. As of December 2021, tikv-jemallocator uses a jemalloc version that is newer and has better performance than the jemalloc version used by jemallocator.

Another alternative allocator that works on many platforms is mimalloc, usable via the mimalloc crate.

Avoiding Regressions

To ensure the number and/or size of allocations done by your code doesn’t increase unintentionally, you can use the heap usage testing feature of dhat-rs to write tests that check particular code snippets allocate the expected amount of heap memory.

Type Sizes

Shrinking oft-instantiated types can help performance.

For example, if memory usage is high, a heap profiler like DHAT can identify the hot allocation points and the types involved. Shrinking these types can reduce peak memory usage, and possibly improve performance by reducing memory traffic and cache pressure.

Furthermore, Rust types that are larger than 128 bytes are copied with memcpy rather than inline code. If memcpy shows up in non-trivial amounts in profiles, DHAT’s “copy profiling” mode will tell you exactly where the hot memcpy calls are and the types involved. Shrinking these types to 128 bytes or less can make the code faster by avoiding memcpy calls and reducing memory traffic.

Measuring Type Sizes

std::mem::size_of gives the size of a type, in bytes, but often you want to know the exact layout as well. For example, an enum might be surprisingly large due to a single outsized variant.

The -Zprint-type-sizes option does exactly this. It isn’t enabled on release versions of rustc, so you’ll need to use a nightly version of rustc. Here is one possible invocation via Cargo:

RUSTFLAGS=-Zprint-type-sizes cargo +nightly build --release

And here is a possible invocation of rustc:

rustc +nightly -Zprint-type-sizes input.rs

It will print out details of the size, layout, and alignment of all types in use. For example, for this type:

#![allow(unused)]
fn main() {
enum E {
    A,
    B(i32),
    C(u64, u8, u64, u8),
    D(Vec<u32>),
}
}

it prints the following, plus information about a few built-in types.

print-type-size type: `E`: 32 bytes, alignment: 8 bytes
print-type-size     discriminant: 1 bytes
print-type-size     variant `D`: 31 bytes
print-type-size         padding: 7 bytes
print-type-size         field `.0`: 24 bytes, alignment: 8 bytes
print-type-size     variant `C`: 23 bytes
print-type-size         field `.1`: 1 bytes
print-type-size         field `.3`: 1 bytes
print-type-size         padding: 5 bytes
print-type-size         field `.0`: 8 bytes, alignment: 8 bytes
print-type-size         field `.2`: 8 bytes
print-type-size     variant `B`: 7 bytes
print-type-size         padding: 3 bytes
print-type-size         field `.0`: 4 bytes, alignment: 4 bytes
print-type-size     variant `A`: 0 bytes

The output shows the following.

• The size and alignment of the type.
• For enums, the size of the discriminant.
• For enums, the size of each variant (sorted from largest to smallest).
• The size, alignment, and ordering of all fields. (Note that the compiler has reordered variant C’s fields to minimize the size of E.)
• The size and location of all padding.

Once you know the layout of a hot type, there are multiple ways to shrink it.

Field Ordering

The Rust compiler automatically sorts the fields in struct and enums to minimize their sizes (unless the #[repr(C)] attribute is specified), so you do not have to worry about field ordering. But there are other ways to minimize the size of hot types.

Smaller Enums

If an enum has an outsized variant, consider boxing one or more fields. For example, you could change this type:

#![allow(unused)]
fn main() {
type LargeType = [u8; 100];
enum A {
    X,
    Y(i32),
    Z(i32, LargeType),
}
}

to this:

#![allow(unused)]
fn main() {
type LargeType = [u8; 100];
enum A {
    X,
    Y(i32),
    Z(Box<(i32, LargeType)>),
}
}

This reduces the type size at the cost of requiring an extra heap allocation for the A::Z variant. This is more likely to be a net performance win if the A::Z variant is relatively rare. The Box will also make A::Z slightly less ergonomic to use, especially in match patterns. Example 1, Example 2, Example 3, Example 4, Example 5, Example 6.

Smaller Integers

It is often possible to shrink types by using smaller integer types. For example, while it is most natural to use usize for indices, it is often reasonable to stores indices as u32, u16, or even u8, and then coerce to usize at use points. Example 1, Example 2.

Boxed Slices

Rust vectors contain three words: a length, a capacity, and a pointer. If you have a vector that is unlikely to be changed in the future, you can convert it to a boxed slice with Vec::into_boxed_slice. A boxed slice contains only two words, a length and a pointer. Any excess element capacity is dropped, which may cause a reallocation.

#![allow(unused)]
fn main() {
use std::mem::{size_of, size_of_val};
let v: Vec<u32> = vec![1, 2, 3];
assert_eq!(size_of_val(&v), 3 * size_of::<usize>());

let bs: Box<[u32]> = v.into_boxed_slice();
assert_eq!(size_of_val(&bs), 2 * size_of::<usize>());
}

The boxed slice can be converted back to a vector with slice::into_vec without any cloning or a reallocation.

ThinVec

An alternative to boxed slices is ThinVec, from the thin_vec crate. It is functionally equivalent to Vec, but stores the length and capacity in the same allocation as the elements (if there are any). This means that size_of::<ThinVec<T>> is only one word.

ThinVec is a good choice within oft-instantiated types for vectors that are often empty. It can also be used to shrink the largest variant of an enum, if that variant contains a Vec.

Avoiding Regressions

If a type is hot enough that its size can affect performance, it is a good idea to use a static assertion to ensure that it does not accidentally regress. The following example uses a macro from the static_assertions crate.

  // This type is used a lot. Make sure it doesn't unintentionally get bigger.
  #[cfg(target_arch = "x86_64")]
  static_assertions::assert_eq_size!(HotType, [u8; 64]);

The cfg attribute is important, because type sizes can vary on different platforms. Restricting the assertion to x86_64 (which is typically the most widely-used platform) is likely to be good enough to prevent regressions in practice.

Standard Library Types

It is worth reading through the documentation for common standard library types—such as Box, Vec, Option, Result, and Rc/Arc—to find interesting functions that can sometimes be used to improve performance.

It is also worth knowing about high-performance alternatives to standard library types, such as Mutex, RwLock, Condvar, and Once.

Box

The expression Box::default() has the same effect as Box::new(T::default()) but can be faster because the compiler can create the value directly on the heap, rather than constructing it on the stack and then copying it over. Example.

Vec

The best way to create a zero-filled Vec of length n is with vec![0; n]. This is simple and probably as fast or faster than alternatives, such as using resize, extend, or anything involving unsafe, because it can use OS assistance.

Vec::remove removes an element at a particular index and shifts all subsequent elements one to the left, which makes it O(n). Vec::swap_remove replaces an element at a particular index with the final element, which does not preserve ordering, but is O(1).

Vec::retain efficiently removes multiple items from a Vec. There is an equivalent method for other collection types such as String, HashSet, and HashMap.

Option and Result

Option::ok_or converts an Option into a Result, and is passed an err parameter that is used if the Option value is None. err is computed eagerly. If its computation is expensive, you should instead use Option::ok_or_else, which computes the error value lazily via a closure. For example, this:

#![allow(unused)]
fn main() {
fn expensive() {}
let o: Option<u32> = None;
let r = o.ok_or(expensive()); // always evaluates `expensive()`
}

should be changed to this:

#![allow(unused)]
fn main() {
fn expensive() {}
let o: Option<u32> = None;
let r = o.ok_or_else(|| expensive()); // evaluates `expensive()` only when needed
}

Example.

There are similar alternatives for Option::map_or, Option::unwrap_or, Result::or, Result::map_or, and Result::unwrap_or.

Rc/Arc

Rc::make_mut/Arc::make_mut provide clone-on-write semantics. They make a mutable reference to an Rc/Arc. If the refcount is greater than one, they will clone the inner value to ensure unique ownership; otherwise, they will modify the original value. They are not needed often, but they can be extremely useful on occasion. Example 1, Example 2.

Mutex, RwLock, Condvar, and Once

The parking_lot crate provides alternative implementations of these synchronization types. The APIs and semantics of the parking_lot types are similar but not identical to those of the equivalent types in the standard library.

The parking_lot versions used to be reliably smaller, faster, and more flexible than those in the standard library, but the standard library versions have greatly improved on some platforms. So you should measure before switching to parking_lot.

If you decide to universally use the parking_lot types it is easy to accidentally use the standard library equivalents in some places. You can use Clippy to avoid this problem.

Iterators

collect and extend

Iterator::collect converts an iterator into a collection such as Vec, which typically requires an allocation. You should avoid calling collect if the collection is then only iterated over again.

For this reason, it is often better to return an iterator type like impl Iterator<Item=T> from a function than a Vec<T>. Note that sometimes additional lifetimes are required on these return types, as this post explains. Example.

Similarly, you can use extend to extend an existing collection (such as a Vec) with an iterator, rather than collecting the iterator into a Vec and then using append.

Finally, when you write an iterator it is often worth implementing the Iterator::size_hint or ExactSizeIterator::len method, if possible. collect and extend calls that use the iterator may then do fewer allocations, because they have advance information about the number of elements yielded by the iterator.

Chaining

chain can be very convenient, but it can also be slower than a single iterator. It may be worth avoiding for hot iterators, if possible. Example.

Similarly, filter_map may be faster than using filter followed by map.

Chunks

When a chunking iterator is required, use slice::chunks_exact when the chunk size is known to exactly divide the slice length. It is equivalent to but faster than slice::chunks in this case.

Bounds Checks

By default, accesses to container types such as slices and vectors involve bounds checks in Rust. These can affect performance, e.g. within hot loops, though less often than you might expect.

There are several safe ways to change code so that the compiler knows about container lengths and can optimize away bounds checks.

• Replace direct element accesses in a loop by using iteration.
• Instead of indexing into a Vec within a loop, make a slice of the Vec before the loop and then index into the slice within the loop.
• Add assertions on the ranges of index variables. Example 1, Example 2.

Getting these to work can be tricky. The Bounds Check Cookbook goes into more detail on this topic.

As a last resort, there are the unsafe methods get_unchecked and get_unchecked_mut.

I/O

Locking

Rust’s print! and println! macros lock stdout on every call. If you have repeated calls to these macros it may be better to lock stdout manually.

For example, change this code:

#![allow(unused)]
fn main() {
let lines = vec!["one", "two", "three"];
for line in lines {
    println!("{}", line);
}
}

to this:

#![allow(unused)]
fn main() {
fn blah() -> Result<(), std::io::Error> {
let lines = vec!["one", "two", "three"];
use std::io::Write;
let mut stdout = std::io::stdout();
let mut lock = stdout.lock();
for line in lines {
    writeln!(lock, "{}", line)?;
}
// stdout is unlocked when `lock` is dropped
Ok(())
}
}

stdin and stderr can likewise be locked when doing repeated operations on them.

Buffering

Rust file I/O is unbuffered by default. If you have many small and repeated read or write calls to a file or network socket, use BufReader or BufWriter. They maintain an in-memory buffer for input and output, minimizing the number of system calls required.

For example, change this unbuffered output code:

#![allow(unused)]
fn main() {
fn blah() -> Result<(), std::io::Error> {
let lines = vec!["one", "two", "three"];
use std::io::Write;
let mut out = std::fs::File::create("test.txt").unwrap();
for line in lines {
    writeln!(out, "{}", line)?;
}
Ok(())
}
}

to this:

#![allow(unused)]
fn main() {
fn blah() -> Result<(), std::io::Error> {
let lines = vec!["one", "two", "three"];
use std::io::{BufWriter, Write};
let mut out = std::fs::File::create("test.txt")?;
let mut buf = BufWriter::new(out);
for line in lines {
    writeln!(buf, "{}", line)?;
}
buf.flush()?;
Ok(())
}
}

Example.

The explicit call to flush is not strictly necessary, as flushing will happen automatically when buf is dropped. However, in that case any error that occurs on flushing will be ignored, whereas an explicit flush will make that error explicit.

Note that buffering also works with stdout, so you might want to combine manual locking and buffering when making many writes to stdout.

Reading Input as Raw Bytes

The built-in String type uses UTF-8 internally, which adds a small, but nonzero overhead caused by UTF-8 validation when you read input into it. If you just want to process input bytes without worrying about UTF-8 (for example if you handle ASCII text), you can use BufRead::read_until.

There are also dedicated crates for reading byte-oriented lines of data and working with byte strings.

Logging and Debugging

Sometimes logging code or debugging code can slow down a program significantly. Either the logging/debugging code itself is slow, or data collection code that feeds into logging/debugging code is slow. Make sure that no unnecessary work is done for logging/debugging purposes when logging/debugging is not enabled. Example 1, Example 2.

Note that assert! calls always run, but debug_assert! calls only run in debug builds. If you have an assertion that is hot but is not necessary for safety, consider making it a debug_assert!. Example 1, Example 2.

Wrapper Types

Rust has a variety of “wrapper” types, such as RefCell and Mutex, that provide special behavior for values. Accessing these values can take a non-trivial amount of time. If multiple such values are typically accessed together, it may be better to put them within a single wrapper.

For example, a struct like this:

#![allow(unused)]
fn main() {
use std::sync::{Arc, Mutex};
struct S {
    x: Arc<Mutex<u32>>,
    y: Arc<Mutex<u32>>,
}
}

may be better represented like this:

#![allow(unused)]
fn main() {
use std::sync::{Arc, Mutex};
struct S {
    xy: Arc<Mutex<(u32, u32)>>,
}
}

Whether or not this helps performance will depend on the exact access patterns of the values. Example.

Machine Code

When you have a small piece of very hot code, it may be worth inspecting the generated machine code to see if it has any inefficiencies, such as removable bounds checks. The Compiler Explorer website is an excellent resource when doing this.

Relatedly, the core::arch module provides access to architecture-specific intrinsics, many of which relate to SIMD instructions.

Parallelism

Rust provides excellent support for safe parallel programming, which can lead to large performance improvements. There are a variety of ways to introduce parallelism into a program and the best way for any program will depend greatly on its design.

An in-depth treatment of parallelism is beyond the scope of this book. If you are interested in this topic, the documentation for the rayon and crossbeam crates is a good place to start.

Binary Size

Sometimes you might need to minimize the size of a compiled Rust binary. In that case, you should consult the comprehensive documentation in the excellent min-sized-rust repository.

General Tips

The previous sections of this book have discussed Rust-specific techniques. This section gives a brief overview of some general performance principles.

As long as the obvious pitfalls are avoided (e.g. using non-release builds), Rust generally has good performance. Especially if you are used to dynamically-typed languages such as Python and Ruby.

Optimized code is often more complex and takes more effort to write than unoptimized code. For this reason, it is only worth optimizing hot code.

The biggest performance improvements often come from changes to algorithms or data structures, rather than low-level optimizations. Example 1, Example 2.

Writing code that works well with modern hardware is not always easy, but worth striving for. For example, try to minimize cache misses and branch mispredictions, where possible.

Most optimizations result in small speedups. Although no single small speedup is noticeable, they really add up if you can do enough of them.

Different profilers have different strengths. It is good to use more than one.

When profiling indicates that a function is hot, there are two common ways to speed things up: (a) make the function faster, and/or (b) avoid calling it as much.

It is often easier to eliminate silly slowdowns than it is to introduce clever speedups.

Avoid computing things unless necessary. Lazy/on-demand computations are often a win. Example 1, Example 2.

Complex general cases can often be avoided by optimistically checking for common special cases that are simpler. Example 1, Example 2, Example 3. In particular, specially handling collections with 0, 1, or 2 elements is often a win when small sizes dominate. Example 1, Example 2, Example 3, Example 4.

Similarly, when dealing with repetitive data, it is often possible to use a simple form of data compression, by using a compact representation for common values and then having a fallback to a secondary table for unusual values. Example 1, Example 2, Example 3.

When code deals with multiple cases, measure case frequencies and handle the most common ones first.

When dealing with lookups that involve high locality, it can be a win to put a small cache in front of a data structure.

Optimized code often has a non-obvious structure, which means that explanatory comments are valuable, particularly those that reference profiling measurements. A comment like “99% of the time this vector has 0 or 1 elements, so handle those cases first” can be illuminating.

Compile Times

Although this book is primarily about improving the performance of Rust programs, this section is about reducing the compile times of Rust programs, because that is a related topic of interest to many people.

Linking

A big part of compile time is actually linking time, particularly when rebuilding a program after a small change. It is possible to select a faster linker than the default one.

One option is lld, which is available on Linux and Windows.

To specify lld from the command line, precede your build command with RUSTFLAGS="-C link-arg=-fuse-ld=lld".

To specify lld from a config.toml file (for one or more projects), add these lines:

[build]
rustflags = ["-C", "link-arg=-fuse-ld=lld"]

lld is not fully supported for use with Rust, but it should work for most use cases on Linux and Windows. There is a GitHub Issue tracking full support for lld.

Another option is mold, which is currently available on Linux and macOS. It is specified in much the same way as lld. Simply substitute mold for lld in the instructions above.

mold is often faster than lld. It is also much newer and may not work in all cases.

Incremental Compilation

The Rust compiler supports incremental compilation, which avoids redoing work when you recompile a crate. It can greatly speed up compilation, at the cost of sometimes making the produced executable run a little more slowly. For this reason, it is only enabled by default for debug builds. If you want to enable it for release builds as well, add the following lines to the Cargo.toml file.

[profile.release]
incremental = true

See the Cargo documentation for more details about the incremental setting, and about enabling specific settings for different profiles.

Visualization

Cargo has a feature that lets you visualize compilation of your program. Build with this command (1.60 or later):

cargo build --timings

or this (1.59 or earlier):

cargo +nightly build -Ztimings

On completion it will print the name of an HTML file. Open that file in a web browser. It contains a Gantt chart that shows the dependencies between the various crates in your program. This shows how much parallelism there is in your crate graph, which can indicate if any large crates that serialize compilation should be broken up. See the documentation for more details on how to read the graphs.

LLVM IR

The Rust compiler uses LLVM for its back-end. LLVM’s execution can be a large part of compile times, especially when the Rust compiler’s front end generates a lot of IR which takes LLVM a long time to optimize.

These problems can be diagnosed with cargo llvm-lines, which shows which Rust functions cause the most LLVM IR to be generated. Generic functions are often the most important ones, because they can be instantiated dozens or even hundreds of times in large programs.

If a generic function causes IR bloat, there are several ways to fix it. The simplest is to just make the function smaller. Example 1, Example 2.

Another way is to move the non-generic parts of the function into a separate, non-generic function, which will only be instantiated once. Whether or not this is possible will depend on the details of the generic function. The non-generic function can often be written as an inner function within the generic function, to minimize its exposure to the rest of the code. Example.

Sometimes common utility functions like Option::map and Result::map_err are instantiated many times. Replacing them with equivalent match expressions can help compile times.

The effects of these sorts of changes on compile times will usually be small, though occasionally they can be large. Example.