Optmization

[shibu]

Hi All,

I would like to optimize my C code for both performance and size.
While searching the groups for useful links on optimization, I found a
link named " Mike Lee's optimization page". But this link is broken
now. Anybody knows the new link for this site. Also any other good
optimization links.

Thanks in advance
Shibu

 

[Kevin Goodsell]

Hi All,

I would like to optimize my C code for both performance and size.
While searching the groups for useful links on optimization, I found a
link named " Mike Lee's optimization page". But this link is broken
now. Anybody knows the new link for this site. Also any other good
optimization links.

Thanks in advance
Shibu

The best optimizations are always algorithm-level improvements. Your
next best bet would probably be to use a good optimizing compiler.
Attempting to micro-tune your C code is unlikely to give good results.

-Kevin

 

[Richard Heathfield]

Hi All,

I would like to optimize my C code for both performance and size.

I would like to build the FASTEST, STRONGEST battle tank in the world. But
the more defensive armour I give it, the slower it will be. Never mind!
I'll use a bigger engine! But that engine will need protecting, so I'll
need more armour. That's gonna affect the speed. Ah! I know! A bigger
engine! (And so it goes.)

You can't optimise for performance AND size. You can trade one off against
the other, though - sometimes.

While searching the groups for useful links on optimization, I found a
link named " Mike Lee's optimization page". But this link is broken
now. Anybody knows the new link for this site. Also any other good
optimization links.

(You may need to mend this link)

http://hpcnc.cpe.ku.ac.th/documentations/optimizationC/www.ontek.com/mikey/optimization.html

I doubt very much whether this is an authorised copy of Mikey's page, but
it's the first Google hit I found. If I had an authorised link, I'd supply
it. Mikey used to be a regular here, but we haven't seen him around for
some time.

 

[pete]

You can't optimise for performance AND size.
You can trade one off against the other, though - sometimes.

It depends on the original state of the code.
There's no reason why code can't exist in a state
where it's both bigger and slower than it needs to be.
Code such as that, *can* be optimised for performance AND size.

 

[William Hughes]

I would like to build the FASTEST, STRONGEST battle tank in the world. But
the more defensive armour I give it, the slower it will be. Never mind!
I'll use a bigger engine! But that engine will need protecting, so I'll
need more armour. That's gonna affect the speed. Ah! I know! A bigger
engine! (And so it goes.)

You can't optimise for performance AND size. You can trade one off against
the other, though - sometimes.

And then I decided to make my tank out of steel rather than cast iron and
it became both stronger and faster. Sometimes you can improve
both performance AND size. In optimization, as in so many other
things in life, all generalizations are false. On the other hand [1]
speed/size tradeoffs are very common in optimization.

- William Hughes

[1] Was it Truman who wanted a one handed economist so he wouldn't have
to keep hearing "on the other hand"?

 

[Thomas Matthews]

Hi All,

I would like to optimize my C code for both performance and size.
While searching the groups for useful links on optimization, I found a
link named " Mike Lee's optimization page". But this link is broken
now. Anybody knows the new link for this site. Also any other good
optimization links.

Thanks in advance
Shibu

Here are some links:
http://www.azillionmonkeys.com/qed/optimize.html
http://www.refactoring.com/


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Malcolm]

I would like to build the FASTEST, STRONGEST battle tank in the
world. But the more defensive armour I give it, the slower it will be.
Never mind!

Optimising the executable code size is a bit like trying to get a cheaper
brand of paint for your tank's camouflage - unless it really is a
bargain-basement tank it won't make any difference.

A lot of algorithms trade off memory use versus speed, however. A typical
example is a hash table, which is usually about half empty to allow fast
access.

Usually memory and speed are not symmetrical. Either you have enough memory,
and the program will run perfectly, or you run out and it won't run at all.
With speed, most operations don't matter either because they are below the
just-noticeable response time for the user, or because they are very fast in
comparison to some other function which is taking a long time. You need to
know what your program is doing before you decide where to apply
optimisation effort.

Another common trade-off is good design, portability, and programmer time
versus efficiency. By choosing to code in C you have sacrificed some speed
for portability / ease of programming.

 

[E. Robert Tisdale]

I would like to optimize my C code for both performance and size.
While searching the groups for useful links on optimization,
I found a link named " Mike Lee's optimization page".
But this link is broken now. Anybody knows the new link for this site.
Also any other good optimization links.

I used Google

http://www.google.com/

to search for

+"premature optimization"

and I found lots of stuff.

Don't modify your source code
to enhance performance or reduce code size.
Learn how to use your compiler's optimization options
and, if that isn't sufficient, shop around
for a better optimizing compiler.
Use your compiler's profiling options
to help you locate and analyze performance problems.
A good optimizing compiler can use the profiling results
to compile faster, more efficient code.
If the profiling results locate a problem
in a particular function, you might consider better algorithms.
Try to make your code simpler
only if it makes it easier to read and understand.
Don't try to "outwit" your compiler.
You will only frustrate the optimizer
and your code will probably run even slower
when you attempt to port it to another target platform.
If you inline lightweight functions
your compiler may be able to take advantage of optimizations
that would not be options otherwise.
Generally, fast code is fatter than slow code
because the optimizing compiler will
inline lightweight functions, unroll loops, etc.
Minimizing code size eventually degrades performance.

 

[Richard Heathfield]

It depends on the original state of the code.
There's no reason why code can't exist in a state
where it's both bigger and slower than it needs to be.
Code such as that, *can* be optimised for performance AND size.

Granted. But, after a certain point, you have to choose, because you can't
have both.

 

[Ben Pfaff]

Granted. But, after a certain point, you have to choose, because you can't
have both.

It depends. In this era of heavy caching, the smaller code can
be faster. There are other circumstances where smaller code is
faster too; for example, I'm currently working on this project
where we're running lots of code under a CPU simulator[*]. The
simulator has a fairly high per-instruction overhead, so code
that executes fewer instructions generally runs faster, to the
extent that telling the compiler to optimize for code size
instead of speed produces much faster executables.

[*] Bochs, if you must know. We've hacked it up a bit though.

 

[Ian Woods]

Granted. But, after a certain point, you have to choose, because you
can't have both.

Oddly enough, a C virtual machine can, and perhaps should, run this...

int i;
for (i=0;i<42;i++) {
/* do something */
}

faster, or at least, no slower, than this:

/* do something */
/* do it again */
/* do it again, again */

....

/* do it again, again, again, again... */

The reason why is that it takes /work/ to find out what the next thing to
do is on a typical computer. You need to read from memory the next
instruction. In the first version, we don't need to read the same pointless
instructions over and over, and just go and do them.

Certainly, there's plenty of cases where the smallest program is also the
quickest and no theoretical reason why the smallest program is slower than
a larger one.

Ian Woods

 

[Kevin Goodsell]

I used Google

http://www.google.com/

to search for

+"premature optimization"

and I found lots of stuff.

<snip>

Here's a document I came across a while ago that I like. It talks
specifically about Perl, but most of the points are equally valid for
other languages:

http://magnonel.guild.net/~schwern/talks/How_To_Be_Lazy/full_slides/rules_of_optimization.html

Snippet:

The Rules Of Optimization

Rule #0 - These are not rules

They are heuristics. They're not hard and fast, just a strong set of
guidelines. They should be walked through, and decided if they should be
violated, in order.

Rule #1 - Don't

Do not optimize. Optimization is the killer of schedules and destroyer
of clean code.

* Optimizations increase code entropy
The more you screw with things, the weirder you make your code.

* They will often wind up slowing down the whole system
For example, pseudo-hashes were added as a way to have faster,
more memory efficient hashes with fixed keys. They're faster by
about 10-15% when used carefully. However, the extra code slows
down *all* hashes and arrays by 10-15%.

* Adds bugs
Its new code, and often more complicated than the last. New code
means new bugs.

* Takes more time
Often the unoptimized version is the fastest one to code.

* Leaks encapsulation
Many optimizations remove subroutine calls, or increase the scope
of routines.

* Readability damaged
Micro-optimizations often do funny tricks to get more speed out.
For example, replacing lexical variables with $_

* Hampers future optimizations
Often, adding in a poorly thought out optimization will actually
make future, and more wide-ranging, ones more difficult with a
net loss in the long run. Consider the case of replacing $obj->foo
with $obj->{foo} (this is bad BTW).

-Kevin

 

[Mark McIntyre]

You can't optimise for performance AND size.

Balderdash. You can always optimise for both at once.

Of course, you do typically have to sacrifice functionality and/or
usability.....


Now thats the real challenge - optimising for functionality,
performance and size all at once.

Hmm, what about robustness, do we need that? Nah.....

 

[Malcolm]

Don't modify your source code
to enhance performance or reduce code size.

What you've got to remember is that programmer time is typically far more
expensive than CPU time. A one second speed-up has got to be executed many
many times before it repays the cost of coding it.

Learn how to use your compiler's optimization options
and, if that isn't sufficient, shop around
for a better optimizing compiler.

This is semi good advice. Firstly, algorithmic optimisation is very often
worthwhile, whilst micro-optimisation, which Robert is talking about,
frequently isn't. Buying a better compiler for a hundred quid is probably
far cheaper than spending the week trying to make the thing run faster.
However often you will have a definite target platform, and be forced to use
one compiler (this is typically the case in games). Then it can be
worthwhile to micro-optimise.