How to counter premature optimisation

There was a time in my career, in the 1960s, when optimisation wasn't optional. System memories were measured in kilobytes, instruction times in tens or hundreds of microseconds. We planned our programs around those limited resources. No longer. In fact, program optimisation is rarely needed these days despite programs that are …

[Anonymous Coward]

Agreed....but it doesnt excuse sloppy code.

I agree with the thrust of the article - that excessive optimisation is often unnecessary, but all too often I see coders adopting practices that are unnecessary slow.

Use of the wrong types of storage objects (lists versus vectors, versus hashmaps etc), incorrect use of algorithms etc.

Its about saying 'Whats the most efficient tool for this job?' All too often this is confused with premature optimisation, rather than being seen for what it is - doing the right thing first time.

[Peter D'Hoye]

It all depends on the target you develop for

Embedded developers can safely ignore the above article ;)

And other developers maybe too... Maybe optimisation is a waste of time if the code was written efficiently, but telling users to buy a faster PC because you can't code efficiently is not the way to go.

So it's not that black/white as the article puts it.

[Michael H.F. Wilkinson]

Exactly

However, optimization is still required in some instances, i.e. where in those areas where performance is CRITICAL, which is probably in less than 0.01% of all code. One example is in image processing, where I have been able to boost the performance of certain algorithms by a factor of between 6 and 10, which is not to be sneezed at. When faster hardware came along, we STILL retained speed-up. There are four reasons we chose to hand optimize:

1. we were sure the image processing operator was useful in the first place

2. we were sure the selected algorithm was correct and had better time complexity than its competitor

3. we were sure we needed high performance for real-time work and/or large data sets

4. we were sure that the resulting (UGLY!!) code is essentially separated from anything else, it is just a routine you call from whatever application needs it.

Only when all four reasons apply does it make sense to optimize for speed.

[David Norfolk]

Not optimising doesn't mean doing it wrong....

True, if premature optimisation is bad, so is careless, bloated programming – as Dave Jewell’s “related article” points out. But it’s not a binary option – most professional programmers follow “good practice” and write good quality, reasonably efficient code (I hope).

Bad programming is NOT the only alternative to premature optimisation.

[Chris Miller]

Yes but

Two minor points:

1. Efficient (elegant) code and understandable (well-documented) code are not diametric opposites. Building in efficiency when the code is first written need not add substantially to the cost. Optimising existing code at a later stage is a different matter.

2. The need for optimisation of memory use and CPU cycles has gone. The focus now is on optimisation of comms capacity. A web page that takes 5 seconds to load is likely to be useless. A client-server app that requires 40 separate TCP messages may perform well on a LAN and then die horribly as it is moved into a WAN environment.

[Anonymous Coward]

Define optimisation....

Recently I developed a .Net application which processed a number of test result log files (approx 20-40MB each). The old tool had been developed in C++, but was slow and a memory hog. When some major changes to it were needed it was decided to do a complete rewrite. Performance wasn't cited as a critical requirement (it had just been accepted that it took an hour or so to run).

Part-way through the development of the replacement tool I tried out the Profiler tool in Visual Studio 2005. Within a short period of time I discovered that what I was doing was very inefficient with memory usage. I was basically converting data between types a lot, causing lots of allocations. Over the whole lifetime of the application this made a significant impact in the length the application took to process the logs. After some 'optimising' (well, refactoring really), I managed to reduce the processing time to about 30% of what it used to be. By doing it quite early in the process, the amount of refactoring/re-working was quite small. Doing this at the end when much of the design had been fixed would have required a much larger amount of work.

Later on I had to automate the importing of the results into Excel. Whilst doing this I discovered (probably sounds obvious to most people!) that assigning single cell values over COM is slow when compared to assigning an array to a range of cells. As a result, I again managed to shave over 50% off the importing time.

The end result is that the entire processing and importing task now takes 20 minutes compared to around 1-2 hours (and unlike the old tool, plays nicely with the CPU load, so doesn't kill the machine in the process, allowing the user to continue working with other things). At our hourly rate, this 'optimisation', even done quite early in the project and taking a few days to nail down, makes a significant difference to our testing processes. Whilst performance wasn't a requirement at the start, the people involved with the testing appreciate the significant improvement in performance, even on the same hardware.

However, was what I did optimisation, or merely following best practices (assigning cells by large ranges, being conscious of memory allocations and castings and their effect on the garbage collector etc)? The changes required to improve performance didn't change readability or maintainability of the code - just changed the way things were done.

[Igor Clark]

Let's not rely on hardware improvements

All fair points and the "optimize last if you need to" approach is sensible, but I fear that it can also lead to the sorts of attitudes that we see with a lot of modern software, for example in the web field we often hear voices in the Rails community shouting: "Scaling? Optimising? Pah - just chuck more hardware at it, it's cheap".

As the first commenter said, excessive optimisation *is* often unnecessary, but there's really neither need nor excuse for sloppy code, and there's no need for laziness in utilising the resources available just because more resources are cheap. It's the same attitude which fuels many environmental problems we face - "use it up, chuck it away, buy another one. Who cares? It's cheap!".

Let's not strangle ourselves with unnecessary constraints, but let's not use that as an excuse to ignore economy and efficiency.

[Mark Lomas]

When to optimise

I think it better to suggest that you should know when to optimise.

If somebody tells me they can double the speed of an application I would tell them not to bother. If I cared about its speed I could probably improve it simply by buying some more memory or degragmenting a disc.

The real problems, however, are when people don't understand the time complexity of their application.

If while processing some data you process each data item a fixed number of times the running time of your application is likely to be linear: increasing the amount of data will increase the running time proportionally.

If instead you compare each data item with every other data item then the running time will increase according to the square of the amount of data. Doubling the data size will increase the running time four-fold.

I have seen too many cases where people don't understand this. A developer might test a program with an unrealistically small amount of data during the development process. Let's imagine that a realistic data set is 100 times as large as the test data and that their algorithm scales according to the square: the user will be subject to a running time 10,000 times as long as during tests.

If you realise this from the outset you redesign your algorithm. In other words you optimise right from the start of your project.

The important observation, however, is that you only optimise those parts of the algorithm where the time complexity is high.

[Neil]

Now always true

As a general coding rule, this might be Ok, but it doesn't always hold true.

I write a lot of T-SQL code. where optimising can make huge differences on large DBs. On several occasions, optimising has been absolutely critical. I.e. part of a website login taking over 30 seconds to run. After I finished - sub 1 second. Or a scheduled process running every minute, taking 3 minutes to run, resulting in huge locking issues and loss of data.

It wasn't that the original code was _wrong_ per se, just not as good as it could have been with a better understanding.

[Anton Ivanov]

This puts all optimisation under the same label.

The article does not distinguish between algorithm level optimisation and implementation level optimisation. Same as many people in the industry nowdays.

As a result quite a lot of w***ers are allowed to hide behind the "do not optimise" mantra and invent "simple to understand" algorithms of their own instead of using applicable well known solutions (most of them long in the textbooks). Full enumeration of alternatives instead of sorting for various "traveller" style problems is just one example. Many others. In many cases these "easy to understand" replacement algorithms do not cover all possible use cases. So scaling problems aside, usage of such "easy to understand" solutions instead of "textbook stuff", no matter how complex is the latter, is one of the common cases of instability in modern software.

Overall, yes - do not optimise is a good mantra. But one missing word. It should be "Do not optimise the _implementation_". You should still use the optimal algorithm when designing and writing your software.

[Nick Kew]

Don't confuse non-optimisation with non-design ...

In about 1988, I was involved in developing an embedded system, with a hard limit of 128K EPROM for a complex system. So code optimisation wasn't optional.

But at the same time, I was able to improve a key mathematical algorithm used. That brought the system startup time from 45 minutes (power-up to fully functional) down to about 90 seconds. It took more code, so it required optimisation too.

Now while that's very clearly not the kind of optimisation the article tells us to dispense with. But there's also a big grey area between the two. So I'll continue to say rude things about the great big messes I see. They may be technically mere optimisation, yet still have an order of magnitude or more effect on performance. Not to mention (sometimes) security.

[David Harper]

The lost art of efficient coding

I cut my teeth writing numerical simulation code in Fortran to run in a batch system on an IBM mainframe shared by several hundred other people. Everyone was strongly encouraged to write efficient code, and I quickly learned that optimisation was the difference between getting a result within hours, or having to sit around twiddling my thumbs for a couple of days.

25 years on, my home PC has more computing power than that early-80s IBM mainframe, and I've switched from Fortran to Java, but I still aim to write efficient code, because my users expect a timely response from their GUI app.

In my Fortran days, optimisation meant removing invariants from loops and recognising symmetries in large matrix calculations. Today, it means fine-tuning SQL queries and avoiding the unnecessary creation of too many short-lived String objects. It's still a valuable exercise in self-discipline and it still provides a deeper understanding of what the code is actually doing.

[Steve Charlton]

The rules for software engineering cover this.

Rule 1: Keep it simple.

Rule 2: Make it work, THEN make it better.

Rule 3: Better is the enemy of good enough.

Rule 4: Don't change 2 variables in an experiment at the same time.

So, get it to work, then you can optimize it, but only if you need to.

I work in embedded systems, so adding more memory or a faster processor isn't usually an option.

[Anonymous Coward]

Premature, yes . . .

I agree with the spirit of this, and the many other articles/books/chapters on a similar vein.

However, I think it's time to choose our words more carefully: premature optimization is not the same as early optimization.

For instance, many key optimizations come at the design stage (bubble sort anyone? proper choice of container?), and many others become second nature to experienced C/C++ programmers in developmental phases (such as the use of register int counters in 'for' loops known to run many hundreds or thousands of times).

I guess I would also add that perhaps ill-informed optimization is the root of premature optimization??

[Anonymous Coward]

I wish

Some of us don't work for companys that upgrade equipment (still using a 4 year old laptop)

With all the point & click programming (and web monkeys claiming to be programmers), I doubt the amount of real optimistaion going on these days anyway.

Having watched the recent developemnt of several systems recently frankly the developers and steering teams don't actually know whats going on in the first place. And the purchaser (my employers) went on promices from the sales people.

Currently the number of servers has grown from 20 to 140, and each server is only coping with 3 users ! A workload previousy coped with by 10 novell servers

It's a nice theory if you work for Intel or whoever, but for the rest of us in the slums.

[Carlie J. Coats, Jr.]

But get data structures and algorithms right

Far too many codes are developed according to the developer's first idea:

he/she blindly goes ahead with the first idea that probably works.

They don't stop to think about what data structures are appropriate, nor what algorithms.

For modern (deeply pipelined) processors, there are two primary performance inhibitors: dependencies and memory access.

Particularly, deeply nested logic or deeply linked data structures have big costs, as do huge data structures.

I just finished re-writing an environmental-simulation code, which (for a primary operational case) went from a working-set

size of 3.4 GB to 640 MB, and a run-time of 130 CPU-minutes/simulation-day to 7 CPU-minutes/simulation-day. The primary optimization was the elimination of several huge scratch-arrays (with their associated memory traffic), and the replacement of "dumb" run-time searches with setup-time sparse matrix construction. *Not* rocket science.

In another example fifteen years ago, went from a more extreme 12 Cray-hours to 163 SPARC2-seconds, replacing dumb array

searches with sparse matrix arithmetic...

And in both these cases, the results are simpler, clearer, and more maintainable than the originals.

"Think (alternatives for data structures and algorithms) before you code" should be Principle Zero.

[Fenwar]

Optimisation and scaling

At the end of the day an envelope calculation is all that's needed. If the time spent on optimisation is less than the total time saved by optimised code, do it. (This applies to development processes just as much as it does to the code itself.)

Even removing tiny delays (<100ms) from software can have bottom-line justification for optimisation - particularly in the area of interface responsiveness, which has a significant effect on a user's perception of software and thus on their overall productivity, (and the likelihood of repeat business, if you're selling it!)

Although I'm definitely often guilty of trying to shave a few more ms off a routine "just for the hell of it" as the article hints ;-)

[Rhys Parsons]

Optimization vs understanding technologies...

To add my own stories...

I once started work at a small company where the lead developer was a somewhat inexperienced Java developer. I went in at the same level (by title, rather than experience) and eventually replaced him. The code I inherited had many bizarre 'workarounds', such as synchrornizing on the application variable in JSPs.

In this application, reports produced XML output and used XSLT to display in the browser. The XML was built using concatenated String objects. I knew this was probably bad, but only did something about it when there was a complaint by a customer that the HTTP request timed out before a report was displayed. I wasn't sure there was much that could be done, thinking most of the time was probably taken up by processing the query rather than by concatenating the strings. But, I reasoned, since I'm looking at this code, I might as well convert all of the string concatenation into appending to a StringBuilder.

Having finished the task, the 30 minutes it took to process the report was reduced to 3 seconds.

In a similar vein, a colleague of mine once used DOM and XPath to parse an XML document and return the values he needed. It was dog slow, unacceptably so. A member of my team re-wrote it using a SAX parser and some POJOs. Performance was improved dramatically and became acceptable.

The moral is: you can't ignore peformance when writing code.Both of these situations were avoidable with a little bit of knowledge and some good advice. People need to understand how the way they solve a problem might impact performance. They need to understand the performance issues of the technology choices they make when they make them, not wait till there's a problem, then deal with it.

[Ed]

Lousy programming practices

The author suggests that optimisation will always make code harder to read. My two most common optimisations to make do not do this:

1. Remove completely useless, irrelevant code. This *really* should not be my most common optimisation. However, most of the time when I get a new program or applet which has performance problems, the issue is that there's a significant block of do-nothing code. I find this to be insane, but true. This optimisation always makes the code easier to read. It is either a sign that the original coder was not attempting to do the simplest thing that could work, or did not refactor after a major code modification.

2. Algorithm optimisations. Sometimes these result in less legible code, but not always. Over the last few years, the most common algorithm optimisations I've performed have been changing to using associative arrays instead of numerical, in instances where numerical arrays are not helpful.

For example, a recent applet maintained a sorted list of records which could potentially include over 10,000 elements. The language provided a sort mechanism for simple arrays, but it provided no way to provide a comparator, and so the author wrote his own max sort routine, and included code in the various update routines to maintain sorted order. The fact that the list was sorted was actually never used - the search through the list was a simple linear search, which did not abort on finding the result; it simply stored it, and continued looking (despite the fact that only one result could ever be found.)

I converted it to use associative arrays, which were provided by the language. That eliminated the 30 lines for the sort routine, and it eliminated the half dozen or so lines at every insertion or deletion operation to maintain sorted order. It also eliminated the 10 lines for the search routine. Finally, it eliminated all of the overhead associated with that code.

The kicker: the language in question doesn't actually support numerical arrays. Instead, it fakes them with associative arrays. As such, there was no increased cost per access of data, even if the list size was 1; instead, the cost was reduced, because instead of having to reference into the array element's record structure to get the key, to see if it was the element I wanted, I just check for the key I want.

I've seen many programmers waste a lot of time on optimisations. Generally, those programmers were doing it incorrectly anyway. For example, the programmer who spent hours optimising the options processing on a program, using a wall clock to time the entire program executions after each code change. For reference, the options processing took less than a tenth of a second at the start of each execution; the rest of the execution took at least 15 minutes - and the program would skip the rest of the processing if the last option was --help.

Note that the last person I saw doing that was inspired by a prior optimization that I had made in the same program: removing a routine at startup which sorted an array of data that was no longer referenced anywhere else in the program, using an algorithm which gave its worst performance when working on already sorted data.

[MrWeeble]

Optimising the right thing

In the example about the decompressor the programmer wrongly assumed that the problem was a slow-decompressor when the actual problem was that a decompressor needed to be used due to small storage space. Spending time and effort solving the wrong problem is always going to be a pointless task. If you always look at the big picture and understand where your system fits into the big scheme then you can fix the right problem first time and can weigh the benefits of scenario a to that of scenario b

[Mike]

Externalities

Joining a chorus, I'll point out that when using such a broad-brush term as "optimize", post-mature optimization (changing to an entirely different data structure two weeks before shipment because on real customer loads the project just doesn't freaking work at all) is at least as bad. Design, prototype, measure, lather, rinse, repeat. Waterfalls are for idiots in barrels.

Now, in particular (and relevant to the title), the reason optimization (and decent design) is still important in embedded systems is that the money for both software and hardware comes out of the same pocket. Often, for legal reasons or just customer expectations, so do support costs. The costs of bad coding are not pushed off to the customer, not "externalities". This can have a marvelous effect on code quality. (Unless, of course, your SVP was taken to a really nice resort by the salesdroids from a "turnkey development house", in which case both you and the shareholders are screwed... :-)

[Lou Gosselin]

AHH!

It's thinking like this that leads to software requiring hundreds of megabytes... Graphical wordprocessors and operating systems used to fit on floppies!

It is true that computers today are faster by over a magnitude, but honestly I can't see much net improvement. Today's beasts are noticeably much slower in startup time, and lag during just about any operation. I'm guessing this is because dozens of megabytes are being accessed every time I do anything. Opening and saving documents, is a real chore for my modern 3.2ghz cpu. Sometimes I type and find that the computer has to catch up with me.

Granted the software back then had many bugs, but it still does and today it is far more difficult to repair. I think I was more productive in the past when I could literally keep a clean backup (or run multiple instances) of windows by copying the files into a new directory. Today we have become accustomed to so many windows annoyances (WPA, registry, IE).

So, no I would have to disagree here about optimization, it clearly helps in some cases, even during design phase. I think this article should have focused on the "Keep It Simple, Stupid" rule, which should be adhered to during all phases.

[Bill Nicholls]

Author Responds

Thanks for all of the thoughtful feedback on Optimization - the right way, the wrong way and the highway. :-}

Optimization only where and when it is needed. That's the clear message you send.

Thanks,

BillN

[Geoffrey Summerhayes]

Must sell hardware on the side...

Anyone else notice that computers are bogging down faster than they used to? Going from V2.0 to V3.0 shouldn't require 10x as much memory for a program doing essentially the same task, but we see it all the time. Useful hardware lifetimes has decreased at our shop in spite of all the speed and size re-re-redoubling over the years, mainly because the applications have all turned into slow bloatware.

It's hard to avoid hearing things like, 'Space is no longer an issue.' Yes, it is, it's just not as much of a problem as it used to be. When we were working with 1-640k systems we didn't have to worry that much about sharing the space with 70+ other processes either.

Software support's default excuse has gone from 'blame MS' to 'blame your lack of new hardware'. When Moore's law finally crashes and burns, all the people who knew how to optimize will have left the industry and the learning process will have to start, with all the incumbent birthing pains, all over again.

It's annoying that so many people take Jackson (and Knuth) quotes as saying, 'Don't optimize.' The main thrust should be: Make it work correctly, and only then look for ways to improve speed and size.

But, actually look for them. I really don't want, in a few years, to boot a 50Tb system, get a message the my virtual memory paging file need to be increased, or told I need to buy more memory, all because I shouldn't be running a web browser and an e-mail program at the same time in such a tiny system.

Judging from the other comments, I'm preaching to the choir.

Mr. Nicholls, I'm supposed to be watching my sodium intake, but the grain I have to take this article with means no salt for the next couple of decades.

[Joe K]

Nonsense article

As proved by the responses, there will always be a place for optimisation. I get the feeling that the article meant "dont sit there all day looking at code to see how it can be better, get on with some proper work"

If we all did that we'd be out of a job ;-)

Anyway, theres nothing better than optimising/bugfixing that teaches you how to code properly, and avoid mistakes and bad habits that others have made. Its a valuable learning tool, and can be fun and immensely satisfying work.

To say we should give it up because computers are fast now is laughable advice from someone a little too stunned by todays CPU power.

[Richard Neill]

Not all optimisations are evil

Consider a few examples:

1)Should a PHP script use echo, or switch out of PHP and embed raw HTML?

* echo "<p>example</p>"

vs

* ?><p>example</p><?

2)Loop evaluation: conditionals inside/outside the loop

* for (i=0; i < 4*PI*r*r; i ++){ z++; }

vs

* a= 4*PI*r*r; for (i=0;i<a;i++) { z++; }

3)Using (or not using) indexes for your database.

Example (1) is utterly pointless. Don't even consider the question.

Example (2) is occasionally relevant, depending on how complex the test condition is, and how many times the loop interates. (the evaluation of a takes much longer than the increment of z).

Example (3). If you don't index your commonly-used fields in a database, your queries will really really crawl.

[Anonymous Coward]

Different goal today

I don't think the article means to imply that optimisation is a bad thing, just that it is not a goal in its own right.

You need to have your priorities straight though. In todays world, optimisation is about designing a solution that can be solved in parallel. Today, typical home PCs have 2 cores. In the not to distant future, it will be 10s, even 100s of cores. An application that is designed to allow parrallel execution will be much more scalable than one that doesn't.

Adam

[wayne]

Title

Our modern programming industry is an bit brain dead. I agree that only experts should do optimisations (and that we need to be more trained) and hardware tricks are undesirable (because they don't transfer over to new machines and hardware etc) but this illustrates the problems in the industry of sheer inefficient bloat and slow down. From the performance of PC software, it just doesn't seem to be highly optimised, but it would not surprise me if it just isn't being done well.

If the hardware, then firmware, then OS, then the design of the program was optimised in the first place, then the programming could be more easily optimised, and Vista and Office could maybe fit in 10MB (depending on graphic/sound/data file use etc) and run at least twice as fast. Instead we have slobbery design from deep down in your computer and up, adding layer on layer of inefficiency with much extra complication and code, which introduce many more errors. We have lost the plot, as far an realtime embedded design principles, which is an side line from the regular mega OS/application programming of the history of computers.

The alternative approach is simpler, specifically talented hand picked people to govern and design the basics of the computer, firmware and large sections of the OS, eventually transfered to machine code longterm (the design being good enough for long term use to justify this). This should vastly shrink the code size, and error rate, of these components, just with that. This means, that only an very small fraction of the programmer/engineering population is needed to achieve this (there is not many of those "100+" times better programmers available anyway). Middleware, development tools, authorware, and tradable code modules, to be done by expert programmers, and the dumb masses of application programmers to use these to make applications, and scripting/authorware for the rest. This resulting level of design optimisation should enable normal programmers to more quickly produce more efficient code.

Does it really matter, we struggle with our present systems after such short times as the industry strives to fill up the extra space. With optimisations we can fit more on our computers, and have them work faster, in everyday language that's still good. But optimisation is an "experts" game.

Wayne Morellini

(PS. Having just read some of the other posted comments, I am glad that others can see the sense in optimisation as well. The optimisation I talk about above, is an example of extreme practical optimisation, that come out of my exposure to the Forth language and Misc processor communities, among others).

[Anonymous Coward]

If you do optimise, do it right

Re. Richard Neill's second example

2)Loop evaluation: conditionals inside/outside the loop

* for (i=0; i < 4*PI*r*r; i ++){ z++; }

vs

* a= 4*PI*r*r; for (i=0;i<a;i++) { z++; }

It would be much better to do

z += 4*PI*r*r;

especially if r is large.

If the side-effect is important this might be written

i = 4*PI*r*r; z += i;

[Alan Donaly]

to sum up

This article is just plain wrong. I use

all the previous comments as evidence.

No faster systems do not mean you

don't have to optimise code you

have no idea where something

may eventually have to run or

what it may have to run with no

program runs alone no system

has infinite resources don't be

so silly.

[Matthew]

Optimisation vs Buggy software

I agree with the author. Don't optimise until the end, only allow experts to play, and put clear explanations around the reason.

Having said that, I think some people may be getting hung up on the word 'optimisation' and think it equates to any change that improves the responsiveness/performance of an application.

If someone implements the wrong algorithm to solve a problem, or invents a problem, putting it right isn't optimisation it's bug fixing.

Example of evil optimisation:

A car race timing system back in the darkest 80s was using an IBM-XT to display the results as the cars crossed the line. To avoid using a multiply the really, really smart guy wrote 15 lines of hand crafted assembly that was smacked into the middle of the C. That code wasn't touched for 10 years, until I came along as a grad, and asked 'What does that do?'.

Not one person working in the company knew, I spent 3 days 'un-optimising' the code, which opened the code up to the compilers optimiser, and thus fixed a accuracy problem we were having. The smart guy solved the right problem on the day, but forgot to tell anybody.

On the flip side:

Big error reporting system was sorting the displayed list (nice really fast binary search) list into time order every time a new entry was added, the fact that the list was already in time order, and that errors came in in time order seemed to have been missed by the developer. Removing the sort was not optimisation, it was bug fixing, the code was more maintainable, worked as specified, and had adequate performance.

For my mind 'optimisation' is the process of breaking code maintainability for the sake of performance.

Improving the performance, maintainability and efficiency of an application through fixing broken code and improving architecture is a very different beast.

[Anonymous Coward]

Wrong - computer time still costs

If your application runs for long enough, or on enough machines, or on sufficiently high-end hardware, then it is still orders of magnitude cheaper to spend money on programmer time to optimize code than to just buy faster hardware.

Too much current code runs too slowly.

Too much current code is too buggy.

Too many articles, like this one, take a simplistic view.

[Francis Fish]

Egad!

1. Run a profiler - it will tell you what's wrong. 99% of the time it isn't what you thought it was. 99% of the time it uncovers a bug! Nothing to do with optimisation.

2. The examples given in the above comments, particularly the invariant in the loop one, assume that the compiler is too stupid to optimise things out. Usually the people who wrote the compiler are much cleverer than you are. Sorry, but it's true. Adding another variable may make the code diffucult to understand, probably not in the contrived example though.

[Matthew Smith]

Number of users

This argument about programmer's time being more valuable than new hardware only works if you are talking about bespoke software. If you are writing a program to publish for a million users, then the economics shift in favour of optimising.

[Rob Crawford]

Errr

Three Days to un-optimise 15 lines of assembler Oh dear !

Sounds like thwe original guy was doing what had to be done to make it work in the first place.

Anyway way having been an obsessive optimiser in the 80s & 90s (I was the one who ended up fixing other peoples code for many Amiga & ST games). Often the 'original' author had used an inappropiate algorithm. Additionally the unrolling of loops, and using much more appropiate instructions for carrying out the task (yes it does matter) could make the difference between 50 frames per sec and less than 15 fps.

I pride myself that my code was very readable (almost always more readable than the original), and the source was commented as details given as to why code was replaced.

However for the most part those days are gone as compilers optimise code, and I have been replaced by the profiler.

Anyway heres an example of chosing the correct algorithm for the task, from a long time ago while I was playing with line drawing and clipping algorithms.

Find an machine with qbasic on it.

1: In qbasic write a version of Bresham's line drawing algorithm (in qbasic). Get that program to draw a selection of lines (use the native POINT command to set the individual pixels along the line)

2: In qbasic write a short program to draw the same selection of lines using the native LINE function

The qbasic version of Bresham averaged a 10 fold speed increase than using the native qbasic LINE algorithm.

If you do the same experiment but also implement your own clipping routine (still in qbasic) and make sure that your lines extend past the screen co-ords and the homebrew line draw is even faster.

Surely that makes you wonder about the functions contained with the .dll fules you link to ?

Sorry for being snotty at the start but assembler isn't a dirty word and theres too many modern programmers (especially the ones that can only handle Java) who don't actually understand whats really going on.

Anyway I'm off to modify my 100% asm Win32 super ping util (it's true you know) as I'm not involved in development anymore, so I have to rely on good old Masm32 as my "free" dev kit :(

[Anonymous Coward]

Title

Matthew

>For my mind 'optimisation' is the process of breaking code maintainability for the sake of performance.

>Improving the performance, maintainability and efficiency of an application through fixing broken code and improving architecture is a very different beast.

Optimisation, in the broader term, is any change that improves performance, and we should probably throw in some bug fixes too. But more accurately, Optimisation is writing it right (including efficiency and speed) and maintainability, as pointed out elsewhere, comes down to documentation. If you don't have to rewrite something, it makes it much more maintainable, and that comes down to design.

The code using an XT to display results, surely must have been more complex than passing data to the XT to display, otherwise it would have been much more productive to rewrite the code in three days then to decipher the assembler code.

I think what people are not understanding, is that optimisation starts in the design and ends in the last bit, and is tight, with an best fit, to real world problem, design strategy. We have had enough of squint until it looks alright, strategies as solutions to real-time computing.

Posted Monday 25th June 2007 05:49 GMT

> If your application runs for long enough, or on enough machines, or on sufficiently high-end hardware, then it is still orders of magnitude cheaper to spend money on programmer time to optimize code than to just buy faster hardware.

> Too much current code runs too slowly.

> Too much current code is too buggy.

> Too many articles, like this one, take a simplistic view.

Whoever you are, you are right, the deficit to humanity, in time and money, to save an few greedy developers, and dumb lazy programmers, some time or money, has been staggering. The down time of one user can outweigh the cost savings of not getting an program right. I should know, I own an certain free, non-opensource, browser, that gets too much positive press around these circles.

Egad!

By Francis Fish

>1. Run a profiler - it will tell you what's wrong. 99% of the time it isn't what you thought it was. 99% of the time it uncovers a bug! Nothing to do with optimisation.

>2. The examples given in the above comments, particularly the invariant in the loop one, assume that the compiler is too stupid to optimise things out. Usually the people who wrote the compiler are much cleverer than you are. Sorry, but it's true. Adding another variable may make the code difficult to understand, probably not in the contrived example though.

I wish it was so, compilers were using an smaller subset of functionality some time ago, and, in PC terms, Intel and MS improved on this, but I was reading an article last week showing how you still had to be careful of dumb compiler optimisations. Processor manufacturers even resorted to optimising for the subset of instructions used by the compilers. I have not written compiler optimisations, but from the complexity of optimising over the sheer number of instructions available, and human nature, I doubt many of these experts would do the job that thoroughly.

W

[Anonymous Coward]

Re: Optimizing the right thing

The example with the decompressor almost certainly involved a slow decompressor. In the 70s, there were several incredibly dramatic improvements made in compression/decompression algorithms. Today, it may not seem like decompression time could be that significant to may people - but that's because most of us are still using the algorithm improvements from the 70s. Before we had zip and gzip, there was compress - but that was also 70s tech. Before compress, there was compact. Compact was pretty darned slow, by comparison, and it didn't compress that well. But I think that may have also been 70s tech. Admittedly, if I remember the hardware specs of the time, I'm not sure the CDC3300 would have handled gzip very well, as it required a lot more memory than previous compressors (over 64k - not even my second computer had enough memory to run it.)

I believe there have been other algorithms used for quick compression/decompression of in-memory storage - but in the late 60s, they didn't have any of those.

On another note, while many compilers have used a subset of commands, many compilers still optimise at the low end better than 95% of hand optimisers - including a few of the ones that only use subsets of the commands. That having been said, many of the optimisations regarding pulling things out of loops that don't need to be there improve legibility, and are worth doing for that reason alone - it's a maintenance optimisation.

For example, once upon a time, I had a problem with an algorithm for calculating standard deviation - I was having math errors, and I found the more data I put in, the more significant the error. The algorithm that was being used was designed to not require the whole data set to be retained - and I needed to preserve that trait. It did not, however, look much like the formula I remembered from college math. I spent several hours expanding out the old infinite series version until I was able to properly simplify it - and it turned out to only need the sum, the sum of squares, and the count. I programmed in the new formula, and my math error went away. Then I tried to demostrate the error - but in the middle of my work, I'd gone home. So now I found I couldn't reproduce the error on my home computer. A bit more algebra work, and I found that I had actually just produced another version of basically the same algorithm - but the new version didn't depend on the previous answer, and the old version did. As such, the new version was much more resilient to errors in FMULT and FDIV, such as existed on the computer which had inspired my work.

The new version was about twice as fast - a linear improvement, and not worth a recode, because even in a program that used standard deviations a lot, it would only amount to at most a 1% overall improvement. However, everyone I showed it to was able to see, with the help of my comments, that it was, indeed, doing a standard deviation. Nobody I knew was able to follow the old algorithm, they just hoped it worked.

[Roddy MacKenzie]

Optimisation versus depessimisation

About a decade ago I had the grave misfortune of taking over a project that included a lot of hand coded inline hex embedded in a Turbo C comms module. This ran to about twenty pages of negatively documented (i.e. the documentation did not describe the code or what it was meant to do) diabolocal code.

I ran it through debug's dissassembler and rewrote the whole lot in plain old C. With compiler optimisation disabled, it ran at least 3 times faster in a third of the memory. With optimisation enabled, it ran 4 times faster in a third of the original memory or 3 times faster in 1/4 of the memory.

On another occasion I depessimised a utility that had been taking a matter of hours to run and made it complete in mere tens of seconds, and knocked 10% off its memory use.

Both piles of (smelly stuff) were written by PhD's

[Anonymous Coward]

I agree...

... with all the comments that indicate that people make non-optimal code nowadways by making complex solutions to complex problems. What happen to simple code that is easy to maintain... Optimization by refactoring the design needs to happen early and at every stage.

If you still have a performance problem due to 'speed of executtion'... well that is done at the end, and with your re-factored and simple implementaiton it should be easy to target the problematic areas.

Memory requirements should be specifed up front and as one person said, non-optimisation != non-design

[Anonymous Coward]

Title

> Both piles of (smelly stuff) were written by PhD's

;) We were talking about experts, instead.

> many compilers still optimise at the low end better than 95% of hand optimisers

Maybe 1% of people can optimise properly, without retraining. hence, why they should do all the low end and middle level stuff where most performance is had.

Glad to see that there are still people out there that recognise the benefits.

[Anonymous Coward]

Are you justifying your incompetence?

what do you prefer?

struct X1 {

char c1; // at offset 0, 1 byte

// bytes 1-3: 3 padding bytes

long l; // bytes 4-7: 4 bytes, aligned on 4-byte boundary

char c2; // byte 8: 1 byte

// bytes 9-11: 3 padding bytes (see narrative)

}; // sizeof(X1) == 12

or this version?

struct X2 {

long l; // bytes 0-3

char c1; // byte 4

char c2; // byte 5

// bytes 6-7: 2 padding bytes

}; // sizeof(X2) == 8