Code Optimisation – Part 1

There is more to life than increasing its speed
~ Mahatma Gandhi

We live in a fast food culture. Not only must our dinner arrive yesterday, our car should be fast and our entertainment instant. Our code should also run like lightning. I want my result. And I want it now.

Ironically, writing fast programs takes a long time.

Optimisation is a spectre hanging over software development, as renowned computer scientist W.A. Wulf observed:

More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason – including blind stupidity.

Optimisation is a well worn subject, one on which many an expert has offered their opinion, and the same advice has been served time and time again. But despite this, a lot of code is still not developed sensibly. Optimisation seems like a good idea, but programmers get it wrong all too often: They get sidetracked by the lure of efficiency, they write bad code in the name of performance, they optimise when it’s really not necessary, or they apply the wrong kind of optimisations.

What is optimisation?

The word optimisation purely means to make something better, to improve it. In our world, it’s generally taken to mean ‘making code run faster’, measuring a program’s performance against the clock. But this is only a part of the picture. Different programs have different requirements; what’s ‘better’ for one may not be ‘better’ for another. Software optimisation may actually mean any of the following:

• Speeding up program execution
• Decreasing executable size
• Improving code quality
• Increasing output accuracy
• Minimizing startup time
• Increasing data throughput (not necessarily the same as execution speed)
• Decreasing storage overhead (database size)

Conventional optimisation wisdom is summed up by M.A. Jackson’s infamous laws of optimisation:

1. Don’t do it.
2. (For experts only) Don’t do it yet.

That is, you should avoid optimisation at all costs. Ignore it at first, and only consider it at the end of development when your code is not running fast enough. This is a simplistic viewpoint – accurate to a point, but potentially misleading and harmful. Performance is really a valid consideration right from the humble beginnings of development, before a single line of code has been written.

Code performance is determined by a number of factors, including:

• The execution platform
• The deployment or installation configuration
• Architectural software decisions
• Low-level module design
• Legacy artefacts (like the need to interoperate with older parts of the system)
• The quality of each line of source code

Some of these are fundamental to the software system as a whole, and an efficiency problem there won’t be easy to rectify once the program has been written. Notice how little impact individual lines of code have; there is so much more that affects performance. We must manage performance issues at every step of the development process and deal with any problems as they arise. In a sense, optimisation (while not a specific scheduled activity) is an ongoing concern through all stages of development.

Think about the performance of your program from the very start; do not ignore it, hoping to make quick fixes at the end of development.

But don’t use this as an excuse to write tortured code based on your notion of what is fast or not. Programmers’ gut feelings for where bottlenecks lie are seldom right, no matter how experienced they are. In the following sections, we’ll see practical solutions to this code-writing dilemma.

But first, the golden rule. Before you consider a stint of code optimisation, you must bear this advice in mind:

Correct code is far more important than fast code. There’s no point in arriving quickly at the wrong answer.

You should spend more time and effort proving that your code is correct than making it fast. Any later optimisation must not break this correctness.

I once discovered that a module I’d written was running unbelievably slowly. I profiled it and tracked the problem down to a single line of code. It was called frequently and appended a single element to a buffer.

Upon inspection, the buffer (which I was given, and hadn’t written) was expanding itself by a single element each time it got full! In other words: Every single append was allocating, copying, and deallocating the entire buffer. Ouch. Needless to say, I was not expecting this behaviour.

This helps to show how we get suboptimal programs: by growth. Few people wilfully attempt to write an ambling program. As we glue software components into a larger system, we can easily make assumptions about the performance characteristics of the code and end up with a nasty shock.

What makes code suboptimal?

In order to improve our code, we have to know the things that will slow it down, bloat it, or degrade its performance. Later on, this will help us to determine some code optimisation techniques. At this stage, it’s helpful to appreciate what we’re fighting against.

• Complexity: Unnecessary complexity is a killer. The more work there is to do, the slower the code will run. Reducing the amount of work or breaking it up into a different set of simpler, faster tasks can greatly enhance performance.


• Indirection: This is touted as the solution to all known programming problems, summarised by the infamous programmer maxim: Every problem can be solved by an extra level of indirection. But indirection is also blamed for a lot of slow code. This criticism is often levelled by old-school procedural programmers, aimed at modern OO designs.


• Repetition: Repetition can often be avoided, and will inevitably ruin code performance. It comes in many guises; for example, by failing to cache the results of expensive calculations or of remote procedure calls. Every time you recompute, you waste precious efficiency. Repeated code sections unnecessarily extend executable size.


• Bad design: It’s inevitable: Bad design will lead to bad code. For example, placing related units far away from each other (across module boundaries, for example) will make their interaction slow. Bad design can lead to the most fundamental, the most subtle, and the most difficult performance problems.


• I/O: A program’s communication with the outside world – its input and output – is a remarkably common bottleneck. A program whose execution is blocked waiting for input or output (to and from the user, the disk, or a network connection) is bound to perform badly.

This list is nowhere near exhaustive, but it gives us a good idea of what to think about as we investigate how to write optimal code.

Why not optimise?

Historically, optimisation was a crucial skill, since early computers ran very, very slowly. Getting a program to complete in anything like reasonable time required a lot of skill and the hand-honing of individual machine instructions. That skill is not so important these days; the personal computer revolution has changed the face of software development. We often have a surplus of computational power, quite the reverse of the days of yore. It might seem that optimisation doesn’t really matter any more.

Well, not quite. The software factory still throws us situations requiring high performance code, and if you’re not careful, you’ll need a mad optimisation dash at the last minute. But it is preferable to avoid optimising code if at all possible. Optimisation has a lot of downsides.

There’s always a price to pay for more speed. Optimising code is the act of trading one desirable quality for another. Some aspect of the code will suffer. Done well, the (correctly identified) more desirable quality is enhanced. These trade-offs are the top reasons to avoid optimising code:

• Loss of readability: It’s rare for optimised code to read as clearly as its slower counterpart. By its very nature, the optimised version is not as direct an implementation of the logic or as straightforward. You sacrifice readability and neat code design for performance. Most ‘optimised’ code is ugly and hard to follow.


• Increase in complexity: A more clever implementation – perhaps exploiting special backdoors (thereby increasing module coupling) or taking advantage of platform-specific knowledge – will add complexity. Complexity is the enemy of good code.


• Hard to maintain/extend: As a consequence of increased complexity and a lack of readability, the code will be harder to maintain. If an algorithm is not clearly presented, the code can hide bugs more easily. Optimisation is a surefire way to add subtle new faults – these will be difficult to find because the code is more contrived and harder to follow. Optimisation leads to dangerous code.
  
  It also stunts the extensibility of your code. Optimisations often come from making more assumptions, limiting generality and future growth.


• Introducing conflicts: Often an optimisation will be quite platform-specific. It might make certain operations faster on one system, at the expense of another platform. Picking optimal data types for one processor type may lead to slower execution on others.


• More effort: Optimisation is another job that needs to be done. We have quite enough to do already, thank you. If the code is working adequately, then we should focus our attentions on more pressing concerns.
  
  Optimising code takes a long time, and it’s hard to target the real causes. If you optimised the wrong thing, you’ve wasted a lot of precious energy.

For these reasons, optimisation should be some way down on your list of concerns. Balance the need to optimise your code against the requirement to fix faults, to add new features, or to ship a product. Often optimisation is not worthwhile, or is uneconomical. If you take care to write efficient code in the first place, you’re less likely to need to optimise anyway.

Alternatives

Often code optimisation is performed when it’s not actually necessary. There are a number of alternative approaches that we can employ without altering our existing good quality code. Consider these solutions before you get too focused on optimisation:

• Can you put up with this level of performance – is it really that disastrous?


• Run the program on a faster machine. This seems laughably obvious, but if you have enough control over the execution platform, it might be more economical to specify a faster computer than spend time tinkering with code. Given the average project duration, you are guaranteed that by the time you reach completion, processors will be considerably faster.
  
  Not all problems can be fixed by a faster CPU, especially if the bottleneck is not execution speed – a slow storage system, for example. Sometimes a faster C can cause drastically worse performance; faster execution can exacerbate thread locking problems.


• Look for hardware solutions: Add a dedicated floating point unit to speed up calculations, add a bigger processor cache, more memory, a better network connection, or a wider bandwidth disk controller.


• Reconfigure the target platform to reduce the CPU load on it. Disable background tasks or any unnecessary pieces of hardware. Avoid processes that consume huge amounts of memory.


• Run slow code asynchronously, in a background thread. Adding threads at the last minute is a road to disaster if you don’t know what you’re doing, but careful thread design can accommodate slow operations quite acceptably.


• Work on user interface elements that affect the user’s perception of speed. Ensure that GUI buttons change immediately, even if their code takes over a second to execute. Implement a progress meter for slow tasks; a program that hangs during a long operation appears to have crashed. Visual feedback of an operation’s progress conveys a better impression of the quality of performance.


• Design the system for unattended operation so that no one notices the speed of execution. Create a batch processing program with a neat UI that allows you to queue work.


• Try a newer compiler with a more aggressive optimiser, or target your code for the most specific processor variant (with all extra instructions and extensions enabled) to take advantage of all performance features.

Look for alternatives to optimising code – can you increase your program’s performance in any other way?

Why optimise?

Having seen the dangers of code optimisation, should you now give up any foolish notion of ever optimising your code? Well, no: You should still avoid optimisation wherever possible, but there are plenty of situations where optimisation is important. And contrary to popular belief, some areas are guaranteed to require optimisation.

• Games programming always needs well-honed code. Despite the huge advances in PC power, the market demands more realistic graphics and more impressive artificial intelligence algorithms. This can only be delivered by stretching the execution environment to its very limits. It’s an incredibly challenging field of work; as each new piece of faster hardware is released, games programmers still have to wring every last drop of performance out.


• Digital Signal Processing (DSP) programming is all about high performance. Digital Signal Processors are dedicated devices specifically optimised to perform fast digital filtering on large amounts of data. If speed didn’t matter, you wouldn’t be using them. DSP programming generally relies less on an optimising compiler, since you want to have a high degree of control over what the processor is doing at all times. DSP programmers are skilled at driving these devices at their maximum performance.


• Resource constrained environments, such as deeply embedded platforms, can struggle to achieve reasonable performance with the available hardware. You’ll have to hone the code for acceptable quality of service or work hard to fit it into the device’s tight memory.


• Real time systems rely on timely execution, on being able to complete operations within well specified quanta. Algorithms have to be carefully honed and proven to execute in fixed time limits.


• Numerical programming – in the financial sector, or for scientific research – demands high performance. These huge systems are run on very large computers with dedicated numerical support, providing vector operations and parallel calculations.

Perhaps optimisation is not a serious consideration for general purpose programming, but there are plenty of cases where optimisation is a crucial skill. Performance is seldom specified in a requirements document, yet the customer will complain if your program runs unacceptably slowly. If there are no alternatives, and the code doesn’t perform adequately, then you have to optimise it.

There is a shorter list of reasons to optimise than not to. Unless you have a specific need to optimise, you should avoid doing so. But if you do need to optimise, make sure you know how to do it well.

Understand when you do need to optimise code, but prefer to write efficient high quality code in the first place.

Next time

Next time we’ll look more closely at practical techniques for program optimisation.

Pete Goodliffe is a programmer who never stays at the same place in the software food chain. He has a passion for curry and doesn’t wear shoes.