Custom Search

Sunday, December 3, 2017

Code speed is overrated

Premature optimization is the root of all evil.
        -- Donald Knuth

I see a lot of arguments about which language or techniques are faster, with some quite heated discussion, and a lot of effort tweaking code to make it faster. As much fun as these may be, they are largely irrelevant to the working programmer.

The reason is the implicit assumption that making the code as fast as possible is the goal of programming. For the working programmer, that's never the goal. Their goal is to meet the project requirements as quickly as possible. In some rare cases, the project requirements might be to make the code as fast as possible, but it's far more likely to be some performance goal like supporting N simultaneous users with an average response time R, or processing Y transactions per second, or handling P percent of the data within S seconds of it being generated.

With the goal being to get done quickly, the critical resource isn't machine cycles, but developer time. The first round of development should be done with an eye to preserving that.

Using developer time wisely

90% of the execution time is spent executing 10% of the code.
       -- Everyone who ever wrote about optimization

It's not the literal truth, but it's not far from it. It's a sufficiently universal truism that there are a number of similar statements about the world in general, such as the Pareto Principle or Sturgeon's Law.

Since the goal is to get to the performance requirements quickly, you should spend time optimizing the critical portions of the code. Given the 90/10 rule, the absolute best you can do with optimizing 90% of the program is a 10% reduction in run time. Assuming that the optimization effort is proportional to code length, then optimizing that critical 10% to the same level will take 1/9th the effort and provide a 90% reduction in run time, giving you 81 times the return on your investment.

Instrument your programs. Measure before making `efficiency' changes.
        -- Kernighan and Plauger

Of course, to know which code is in the 10% and which in the 90%, you have to benchmark it. Which means you have to have it working well enough to benchmark.

Make it right before you make it faster.
        -- Kernighan and Plauger

Making the code right has to be the first goal. It really doesn't matter how fast you can do the wrong thing - you're going to have to rewrite the code to make it right. Any time the developer spends optimizing code that isn't right is wasted.

Make it clear before you make it faster.
        -- Kernighan and Plauger

Similarly, the clearer the code is, the easier it is to see that it's right. Clearer code is usually shorter, meaning it's faster to write, and faster to read. So writing clear, obvious code will use less developer time.

Developer Time Summary

It should be obvious at this point that the first round of code should be as clear as possible. For about 90% of the code, that will be fast enough that no further work is needed if you avoid obvious mistakes.

To catch those obvious mistakes, do a code review after you believe the code is right. This will also help make the code clearer and faster. It's a critical part of the development process, and keeping the code clear will help the review go faster, again saving developer time.

Why ugly techniques are overrated

Let your compiler do the simple optimizations
        -- Kernighan and Plauger

A lot of the discussions I see center around specific techniques. Recent examples include arrays vs. linked lists, pointer arithmetic vs. arrays, and recursion vs. manually managing the stack. All of these things make the code less clear, possibly longer, and more prone to bugs. Worse yet, a good peephole optimizer will take care of a lot of these things for you. As such, they aren't things you should be doing before you measure your code. You also probably don't want to do them after you've gotten things right, run benchmarks that show the code isn't fast enough, and then profiled the code to find out where you can improve the performance.

Don't diddle code to make it faster -- find a better algorithm.
        -- Kernighan and Plauger

The thing is, these changes are simple micro-optimizations. If the compiler is doing them for you, all such a change does is make the code harder to read. Even if they improve performance, you'll probably get a better return on your time by changing the algorithm. If that's not possible, using a better language processor, if available, is likely to get you all those changes at once, and possibly others as well.

My favorite example of a poorly thought out development test was a reply to pointing out that a compiler should do this that went roughly "Try it in JavaScript, using any engine. Using my bad idea will be a lot faster."

True, but irrelevant. 90% of the time you're optimizing the wrong code, so you've wasted your time. In the 10% of the code that matters, if you're using a JavaScript engine, you're using an interpreter. I don't care how much effort you spend peephole optimizing that code by hand, you aren't going to make the code as fast as simply using a compiler with a good optimizer.

Why speed shootouts are overrated

The other type of discussion is the "language shootout". There are even sites dedicated to these. These are even less relevant to a working programmer. Here's why.

They use extreme measures

Don't sacrifice clarity for small gains in `efficiency'.
        -- Kernighan and Plauger

The basic problem is that these shootouts just measure how fast you can get code in the language to run. As such, the participants throw coding style to the wind, and take whatever extreme measures are required to squeeze the last cycle out of the machine. Even languages that have idioms for fast code - using unboxed values, avoiding convenient but expensive features, etc. - have entries that abandon other idioms in pursuit of extra speed. This pretty much breaks every rule in the first section about saving developer time. So while it's a lot of fun, it's also not something to do for production code.

C programs with Foo syntax

Don't patch bad code -- rewrite it.
        -- Kernighan and Plauger

The fastest language is pretty much always some low-level, imperative language that has a good mapping for modern hardware (usually C, since it's compilers get a lot of attention). Since they've already abandoned idiomatic code for your language, shootout entries tend to turn into exercises in getting the compiler to generate code as close to that generated by the low-level, imperative language. This tends to be very specific to a compiler, and updating the tool chain is likely to change the results. It often means translating C code into your chosen languages syntax. Most modern languages have a foreign function interface that allows you to plug in code written in C. If you're going to write C, you might as well use C's syntax. This will also protect you from changes in the tool chain.


The way to finish your projects quickly - the hallmark of a good programmer, and what the people you work for, whether they are your employer or people running an open source system - is to write clean, clear code to start with. Set up for a code review, and while you're waiting for that feedback, benchmark the code to see if it meets the project requirements. If it does and none of the reviewers have changes, you're done. If it does and there are changes from the review, make them and repeat the review/benchmark cycle.

If it's not fast enough, profile it to find that code that's using most of the time. You may need to deal with the code review in some way as well.

If the code using the most time is using enough time that a reasonable improvement in it will meet your requirements, you can probably ignore the rest of the code. If it's really close, make sure you're not falling into one of the performance anti-patterns for your language, or if there's some simple change - the kind of mistakes you have a code review to catch - that will get you over the edge.
More likely, you'll want to check the algorithm for inefficiencies that scale badly. One thing to watch out for outside the code that's using the most time is the code that's calling it. If you can change that algorithm to get an order of magnitude reduction in those calls, then you get an 81% reduction in run time.

Final note

All Kernighan and Plauger quotes are from The Elements of Programming Style, Second Edition, McGraw-Hill Book Company, New York, New York. While some of the advice is dated by the language choice, you should still own this book, and reread it every few years.

No comments:

Post a Comment