Optimizing, examples of very fast programs ;)

[peter_k]

Hi,

Last time i'm interested in optimizing small c programs. On my studies
we are sending the programs using the web interface to online judge.
The person who will wrote the faster program get the bonus score. This
are usually simple problems, like sorting small numbers, parsing the
text and checking something etc... To get the bonus the good algorithm
is not everything, you have to do a lot of optimizations on c level (or
asembler sometimes). Ok..., so usually my programs are very fast, but
"the best" students are sendings programs few seconds/miliseconds
faster. Because i like optimizing sometimes i'm spending 1-2 days
coding. But nearly everytime i'm touching the run-time, which i cannot
beat, even i'll code few days more And i'm interested how faster
code can look, i want to learn something

Can anyone send me some example sources + problem content of very
optimized sources? I mean small programs (1 file) in c language, text
mode, parameters given in standard input, return in standard output...
Of course i'll send sources of my "optimized" applications. Please use
my email (in header of the message).

For example the one of optimization is using read() instead of scanf(),
and "parsing the number" using own code...

Greets&Thanks,
Peter_K

 

[peter_k]

"For example the one of optimization is using read() instead of
scanf(),
and "parsing the number" using own code... "

Of course this is only one of a lot of optimizations in the code...
I'm trying to optimizing nearly everything.

 

[Tomás]

Post an algorithm you're writing, and participants may give advice.


-Tomás

 

[Keith Thompson]

"For example the one of optimization is using read() instead of
scanf(),
and "parsing the number" using own code... "

Since read() is not a standard C function, that optimizes speed
(maybe) at the expense of portability and topicality in this
newsgroup.

Any performance in improvement is likely to overwhelmed by the time it
takes to read the input from whatever device it's coming from. If
you're doing this as an exercise, that's fine, but don't expect it to
be useful in the real world. Knowing when *not* to optimize is
probably more important than knowing *how* to optimize.

And please read <http://cfaj.freeshell.org/google/>.

 

[Julian V. Noble]

Hi,

Last time i'm interested in optimizing small c programs. On my studies
we are sending the programs using the web interface to online judge.
The person who will wrote the faster program get the bonus score. This
are usually simple problems, like sorting small numbers, parsing the
text and checking something etc... To get the bonus the good algorithm
is not everything, you have to do a lot of optimizations on c level (or
asembler sometimes). Ok..., so usually my programs are very fast, but
"the best" students are sendings programs few seconds/miliseconds
faster. Because i like optimizing sometimes i'm spending 1-2 days
coding. But nearly everytime i'm touching the run-time, which i cannot
beat, even i'll code few days more And i'm interested how faster
code can look, i want to learn something

Can anyone send me some example sources + problem content of very
optimized sources? I mean small programs (1 file) in c language, text
mode, parameters given in standard input, return in standard output...
Of course i'll send sources of my "optimized" applications. Please use
my email (in header of the message).

For example the one of optimization is using read() instead of scanf(),
and "parsing the number" using own code...

Greets&Thanks,
Peter_K

Have you looked at Jon Bentley's "Programming Pearls" v. 1 & 2 ? If not,
do. He has some good ideas. It is hard to do better than a good modern
compiler at the code level. Usually algorithmic optimization is worth
while. It helps to know something about the cpu also. For example, if
you have a loop (as in matrix inversion) where you divide a whole lot
of numbers by a common factor (the pivot), it is better to calculate

inv_pivot = 1/pivot

before the loop, and multiply by inv_pivot. Of course I am talking
about various Pentia, where fp division is 40x more costly than mul-
tiplication. On other cpu's or fpu's the times may be comparable, so
you get no improvement by this trick.

 

[Thad Smith]

Last time i'm interested in optimizing small c programs. On my studies
we are sending the programs using the web interface to online judge.
The person who will wrote the faster program get the bonus score. This
are usually simple problems, like sorting small numbers, parsing the
text and checking something etc... To get the bonus the good algorithm
is not everything, you have to do a lot of optimizations on c level (or
asembler sometimes). Ok..., so usually my programs are very fast, but
"the best" students are sendings programs few seconds/miliseconds
faster.

Can anyone send me some example sources + problem content of very
optimized sources?

If the competition is part of a course, then you should be provided the
code for the winning entries for all to learn. If you are not getting
these, ask for them. If you can't get them, the instructor is missing a
good opportunity for teaching.

In real life, it is more important to have correct code than fast code.
There are cases when it matters, though.

 

[Christopher Benson-Manica]

Last time i'm interested in optimizing small c programs. On my studies
we are sending the programs using the web interface to online judge.
The person who will wrote the faster program get the bonus score.

It hasn't been noted yet, but if simply choosing the right algorithm
is not enough, optimization is inherently dependent on your
implementation, or in this case the implementation used for testing.
The fastest your code could possibly be would be choosing the best
algorithm for your specific problem and implementing it entirely in
assembler, although modern compilers know much more about generating
efficient assembly than the average programmer.

Can anyone send me some example sources + problem content of very
optimized sources? I mean small programs (1 file) in c language, text
mode, parameters given in standard input, return in standard output...

1) Post here, read here.

2) You may be interested in Duff's Device,

http://c-faq.com/misc/duff.html

although again your typical modern compiler is plenty smart enough to
unroll loops if you ask nicely.