Opinion
Computing Applications Kode Vicious

What Are You Trying to Pull?

A single cache miss is more expensive than many instructions.
Posted
  1. Dear KV,
  2. Dear Pull,
  3. Author
What Are You Trying to Pull? illustrative photo

back to top   Dear KV,

I have 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 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 have not bothered to check whether or not this would save instructions, because I know from benchmarking the code those instructions are not where the majority of the function spends its time. He has argued any instruction we do not execute saves us time, and my point is his code is confusing and difficult to read. If he could show a 5% or 10% increase in speed, it might be worth considering, but he has not been able to show that in any type of test. I have blocked several of his commits, but I would prefer to have a usable argument against this type of optimization.

Pull the Other One

Back to Top

Dear Pull,

Saving instructions—how very 1990s of him. It is always nice when people pay attention to details, but sometimes they simply do not 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 are smarter than their tools, and sometimes they are right about that, but mostly they are 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:

ins01.gif

and, honestly, I do not really want to. Modern compilers, or even not so modern ones, play all the tricks 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 is no good having code that is fast and wrong. First the code must be right, then the code must perform; that is the priority that any sane programmer must obey. Insane programmers, well, they are best to be avoided.

The other significant problem with the suggested code is 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 the book is still relevant, and that I have been repeating myself every decade. No matter what you think of a computer language, you ought to respect its idioms for the same reason 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:

ins02.gif

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 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 have ever seen in code, anywhere—and now that you are on the case, I hope I never have to.


When the choice is between code clarity and minor optimizations, clarity must, nearly always, win.


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 do not 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 are not that important to this conversation; what is 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 does not 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 do not choke on instructions; they drown in data. The cache effects of processing data far outweigh the overhead of an extra instruction or two, or 10. A single cache miss is a 32-nanosecond penalty, or about 100 cycles on a 3GHz 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 is not 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

q stamp of ACM Queue Related articles
on queue.acm.org

Human-KV Interaction
http://queue.acm.org/detail.cfm?id=1122682

Quality Software Costs Money—Heartbleed Was Free
Poul-Henning Kamp
http://queue.acm.org/detail.cfm?id=2636165

The Network Is Reliable
Peter Bailis and Kyle Kingsbury
http://queue.acm.org/detail.cfm?id=2655736

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More