Advent of Code in Rust: lessons learned
Last December, I decided to solve the Advent of Code (AoC) programming puzzles in Rust. This website is an advent calendar proposing a new algorithmic problem of varying difficulty every day throughout December, so it’s a great way to learn and practice a programming language. There is also a leaderboard for the fastest people to solve them, but the past problems remain available forever, so don’t worry if you’re too slow or busy in December, you can try them any time of the year - as this overdue blog post shows!
I already have some experience in Rust programming, but I felt that I could learn more about idiomatic Rust. Given the short time to solve each problem, it was a perfect opportunity to avoid reinventing the wheel but use the standard library as much as possible.
Here are the most useful Rust features that I learned and used during this challenge.
Language features
Rust is already a rich programming language, so I had the opportunity to use some of its many features.
Iterators
After a few days, it became clear to me that iterators are one of the big advantages of Rust to write complex algorithms.
To give a simple example (yet quite artificial), let’s write an algorithm to compute the sum of the first even numbers in a file, where each line of the text file contains a number in decimal format. Don’t worry, the real AoC problems are less artificial than that!
Here is a Rust function that implements this algorithm, with a functional style.
// Rust
fn foo(path: &Path) -> i32 {
let input = File::open(path).unwrap();
BufReader::new(input)
.lines()
.map(|line| line.unwrap().parse::<i32>().unwrap())
.filter(|x| x % 2 == 0)
.take(5)
.sum()
}
In C++, the same algorithm could be written as follows, with an imperative style.
// C++
int foo(const std::string& path) {
std::ifstream input(path);
int sum = 0, count = 0;
for (std::string line; std::getline(input, line); ) {
int x = std::stoi(line);
if (x % 2 == 0) {
sum += x;
if (++count == 5) {
break;
}
}
}
return sum;
}
The C++ version a bit longer than the Rust version, but the difference is not so big ; it’s mostly a matter a style.
Still, I find the C++ version less easy to follow, due to the interleaving of several operations: iterating, parsing, filtering, computing the sum.
On the contrary, the Rust version translates each constraint of the problem into one function (.lines() to split the input into lines, .take(5) to take the first 5 numbers, etc.).
Granted, you need to know the available iterator functions, but the documentation about them is pretty good.
A similar example would be to compute the sum directly from a vector of strings. As you can see below, the Rust version is very similar to the one taking lines in a file, because iterators are generic over the data type.
// Rust
fn bar(values: &Vec<String>) -> i32 {
values
.iter()
.map(|value| value.parse::<i32>().unwrap())
.filter(|x| x % 2 == 0)
.take(5)
.sum()
}
As an exercise, here is a C++ version with an equivalent functional style, using the algorithms from the standard library.
// C++
#include <algorithm>
int bar(const std::vector<std::string>& values) {
std::vector<int> numbers;
std::transform(values.begin(), values.end(),
std::back_inserter(numbers),
[](std::string value) { return std::stoi(value); });
numbers.erase(std::remove_if(numbers.begin(), numbers.end(),
[](int x) { return x % 2 == 0; }),
numbers.end());
int sum = 0;
std::for_each_n(numbers.begin(), std::min(numbers.size(), 5),
[&sum](int x) { sum += x; });
return sum;
}
This is quite verbose!
You can also use std::accumulate from the numeric header to compute the sum, but I’m not sure it’s simpler in this case.
// C++
#include <numeric>
int sum = std::accumulate(numbers.begin(),
numbers.size() <= 5
? numbers.end()
: std::advance(numbers.begin(), 5));
These functional-style algorithms end up much more verbose in C++. For example, the filtering part requires:
- calls to both
eraseandremove_if, - 4 mentions of the
numberscontainer, std::qualifications everywhere (unless you preferusing namespace std;),- verbosity in the lambda syntax.
Besides, this is in principle less efficient than the imperative style, because:
- the numbers need to be stored in an intermediate container, which requires allocation,
- even though only the first 5 terms are used, all of the values are parsed.
On the contrary, Rust’s iterators really provide a zero-cost abstraction, with the same performance as the imperative style, but more conciseness and a greater separation of the various parts of the logic.
Traits
All these easy-to-use algorithms on iterators are enabled by Rust traits. Traits are a bit like Java interfaces or C++ abstract classes, but applied to C++ templates.
Contrary to object-oriented interfaces, traits are static instead of dynamic, i.e. they are resolved at compile time.
This means that if a function takes a trait as argument (such as fn<I: Iterator> foo(iter: I)), a new version of the function will be compiled for each concrete type that implements the trait.
This is different from inheritance in C++ or Java (think void foo(const Iterator& iter)), where only one version of the function is compiled, but the dispatch to the concrete type happens at runtime.
This static polymorphism can yield significant performance gains, because besides avoiding a runtime dispatch to the real type, the compiler can optimize the implementation for each concrete type. It can for example inline the polymorphic function calls and then do all sorts of simplifications. As such, Rust traits are zero-cost abstractions, and in practice the examples above yield similarly optimized code as writing a loop, even though the source code involves many function calls and lambdas1. A drawback of Rust’s approach is that the size of a full binary can be larger, especially if you compile the same generic code for many types.
A second advantage of Rust traits compared to inheritance is that a given type can implement many traits, whereas multiple inheritance can often end up tricky if at all allowed by the language. For example, in Java, a class can only inherit from up to one class, but can implement several interfaces. In this sense, Rust traits are closer to Java interfaces than to a base class.
Although C++ templates are also a form of static polymorphism, they currently lack the type-checking enforced by Rust traits.
Thanks to these advantages of strong typing and zero-cost abstractions, I think that Rust traits provide one of the most mature generics of production-level programming languages. The only lacking part is the so-called const generics, but these are coming.
To come back to the Advent of Code problems, even though I didn’t get to define my own traits, I extensively implemented common traits of the standard library.
For example, I used the Eq (equality) and Hash traits to use hash tables keyed by my own types.
It turns out that these common traits have default implementations that can be derived for new types in a single line.
All it takes is the following to define a position type that can be a hash table key.
#[derive(PartialEq, Eq, Hash)]
struct Position {
x: usize,
y: usize,
}
One good thing about derive is that these traits are not derived by default.
This is an opt-in, which helps ensure strong type semantics.
Another common trait is the Ord trait, that defines a comparison function to sort items.
This comparison function returns an Ordering, which is either less, equal or greater.
This can be more efficient than having separate operators for « less-than » and equality (as you would do in C++), because you can compute both in one pass.
Besides, computing lexicographical comparison is simple thanks to the .then() method, which uses a second comparison as a tie-breaker only if the first yields equality.
impl Ord for Position {
fn cmp(&self, other: &Position) -> Ordering {
self.x.cmp(&other.x).then(self.y.cmp(&other.y))
}
}
Type inference
One nice thing about Rust is that even though it has a strong type system (even conversions between numeric types, such as from a 16-bit to a 32-bit integer, must be explicit), the compiler implements type inference.
This means that you generally only need to specify the types for structure fields and function signatures.
Although this isn’t something uncommon anymore among major programming languages (since C++11 introduced auto for type inference of variables), this is quite ergonomic.
One feature of Rust’s type inference is that it isn’t restricted to the declaration of a variable. For example, it isn’t uncommon to create an empty container – at which point the type of the contained elements is unknown – and then fill it with elements – at which point the compiler infers the type.
// Creates a new vector, but the exact type is unknown at this point.
let mut v = Vec::new();
// Variable of type u8, an unsigned 8-bit number.
let x = 1u8;
// Now the compiler infers that v is of type Vec<u8>.
v.push(x);
A point where type inference can be somewhat confusing is when chaining many iterator adaptors together. Because iterators generally yield references to the iterated objects (to avoid copying), you can end up with multiple levels of indirection. For example, the following program (counting the number of true statements in a vector of booleans) doesn’t compile.
fn main() {
let x: Vec<bool> = vec![false, true, false, false, true];
let count_true = x.iter().filter(|b| b).count();
println!("There are {} true statements", count_true);
}
The error message is the following.
error[E0308]: mismatched types
--> src/main.rs:3:42
|
3 | let count_true = x.iter().filter(|b| b).count();
| ^ expected bool, found &&bool
|
= note: expected type `bool`
found type `&&bool`
This suggests that the booleans have been borrowed twice!
First, the iter() method yields reference to the elements, i.e. of type &bool.
Second, the filter() method passes references to its items as parameters to the lambda function, i.e. b is of type &&bool.
Turns out that this behavior of filter() is documented, and you can work around it by writing filter(|b| **b), filter(|&b| *b) or filter(|&&b| b).
No lifetimes!
Rust is well-known for its lifetime annotations on references. These allow safe and efficient memory management without garbage collection, thanks to compile-time checks. Although the concept of lifetime can be quite daunting, the compiler can often infer the lifetimes so that the annotations can be elided in many cases. This is especially the case for simple algorithms that don’t require complex data structures but only a few functions.
In practice, I didn’t have to write my own lifetimes for AoC problems, so I could use references seamlessly. However, as mentioned in the previous section, I had to fight against multiple levels of unexpected borrowing.
The rules for lifetime elision are explained in the book and also in the rustnomicon.
Crates
One of the advantages of the Rust ecosystem is its growing repository of packages, called crates. I ended up using two of them to avoid reinventing the wheel.
Regular expressions
Since the Advent of Code problems have inputs in a textual format, you need to do a bit of parsing to convert the inputs into useful data structures. In general, I wouldn’t recommend using regular expression directly to parse complex files (I’d recommend dedicated crates to handle common formats such as JSON, TOML or ZIP), but these were simple problems so a regex would do the job in a concise way.
Contrary to C++ (since C++11), the Rust standard library doesn’t have regular expressions.
However, there is a regex crate managed by the Rust Project Developers, and Rust’s package management is so smooth that it takes only two more lines to import it (add the dependency in Cargo.toml and an extern crate statement in the source code).
Under the hood, this crate implements regexes efficiently (linear time) thanks to finite automata, and proved very handy to parse the text-based inputs to the puzzles.
More iterators
Although I didn’t use it as much as regexes, I experimented a bit with the itertools crate, which provides even more iterator adaptors on top of the already extensive Iterator trait of the standard library.
Tools
While experimenting on the Advent of Code problems, I benefited from the amazing tools available in the Rust ecosystem. Here are some of my favorites.
Compiler explorers
The online compiler explorer at https://godbolt.org/ shows the assembly of programs as you edit them, and supports many compiled languages (Rust, C++, OCaml, etc.), as well as various compiler versions and compilation options.
I find it very useful to quickly see the difference between optimization levels (debug vs. release).
To see the optimized version of a Rust program, use the -O option.
More specifically with Advent of Code, it was helpful to see how optimizing the complexity of an algorithm translates at the assembly level. I’m far from an expert in assembly, but the interactive interface maps lines of source code to the corresponding assembly, which helps to follow the compiled program.
More specific to Rust, the playground at https://play.rust-lang.org/ additionally allows to run programs from the web interface, but the assembly explorer is less intuitive because it only shows the result without mapping it to the source code.
The caveat of these online tools is that you send the source code to their website, so you need to be careful not to submit private source code.
All in all, you might be surprised how many optimizations the compiler can do for you!
Can you guess how many lines of assembly are generated by the following code, for a
skylaketarget CPU?2pub fn foo(x: &[u8]) -> u32 { x.iter().map(|y| y.count_ones()).sum() }
- Hint 1: most moderns CPUs have a
popcntinstruction to count the bits set to one.- Hint 2: optimizers love to inline lambda functions.
- Hint 3: optimizers love to unroll loops these days.
Answer: https://godbolt.org/z/HXKibY.
Now, can you guess what is compiled for this slightly modified code?
pub fn bar(x: &[u8; 1024]) -> u32 { x.iter().map(|y| y.count_ones()).sum() }
Answer: https://godbolt.org/z/iTlWAN.
The usual Rust tools
This is not specific to the Advent of Code, but besides the Rust language itself, the Rust ecosystem has many useful tools that improve the programming experience.
Rustfmt
The first that I recommend is Rust format, that you can install with rustup.
rustup component add rustfmt
You can then run it on a full project to format your code.
cargo fmt
I also like to have it enabled in my Vim configuration, using rust.vim.
The following line in .vimrc enables automatic formatting every time you save a Rust file.
let g:rustfmt_autosave = 1
The nice thing about Rust format is that it removes the endless debates about whether to use N tabs or N spaces to indent the code.
You just get a nice formatting by default, and anyone using your code will get the same formatting rules, so code diffs don’t get scrambled by re-formatting.
And if you don’t like the defaults, you can customize formatting rules for your project with a rustfmt.toml file, so that anyone contributing to your project will also apply the same custom rules.
Clippy
The second tool that I recommend is Rust’s linter called Clippy.
You can also install it with rustup.
rustup component add clippy
It already has 300+ rules organized in various categories (so that you can selectively enable/disable some rules).
When I first enabled Clippy, it had a lot to say about my code, so it was definitely worth trying it. Here are some common mistakes that I was making.
- Using
&Vec<T>as a function parameter. Unless the function reads the vector’s capacity (which is quite rare), it’s more generic to use a slice (&[T]) instead. Note that this doesn’t necessarily applies to&mut Vec <T>, especially if you want to add elements to the vector. - Passing a trivially-copyable type by reference for a function parameter. It’s more efficient to directly pass the object. Clippy will warn for the obvious cases like
u32, but also for less obvious cases such as enums or small structs. - Checking emptyness of a container with
x.len() == 0. Usingx.is_empty()shows the intent more clearly. - Similarly, filtering
Nonevalues of an option withif let None = x { ... }. TheOptiontype has ais_none()method. - Using
iter.map(|&x| x)oriter.map(|x| *x)to copy elements out of an iterator of references. Theiter.copied()(oriter.cloned()) method is dedicated for this task. - Using
map.entry(key).or_insert(vec![0; 100])to insert a big object in a map if the entry for some key is empty. This always creates the big object (vec![0; 100]), even when the map already contains the key. Instead,.or_insert_with(|| vec![0; 100])only creates the big object when necessary. - Looping over an integer to only index in a sequence
for i in 0..n { let x = foo[n]; ... }. You can directly iterate over the container (for x in foo { ... }), which is simpler and may end up better optimized. - Using
iter.fold(0, |acc, x| acc + x)instead ofiter.sum()to sum all the elements of an iterator. Yes, Clippy can find optimizations in complex expressions too! - Writing
123456789without thousand separators. Clippy will suggest123_456_789instead, for better readability. - Using
return x;at the end of a function. You can directly put the expression to return at the end of the block, withoutreturnnor semi-colon.
These are just some examples, there are many more mistakes to make, and opportunities to simplify and optimize your code. Try Clippy on your own code!
Conclusion
Rust is a very versatile language: on the one hand you can write safe and performant complex programs confidently with the help of many useful abstractions; on the other hand you can prototype quickly and concisely with all the libraries available on crates.io.
All the constraints put on references and mutability may seem to slow down prototyping, but the compiler provides great error messages to help you overcome them, and with some practice you can learn what idioms are well-suited to Rust’s checks. The Advent of Code problems are a great way to get some of this practice!
Thanks to type and lifetime inference, my code wasn’t bloated with annotations, and I would probably not have written much less code in a scripting language like Python.
-
On the topic of compiler optimizations, I highly recommend watching the talk What Else Has My Compiler Done For Me Lately? by Matt Godbolt. ↩
-
Compiled with
-O -C target-cpu=skylake. ↩
Comments
To react to this blog post please check the Twitter thread.
You may also like