wrinting an optimised code

[junky_fellow]

What are the basic guidelines to write an optimised code.
What points should one keep in mind for this ?
Is this purely architecture or complier specific ?
Are there any general techniques that are valid for
all architectures ?

 

[Walter Roberson]

:What are the basic guidelines to write an optimised code.
:What points should one keep in mind for this ?
:Is this purely architecture or complier specific ?
:Are there any general techniques that are valid for
:all architectures ?

One of the most important guidelines in writing optimised code is:

Don't.

Write well-designed maintainable code instead. Then benchmark it
with real data to see where it's -really- spending it's time.
See if you can optimize that. If so, good; if not, then rethink
the -algorithm- rather than getting involved with all kinds of
coding tricks.

Unless your code has a realistic chance of being executed
over and over and over again, tens of thousands of times,
taking several minutes each time, the time spent writing the
clever code will often be more than the total amount of computer
time saved during the execution lifetime of the code. And
the maintenance of "optimized" code... Ei Yi Yi!!

Another point to keep in mind is to watch out for the constants
of proportionality. For example, there are data sets for which
a Bubble Sort is faster than Quick Sort, because Quick Sort has
more startup overhead. Don't fret about finding the perfect
algorithm until you know that the time invested in it will be
worthwhile.


C specific hints: use 'const' and 'register' liberally. Pointer
aliasing is a problem in C, blocking optimizations, and
'const' and 'register' give the compiler clues about things
that are -not- aliases (or that if they are, that it's okay
not to take some cases into account because your code is
implicitly asserting that they aren't aliased.] Similarily,
in C, using pointers is NOT always faster: using explicit
array indexing can produce faster code because the compiler
can know what is not aliased to what, and has an easier time
unrolling loops without worrying that some subtle pointer
end-value semantic is being violated.

 

[Michael Mair]

What are the basic guidelines to write an optimised code.
What points should one keep in mind for this ?

1. Premature optimization is the root of all evil (C.A.R.Hoare,
often also wrongly ascribed to Knuth who just cited Hoare)
2. Use good algorithms.
3. (Experts only) Do not optimize yet.

Is this purely architecture or complier specific ?

This is general.

Are there any general techniques that are valid for
all architectures ?

No.
Get it to work, profile if it is to slow, optimise, profile again
to see whether it brought any effect.

Please read past articles in comp.lang.c -- this issue has come
up again and again. Best start with FAQ 20.12 to 20.14

Cheers
Michael

 

[Erik de Castro Lopo]

What are the basic guidelines to write an optimised code.
What points should one keep in mind for this ?
Is this purely architecture or complier specific ?
Are there any general techniques that are valid for
all architectures ?

The best way to get a job done quickly is to choose
the right algoirthm.

Erik
--
+-----------------------------------------------------------+
Erik de Castro Lopo (e-mail address removed) (Yes it's valid)
+-----------------------------------------------------------+
"Cunnilinugus and psychiatry brought us to this."
-- Tony Soprano in HBO's "the Sopranos"

 

[Achintya]

What are the basic guidelines to write an optimised code.
What points should one keep in mind for this ?
Is this purely architecture or complier specific ?
Are there any general techniques that are valid for
all architectures ?

Hi,

First write a working code and post it here.

(this is the best way to write a optimized code
)

-vs_p...

 

[Jason Curl]

What are the basic guidelines to write an optimised code.
What points should one keep in mind for this ?
Is this purely architecture or complier specific ?
Are there any general techniques that are valid for
all architectures ?

Depends on what you mean by optimised code. Code itself isn't as
important as the design, and certainly maintenance in the long run will
take more time if you "over optimise" (as extremely optimised code tends
to be unreadable).

Write the code after scribbling a design on paper. Then, when you've
written it, use tools (like profilers) to determine where the most time
of your program is taking and then change algorithms to "optimise" your
code. The algorithms generally make much more impact than just code.

Cheers,
Jason.

 

[Christian Bau]

What are the basic guidelines to write an optimised code.

1. Don't do it.
2. Don't do it yet.
3. Measure.

What points should one keep in mind for this ?
Is this purely architecture or complier specific ?

Are there any general techniques that are valid for
all architectures ?

Yes.

1. Don't do it.
2. Don't do it yet.
3. Measure.

 

[Kevin D. Quitt]

To amplify what's been said: Optimizing code is called micro-optimization, not the least because
that's the effect it usually has. Micro-optimization will never be important for you unless you
are involved in hard-real-time on a system where the hardware is marginally able to perform the
job. In other words, you micro-optimize only when you have no choice; and usually you will end up
delving into assembly language and very-bad-things (TM).

 

[Walter Roberson]

:To amplify what's been said: Optimizing code is called micro-optimization, not the least because
:that's the effect it usually has. Micro-optimization will never be important for you unless you
:are involved in hard-real-time on a system where the hardware is marginally able to perform the
:job.


That's a bit of an overgeneralization.

Something simple like changing an array dimension to not be an
exact power of 2 is a "micro-optimization", but it can make very very
large performance differences if it removes cache-line thrashing.

Similarily, just adding a 'register' storage class is a
"micro-optimization", but can get the compiler the clue it needs
to know that pointer aliasing is not taking place, thus allowing it
to perform optimizations that it would otherwise not be able to make.
One might already be using the theoretically best algorithm, but
the extra non-aliasing clue can be enough to allow the compiler to
output deeply optimized object code that takes advantage of
multiple execution units ("hyperthreading" to some) and overlapping
instruction execution, branch prediction, filling a branch
delay slot properly, knowing that one can use primary cache exclusively,
and so on.


*Generally* speaking, Fortran optimizers are better at automatic padding
of arrays to prevent cache-line thrashing; C compilers tend to need
relatively specific compile-time switches to be told what to
pad and how. But of course it depends a lot on how the code is
written.

 

[websnarf]

What are the basic guidelines to write an optimised code.

Its not so easy to express them in a single post. I have some ideas
that you can read about here:

http://www.pobox.com/~qed/optimize.html

What points should one keep in mind for this ?

All coding/design changes, or constraints you put on your code
increases the pressure on it correctness and maintainability. One must
balance the cost of optimizing (such potentially changing the
operational limits, as the Y2K problem demonstrated, or just increasing
your bug rate or maintenance cost) versus the benefit (maybe your
program goes a little faster). But one of the main lessons of code
optimization is that you usually don't have to apply it to that much
code. By locating the hotspots or critical paths of your code
(commonly done with a runtime execution profiler), you can usually
isolate the process of code optimization to a very small fraction of
your code. So very often this cost can be quite low.

A lot of people posting here, are doing their best to discourage you
from attempting to optimize for some reason. Indeed if you feel you
are not able to balance multiple constraints on code development, and
need to make coding as simple a problem as possible, then optimization
may not be for you. I'm not sure why these other posters automatically
assume that you are not capable of putting more constraints on your
coding, but if they are right and you are a low skilled programmer,
then indeed, just stay away from optimization.

Is this purely architecture or complier specific?

In the most general sense, optimization is not limited to one or the
other. If you are really serious about optimization, you usually try
to think about all modes of optimization.

Are there any general techniques that are valid for
all architectures ?

Reducing algorithmic complexity (for example changing a O(n^2)
algorithm to a O(n*ln*(n)) one) in the face of large input data usually
applies to all architectures. Also removing redundant operations from
your inner loops usually is at worst no different, and often a benefit
to your program's performance.

There are also certain operations which are universally slow (like
division, modulo, trig functions, etc.) So using techniques such as
algebraic simplification to reduce their impact (known as "strength
reduction") usually leads improved performance (if these operations are
critical bottlenecks.)

 

[Walter Roberson]

A lot of people posting here, are doing their best to discourage you
from attempting to optimize for some reason. Indeed if you feel you
are not able to balance multiple constraints on code development, and
need to make coding as simple a problem as possible, then optimization
may not be for you. I'm not sure why these other posters automatically
assume that you are not capable of putting more constraints on your
coding, but if they are right and you are a low skilled programmer,
then indeed, just stay away from optimization.

I do not feel that that is a fair representation of what the other
posters such as myself have been saying.

What we have been saying is not really "Don't optimize", but rather
closer to "Don't set out to -write- an 'optimized' program: write
a good program instead and then fine-tune it."


Learn from my mistakes: don't optimize so much. Especially on
science programs, I have a tendancy to spend months on figuring
out better ways of doing things, boundary conditions within which
one can use simpler algorithms, and so on. And then only a few people
end up using the program, and the value of the time they save is
a fraction of the value of the time that I expended in my quest
for perfection. Cheaper for my bosses to buy a faster machine than
to have me make the program 5, 10, or 100 times faster.


RealPolitics: cleaning up the obvious GUI bugs is more appreciated
than speeding up the code, and cleaning up the more common code crashes
is generally more appreciated than getting the "right" answer,
particularily if no-one knows what the "right" answer -is-.

(Oh sure, if you polled the scientists about whether some minor
cosmetic fixes were more important than reducing the calculation error
by 10%, they would say the calculation error comes first -- but
you'll get 20+ complaining "The label on the graph is too close
to the axes" for each one that complains that "In this dataset,
the error bounds could be greatly improved.")

 

[Kevin D. Quitt]

That's a bit of an overgeneralization.

True, but just a bit.

Something simple like changing an array dimension to not be an
exact power of 2 is a "micro-optimization", but it can make very very
large performance differences if it removes cache-line thrashing.

Again, true, but this kind of optimization is only worthwhile for large,
contiguous data sets on a semi-dedicated machine. And it's only of
significance if profiling shows that to be the problem. OTOH, changing a
constant like that is a simple enough thing to do, just as a matter of
course.

Similarily, just adding a 'register' storage class is a
"micro-optimization",

Are there actually any compilers that pay attention to 'register'? None of
the ones I use do. Well, except one, where it forces the compiler to
generate what is usually awkward code.

*Generally* speaking, Fortran optimizers are better at automatic padding
of arrays to prevent cache-line thrashing; C compilers tend to need
relatively specific compile-time switches to be told what to
pad and how. But of course it depends a lot on how the code is
written.

Generally speaking, Fortran optimizes everything better than C. And COBOL
optimizes better than Fortran, but then again, it's starting so far back...