wrinting an optimised code

Discussion in 'C Programming' started by junky_fellow@yahoo.co.in, May 17, 2005.

  1. Guest

    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 ?
     
    , May 17, 2005
    #1
    1. Advertising

  2. In article <>,
    <> wrote:
    :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.
    --
    Studies show that the average reader ignores 106% of all statistics
    they see in .signatures.
     
    Walter Roberson, May 17, 2005
    #2
    1. Advertising

  3. Michael Mair Guest

    wrote:
    > 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
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, May 17, 2005
    #3
  4. wrote:
    >
    > 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 (Yes it's valid)
    +-----------------------------------------------------------+
    "Cunnilinugus and psychiatry brought us to this."
    -- Tony Soprano in HBO's "the Sopranos"
     
    Erik de Castro Lopo, May 17, 2005
    #4
  5. Achintya Guest

    wrote:
    > 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...
     
    Achintya, May 17, 2005
    #5
  6. Jason Curl Guest

    wrote:
    > 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.
     
    Jason Curl, May 17, 2005
    #6
  7. In article <>,
    wrote:

    > 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.
     
    Christian Bau, May 17, 2005
    #7
  8. 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).


    --
    #include <standard.disclaimer>
    _
    Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
     
    Kevin D. Quitt, May 18, 2005
    #8
  9. In article <>,
    Kevin D. Quitt <> wrote:
    :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.
    --
    Any sufficiently advanced bug is indistinguishable from a feature.
    -- Rich Kulawiec
     
    Walter Roberson, May 18, 2005
    #9
  10. Guest

    wrote:
    > 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.)

    ---
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , May 18, 2005
    #10
  11. In article <>,
    <> wrote:
    >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.")
    --
    "Mathematics? I speak it like a native." -- Spike Milligan
     
    Walter Roberson, May 18, 2005
    #11
  12. On 18 May 2005 16:58:50 GMT, -cnrc.gc.ca (Walter Roberson)
    wrote:
    >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...


    --
    #include <standard.disclaimer>
    _
    Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
     
    Kevin D. Quitt, May 19, 2005
    #12
    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. mark | r
    Replies:
    1
    Views:
    307
    Amber
    Nov 7, 2003
  2. Kamal Advani

    Optimised String Concatenation?

    Kamal Advani, Mar 8, 2006, in forum: Java
    Replies:
    2
    Views:
    364
    Chris Uppal
    Mar 8, 2006
  3. Thuswise Webmaster
    Replies:
    0
    Views:
    814
    Thuswise Webmaster
    Jun 28, 2003
  4. Emmanuel
    Replies:
    3
    Views:
    329
    John J. Lee
    Feb 7, 2004
  5. dbuser
    Replies:
    8
    Views:
    516
    Thomas J. Gritzan
    Oct 10, 2005
Loading...

Share This Page