- 2.1 Ode to the Method
- 2.2 How Much + in C++?
- 2.3 Something Sleek and Modern
- 2.4 What's in a Cache Miss?
- 2.5 Code Spelunking
- 2.6 Input Validation
This chapter is from the book
This chapter is from the book
This chapter is from the book
2.4 What’s in a Cache Miss?
People who are really serious about software should make their own hardware.
Alan Kay
Many people who develop software would like to pretend that hardware doesn’t exist at all and that all their creations run on a perfectly imagined concept of a computer, but of course this is not actually the case. Software runs on hardware, and hardware is made up of bits that have to obey real-world constraints, such as the speed of light and entropy and other messy things that can interfere with our concepts of software.
While it might not be necessary to understand hardware at the level of the electrical engineers who build our chips, it is necessary at some level to understand how hardware affects the performance of software. No single change in computer architecture has had as profound an effect on overall system performance as that of introducing multiple levels of caching into CPUs. Most software performance is still predicated on a very old model of how CPUs execute software, but that model is long gone, except in perhaps the cheapest of low-end processors. The following letter and response tries to catch us up with the state of the art in which many of our performance problems lie hidden.
Dear KV,
I’ve been reading some pull requests from a developer who has recently been working in code that I also have to look at from time to time. The code he has been submitting is full of strange changes that he claims are optimizations. Instead of simply returning a value such as 1, 0, or -1 for error conditions, he allocates a variable and then increments or decrements it, and then jumps to the return statement. I haven’t bothered to check whether or not this would save instructions, because I know from benchmarking the code that those instructions are not where the majority of the function spends its time. He has argued that any instruction we don’t execute saves us time, and my point is that his code is confusing and hard to read. If he could show a 5 or 10 percent increase in speed, it might be worth considering, but he has not been able to show that in any type of test. I’ve blocked several of his commits, but I would prefer to have a usable argument against this type of optimization.
Pull the Other One
Dear Pull,
Saving instructions, how very 1990s of him. It’s always nice when people pay attention to details, but sometimes they simply don’t pay attention to the right ones. While KV would never encourage developers to waste instructions, given the state of modern software, it does seem like someone already has. KV would, as you did, come out on the side of legibility over the saving of a few instructions.
It seems that no matter what advances are made in languages and compilers, there are always programmers who think they’re smarter than their tools, and sometimes they’re right about that, but mostly they’re not. Reading the output of the assembler and counting the instructions may be satisfying for some, but there had better be a lot more proof than that to justify obfuscating code. I can only imagine a module full of code that looks like this:
if (some condition) retval++; goto out: else retval-; goto out: ... out: return(retval)
and, honestly, I don’t really want to. Modern compilers, or even not so modern ones, play all the tricks that programmers used to have to play by hand: inlining, loop unrolling, and many others, and yet there are still some programmers who insist on fighting their own tools.
When the choice is between code clarity and minor optimizations, clarity must nearly always win. A lack of clarity is the source of bugs, and it’s no good having code that’s fast and wrong. First the code must be right, and then the code must perform; that is the priority that any sane programmer must obey. Insane programmers, well, they’re best to be avoided. Eventually they wind up moving to a Central American nation, mixing their own drugs in bathtubs, and claiming they can unlock iPhones.
The other significant problem with the suggested code is that it violates a common coding idiom. All languages, including computer languages, have idioms, as pointed out at length in The Practice of Programming by Brian W. Kernighan and Rob Pike (Addison-Wesley Professional, 1999), which I recommended to readers more than a decade ago. Let’s not think about the fact that that book is still relevant, and that I’ve been repeating myself every decade. No matter what you think of a computer language, you ought to respect its idioms for the same reason that one has to know idioms in a human language; they facilitate communication, which is the true purpose of all languages, programming or otherwise. A language idiom grows organically from the use of a language. Most C programmers, though not all, of course, will write an infinite loop in this way:
for (;;)
or as
while (1)
with an appropriate break statement somewhere inside to handle exiting the loop when there is an error. In fact, checking the Practice of Programming book, I find that this is mentioned early on (in section 1.3). For the return case, you mention it is common to return using a value such as 1, 0, or -1 unless the return encodes more than true, false, or error. Allocating a stack variable and incrementing or decrementing and adding a goto is not an idiom I’ve ever seen in code, anywhere, and now that you’re on the case, I hope that I never have to.
Moving from this concrete bit of code to the abstract question of when it makes sense to allow some forms of code trickery into the mix really depends on several factors, but mostly on how much speedup can be derived from twisting the code a bit to match the underlying machine a bit more closely. After all, most of the hand optimizations you see in low-level code, in particular C and its bloated cousin C++, exist because the compiler cannot recognize a good way to map what the programmer wants to do onto the way the underlying machine actually works. Leaving aside the fact that most software engineers really don’t know how a computer works, and leaving aside that what most of them were taught if they were taught about computers, hails from the 1970s and 1980s before superscalar processors and deep pipelines were a standard feature of CPUs, it is still possible to find ways to speed up by playing tricks on the compiler.
The tricks themselves aren’t that important to this conversation; what’s important is knowing how to measure their effects on the software. This is a difficult and complicated task. It turns out that simply counting instructions as your co-worker has done doesn’t tell you very much about the runtime of the underlying code. In a modern CPU the most precious resource is no longer instructions, except in a very small number of compute-bound workloads. Modern systems don’t choke on instructions; they drown in data. The cache effects of processing data far outweigh the overhead of an extra instruction or two, or ten. A single cache miss is a 32-nanosecond penalty, or about 100 cycles on a 3-GHz processor. A simple MOV instruction, which puts a single, constant number into a CPU’s register, takes one-quarter of a cycle, according to Agner Fog at the Technical University of Denmark.
http://www.agner.org/optimize/instruction_tables.pdf
That someone has gone so far as to document this for quite a large number of processors is staggering, and those interested in the performance of their optimizations might well lose themselves in that site generally.
http://www.agner.org
The point of the matter is that a single cache miss is more expensive than many instructions, so optimizing away a few instructions isn’t really going to win your software any speed tests. To win speed tests you have to measure the system, see where the bottlenecks are, and clear them if you can. That, though, is a subject for another time.
KV