optimizing code: sort algorithm, random numbers etc. Best resources for optimization?

[PWalker]

Hi, I have written code that I would like to optimize. I need to push it to
the limit interms of speed as the accuracy of results are proportional to
runtime.

First off, would anyone know any resources that explains how to optimize
code i.e. give some rules on c++ optimization? e.g. using memcpy to copy an
array (which i have done).

Also, what is the best sorting algorithm out there for sorting an array of
of size 100 or less? I have considered heapsort and insertsort. I am however
wanting to find the fastest.

Also I'm looking for a good fast random number generator. I am currently
using Boost:

boost::minstd_rand
boost::uniform_real<>
boost::uniform_int<>
boost::variate_generator<boost::minstd_rand, boost::uniform_real<> >
boost::variate_generator<boost::minstd_rand, boost::uniform_int<> >

Is the Mersenne-Twister RNG faster/better?

I am running VC++ 7 on an AMD Mobile XP 2600+ if that helps.

Thanks!
Cheers,
Peter

 

[Puppet_Sock]

PWalker wrote:
[bunch of questions not directly related to C++ language]

Most of your questions will be best addressed with a web search.
Say you start at www.google.com, and possibly with groups.google.com.
Socks

 

[Ivan Vecerina]

Hi, I have written code that I would like to optimize. I need to push it
to the limit interms of speed as the accuracy of results are proportional
to runtime.

First off, would anyone know any resources that explains how to optimize
code i.e. give some rules on c++ optimization? e.g. using memcpy to copy
an array (which i have done).

This may not always be a good idea. Beware of undefined behavior...

Also, what is the best sorting algorithm out there for sorting an array of
of size 100 or less? I have considered heapsort and insertsort. I am
however wanting to find the fastest.

Try std::sort. In popular C++ library implementations, it is based on
the IntroSort algorithm, which itself is an improvement over the famed
QuickSort. But the best approach will depend on the contents of the
array (e.g. sometimes a linked list based MergeSort, with guaranteed
NlgN complexity and reduced number of object copies may do better).

Also I'm looking for a good fast random number generator. I am currently
using Boost:

boost::minstd_rand
boost::uniform_real<>
boost::uniform_int<>
boost::variate_generator<boost::minstd_rand, boost::uniform_real<> >
boost::variate_generator<boost::minstd_rand, boost::uniform_int<> >

Is the Mersenne-Twister RNG faster/better?

How do you define "better" ?
To what extent is RNG speed relevant to your problem ?


The most critical rule when optimizing code is to *measure first*.
From your post, it does not sound like you have done much
profiling so far.
Do you know what percentage of the execution time is spent on
sorting or on other functions?
If not, it is likely that you are wasting your time.

Next, you need to look at algorithms complexity, and avoid
doing any computations when possible (e.g. caching, etc...).

Tertio, remember that memory access is the bottleneck of many
computer programs today. Try to make your memory accesses
contiguous and cache friendly (e.g. use in-lined data members
instead of pointers to separate objects; use arrays and std::vector
instead of other object collections when possible).


For C++ itself, all you need is to be aware of the cost of
some features (e.g. exceptions if relevant, virtual calls,
construction/destruction of objects, etc).

Also, remember to 'tune' the compiler options for generating fast
code. You may even consider switching compilers (some generate
noticeably faster code than others).


There are many targeted optimization techniques and approaches,
but you have given too little information about the kind of
problem that you are working on...


But again: measure first to know what part of your system
should be the target of your optimization efforts.


Cheers,
Ivan

 

[richardv2]

The answer to almost every "Which sort is fastest?" question is "It
depends."

The slightly smart bubble sort will kick butt on a list that was sorted
recently and has just had a few additions at the end.

When I needed these answers for work problems years ago, I could only
program each as best I could, then try them with normal distribution
(what I usually gave to the sort), then some completely random, then
some *almost* sorted samples.

Back then, I chose the second best (Shell) over the fastest (QuickSort)
because I actually understood Shell. (Could write the code as fast as I
could type.) but I could not remember Quick well enough to write or
troubleshoot in my head. And the time difference was minimal.

Yesterday I sorted 10,000 floats in 0.6 seconds with a not so great
algorithm. When I last did this that would have taken quite a long
time!