Ask for book for efficient coding in C

[MBALOVER]

Hi all,

Do you know what book that discusses what we should and should not do
in C programming? It is not a book teaching about syntax, etc. but a
book teaches us the experience to optimize our code.

For example, I read somewhere that we should avoid function calls to
make the program run fast. Calling (and returning from) a function is
time-consuming, and not because the content of the function takes time
to execute — just getting into the function, and back out of it, uses
processor time.

I want to find some experiences like this.

Do you know any book discussing this?

Thank you.

 

[MBALOVER]

Thanks Richard,

I am reading the web site and it is really helpful.

Thanks a lot.

 

[Hamiral]

http://leto.net/docs/C-optimization.php

Not sure if that's the owner's link, but it looks good.

To answer to the OP :
"Part of the clarity is making hunks of code into functions when
appropriate. The cost of a function call is extremely small on modern
machines, so optimization is NOT a valid excuse for writing ten-page
functions."
This is an extract from the website you gave, and every programmmer (any
language) should stick to that.

Ham

 

[Anand Hariharan]

Thanks Richard,

I am reading the web site and it is really helpful.

Thanks a lot.

Please read up on usenet etiquette; in particular, please do not top-
post, quote signatures.



Depending upon what "avoid function calls" means, that is very bad
advice (results in spaghetti code) or if it is taken to mean inlining
(implementations provide them as optimisation options), may or may not
lead to faster programs:

http://www.parashift.com/c++-faq-lite/inline-functions.html#faq-9.3

(Note that the link is about a C++ keyword, but the specific answer is
meaningful for C as well.)

- Anand

 

[Malcolm McLean]

"Part of the clarity is making hunks of code into functions when
appropriate. The cost of a function call is extremely small on modern
machines, so optimization is NOT a valid excuse for writing ten-page
functions."

Normally you're right. However there might be situations where the
program doesn't have a few tight inner loops (which are usually the
only things worth optimising). In this case, the function call
overhead may be significant.

 

[santosh]

Normally you're right. However there might be situations where the
program doesn't have a few tight inner loops (which are usually the
only things worth optimising). In this case, the function call
overhead may be significant.

Did you mean to say that function call overhead may be significant in
the case of programs having inner loops?

One side benefit of keeping functions relatively small is that it
becomes easier for the compiler to inline calls to such functions,
rather than massive monolithic ones. However, as in everything else,
you can take this strategy too far.

 

[Malcolm McLean]

Did you mean to say that function call overhead may be significant in
the case of programs having inner loops?

Every program that takes a long time to execute will perform a large
number of operations, which means it must either have one big loop
which means most of the code is executed many many times, or several
inner loops, such that the inner loops are executed many many times,
but the rest of the code only a few times.
The second situation is by far the most common, but the first is
possible. If the first, you may find that breaking the program down
into functions has an appreciable effect on execution time. In the
second case, only adding or removing function calls from the inner
loops will have any appreciable effect.

 

[Eric Sosman]

Hi all,

Do you know what book that discusses what we should and should not do
in C programming? It is not a book teaching about syntax, etc. but a
book teaches us the experience to optimize our code.

For example, I read somewhere that we should avoid function calls to
make the program run fast. Calling (and returning from) a function is
time-consuming, and not because the content of the function takes time
to execute — just getting into the function, and back out of it, uses
processor time.

I want to find some experiences like this.

Do you know any book discussing this?

If you find such a book, burn it.

Don't burn the author, not yet, because it's just barely
possible he might be saying something useful. However, your
understanding of C -- of programming in general, I'd guess --
is not yet advanced enough to let you distinguish folly from
useful advice.

For example, the advice that you "read somewhere" is folly,
at least in the form you've repeated it. This means either that
the writer was a fool, or (more likely) that you've omitted the
important context that might -- might! -- make the advice not
be foolhardy. Why would you leave such things out? Because,
probably, you're not yet equipped to recognize their importance.
Advice is situational; advice that is good in one situation may
be terrible in another, and you cannot use the advice wisely
until you've learned to recognize the situations.

Here's my bit of advice: First, the most important thing
about a program is that it does what it is supposed to -- if
it fails to do that, or does it wrong, the speed seldom matters.
So, concentrate first on getting your code to work, because a
fast failure is of no use to anybody.

Second, once the code is working you may -- may! -- find
that it's too slow for your purposes. If so, you must *measure*
its behavior to discover where the time is going. You must also
realize that a lot of what you measure will be specific to the
particular compiler and machine and so on that you're using, and
may not be transferable to other compilers, other machines. Make
changes as your *measurements* suggest, and *measure* the speedup;
if a change doesn't produce a speedup, rescind it. Once the
program is "fast enough," stop!

I'll leave you with Michael Jackson's oft-quoted advice:

FIRST LAW OF PROGRAM OPTIMIZATION: Don't do it.

SECOND LAW OF PROGRAM OPTIMIZATION (for experts only):
Don't do it yet.

He's smarter than both of us put together; heed his message.

 

[Eric Sosman]

I cannot imagine that you are advocating burning books on optimisation.
Presumably you only intend to advocate burning /bad/ books on optimisation?

Not even that: My advice was directed specifically to the O.P.,
a person to whom Jackson's Second Law does not yet apply. At his
present stage of development, optimization books good or bad can
only do him harm.

 

[Richard Bos]

I am reading the web site and it is really helpful.

Be aware that at your current level of proficiency (i.e., given that you
have to ask these questions in the first place!), the most important
section by far for you is the one titled "GOTCHAS".

Richard

 

[Andrew Poelstra]

Be aware that at your current level of proficiency (i.e., given that you
have to ask these questions in the first place!), the most important
section by far for you is the one titled "GOTCHAS".

Richard

Glancing through the text in question, it's strewn with
warnings and cautions and "profile first!" and "fix bugs
first!".

So even if the OP drops 50% of the sentences he reads
into the bit bucket, statistically he'll be okay.

 

[Nick Keighley]

Every program that takes a long time to execute will perform a large
number of operations, which means it must either have one big loop
which means most of the code is executed many many times, or several
inner loops, such that the inner loops are executed many many times,
but the rest of the code only a few times.

or its got some slow i/o or its swopping or it's doing some
unnecessary stuff

(I know "unnecessary stuff" may be covered by your "inner loops" but I
think the emphasis is important)

The second situation is by far the most common, but the first is
possible. If the first, you may find that breaking the program down
into functions has an appreciable effect on execution time.

to increase it?

In the
second case, only adding or removing function calls from the inner
loops will have any appreciable effect.

or removing the loops.

Micro-optisations like moving code in and out of functions will
normally not have much effect. First fix your algorithms, including
the removal of unnecessary stuff. And use profiling to find those
inner loops.

 

[Nick Keighley]

As an addendum, my view is that one should create small functions
as much as possible when creating the initial version of code.
In part this is an intellectual divide and conquer strategy.
Using small functions reduces design and coding work.

to add to the platitudes. The saving in intellectual cost is also
important. If the program is easy to understand it will be easier to
optimise.

I've seen programs suffer from a sort of Inflation (I'm thinking the
cosmological type). The program becomes so large and complex no one
can understand it. The same things are done in different ways. Copy-
Paste is the anti-pattern d'jour. A vicious cycle sets in, the program
becomes larger and harder to understand because it is large and hard
to understand. The change rate is high because the bug rate is high.
The bug rate increases because the change rate is high.

 

[Nick Keighley]

I'm sorry, as stated that's terrible advice. I encountered a
programming standard that encouraged all functions to use only one
parameter ("then the compiler will use a register rather than the
stack"). This led to packs of feral Global Variables roaming the
address space.

 

[Nick]

There's a very simple rule that applies to the most experienced and
the most novice programmer: Don't optimise it unless you have measured
it. Measure it first. Decide whether investing time to optimise it
could possibly improve it buy an amount that is worth the work. If it
is worth it, optimise it _and measure it again_. If it didn't improve,
throw the optimisations away.

The important thing: Measure it. If you are not willing to spend the
time to measure the speed of your code, that on its own proves that
you shouldn't waste your time optimising it.

Among other things, and not as often spoken of, this will let you be
absolutely sure all the "scaffolding" of your program works - option
reading and parsing, I/O, data preparation etc. Once you have a
"simple" program producing the right output, and it's too slow, /then/
you can start optimising it, and if the difficult code fails to work
properly, you have a reference to compare it to.

 

[Malcolm McLean]

There's a very simple rule that applies to the most experienced and
the most novice programmer: Don't optimise it unless you have measured
it. Measure it first.

That's right for "this program only" functions. If a function is
reusable, you have to consider whether it is worth investing the time
to make a Porche, or if a Trabby is good enough.

 

[Ian Collins]

That's right for "this program only" functions. If a function is
reusable, you have to consider whether it is worth investing the time
to make a Porche, or if a Trabby is good enough.

Reused doesn't matter. Whether or not a function is reusable, start
simple and optimise only if is shown to be a performance bottleneck.

 

[Dann Corbit]

There's a very simple rule that applies to the most experienced and
the most novice programmer: Don't optimise it unless you have measured
it. Measure it first. Decide whether investing time to optimise it
could possibly improve it buy an amount that is worth the work. If it
is worth it, optimise it _and measure it again_. If it didn't improve,
throw the optimisations away.

The important thing: Measure it. If you are not willing to spend the
time to measure the speed of your code, that on its own proves that
you shouldn't waste your time optimising it.

I agree with this wholeheartedly.

There is one thing though, and it has to do with initial creation of the
code.

If you know that a particular function is asymptotically superior and
you know that it is possible for the data set to grow, choosing the more
efficient algorithm is usually the safer choice. Asymptotically
superior algorithms can definitely be inferior with smaller data sets,
but they won't go into the crapper when the data blows up into a giant
set that you were not expecting.

So (IMO) the initial design phase is a good place for some thought in
this regard.

After the code is written, never try to optimize without measuring
first.

 

[websnarf]

I agree with this wholeheartedly.

There is one thing though, and it has to do with initial creation of the
code.

If you know that a particular function is asymptotically superior and
you know that it is possible for the data set to grow, choosing the more
efficient algorithm is usually the safer choice.  Asymptotically
superior algorithms can definitely be inferior with smaller data sets,
but they won't go into the crapper when the data blows up into a giant
set that you were not expecting.

So (IMO) the initial design phase is a good place for some thought in
this regard.

After the code is written, never try to optimize without measuring
first.

I have two main comments on this:

1) You can *measure* performance before you even write code. That
speaks to your algorithmic complexity point, but can equally apply to
novel code you are writing for the first time. For example, deciding
on which data structure you should use to hold the dictionary of the
english language, it might actually pay to do some back of the
envelope calculations to see whether or not your structure fits into
the on chip L2 cache of your CPU.

2) If you are writing a *library* (that you expect to be reused) then
you don't get to say what the final usage of the code is. In other
words whether or not your code is optimal will depend on some other
code written by someone else at some later time. Usually people need
the library to exist before they can write code that uses it and
someone runs a benchmark against it. As such it make sense to perform
up-front optimization that is appropriate, with *all expected usage*.

Portability, re-entrancy, maintainability and performance optimization
are all aspects of the quality of the code you produce. This
obsession with performance optimization being some kind of demon that
will cause your code to rot is just silly. Because I have spent so
much of my career optimizing code, I just do it naturally as I am
writing and designing it, so it all just comes for free anyways. The
way I make sure the quality of the code is not compromised is that I
also simultaneously write code for other quality factors as well.
That, to me, is just what it means to be a modern professional
computer programmer.

You can take this sort of hands-off "oh I never optimize until I am
totally satisfied with the code I've written that I will need to
rewrite to optimize anyways" approach if you like. But its worth
asking yourself whether or not that attitude is more dogmatic than
useful.

To the OP: the post by Branimir Maksimovic contains 4 links any one of
which is far more useful than the rest of this discussion combined.

 

[Tim Rentsch]

I agree with this wholeheartedly.

There is one thing though, and it has to do with initial creation of the
code.

If you know that a particular function is asymptotically superior and
you know that it is possible for the data set to grow, choosing the more
efficient algorithm is usually the safer choice. Asymptotically
superior algorithms can definitely be inferior with smaller data sets,
but they won't go into the crapper when the data blows up into a giant
set that you were not expecting.

So (IMO) the initial design phase is a good place for some thought in
this regard.

After the code is written, never try to optimize without measuring
first.

I have two main comments on this:

1) You can *measure* performance before you even write code. [snip]

It's not possible to measure the performance of anything if the thing
to be measured doesn't exist. You can analyze what you expect the
performance might be, or you can measure the performance of something
else, but you can't measure the performance (or anything else) of a
piece of code until the code has been written.