Summary

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 solve the problem at hand, which will tell you where your time needs to be spent. Thirdly, understand your machine. Modern superscalar, parallel machines are odd beasts to program and, without giving a thought to their behaviors, it's going to be tough understanding why your program behaves the way it does. Finally, algorithms matter above all else. Our naive HashMap failed to perform well because it was a screwy idea to perform an average O(n/2) operations for every insertion, which we proved out in practice. Standard library's HashMap is a good, general-purpose structure based on linear probing and clearly, a lot of thought went into making it function well for a variety of cases. When your program is too slow, rather than micro-optimizing, take a step back and consider the problem space. Are there better algorithms available, is there some insight into the data that can be exploited to shift the algorithm to some other direction entirely?

That's performance work in a nutshell. Pretty satisfying, in my opinion.