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

Discussion in 'C++' started by PWalker, Dec 15, 2004.

  1. PWalker

    PWalker Guest

    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
     
    PWalker, Dec 15, 2004
    #1
    1. Advertising

  2. PWalker

    Puppet_Sock Guest

    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
     
    Puppet_Sock, Dec 15, 2004
    #2
    1. Advertising

  3. "PWalker" <> wrote in message
    news:41c059dd$...
    > 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
    --
    http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
    Brainbench MVP for C++ <> http://www.brainbench.com
     
    Ivan Vecerina, Dec 15, 2004
    #3
  4. PWalker

    richardv2 Guest

    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!
     
    richardv2, Dec 15, 2004
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    10
    Views:
    635
    Xah Lee
    Sep 8, 2006
  2. Replies:
    18
    Views:
    527
    Xah Lee
    Sep 8, 2006
  3. Kevin Walzer

    Re: PIL (etc etc etc) on OS X

    Kevin Walzer, Aug 1, 2008, in forum: Python
    Replies:
    4
    Views:
    451
    Fredrik Lundh
    Aug 13, 2008
  4. GIMME
    Replies:
    5
    Views:
    200
    Thomas 'PointedEars' Lahn
    Jul 26, 2004
  5. Replies:
    10
    Views:
    222
    Xah Lee
    Sep 8, 2006
Loading...

Share This Page