Optimization questions

[Nawabzada]

Hi

At an "Advanced Systems Programming in C" course I attended recently, we
covered some optimization techniques. There were two I haven't been able
to find referenced in any books...

1) In loops, it's better to count down from n to 0 (instead of from 0 to
n), because a test for 0 is more efficient than comparing 2 variables

2) Also, preincrements ++i are usually quicker than postincrements i++.

I guess I have two questions: Are these right? And if so, why isn't there
more code around that uses them?

//n

 

[James Kuyper]

Hi

At an "Advanced Systems Programming in C" course I attended recently, we
covered some optimization techniques. There were two I haven't been able
to find referenced in any books...

1) In loops, it's better to count down from n to 0 (instead of from 0 to
n), because a test for 0 is more efficient than comparing 2 variables

That sounds plausible, and might be true on most systems, possibly all
of them. However, comparisons like that tend to be system dependent. I
wouldn't recommend worrying too much about such issues unless you're
writing code that is, as the result of a carefully considered deliberate
decision, not intended to be portable to other systems.

2) Also, preincrements ++i are usually quicker than postincrements i++.

If your code makes use of the results of the expression, you generally
don't have a choice; you have to use whichever expression produces the
result you need to use.

If your code doesn't maek any use of the result, any decent compiler
should produce equivalent code for i++, ++i, i+=1, or i=i+1. If it
doesn't, and the difference is important enough to matter, I recommend
getting a better compiler, not re-writing your code.

I guess I have two questions: Are these right? And if so, why isn't there
more code around that uses them?

Looping backwards is counter-intuitive in most contexts (even the ones
where it's required, much less the ones where it's merely more efficient).

 

[Flash Gordon]

Hi

At an "Advanced Systems Programming in C" course I attended recently, we
covered some optimization techniques. There were two I haven't been able
to find referenced in any books...

1) In loops, it's better to count down from n to 0 (instead of from 0 to
n), because a test for 0 is more efficient than comparing 2 variables

On some processors yes, on others no. in either case, you would have to
be doing very little else in the loop for it to matter.

2) Also, preincrements ++i are usually quicker than postincrements i++.

In C, in the situations where either would be correct code, there is
unlikely to be any difference. The compiler is likely to generate the
same code in either case. In situations where it makes a difference you
need what is correct!

I guess I have two questions: Are these right? And if so, why isn't there
more code around that uses them?

There isn't more code using them because it is incredibly out-dated advice.

 

[Phil Carmody]

That's wrong.

A loop which only increments or decrements
and unsigned variable
and tests the value of that variable
against zero as the loop conditition:
will always terminate.

That depends if equality is a loop-terminating condition or not.
I'd say that ``if(u<0)'', ``if(u<=0)'' and ``if(u==0)'' all
qualify as 'testing the value against zero'. (I.e. unadorned
'testing' in the context of values would be a trichotomy rather
than just a dichotomy.)

Phil

 

[scott]

Hi

At an "Advanced Systems Programming in C" course I attended recently, we
covered some optimization techniques. There were two I haven't been able
to find referenced in any books...

1) In loops, it's better to count down from n to 0 (instead of from 0 to
n), because a test for 0 is more efficient than comparing 2 variables

2) Also, preincrements ++i are usually quicker than postincrements i++.

I guess I have two questions: Are these right? And if so, why isn't there
more code around that uses them?

//n

Unless the class you are attending is based on your exact tool chain
and processor any advice given regarding optimization should probably
just be ignored. I would actually question anything else taught by an
instructor who does not realize this and make it clear in the class.
the bottom line is don't optimize unless you determine your system
does not meet some sort of performance requirement and then do so only
after performing many measurements to determine what optimizations are
going to actually provide the most bang for the buck. This is not to
say that you should just do dumb things up front that are going to
obviously make things slower but both of the cases you cite are rather
obscure and may or may not speed thin gs up and in fact may slow
things down.

 

[Chris Dollin]

2) Also, preincrements ++i are usually quicker than postincrements i++.

If the increment is for effect, not for value, then there will [should]
be no difference.

If the increment is for value as well as effect, then the values are
/different/, and the /right one/ should be chosen. Picking the faster
one (even assuming there /is/ a faster one) and having the code be wrong
may lead to an unfortunate, perhaps terminal, situation.

--
"I know it was late, but Mountjoy never bothers, /Archer's Goon/
so long as it's the full two thousand words."

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

 

[Walter Banks]

The following two statments, do two different things

Yes they do but they demonstrate the code generation
differences between pre and post inc/dec sequences for
processors that don't have inc/dec var instructions on
syntactically similar sequences. This is the origin of the

2) Also, preincrements ++i are usually quicker than
postincrements i++.

Regards,

 

[Stephen Sprunk]

At an "Advanced Systems Programming in C" course I attended recently, we
covered some optimization techniques. There were two I haven't been able
to find referenced in any books...

1) In loops, it's better to count down from n to 0 (instead of from 0 to
n), because a test for 0 is more efficient than comparing 2 variables

2) Also, preincrements ++i are usually quicker than postincrements i++.

I guess I have two questions: Are these right?

They were a long, long time ago. In cases where the two would be
equally correct, a modern compiler will generate identical output.

If you modify "n" in the loop, or you use the result of "i++", the
transformation cannot be applied and the resulting output may differ, as
it should.

And if so, why isn't there more code around that uses them?

These tricks aren't used much (any more) because:

a) they're unnecessary with modern optimizing compilers

b) the primary audience for code is other programmers, not the compiler,
so you should write code that best explains your program's logic --
unless actual performance tests show that it doesn't run fast enough for
your needs _and_ something else does.

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

S

 

[user923005]

Hi

At an "Advanced Systems Programming in C" course I attended recently, we
covered some optimization techniques. There were two I haven't been able
to find referenced in any books...

1) In loops, it's better to count down from n to 0 (instead of from 0 to
n), because a test for 0 is more efficient than comparing 2 variables

This sort of optimization is silly. It's not even worth trying unless
something is failing to meet performance specifications and all other
efforts have failed.

2) Also, preincrements ++i are usually quicker than postincrements i++.

This is true for C++ classes in general, but any value for C is highly
dubious.

I guess I have two questions: Are these right? And if so, why isn't there
more code around that uses them?

These sorts of tweaky little things are the wrong sorts of things to
try to speed up slow code. The most important thing to try is to find
a better algorithm. People who code with the above as assumptions are
making unwarranted assumptions. The code may be faster or slower or
unchanged in speed. The most important thing in writing code in any
language is to write code that is clear as possible. Using little
chummy hacks because you think that they might be faster is a bad
idea. It may be that it is faster when you first test and write the
code. But three years later because of compiler and CPU upgrades it
is now much slower than the alternative.

Most micro-optimizations are things that are better performed by the
compiler (see http://en.wikipedia.org/wiki/Compiler_optimization).

First of all, you should *never* perform micro-optimization unless the
code fails to meet performance specifications. If (and only if)
performance specifications are not met, then we must profile the
project. If (and only if) a particular routine is demonstrated to be
a bottleneck we can consider optimizations to that routine. Once we
have identified our bottleneck then we should try to find a better
algorithm to perform the same job.

If you want efficient code, then an algorithm upgrade is the correct
solution. If there are no superior algorithms, then it is time to
look for other ways to improve the code.

 

[Walter Banks]

These do not do the same thing.

No they don't do the same thing. They illustrate syntactically similar
code to show why pre or post inc/dec made a difference.

If one instruction makes the difference between having to upgrade
to a faster processor or not, you really should be coding this in
hand-coded assembly language. If hand-coded assembly language is too
expensive, maybe you should re-think upgrading to a faster processor.
It the specs are that tight now, will it be able to perform after
a couple of bug fixes that might each add an instruction?

This is generally not the point for embedded system applications. Compiled
code for embedded systems will be as tight as hand coded assembly. There
have been tons of threads where this has been debated at length. We
can demonstrate that any application code written in assembler with any
processor we support can be written in C in the same or less ROM, RAM
and timing.

The issue isn't to use a faster processor to get enough cycles to perform
the application but top use the same processor slower to reduce power
consumption and EMI. I have first hand details on two cell phone
examples where battery life was extended by about half simply by
using a different compiler.

Several of the embedded systems compilers including one we did
optimize for power consumption. In this type of optimization var reads
and writes are expensive and avoided whenever possible.

If by that you mean you're simply going to make lots and lots of copies
of the embedded system, I don't see how that's relevant. If by that you
mean that little inefficiencies in a single system add up, they do, and
perhaps at this point you need to upgrade to faster hardware or hand-code
the whole thing in assembly language.

The little inefficiencies add up requiring more power and more expensive
silicon. One of our customers a few months ago did a 100,000 piece
pre production run. An increase of a few cents adds up.

There is a second reason why this is a factor and that is any savings
realized by a compiler pays back over the whole product. Compile times
for embedded systems are not as important as code that is only going
to be executed a few times where compile times represent a significant
overhead in executing the application code.

Regards,

 

[jameskuyper]

No they don't do the same thing. They illustrate syntactically similar
code to show why pre or post inc/dec made a difference.

The point is, the question was about whether i++ or ++i was faster; a
question that is worth asking only in cases where you could reasonably
substitute i++ for ++i (or vice versa). This is not such a case.

 

[jfbode1029]

Hi

At an "Advanced Systems Programming in C" course I attended recently, we
covered some optimization techniques. There were two I haven't been able
to find referenced in any books...

1) In loops, it's better to count down from n to 0 (instead of from 0 to
n), because a test for 0 is more efficient than comparing 2 variables

2) Also, preincrements ++i are usually quicker than postincrements i++.

I guess I have two questions: Are these right?

For specific architectures or instruction sets, yes. In general,
probably not.

And if so, why isn't there more code around that uses them?

Because optimization at this level should only be done after you've
picked the right algorithm and data structure for the problem at hand,
profiled to the code to find the actual bottlenecks, and eliminated
any unnecessary/redundant code. The kind of optimization described
above should only be done if you're not meeting a hard performance
requirement *and* you've already tweaked everything else at the higher
levels.

 

[Guest]

Gordon Burditt wrote:


No they don't do the same thing. They illustrate syntactically similar
code to show why pre or post inc/dec made a difference.


This is generally not the point for embedded system applications. Compiled
code for embedded systems will be as tight as hand coded assembly.

So why do you need to do these optimisations? Can't the compiler
spot that
for (i = 0; i < MAX; i++)
is the same as
for (i = 0; i < MAX; ++i)
?

<snip>

 

[Walter Banks]

Tor Rustad said:



'I hope you've gotten a sense from this chapter that optimization
isn't about "code tweaks" at all. Instead it's about choosing
efficient algorithms based on O-notation, implementing those
algorithms correctly, and then using profilers to evaluate your
program for hotspots where some micro-optimizations would be
appropriate, while respecting other programming goals like
readability and portability throughout the process." - Mikey Lee,
in Ch3 of "C Unleashed".

Context is all. Mikey would have been remiss not to have *mentioned*
loop inversion, but he is right to stress algorithm choice as the
principal optimisation technique.

Efficient code starts with good software design. Algorithm choice
regularly beats all other optimizations.

C compilers are implementation tools that turn programmers code
into machine code. Compilers are good at accounting, programmers
are not. (Ram and Rom allocation and instruction selection and
symbol table management)

The best compiler optimization will not turn a bubble sort
into a quick sort but it will make the bubble sort as
efficient as possible.

Regards,