Posted in Coding

At work I’m seeing more and more embedded software; over the past few years in, among others, coffee machines, forklifts, and cars. Embedded software needs to be fast and extremely efficient with hardware resources. In some cases it not even acceptable to have a tiny break for some garbage collection. So, typical tech stacks for backend development can’t be used, never mind anything that uses browser technologies. Unsurprisingly, almost all embedded software is written in C++, and, in fact, that is also what I used recently for a personal project with a micro-controller.

Now, if you’ve programmed in C++ you probably didn’t find the experience all too pleasant or productive compared to the developer experience we have in modern web development (server as well as browser). I certainly feel that way, and it seems like I’m not alone. Three hugely influential IT organisations, who had to deal with writing code in C or a C-based language, each decided to invent an entirely new programming language just so that they had a an alternative. The organisations are Apple (Swift), Google (Golang), and Mozilla (Rust).

My personal experience with Swift, when I wrote the Dancing Glyphs screensaver a couple of years ago, was mixed at best. I understand that a number of design decisions in the language that annoyed me as a programmer were made to help the compiler/optimiser generate more resource efficient code, ultimately giving the users longer battery life. Looking through the remaining choices, I went past Golang, which uses garbage collection, and set my eyes on Rust.

In this post I’ll describe my first impressions, some of the frustrating moments, but also the extremely impressive performance on a larger piece of code.

Getting started

To be honest, following long tutorials isn’t for me. I prefer to learn a new programming language by writing something in it. In this case I decided to revisit a Genetic Programming (GP) simulation I had written in Clojure last year, which, by the way, had been a very pleasant experience. The simulation is a tricky problem in so far as it has lots of state, but at the same time it allows to focus on actual programming; the only APIs needed are for serialising JSON to files.

These days, my default choice for writing code (and text like this post) is Visual Studio Code, which does have Rust support. However, after some back and forth I found the Rust support in IntelliJ superior. It’s not perfect either, though. For example, extracting variables works, but inlining doesn’t. Extracting methods works, sometimes. Most type checking works, but sometimes the compiler will still surprise you.

Installing the Rust tool chain was straight forward, and the default package manager, Cargo, is quite similar to what I am used to from languages like Ruby and JavaScript. The project structure is a bit unusual, though. Almost all code is in a library, with a small, separate, main wrapper to make it a program. Like with Go, the tools produce an executable file that contains all dependencies and can be run directly from the command line.

Unit testing is a first-class citizen; so much so that the unit tests go into the same file as the code they are testing. This felt decidedly odd at first. The default project structure also has support for integration tests in a separate directory, which I used for my acceptance tests.

Finding answers

One area that I struggled with was finding answers to my problems on the web. Firstly, the terms rust and cargo are just not very distinctive and, secondly, Rust was released early in its own development cycle, long before the 1.0 version, so lots of answers found on, say, StackOverflow are not applicable to today’s Rust. To be fair, there is an effort underway by the Rust community to flag outdated discussions.

The issue with finding good answers quickly became more relevant because I had to look up a lot of problems. Often, even seemingly simple tasks didn’t have an obvious implementation. I’m not saying I disagree with the design choices, I’m illustrating why I spent a fair amount of time on StackOverflow and Reddit.

Take this code, which is the simplest solution I could find to get some timing in milliseconds:

let start = SystemTime::now();
/* do stuff */
let end = SystemTime::now();
let duration = end.duration_since(start).expect("can't get duration");
let millis = duration.as_secs() * 1000 + duration.subsec_millis() as u64;

Note the insistence of the duration_since() method to be allowed to return an error (because sometimes two times cannot be compared) and the use of expect() to ignore any potential error nonetheless. Also note how the duration can’t return milliseconds and how it uses different types for seconds and subsecond millis, which makes that cast to u64 necessary.

Staying with time, another problem I had was to generate a timestamp in a human-readable format. As it turns out, Rust is, by design, kept small. Even handling of dates is left to a third party library; the big question being “which one”? That said, once I had the right library, creating the timestamp was easy. In general, the libaries I encountered felt polished and well thought-through.

By the way, you probably noticed that there were no types given in any of the let declarations even though Rust is a statically typed language. Type inference works really well.

Managing memory

Rust doesn’t use a garbage collector but, of course, the designers didn’t want to burden developers with manual memory management, not only because it is painful, but also because it is a huge source for hard-to-trace bugs. So, they came up with the concept of ownership and combined it with scope to manage memory automatically.

The ownership concept is quite noticeable in code, mainly because Rust tackles another problem at the same time; the problem of data races. Rust has references to data owned by someone else, but you can either have multiple read-only references or you can have one (and only one) reference that can be used to change (mutate) the data. In theory, ownership and mutability are two separate concepts. In practice, though, they tend to get mixed up.

One of the reasons is that calling a method uses the same syntax, no matter whether it’s on an owned structure or on a reference. (In C-based languages . and -> are used respectively. Java and other languages only have references.) There are further subtleties when primitive types like numbers are involved, because these may have to be dereferenced. Another reason why the concepts mix is that the compiler often can’t tell how long a reference will be valid, because the underlying structure may lose ownership and be deallocated. In such situations explicit lifetime specifiers are required.

Even the authors of the (well-written) Rust Book warn that this all takes time to get used to and concede that the compiler’s error messages can be frustrating. I have certainly seen a fair share of error messages like the following:

 error[E0502]: cannot borrow `self` as immutable because `self.terrain` is also borrowed as mutable
   --> src/world.rs:130:39
    |
129 |         let terrain = &mut self.terrain;
    |                            ------------ mutable borrow occurs here
130 |         terrain.do_with_creatures_mut(|terrain, creature, pos|
    |                                       ^^^^^^^^^^^^^^^^^^^^^^^^ immutable borrow occurs here
...
137 |                 return Some(creature.do_cycle(pos, terrain, self));
    |                                                             ---- borrow occurs due to use of `self` in closure
138 |             });
139 |     }
    |     - mutable borrow ends here

I also found myself pondering whether I needed a mutable reference to an option or an owned option on a mutable reference. (Rust doesn’t have null pointers and uses an Option type.) In combination with the matching syntax, I will admit that sometimes I just tried adding an ampersand here and there or putting a tentative ref mut into the match until the compiler accepted it and my tests passed. I guess, my confidence in the compiler and my tests is still greater than that in my understanding of the intricacies of mutability and ownership.

Object-oriented programming

Rust allows for object-oriented programming by attaching methods to structures. There isn’t a specific class keyword and methods are simply functions where the first argument is self, a reference to the structure. Unlike in Objective-C but like in Python that self reference is explicit, visible, and must be written by the developer. True to Rust’s rules around mutability the methods must declare whether they require a mutable reference or whether read-only access is sufficient.

The following is a simple method attached to the World structure in my GP simulation. The reference to self needs to be mutable, not because this method changes anything on it, but because the method it calls in the loop needs a mutable reference. Like in C, the ampersand denotes references.

pub fn do_cycles(&mut self, num: u64) {
    for _ in 0..num {
        self.do_one_cycle();
    }
}

Inheritance does not exist at this level. To make up for it Rust offers Traits which are collections of methods that can be attached to structures. Personally, I think this is a good choice because inheritance is actually quite difficult to use correctly and for that reason I’ve long favoured composition over inheritance.

In combination with the ownership concept, this can lead to some interesting consequences. More on that later.

A puzzle remaining

The consequences of Rust’s seemingly simple ownership rules have some surprising consequences, some of which I still don’t understand. One has to do with the impact of evaluating function arguments. This is best explained with an example.

In my acceptance tests I often have to run a number of cycles of the simulation to make sure a section of a creature’s programs is run. For that I created a helper function num_cycles(), which, given the simulation parameters and a program in the form of a list (vector) of instructions, returns the number of simulation cycles needed to run all the instructions. The return value is a 64-bit unsigned integer.

pub fn cycle_count(params: &Params, program: &Vec<Instr>) -> u64 {
    program.iter().fold(0, |acc, instr| acc + params.instr_cycles(&instr))
}

The implementation is of no interest here, but it shows a more functional side of Rust with the use of a closure. What still puzzles me is what happens when I try to use this function.

let mut world = World::for_testing();
/* ... */
world.do_cycles(cycle_count(&world.params, &vec![EAT]));

In my mind, cycle_count() is run first, returning the number of cycles for the EAT instruction. Then, the do_cycles() method is called with the return value. The two functions are run sequentially and a plain integer is passed between them. Somehow the compiler disagrees:

error[E0502]: cannot borrow `world.params` as immutable because `world` is also borrowed as mutable
   --> tests/integration_tests.rs:268:34
    |
268 |     world.do_cycles(cycle_count(&world.params, &vec![EAT]));
    |     -----                        ^^^^^^^^^^^^             - mutable borrow ends here
    |     |                            |
    |     |                            immutable borrow occurs here
    |     mutable borrow occurs here

Basically, it detects a conflict of the reference rules. It says it needs a mutable reference to world to call the do_cycles() method on it. This is expected given the code shown earlier. The compiler also says that it needs an immutable reference to world, which seems plausible because params is a property of World and a reference to it is used as an argument to num_cycles(). However, my understanding of the rules is that these references cannot be held simultaneously while, again in my mind, the references here are needed sequentially.

Making the sequential nature of access implicit, with an intermediate variable, solves the problem that I thought I didn’t have. The following code compiles and works as expected.

let n = cycle_count(&world.params, &vec![EAT]);
world.do_cycles(n);

Can anyone explain this? At least this case illustrates why the extract variable refactoring is important, and why I didn’t miss the inline variable refactoring too much.

Another puzzle

This puzzle revolves around traits and ownership. It was pretty clear that I needed my own wrapper around random number generation. Mostly because I want to stub the values in tests. So, I created a trait called RNG with methods to return random numbers, and had two structures implement the trait. SystemRandom implements the methods using a system provided random number generator while StubbedRandom returns values that can be set. So far so good.

Now, the World structure has two “constructors”, one for the actual simulation and another for testing purposes. The following code omits a lot of code irrelevant for this discussion.

pub struct World {
    random: RNG,
}

impl World {
    pub fn new(params: Params) -> World {
        World {
            params, // short for params: params
            random: SystemRandom::new(),
        }
    }

    pub fn for_testing() -> World {
        World {
            params: Params::default_params(),
            random: StubbedRandom::new(),
        }
    }

This doesn’t work. The size of the World structure can’t be known at compile time because the compiler doesn’t know which kind of RNG implementation will be used. In fact, both may be used. An obvious solution is for the world to only hold references to the RNG implementation, because references are of the same size. The ampersand denotes references.

pub struct World {
    random: &mut RNG,
}

impl World {
    pub fn new(params: Params) -> World {
        let mut system_random = SystemRandom::new();
        World {
            params, // short for params: params
            random: &mut system_random,
        }
    }

    pub fn for_testing() -> World {
        let mut stubbed_random = StubbedRandom::new();
        World {
            params: Params::default_params(),
            random: &mut stubbed_random,
        }
    }

Now the compiler is happy because it knows the size of the World structure. It is still unhappy, though, because it doesn’t fail to notice that a reference to the random number generators would be held in the World struct, which is returned to the outside from new() and for_testing(), while the owner, the local variables inside these functions, will go out of scope and will therefore result in the deallocation of the random number generator, which would leave the references dangling.

Rust does offer Smart Pointers, which I expect to be a reference counting scheme that might help in this situation, but, to be honest, I didn’t get that far in the Rust book yet. The last two examples were simply meant to illustrate the profound impact that Rust’s concepts of ownership, references, and mutability have on programming.

The reward: performance

The experience of rewriting the GP simulator in Rust wasn’t nearly as bad as the discussion above might suggest, but it wasn’t as pleasant as writing the original simulator in Clojure either. Something that the Rust version should have going for it, though, is performance.

On my computer the Clojure implementation can simulate about 110 processing cycles of a creature per millisecond. The Clojure code doesn’t have any obvious bottlenecks and the data structures are chosen to allow for efficient access, e.g. I’m not not using a data structure that requires O(n) when another structure works in O(log n).

Of course, I expected a performance increase and the very first run of the Rust simulator didn’t disappoint. It ran at about 1800 cycles/ms; more than 16 times faster than the Clojure version. Even though I was reasonably confident that the two simulators were doing the same thing, because I had translated the acceptance tests one by one, I still ran a number of simulations to confirm that the behaviour of the two simulators was the same.

A bit later, while looking at a change in the Rust code that (negatively) affected performance, it hit me like a ton of bricks: I was using a debug build of the Rust code, which has lots of safety checks built in. From working in C and Swift I knew that optimised release builds could be a lot faster. So, I ran the Rust simulator as a release build. On average it did 25,000 cycles/ms, sometimes even over 30k cycles/ms.

Or, in real world terms, running 10,000 simulations to explore the impact of some parameters Monte-Carlo style:

• Rust: a couple of hours
• Clojure: about three weeks

That certainly made using the simulator a completely different experience!

Footnote

I should mention that I never ran the Clojure version for three weeks on end, and in its current form it would need an external script to launch multiple simulations in parallel. Unlike the Rust code, which was inherently thread-safe, making it trivial to build a simulation launcher into the program, the Clojure code still uses some global state. Running a single simulation in multiple threads doesn’t make sense, by the way, the coordination overhead is just too high.