Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm talking about the way we write simple routines in order to improve performance without making your code harder to read... for instance, this is the typical for we learned:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

But, I usually do this when a foreach is not applicable:

for(int i = 0, j = collection.length(); i < j; i++ ){
   // stuff here
}

I think this is a better approach since it will call the length method once only... my girlfriend says it's cryptic though. Is there any other simple trick you use on your own developments?

share|improve this question
28  
+1 just for having a girlfriend who will tell you when your code isn't clear. –  Kristo Sep 26 '10 at 0:20
66  
You're just posting this to tell us you have a girlfriend. –  Josh K Sep 26 '10 at 0:33
9  
@Christian: Don't forget that there are compiler optimizations which might do this for you so you might only be affecting readability and not affecting performance at all; premature optimization is the root of all evil... Try to avoid more than one declaration or assignment on the same line, don't make people read it twice... You should use the normal way (your first example) or put the second declaration outside the for loop (although that also decreases readability as you would need to read back to see what the j means). –  Tom Wijsman Sep 26 '10 at 0:35
4  
@TomWij: The correct (and complete) quote: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." –  Robert Harvey Sep 26 '10 at 1:11
1  
@tomwij: If you are spending the three percent, then by definition you should be doing it in time-critical code, and not wasting your time on the other 97%. –  Robert Harvey Sep 26 '10 at 2:16
show 11 more comments

15 Answers

up vote 26 down vote accepted

insert premature-discussion-is-the-root-of-all-evil lecture

That said, here are some habits I've gotten into to avoid unnecessary efficiency, and in some cases, make my code simpler and more correct as well.

This isn't a discussion of general principles, but of some things to be aware of to avoid introducing unnecessary inefficiencies into code.

Know your big-O

This should probably be merged into the lengthy discussion above. It's pretty much common sense that a loop inside of a loop, where the inner loop repeats a calculation, is gonna be slower. For example:

for (i = 0; i < strlen(str); i++) {
    ...
}

This will take a horrendous amount of time if the string is really long, because the length is being recalculated on every iteration of the loop. Note that GCC actually optimizes this case because strlen() is marked as a pure function.

When sorting a million 32-bit integers, bubble sort would be the wrong way to go. In general, sorting can be done in O(n * log n) time (or better, in the case of radix sort), so unless you know your data is going to be small, look for an algorithm that's at least O(n * log n).

Likewise, when dealing with databases, be aware of indexes. If you SELECT * FROM people WHERE age = 20, and you don't have an index on people(age), it'll require an O(n) sequential scan rather than a much faster O(log n) index scan.

Integer arithmetic hierarchy

When programming in C, bear in mind that some arithmetic operations are more expensive than others. For integers, the hierarchy goes something like this (least expensive first):

  • + - ~ & | ^
  • << >>
  • *
  • /

Granted, the compiler will usually optimize things like n / 2 to n >> 1 automatically if you're targeting a mainstream computer, but if you're targeting an embedded device, you might not get that luxury.

Also, % 2 and & 1 have different semantics. Division and modulus usually rounds toward zero, but it's implementation defined. Good ol' >> and & always rounds toward negative infinity, which (in my opinion) makes a lot more sense. For instance, on my computer:

printf("%d\n", -1 % 2); // -1 (maybe)
printf("%d\n", -1 & 1); // 1

Hence, use what makes sense. Don't think you're being a good boy by using % 2 when you were originally going to write & 1.

Expensive floating point operations

Avoid heavy floating point operations like pow() and log() in code that doesn't really need them, especially when dealing with integers. Take, for example, reading a number:

int parseInt(const char *str)
{
    const char *p;
    int         digits;
    int         number;
    int         position;

    // Count the number of digits
    for (p = str; isdigit(*p); p++)
        {}
    digits = p - str;

    // Sum the digits, multiplying them by their respective power of 10.
    number = 0;
    position = digits - 1;
    for (p = str; isdigit(*p); p++, position--)
        number += (*p - '0') * pow(10, position);

    return number;
}

Not only is this use of pow() (and the int<->double conversions needed to use it) rather expensive, but it creates an opportunity for precision loss (incidentally, the code above doesn't have precision issues). That's why I wince when I see this type of function used in a non-mathematical context.

Also, notice how the "clever" algorithm below, which multiplies by 10 on each iteration, is actually more concise than the code above:

int parseInt(const char *str)
{
    const char *p;
    int         number;

    number = 0;
    for (p = str; isdigit(*p); p++) {
        number *= 10;
        number += *p - '0';
    }

    return number;
}
share|improve this answer
    
Very thorough answer. –  Paddyslacker Sep 26 '10 at 22:38
    
Note, the premature optimization discussion does not apply for garbage code. You should always use an implementation working well in the first place. –  user1249 Nov 1 '10 at 9:22
    
Note that GCC actually optimizes this case because strlen() is marked as a pure function. I think you mean that it is a const function, not pure. –  Andy Lester Nov 1 '10 at 16:58
    
@Andy Lester: Actually, I did mean pure. In the GCC documentation, it states that const is slightly stricter than pure in that a const function cannot read global memory. strlen() examines the string pointed to by its pointer argument, meaning it can't be const. Also, strlen() is indeed marked as pure in glibc's string.h –  Joey Adams Nov 2 '10 at 1:37
    
You're right, my mistake, and I should have double-checked. I've been working on the Parrot project annotating functions as either pure or const and even documented it in the header file because of the subtle difference between the two. docs.parrot.org/parrot/1.3.0/html/docs/dev/c_functions.pod.html –  Andy Lester Nov 2 '10 at 4:36
show 1 more comment

From your question and the comment thread, it sounds like you "think" that this code change improves performance, but you don't really know whether it does or not.

I'm a fan of Kent Beck's philosophy:

"Make it work, make it right, make it fast."

My technique to improve code performance, is first get the code passing the unit tests and well factored and then (particularly for looping operations) write a unit test that checks performance and then refactor the code or think of a different algorithm if the one I've chosen isn't working as expected.

For example, to test speed with .NET code I use NUnit's Timeout attribute to write assertions that a call to a particular method will execute within a certain amount of time.

Using something like NUnit's timeout attribute with the code example you gave (and a large number of iterations for the loop), you could actually prove whether or not your "improvement" to the code really did help with the perfomance of that loop.

One disclaimer: While this is effective at the "micro" level, it is certainly not the only way to test performance and doesn't take into account issues that might arise at the "macro" level - but it's a good start.

share|improve this answer
2  
While I am a big believer in profiling, I also believe it is smart to keep the kinds of tips Cristian is looking for in mind. I will always choose the faster of two equally readable methods. Being forced into post-mature optimization is no fun. –  AShelly Sep 26 '10 at 0:05
    
There is not necessarily need for unit tests, but it is always worthwhile to spend this 20 minutes to check if some performance myth is true or not, especially because answer often depends on compiler and state of -O and -g flag (or Debug/Release in case of VS). –  mbq Sep 26 '10 at 0:33
    
+1 This answer supplements my related comment to the question itself. –  Tom Wijsman Sep 26 '10 at 0:39
1  
@AShelly: if we're talking about simple reformulations of loop syntax, changing it after the fact is very easy to do. Also, what you find equally readable might not be so for other programmers. Best to use "standard" syntax as much as possible, and only vary it when proven necessary. –  Joeri Sebrechts Sep 26 '10 at 13:21
    
@AShelly surely if you can think of two equally readable methods and you choose the less efficient one you're just not doing your job? Would anyone actually do that? –  glenatron Nov 1 '10 at 10:03
show 1 more comment

Bear in mind that your compiler may well turn:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

into:

int j = collection.length();
for(int i = 0; i < j; i++ ){
   // stuff here
}

or something similar, if collection is unchanged over the loop.

If this code is in a time critical section of your application it would be worth finding out whether this is the case or not - or indeed whether you can change the compiler options to do this.

This will maintain the readability of the code (as the former is what most people will expect to see), while gaining you those few extra machine cycles. You are then free to concentrate on the other areas where the compiler can't help you.

On a side note: if you change collection inside the loop by adding or removing elements (yes, I know it's a bad idea, but it does happen) then your second example either won't loop over all the elements or will try to access past the end of the array.

share|improve this answer
1  
Why not just do it explicitly? –  user1249 Nov 1 '10 at 9:22
2  
In some languages that bounds-check, you will SLOW your code if you do it explicitly. With a loop to collection.length the compiler moves it out for you and omits the bounds check. With a loop to some constant from elsewhere in your app you'll have a bounds check on every iteration. That's why it's important to measure - intuition about performance is almost never right. –  Kate Gregory Nov 1 '10 at 11:12
1  
Which is why I said "it would be worth finding out". –  ChrisF Nov 1 '10 at 11:18
    
How can the C# compiler know that collection.length() doesn't modify collection, in the way that stack.pop() does? I think it would be best to check the IL rather than assume the compiler optimises this. In C++, you can mark a method as const ('does not change the object'), so the compiler can make this optimisation safely. –  JBRWilkinson Nov 1 '10 at 12:32
    
@JBRW Optimizers that do this are also aware of the ok-let's-call-it-constness-even-though-this-isn't-C++ of methods of the collections. After all you can only bounds-check if you can notice that something is a collection and know how to get its length. –  Kate Gregory Nov 4 '10 at 16:49
add comment

This kind of optimization is usually not recommended. That piece of optimization can easily be done by compiler, you are working with a higher level programming language instead of assembly, so think in the same level.

share|improve this answer
1  
Give her a book about programming ;) –  Joeri Sebrechts Sep 26 '10 at 13:22
1  
+1, as most of our girlfriends are likely more interested in Lady Gaga than code clarity. –  haploid Sep 26 '10 at 22:05
    
Could you explain why it's not recommended? –  Macneil Oct 30 '10 at 17:49
    
@macneil well... that trick makes codes not that common and totally doesn't work, that piece of optimization is supposed to be done by compiler. –  tactoth Oct 31 '10 at 8:38
    
@macneil if you are working in a higher level language, think in the same level. –  tactoth Oct 31 '10 at 8:39
show 2 more comments

This may not apply so much for general purpose coding, but I do mostly embedded development these days. We have a specific target processor (which is not going to get faster - it will seem quaintly obsolete by the time they retire the system in 20+ years), and very restrictive timing deadlines for much of the code. The processor, like all processors, has certain quirks regarding which operations are fast or slow.

We have a technique used to ensure we are generating the most efficient code, while maintaining readibility for the whole team. In those places where the most natural language construct does not generate the most efficient code, we have created a macros that do ensure the optimal code is used. If we do a follow-on project for a different processor, we can update the macros for the optimal method on that processor.

As a specific example, for our current processor, branches empty the pipeline, stalling the processor for 8 cycles. The compiler takes this code:

 bool isReady = (value > TriggerLevel);

and turns it into the assembly equivalent of

isReady = 0
if (value > TriggerLevel)
{
  isReady = 1;
}

This will either take 3 cycles, or 10 if it jumps over isReady=1;. But the processor has a single-cycle max instruction, so it is much better to write code to generate this sequence which is guaranteed to always take 3 cycles:

diff = value-TriggerLevel;
diff = max(diff, 0);
isReady = min(1,diff);

Obviously, the intent here is less clear than the original. So we have created a macro, which we use whenever we want a boolean Greater-Than comparison:

#define BOOL_GT(a,b) min(max((a)-(b),0),1)

//isReady = value > TriggerLevel;
isReady = BOOL_GT(value, TriggerLevel);

We can do similar things for other comparisons. To an outsider, the code is a bit less readable than if we only used the natural construct. However it quickly becomes clear after spending a little time working with the code, and it is much better than letting every programmer experiment with their own optimization techniques.

share|improve this answer
add comment

Well, the first advice would be to avoid such premature optimisations until you know exactly what's happening to the code, so that you are sure that you are actually making it faster, and not slower.

In C# for example the compiler will optimise the code if you are looping the length of an array, as it knows that it doesn't have to range check the index when you access the array. If you try to optimise it by putting the array length in a variable, you will break the connection between the loop and the array, and actually make the code a lot slower.

If you are going to micro-optimise, you should limit yourself to things that are known to use a lot of resources. If there is just a slight performance gain, you should go with the most readable and maintainable code instead. How computer work change over time, so something that you find out is slightly faster now, may not stay that way.

share|improve this answer
add comment

I have a very simple technique.

  1. I make my code work.
  2. I test it for speed.
  3. If it's fast, I go back to step 1 for some other feature. If it's slow, I profile it to find the bottleneck.
  4. I fix the bottleneck. Go back to step 1.

There are plenty of times where it saves time to circumvent this process, but in general you'll know if that's the case. If there's doubt, I stick to this by default.

share|improve this answer
add comment

Wait six months, get your boss to buy everyone new computers. Seriously. Programmer time is way more expensive than hardware in the long run. High performance computers allow coders to write code in a straightforward manner without being as concerned about speed.

share|improve this answer
5  
Er...What about the performance your customers see? Are you wealthy enough to buy new computers for them also? –  Robert Harvey Sep 26 '10 at 0:27
2  
And we have almost hit the performance wall; multicore computation is the only way out, but waiting won't make your programs use it. –  mbq Sep 26 '10 at 0:30
    
+1 This answer supplements my related comment to the question itself. –  Tom Wijsman Sep 26 '10 at 0:38
2  
No programming time is not more expensive than hardware when you have thousands or milllion of users. Programmer time is NOT more important than user time, get this through your head as soon as possible. –  HLGEM Oct 4 '10 at 14:02
1  
Get into good habits, then it doesn't take any programmer time as it is what you do all the time. –  DominicMcDonnell Nov 1 '10 at 10:51
show 1 more comment

Try not to optimize too much ahead of time, then when you do optimize worry a bit less about readability.

There little I hate more than unnecessary complexity, but when you hit a complex situation a complex solution is often required.

If you write the code the most obvious way then make a comment explaining why it has been altered when you make the complex change.

Specifically to your meaning though, I find that a lot of times doing the Boolean opposite of the default approach sometimes helps:

for(int i = 0, j = collection.length(); i < j; i++ ){
// stuff here
}

can become

for(int i = collection.length(); i > 0; i-=1 ){
// stuff here
}

In many languages as long as you make appropriate adjustments to the "stuff" part and it is still readable. It just doesn't approach the problem the way most people would think of doing it first because it counts backwards.

in c#for example:

        string[] collection = {"a","b"};

        string result = "";

        for (int i = 0, j = collection.Count() - 1; i < j; i++)
        {
            result += collection[i] + "~";
        }

could also be written as:

        for (int i = collection.Count() - 1; i > 0; i -= 1)
        {
            result = collection[i] + "~" + result;
        }

(and yes, you should o that with a join or a stringbuilder, but I am trying to make a simple example)

There are many other tricks one can use that are not difficult to follow but many of them do not apply across all languages like using mid on the left side of an assignment in old vb to avoid the string reassignment penalty or reading text files in binary mode in .net to get past the buffering penalty when the file is too big for a readtoend.

The only other really generic case I can think of that would apply everywhere would be to apply some Boolean algebra to complex conditionals to try to transform the equation to something that stands a better chance of taking advantage of a short-circuiting conditional or turn a complex set of nested if-then or case statements into an equation entirely. Neither of these work in all cases, but they can be significant time savers.

share|improve this answer
    
it's a solution, but the compiler will likely spit out warnings as for most common classes length() returns an unsigned type –  stijn Sep 26 '10 at 8:10
    
But by reversing the index, the iteration itself could become more complex. –  Tom Wijsman Sep 26 '10 at 11:21
    
@stijn I was thinking of c# when I wrote it, but perhaps this suggestion also falls in the language specific category for that reason - see edit... @ToWij certainly, I don't think there are many if any suggestions of this nature that do not run the risk of that. If your //stuff was some kind of stack manipulation it may not even be possible to reverse the logic correctly, but in many cases it is and is not too confusing if done carefully in most of those cases IMHO. –  Bill Sep 26 '10 at 16:12
    
you're right; in C++ I'd still prefer the 'normal' loop but with the length() call taken out of the iteration (as in const size_t len = collection.length(); for(size_t i=0;i<len;++i ){} ) for two reasons: I find the 'normal' forward counting loop to be more readable/understandable (but that's probably just because it's more common), and it takes the loop invariant length() call out of the loop. –  stijn Sep 26 '10 at 16:31
add comment

Take advantage of short-circuiting:

if(someVar || SomeMethod())

takes just as long to code, and is just as readable as:

if(someMethod() || someVar)

yet it's going to evaluate more quickly over time.

share|improve this answer
add comment

Well there are alot of performance changes you can make when accessing data that will have a huge impact on your application. If you write queries or use an ORM to access a databse, then you need to read some performance tuning books for the database backend you use. Chances are you are using known poorly performing techinques. There is no reason to do this except ignorance. This is not premature optimization (I curse the guy who said this because it has been so widely interpeted as never worry about performance), this is good design.

Just a quick sample of performance enhancers for SQL Server: Use appropriate indexes, avoid cursors - use set-based logic, use sargable where clauses, don't pile views on top of views, don't return more data than you need or more columns than you need, don't use correlated subqueries.

share|improve this answer
add comment

If this is C++, you should get in the habit of ++i rather than i++. ++i will never be worse, it means exactly the same as a stand-alone statement, and in some cases it could be a performance improvement.

It's not worth changing existing code on the off-chance that it will help, but it's a good habit to get into.

share|improve this answer
add comment

I've got a little different take on it. Just simply following advice you get here isn't going to make much difference, because there are some mistakes you need to make, which you then need to fix, which you then need to learn from.

The mistake you need to make is to design your data structure in the way everyone does. That is, with redundant data and many layers of abstraction, with properties and notifications that propagate throughout the structure trying to keep it consistent.

Then you need to do performance tuning (profiling) and have it show you how, in many ways, what is costing you oodles of cycles is the many layers of abstraction, with properties and notifications that propagate throughout the structure trying to keep it consistent.

You may be able to fix these problems somewhat without major changes to the code.

Then if you are lucky you can learn that less data structure is better, and that it is better to be able to tolerate temporary inconsistency than to try to keep many things tightly in agreement with waves of messages.

How you write loops has really nothing to do with it.

share|improve this answer
add comment
  1. Profile. Do we even have a problem? Where?
  2. In 90% cases where it's somehow IO related, apply caching (and maybe get more memory)
  3. If it's CPU related, apply caching
  4. If performance is still a problem, we have left the realm of simple techniques -- do the math.
share|improve this answer
add comment

Use the best tools you can find - good compiler, good profiler, good libraries. Get the algorithms right, or better still - use the right library to do it for you. The trivial loop optimizations are small potatoes, plus you are not as smart as the optimizing compiler.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.