This chapter requires a working Rust installation. The details of verifying your installation are covered in Chapter 1, Preliminaries – Machine Architecture and Getting Started with Rust. The Valgrind suite of tools will be used here. Many operating systems bundle valgrind packages but you can find further installation instructions for your system at valgrind.org. Linux Perf is used and is bundled by many Linux distributions. Any other software required for this chapter is installed as a part of the text.

You can find the source code for this book's projects on GitHub: https://github.com/PacktPublishing/Hands-On-Concurrency-with-Rust. The source code for this chapter is under Chapter02.

The hard truth is that there's a diminishing return when applying more and more concurrent computational resources to a problem. Performing parallel computations implies some coordination overhead—spawning new threads, chunking data, and memory bus issues in the presence of barriers or fences, depending on your CPU. Parallel computing is not free. Consider this Hello, world! program:

fn main() {
    println!("GREETINGS, HUMANS");
}

Straightforward enough, yeah? Compile and run it 100 times:

hello_worlds > rustc -C opt-level=3 sequential_hello_world.rs
hello_worlds > time for i in {1..100}; do ./sequential_hello_world > /dev/null; done

real    0m0.091s
user    0m0.004s
sys     0m0.012s

Now, consider basically the same program but involving the overhead of spawning a thread:

use std::thread;

fn main() {
  ...

In this section, we'll focus on the serial performance of a common data structure—associative arrays. We'll apply the tools we learned about in the previous chapter to probe different implementations. We'll focus on the associative array because it is fairly well-trod territory, studied in introductory computer science courses, and is available in most higher-level languages by default, Rust being no exception save the higher-level bit. We'll look at Rust's associative array first, which is called std::collections::HashMap.

Let's poke around in HashMap's internals. A good starting place, I find, for inspecting unfamiliar Rust data structures is...

What should we understand from all of this? To produce software that operates at the edge of the machine's ability, you must understand some important things. Firstly, if you aren't measuring your program, you're only guessing. Measuring runtime, as criterion does, is important but a coarse insight. Where is my program spending its time? is a question the Valgrind suite and perf can answer, but you've got to have benchmarks in place to contextualize your questions. Measuring and then validating behavior is also an important chunk of this work, which is why we spent so much time on QuickCheck and AFL. Secondly, have a goal in mind. In this chapter, we've made the speed of standard library HashMap our goal but, in an actual code base, there's always going to be places to polish and improve. What matters is knowing what needs to happen to...

In this chapter, we covered measuring and improving the performance of a serial Rust program while demonstrating the program's fitness for purpose. This is a huge area of work and there's a deep well of literature to pull from.

• Rust's std::collections is absolutely horrible, available at https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcollections_is_absolutely_horrible/. The original poster admitted the title is a bit on the click-baity side but the discussion on Reddit is well worth reading. The original author of standard library's HashMap weighs in on the design decisions in the implementation.

• Robin Hood Hashing, 1985, Pedro Celis. This thesis introduced the Robin Hood hashing strategy for constructing associative arrays and is the foundation for the implementation you'll find in Rust. The paper also goes into further...