Premature Optimisation: We Knew Better 50 Years Ago

All good software engineers want to write good code. Unfortunately, many software engineers believe that good code must always be efficient, leading them to optimise unnecessarily or prematurely. Code is written primarily for people to read, so it should be as clear and simple as possible. One of the few constants in software engineering is change, and clear, simple code is easier to change without introducing bugs.

However, what good software engineers really want to write is good software. This is even more important in the new world of AI, but this isn’t an article about AI.

I am not suggesting that code never needs to be optimised, or that an engineer shouldn’t consider performance when writing it. For example, a value that is expensive to evaluate but remains constant should be initialised outside a loop rather than recalculated on every iteration. However, halving the execution time of a 2ms calculation in a request that also makes a 40ms database call makes very little difference to the overall response time, especially if the optimisation makes the code more complicated and harder to understand.

The importance of understanding where optimisation will make a meaningful difference is nothing new. Software engineers were exploring this more than fifty years ago - years before I was born!

We worked this out fifty years ago

In 1971, Donald Knuth, an American computer scientist and professor at Stanford University, published An Empirical Study of FORTRAN Programs. Knuth is best known for The Art of Computer Programming, a series of books that has had an enormous influence on the study of algorithms and computer programming. One of his principal conclusions was that engineers needed to understand where their programs were spending their time before attempting to make them faster.

Knuth was advocating profiling, using measurements of how frequently statements were executed to identify the parts of a program that would benefit most from optimisation. He recognised that engineers had a long history of optimising the wrong things, spending time improving code that was rarely executed while overlooking the parts responsible for most of the processing.

Interestingly, Knuth wasn't arguing that efficiency was unimportant. Quite the opposite. He recognised that the industry had moved away from a time when computer resources were expensive and engineers were expected to make every instruction count. As machines became faster and cheaper, development and maintenance costs became increasingly important. Readability and maintainability were rightly receiving more attention, but Knuth believed the balance had moved too far.

His solution wasn't to optimise everything. It was to identify where optimisation would make a meaningful difference and concentrate effort there.

Three years later, in 1974, Knuth returned to the subject in Structured Programming with go to Statements. This is where he made his famous observation:

Premature optimisation is the root of all evil.

It's probably one of the most frequently repeated quotations - and if it isn't, it should be - in software engineering, and one of the most frequently misunderstood. It's also usually quoted without the surrounding explanation, which is important to understanding what Knuth was actually saying.

Knuth wasn't saying that optimisation was evil, or that engineers should ignore performance. He was arguing that engineers waste enormous amounts of time worrying about the efficiency of code that isn't critical. Worse, these attempts at optimisation can make programs harder to debug and maintain.

He suggested forgetting about small efficiencies approximately 97% of the time, while paying careful attention to the remaining 3%. The important point is that the critical code needs to be identified first.

In the same paper, Knuth discusses the value of applying disciplined optimisation to a program whose correctness has already been established. This reinforces the point I'm making. First establish that the program is correct, then improve its performance without compromising that correctness.

Also in 1974, Knuth published Computer Programming as an Art, which is where my research into the origins of our understanding of optimisation in software engineering began.

Knuth described several characteristics of a good program. It should work correctly, be understandable and be relatively easy to change. Efficiency matters too, but it shouldn't come at the expense of those other qualities without good reason.

Once again, he returned to the importance of measurement. Engineers frequently misunderstand where their programs spend their time, and without profiling information they can easily optimise the wrong things.

Over a few years in the early 1970s, Knuth had made essentially the same argument across three publications. Optimisation is important when it matters, but decisions about what to optimise should be based on evidence rather than guesswork.

Make it right before you make it faster

Also published in 1974 was The Elements of Programming Style by Brian Kernighan and P. J. Plauger (ISBN-13: 978-0070341999). Kernighan worked at Bell Labs, contributed to the development of Unix and helped popularise C through his books. Plauger is a programmer and author known for his contributions to the C and C++ standard libraries. This book is particularly interesting because it presents a collection of practical rules for writing better programs, several of which address optimisation directly.

Among them are:

• Make it right before you make it faster.
• Make it clear before you make it faster.
• Don't sacrifice clarity for small gains in efficiency.
• Let the compiler do the simple optimisations.
• Don’t tinker to make it faster - find a better algorithm.
• Beware of preconceptions about where a program spends its time.

These are remarkably straightforward principles, and I think they're as relevant today as they were in 1974.

The authors recognised that readable code and efficient code aren't mutually exclusive. In fact, clear and straightforward code can often be more efficient than unnecessarily clever alternatives. More importantly, code that is easy to understand is also easier to maintain, change and improve.

There's another important distinction here. Optimisation doesn't necessarily mean making individual statements execute faster. Choosing a better algorithm can produce far greater improvements than spending hours tuning loops or replacing individual operations.

The book also makes a point that I think is fundamental: if a program doesn't work correctly, it doesn't matter how fast it runs.

I tend to think of this in terms of motor racing. First, get the car to the end of the race. Then worry about making it faster. A car that breaks down halfway through isn't much use, however quick it was before it stopped.

Don't do it. Don't do it yet.

In 1975, Michael A. Jackson, a British software engineer best known for developing Jackson Structured Programming (JSP), published Principles of Program Design (ISBN: 0-12-379050-6). Of all the books I've read while researching this subject, Jackson provides perhaps the clearest statement of when engineers should optimise.

He introduces two rules:

• Rule 1: Don't do it.
• Rule 2: Don't do it yet.

The second rule is intended for experts, and means waiting until a clear, unoptimised solution exists.

Jackson explains that optimisation has a cost. Making a program faster or smaller can also make it more difficult to understand, maintain and modify. It can introduce errors and increase the overall cost of developing and operating the system.

His first rule means that optimisation needs a positive, quantified justification. There's little point making a program faster if the only result is more unused CPU time. Similarly, reducing memory consumption doesn't necessarily provide any benefit if the memory wasn't a constraint in the first place.

His second rule is equally important. Start with a clear, unoptimised design that can be fully understood. Only then should you consider changing it for performance reasons.

Jackson also points out that optimisation can obscure the structure of a program, making further improvements more difficult. This is something I think developers can easily overlook. An optimisation that provides a small improvement today might make it considerably harder to achieve a more substantial improvement tomorrow.

This isn't just a theoretical concern. I've seen exactly this sort of thing in practice. Earlier this year, I wrote about why deep imports are harmful. An engineer had chosen to bypass a component's public interface and import directly from its internal implementation in pursuit of better build performance. This increased coupling and made the code harder to maintain, without providing a meaningful performance improvement. I followed this up with Deep Imports Are Not Faster, which explored why the supposed performance benefit wasn't there.

It's a good example of sacrificing software design for an optimisation that wasn't justified in the first place.

What I find particularly interesting is how closely Jackson's advice matches Knuth's. They were writing about different aspects of programming, but they reached very similar conclusions.

By 1975, the principles were already well established:

• Don't optimise without justification.
• Don't optimise too early.
• Understand the program first.

Twenty-five years later, nothing had changed

Fast forward to 1999 and The Practice of Programming by Brian Kernighan and Rob Pike (ISBN-13: 978-0201615869). Pike is another former Bell Labs computer scientist, known for his work on Unix, the Plan 9 operating system and, later, the Go programming language. I was encouraged to read this book early in my professional career and it has helped form much of my general approach to software engineering. When I’ve built software teams, I’ve encouraged my engineers to read it too.

Chapter 7, Performance, opens by considering whether efficiency still matters when computers have become so much faster and cheaper.

Their answer is yes, but only when there's a genuine problem worth solving and a reasonable expectation that performance can be improved without compromising correctness, robustness or clarity.

Their first principle of optimisation is, once again, don't.

What I particularly like about this chapter is that it goes beyond explaining why premature optimisation is a bad idea and describes a practical approach to improving performance.

Start with appropriate algorithms and data structures. Measure the program's performance. Use profiling to identify where time is being spent. Consider which changes are likely to make the biggest difference. Make changes individually and measure again.

They also recommend retaining the original, simpler implementations so that the optimised versions can be checked against them.

This is an important point because it connects optimisation directly to testing.

Performance improvements need to be repeatable and measurable, but correctness also needs to be preserved. A change that makes a program twice as fast while introducing an incorrect result isn't an improvement.

The authors discuss automated benchmarks, keeping records and using regression tests to ensure that changes haven't introduced problems or undone previous improvements.

This is where I think we should be particularly disciplined today. We have automated testing frameworks, continuous integration and readily available profiling tools. There's little excuse for making significant performance changes without first establishing that the existing behaviour is covered by tests.

Before optimising code, I want automated tests that demonstrate what it currently does. Those tests should continue to pass after the optimisation. Otherwise, how can we be confident that we've improved the implementation rather than accidentally changed the behaviour?

Of course, passing tests can't guarantee that a program is correct, particularly if the tests are incomplete. But they provide a level of confidence that simply looking at the code cannot. I would go further and suggest that optimisation without adequate automated tests is an unnecessary risk. If the code is important enough to optimise, surely it's important enough to test?

There's another point from The Practice of Programming that I particularly like. The authors suggest that the time spent making a program faster should be considered against the time that improvement will save over the lifetime of the program.

That's a useful way of looking at optimisation. We shouldn't spend days saving milliseconds in a program that runs once a month unless those milliseconds genuinely matter.

Optimisation needs to provide value, not simply produce a faster benchmark.

There's also an opportunity cost to optimisation. Time spent making code faster when there's no meaningful performance problem is time that could have been spent fixing bugs, improving reliability or delivering something more useful. Even if an optimisation doesn't make the code more complicated, it still needs to justify the time spent implementing it.

The fastest isn't always the best

In 1999, Andrew Hunt and David Thomas, two experienced software developers who helped establish the Pragmatic Programmers publishing business, published The Pragmatic Programmer (ISBN-13: 978-0201616224), another book that was recommended to me, that I continue to recommend and that has helped shape my thinking. In the section Best Isn't Always Best, they make another important observation: 

The fastest algorithm isn't necessarily the most appropriate.

For a small collection of data, a simple insertion sort may be perfectly adequate. A theoretically faster algorithm can involve additional complexity or setup costs that provide little or no benefit for the actual problem being solved.

The authors also explicitly warn against premature optimisation and recommend establishing that an algorithm is genuinely a bottleneck before investing time improving it.

This adds another dimension to the argument. Even when we understand the theoretical performance characteristics of an algorithm, that doesn't necessarily tell us which implementation is best for a particular application.

We need to understand the size of the data, how frequently the operation runs and what performance is actually required.

Once again, context matters.

In 2000, Jon Bentley, an American computer scientist who also worked at Bell Labs and is known for his research into algorithms and programming techniques, published the second edition of Programming Pearls (ISBN-13: 978-0201657883). Interestingly, Kernighan, Pike and Bentley all worked at Bell Labs, an organisation that played a significant role in the development of modern software engineering. In the chapter on code tuning, Bentley makes a similar argument.

Bentley describes two extremes. Some programmers become so concerned with efficiency that they produce unnecessarily clever code that is difficult to maintain. Others pay too little attention to performance and produce beautifully structured programs that are too inefficient to be useful.

Neither approach is particularly helpful.

The important thing is to keep efficiency in context. It's one of several characteristics of good software, and sometimes it's extremely important. However, it isn't always the most important characteristic, and it certainly isn't something that needs to be pursued everywhere.

What should we be doing today?

Looking back over these publications, from Knuth in 1971 through to Bentley, Hunt and Thomas in 2000, I'm struck by just how consistent the advice has been.

The authors don't all agree on every detail, and they certainly don't suggest that performance can be ignored. But they repeatedly return to the same fundamental principles:

• Write code that is correct, clear and maintainable. Choose appropriate algorithms and data structures rather than automatically reaching for the most complicated or theoretically fastest solution. 
• Establish whether there's actually a performance problem. Not whether something could be faster, because almost anything could be faster, but whether making it faster would provide a meaningful benefit.
• Measure before making changes. Use profiling and realistic benchmarks to identify where the time or resources are being consumed. Don't rely on assumptions about which parts of the code must be slow.
• Before making changes, ensure that the existing behaviour is adequately covered by automated tests. Optimisation shouldn't change what a program does, only how efficiently it does it.
• Optimise the parts that matter, measure again and run the tests. If the change doesn't provide a worthwhile improvement, or introduces unnecessary complexity, question whether it should be kept at all.

None of this means we should deliberately write inefficient software. There's a difference between choosing sensible algorithms and data structures from the outset and prematurely optimising individual pieces of code. We should understand the performance implications of our designs without feeling compelled to squeeze every possible microsecond out of them.

Neither am I suggesting that performance can always wait until a system is in production. Some applications have strict performance requirements that need to influence their design from the beginning. But even then, those requirements should be explicit, and the decisions made to satisfy them should be supported by evidence.

What concerns me is the tendency to treat optimisation as an inherently good thing. As though making something faster automatically makes it better, regardless of whether that improvement was needed or what it cost in complexity and maintainability.

We have faster computers, more sophisticated compilers, better profiling tools and far more accessible automated testing than the programmers of the 1970s could have imagined.

Yet the underlying advice hasn't really changed.

• Make it right. 
• Make it clear.
• Test it. 
• Measure it. 
• Then, and only if there's a good reason, make it faster.

Finally

A friend of mine, a sometimes colleague and brilliant software engineer, doesn't read software books. They feel that they go out of date too quickly, sometimes even before they've been published. They're not wrong either. Books about programming languages, frameworks or the latest fad can become outdated very quickly. However, books about how we approach software engineering can remain relevant, at least in part, for decades.

I regularly encounter engineers who appear to be unaware of software engineering principles that I consider fundamental and apply throughout the systems I develop. I can't help feeling that reading some of these books and engaging with the wider software engineering community, as I've done throughout my career, would help them write clearer, more understandable code and, ultimately, more robust and reliable software.

Some engineers may never have encountered these books or papers. Others may know Knuth's famous quotation without having read the reasoning behind it. What I hope I've demonstrated is that the principles behind effective optimisation have been understood for more than fifty years. The technology has changed enormously but the advice remains remarkably consistent. Perhaps instead of looking for new ways to make our code faster, we should spend a little more time understanding what the engineers who came before us have already learned.

Perhaps instead of looking for new ways to make our code faster, we should spend a little more time understanding what the engineers who came before us have already learned.