Give some ideas for c Optimzation

Discussion in 'C Programming' started by chellappa, Jul 7, 2005.

  1. chellappa

    chellappa Guest

    hi
    suppose like this function ,,,
    i want optimize to exceute more fast....
    please give some optimization techiques for this routine and also give
    some ideas for c programming optimzation for
    1.complier optimzation
    2.programming optimzation

    int hextodecimal(char a[],int no)
    {
    int ds=0, pw=0;
    int k;
    for(k=no-1;k>=0;k--)
    {
    switch (a[k])
    {
    case '0' :{ds=ds+(0*(pow(16,pw)));break;}
    case '1' :{ds=ds+(1*(pow(16,pw)));break;}
    case '2' :{ds=ds+(2*(pow(16,pw)));break;}
    case '3' :{ds=ds+(3*(pow(16,pw)));break;}
    case '4' :{ds=ds+(4*(pow(16,pw)));break;}
    case '5' :{ds=ds+(5*(pow(16,pw)));break;}
    case '6' :{ds=ds+(6*(pow(16,pw)));break;}
    case '7' :{ds=ds+(7*(pow(16,pw)));break;}
    case '8' :{ds=ds+(8*(pow(16,pw)));break;}
    case '9' :{ds=ds+(9*(pow(16,pw)));break;}
    case 'a': case 'A':{ds=ds+(10*(pow(16,pw)));break;}
    case 'b': case 'B':{ds=ds+(11*(pow(16,pw)));break;}
    case 'c': case 'C':{ds=ds+(12*(pow(16,pw)));break;}
    case 'd': case 'D':{ds=ds+(13*(pow(16,pw)));break;}
    case 'e': case 'E':{ds=ds+(14*(pow(16,pw)));break;}
    case 'f': case 'F':{ds=ds+(15*(pow(16,pw)));break;}
    }
    pw=pw+1;
    }
    return ds;
     
    chellappa, Jul 7, 2005
    #1
    1. Advertising

  2. chellappa

    chellappa Guest

    chellappa, Jul 7, 2005
    #2
    1. Advertising

  3. chellappa

    Suman Guest

    chellappa wrote:
    > hi
    > suppose like this function ,,,
    > i want optimize to exceute more fast....
    > please give some optimization techiques for this routine and also give
    > some ideas for c programming optimzation for
    > 1.complier optimzation
    > 2.programming optimzation

    Oft quoted here in clc are idioms like:
    0. If it doesn't work, don't optimize.
    - adapted from Christian Bau's post sometime back
    1. Don't optimize yet!
    2. Premature optimization is the root of all evil - C.A.R.Hoare

    Things to do:
    1. Decide what procedures you want
    2. Choose the best algorithms available
    3. Test
    If and only if the performance is way below expectation, then
    4. profile & identify bottlenecks
    5. work on those areas, which might incur a change in overall design
    And in the extreme cases, you might be forced to do
    some micro-optimization, but avoid that is a path less travelled.
    >
    > int hextodecimal(char a[],int no)
    > {
    > int ds=0, pw=0;
    > int k;
    > for(k=no-1;k>=0;k--)
    > {
    > switch (a[k])
    > {
    > case '0' :{ds=ds+(0*(pow(16,pw)));break;}
    > case '1' :{ds=ds+(1*(pow(16,pw)));break;}
    > case '2' :{ds=ds+(2*(pow(16,pw)));break;}
    > case '3' :{ds=ds+(3*(pow(16,pw)));break;}
    > case '4' :{ds=ds+(4*(pow(16,pw)));break;}
    > case '5' :{ds=ds+(5*(pow(16,pw)));break;}
    > case '6' :{ds=ds+(6*(pow(16,pw)));break;}
    > case '7' :{ds=ds+(7*(pow(16,pw)));break;}
    > case '8' :{ds=ds+(8*(pow(16,pw)));break;}
    > case '9' :{ds=ds+(9*(pow(16,pw)));break;}
    > case 'a': case 'A':{ds=ds+(10*(pow(16,pw)));break;}
    > case 'b': case 'B':{ds=ds+(11*(pow(16,pw)));break;}
    > case 'c': case 'C':{ds=ds+(12*(pow(16,pw)));break;}
    > case 'd': case 'D':{ds=ds+(13*(pow(16,pw)));break;}
    > case 'e': case 'E':{ds=ds+(14*(pow(16,pw)));break;}
    > case 'f': case 'F':{ds=ds+(15*(pow(16,pw)));break;}
    > }
    > pw=pw+1;
    > }
    > return ds;

    pow() returns a double, and you are working with int's.
    There is a potential overflow problem here.
     
    Suman, Jul 7, 2005
    #3
  4. In article <>,
    "chellappa" <> wrote:

    > hi
    > suppose like this function ,,,
    > i want optimize to exceute more fast....
    > please give some optimization techiques for this routine and also give
    > some ideas for c programming optimzation for
    > 1.complier optimzation
    > 2.programming optimzation


    Usually people will tell you not to worry about optimisation. The rule
    is:

    1. Don't optimise.
    2. Don't optimise yet.

    For your special consideration, I will add another rule:

    0: Don't write completely brain-damaged code in the first place.
     
    Christian Bau, Jul 7, 2005
    #4
  5. chellappa

    CBFalconer Guest

    chellappa wrote:
    >
    > suppose like this function ,,,
    > i want optimize to exceute more fast....
    > please give some optimization techiques for this routine and also give
    > some ideas for c programming optimzation for
    > 1.complier optimzation
    > 2.programming optimzation
    >
    > int hextodecimal(char a[],int no)
    > {
    > int ds=0, pw=0;
    > int k;
    > for(k=no-1;k>=0;k--)
    > {
    > switch (a[k])
    > {
    > case '0' :{ds=ds+(0*(pow(16,pw)));break;}
    > case '1' :{ds=ds+(1*(pow(16,pw)));break;}
    > case '2' :{ds=ds+(2*(pow(16,pw)));break;}
    > case '3' :{ds=ds+(3*(pow(16,pw)));break;}
    > case '4' :{ds=ds+(4*(pow(16,pw)));break;}
    > case '5' :{ds=ds+(5*(pow(16,pw)));break;}
    > case '6' :{ds=ds+(6*(pow(16,pw)));break;}
    > case '7' :{ds=ds+(7*(pow(16,pw)));break;}
    > case '8' :{ds=ds+(8*(pow(16,pw)));break;}
    > case '9' :{ds=ds+(9*(pow(16,pw)));break;}
    > case 'a': case 'A':{ds=ds+(10*(pow(16,pw)));break;}
    > case 'b': case 'B':{ds=ds+(11*(pow(16,pw)));break;}
    > case 'c': case 'C':{ds=ds+(12*(pow(16,pw)));break;}
    > case 'd': case 'D':{ds=ds+(13*(pow(16,pw)));break;}
    > case 'e': case 'E':{ds=ds+(14*(pow(16,pw)));break;}
    > case 'f': case 'F':{ds=ds+(15*(pow(16,pw)));break;}
    > }
    > pw=pw+1;
    > }
    > return ds;


    Don't worry about optimization. Worry about accuracy and
    robustness.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Jul 7, 2005
    #5
  6. chellappa

    Mark Guest

    "chellappa" <> wrote in message
    news:...
    > hi
    > suppose like this function ,,,
    > i want optimize to exceute more fast....


    then throw out that mess and use strtol();
     
    Mark, Jul 7, 2005
    #6
  7. chellappa

    Chris Dollin Guest

    chellappa wrote:

    > hi
    > suppose like this function ,,,
    > i want optimize to exceute more fast....


    First learn to write decent C.

    > int hextodecimal(char a[],int no)
    > {
    > int ds=0, pw=0;
    > int k;
    > for(k=no-1;k>=0;k--)
    > {
    > switch (a[k])
    > {
    > case '0' :{ds=ds+(0*(pow(16,pw)));break;}
    > case '1' :{ds=ds+(1*(pow(16,pw)));break;}
    > case '2' :{ds=ds+(2*(pow(16,pw)));break;}
    > case '3' :{ds=ds+(3*(pow(16,pw)));break;}
    > case '4' :{ds=ds+(4*(pow(16,pw)));break;}
    > case '5' :{ds=ds+(5*(pow(16,pw)));break;}
    > case '6' :{ds=ds+(6*(pow(16,pw)));break;}
    > case '7' :{ds=ds+(7*(pow(16,pw)));break;}
    > case '8' :{ds=ds+(8*(pow(16,pw)));break;}
    > case '9' :{ds=ds+(9*(pow(16,pw)));break;}
    > case 'a': case 'A':{ds=ds+(10*(pow(16,pw)));break;}
    > case 'b': case 'B':{ds=ds+(11*(pow(16,pw)));break;}
    > case 'c': case 'C':{ds=ds+(12*(pow(16,pw)));break;}
    > case 'd': case 'D':{ds=ds+(13*(pow(16,pw)));break;}
    > case 'e': case 'E':{ds=ds+(14*(pow(16,pw)));break;}
    > case 'f': case 'F':{ds=ds+(15*(pow(16,pw)));break;}
    > }
    > pw=pw+1;
    > }
    > return ds;


    This code is so completely horrible I can't bear to dissect
    it. Any time [1] you see so much duplication in a bunch of code
    you *know* something is wrong. Any time [1] you see so much
    code to do such a little jon, you *know* something is wrong.

    [1] Unless there's some compelling, *measured*, efficiency
    reason. Which there is, one time in five hundred and
    sixty-seven.

    --
    Chris "electric hedgehog" Dollin
    It's called *extreme* programming, not *stupid* programming.
     
    Chris Dollin, Jul 7, 2005
    #7
  8. chellappa

    Richard Bos Guest

    "chellappa" <> wrote:

    > read this web site http://www.*********.com/qed/optimize.html


    Or, perhaps, do not. It's written by Paul Hsieh, whose opinions on what
    is good C are... let's be generous and call them unusual in this group.

    Richard
     
    Richard Bos, Jul 7, 2005
    #8
  9. chellappa

    Guest

    This appears to be a hexstring -> numeric converter. I'll assume
    that's what it is, and dispense with correctness analysis.

    So let us examine some simple techniques that should help deliver
    higher performance.

    1. pow(16,pw), were pw is a positive int, and the output is assumed not
    to overflow INT_MAX can be simplified to: (1 << (4*pw)). Remember your
    exponentialtion rules, and remember that pow(2,unsigned int x) is the
    same as (1 << x). The performance improvement from doing this alone is
    *enormous*. Everyone knows this, except for the regulars that post in
    this newsgroup for some reason.

    The compiler cannot catch this optimization because of the assumption
    about not overflowing. I.e., the transformation is really only sound
    so long as the no-overflow assumption holds.

    2. switch() is a relatively slow operation (can be slower than a
    function call, and is always slower than a single if()). So let's see
    what can be done about removing it. Each of your cases is of the form:


    ds=ds+(<some constant>*(pow(16,pw)));

    So the obvious first simplification is:

    ds += SomeTable[(unsigned char) a[k]] * (1 << (4*pw));

    Where "SomeTable" has been initialized to all 0's except for '0'-'9',
    'A'-'F' and 'a'-'f', as 0-9, 10-15 and 10-15 respectively. The cast to
    unsigned char is kind of important for safety reasons. Well ok, but
    even this can be simplified further:

    ds += SomeTable[(unsigned char) a[k]] << (4*pw);

    So we can drop the switch altogether. By replacing the inner loop with
    this. These first two are just ordinary math, and you should
    familiarize yourself with exponent rules and shifting math. Its fairly
    important in real world programming such this case.

    Again, the compiler can never perform any of these simplifications
    because of how overflows happen.

    3. Ok, there is still the matter of potential strength reduction of
    "4*pw". Rather than incrementing it by 1 each time, then multiplying
    it by 4, why not simply increment it by 4? So here's my recoding of
    the inner loop:

    for(k=no-1;k>=0;k--) {
    ds += SomeTable[(unsigned char) a[k]] << pw;
    pw += 4;
    }

    Some compilers are capable of doing automatic strength reduction with
    maximum optimization switches set.

    4. We might try unrolling, however that can really uglify the code, and
    besides that is one that most compilers can do on their own. So just
    replacing the loop with the one you see in #3, while "SomeTable"
    initialized as discussed in #2, and setting your compiler optimizations
    for maximum will probably yield pretty good results.

    For further optimizations, I would look into seeing about cases where
    "no" is a constant. "no" will have to be fairly small for most typical
    hex conversions, in which case you should manually fully unroll the
    loop and save yourself a little bit of overhead there as well. In such
    cases, making the function a "macro" may serve to reduce overhead even
    more.

    There have been other comments that suggest you simply should not do
    any of this. That optimizing is the root of all evil, etc. As you
    might imagine I strongly disagree, and I think this kind of exercise,
    analysis is useful and very valuable to apply to your code by default.
    Many times, and this is a prime example of this, the process of
    optimizing your code leads to great simplification of your code which
    can make it easier to read/maintain, and will lead you to have a better
    understanding of programming in general.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , Jul 7, 2005
    #9
  10. On 2005-07-07 09:40:08 -0400, said:

    > 2. switch() is a relatively slow operation (can be slower than a
    > function call, and is always slower than a single if()).


    That is simply not true, and demonstrably so. Given the following code:

    int foo1(char c)
    {
    switch(c)
    {
    default: return 1;
    case 0: return 0;
    }
    }

    int foo2(char c)
    {
    if(c) return 1;
    else return 0;
    }


    My compiler produces identical code for each function:

    _foo1:
    stmw r30,-8(r1)
    stwu r1,-48(r1)
    mr r30,r1
    mr r0,r3
    stb r0,72(r30)
    lbz r0,72(r30)
    extsb r0,r0
    cmpwi cr7,r0,0
    beq cr7,L3
    li r0,1
    stw r0,24(r30)
    b L4
    L3:
    li r0,0
    stw r0,24(r30)
    L4:
    lwz r0,24(r30)
    mr r3,r0
    lwz r1,0(r1)
    lmw r30,-8(r1)
    blr
    .align 2
    .globl _foo2
    _foo2:
    stmw r30,-8(r1)
    stwu r1,-48(r1)
    mr r30,r1
    mr r0,r3
    stb r0,72(r30)
    lbz r0,72(r30)
    extsb r0,r0
    cmpwi cr7,r0,0
    beq cr7,L7
    li r0,1
    stw r0,24(r30)
    b L9
    L7:
    li r0,0
    stw r0,24(r30)
    L9:
    lwz r0,24(r30)
    mr r3,r0
    lwz r1,0(r1)
    lmw r30,-8(r1)
    blr



    > So let's see what can be done about removing it. Each of your cases
    > is of the form:
    >
    > ds=ds+(<some constant>*(pow(16,pw)));
    >
    > So the obvious first simplification is:
    >
    > ds += SomeTable[(unsigned char) a[k]] * (1 << (4*pw));
    >
    > Where "SomeTable" has been initialized to all 0's except for '0'-'9',
    > 'A'-'F' and 'a'-'f', as 0-9, 10-15 and 10-15 respectively. The cast to
    > unsigned char is kind of important for safety reasons. Well ok, but
    > even this can be simplified further:


    The optimization of using a lookup table is very likely premature, as
    most compilers are smart enough to do that for you behind the scenes.

    [snip]

    > There have been other comments that suggest you simply should not do
    > any of this. That optimizing is the root of all evil, etc.


    Optimization is not the root of all evil, *premature* optimization is.
    Given clear code that communicates the programmer's intent, it is
    unlikely that you will beat a good compiler in the general case.

    > As you might imagine I strongly disagree, and I think this kind of exercise,
    > analysis is useful and very valuable to apply to your code by default.
    > Many times, and this is a prime example of this, the process of
    > optimizing your code leads to great simplification of your code which
    > can make it easier to read/maintain, and will lead you to have a better
    > understanding of programming in general.


    --
    Clark S. Cox, III
     
    Clark S. Cox III, Jul 7, 2005
    #10
  11. chellappa

    CBFalconer Guest

    Richard Bos wrote:
    > "chellappa" <> wrote:
    >
    >> read this web site http://www.*********.com/qed/optimize.html

    >
    > Or, perhaps, do not. It's written by Paul Hsieh, whose opinions on
    > what is good C are... let's be generous and call them unusual in
    > this group.


    What was the point in wiping out the URL and preventing readers
    from making their own evaluation? I have had my disagreements with
    Mr Hsieh, and his peculiarities that really stick in my mind are:
    1. All ints are guaranteed 32 bits. 2. Shift operations on
    signed integral types are always valid.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Jul 7, 2005
    #11
  12. chellappa wrote:
    > hi
    > suppose like this function ,,,
    > i want optimize to exceute more fast....
    > please give some optimization techiques for this routine and also give
    > some ideas for c programming optimzation for
    > 1.complier optimzation
    > 2.programming optimzation
    >
    > int hextodecimal(char a[],int no)
    > {
    > int ds=0, pw=0;
    > int k;
    > for(k=no-1;k>=0;k--)
    > {
    > switch (a[k])
    > {
    > case '0' :{ds=ds+(0*(pow(16,pw)));break;}
    > case '1' :{ds=ds+(1*(pow(16,pw)));break;}
    > case '2' :{ds=ds+(2*(pow(16,pw)));break;}
    > case '3' :{ds=ds+(3*(pow(16,pw)));break;}
    > case '4' :{ds=ds+(4*(pow(16,pw)));break;}
    > case '5' :{ds=ds+(5*(pow(16,pw)));break;}
    > case '6' :{ds=ds+(6*(pow(16,pw)));break;}
    > case '7' :{ds=ds+(7*(pow(16,pw)));break;}
    > case '8' :{ds=ds+(8*(pow(16,pw)));break;}
    > case '9' :{ds=ds+(9*(pow(16,pw)));break;}
    > case 'a': case 'A':{ds=ds+(10*(pow(16,pw)));break;}
    > case 'b': case 'B':{ds=ds+(11*(pow(16,pw)));break;}
    > case 'c': case 'C':{ds=ds+(12*(pow(16,pw)));break;}
    > case 'd': case 'D':{ds=ds+(13*(pow(16,pw)));break;}
    > case 'e': case 'E':{ds=ds+(14*(pow(16,pw)));break;}
    > case 'f': case 'F':{ds=ds+(15*(pow(16,pw)));break;}
    > }
    > pw=pw+1;
    > }
    > return ds;


    I took it as an excercise myself.


    int hextodecimal(char a[], int n)
    {
    int ds = 0;
    int pow16 = 1;
    int i, tmp;

    for (i = n - 1; i >= 0; i--)
    {
    //if (a >= '0' && a <= '9')
    if (isdigit(a))
    {
    ds += (a - '0') * pow16;
    }
    else
    {
    tmp= a;
    #if 1 // with topper()
    if ((tmp = toupper(a)) >= 'A' && tmp <= 'F')
    {
    ds += (10 + tmp - 'A') * pow16;
    }
    else
    {
    return -1; // ERROR!
    }

    #else // without toupper()
    if (tmp >= 'a' && tmp <= 'f')
    {
    tmp += 'A' - 'a';
    }

    if (tmp >= 'A' && tmp <= 'F')
    {
    ds += (10 + tmp - 'A') * pow16;
    }
    else
    {
    return -1; // ERROR!
    }
    #endif
    }
    pow16 <<= 4;
    }

    return ds;
    }

    This is cleaner, and should still be fairly portable in practice. But
    you must take care not to feed it too large values. Or just include a
    size test in the function itself, which is usually better.

    As you can see, there are no floating point calculations or conversions
    involved (like with pow()), integers are faster. You could also
    precalculate the values you need and put them in a static array in the
    function, like static int pow16[] = { 1, 16, 4096...}, and do pow16[pw]
    instead. Same goes for the char ascii values. But that would seem
    pointless in this case, since the calculations are rather simple and
    fast to begin with. So don't bother trying, except if you really want
    to experiment to learn.

    And in general, small code is often faster than big code, because it has
    a higher chance of fitting in the processor's cache. Removing the need
    for pow() makes the code a lot smaller, given that you don't use
    hextodecimal() in a loop that also uses pow(). But all of this depends
    on the context in which the function is called. In any case, compiling
    only hextodecimal() resulted in my function compiling into smaller
    object code than yours, no matter which optimization level I used.

    You can choose if you want to use isdigit() and toupper() or not. I've
    basically rewritten those functions in my example. Whether avoiding
    those function calls will make it slower or faster, depends. But
    usually, readability is a higher concern than minor optimizations like
    this, that may have no real significance.

    Or just use strtol() or strtoul(), they are standard C89 functions that
    will probably do what you need. But I take it you are doing this to
    learn. And if you are sure that you really need some extra speed, you
    should profile you program and make sure the problem isn't really
    somewhere else than in this function.

    And now, watch as the optimization and portability experts pick my
    arguments apart and make me eat them. ;)
     
    Tydr Schnubbis, Jul 7, 2005
    #12
  13. chellappa

    Netocrat Guest

    On Thu, 07 Jul 2005 17:12:27 +0000, CBFalconer wrote:

    > Richard Bos wrote:
    >> "chellappa" <> wrote:
    >>
    >>> read this web site http://www.*********.com/qed/optimize.html

    >>
    >> Or, perhaps, do not. It's written by Paul Hsieh, whose opinions on what
    >> is good C are... let's be generous and call them unusual in this group.

    >
    > What was the point in wiping out the URL and preventing readers from
    > making their own evaluation? I have had my disagreements with Mr Hsieh,
    > and his peculiarities that really stick in my mind are: 1. All ints are
    > guaranteed 32 bits. 2. Shift operations on signed integral types are
    > always valid.


    On reading through some of Paul Hsieh's site I found it to be informative
    and practical. I certainly didn't see any glaring errors. As far as shift
    operations he specifically mentions on one page that right shift is not
    defined by standard C for signed integers, so if he once argued the
    opposite he has corrected the error. His ideas on optimisation with
    assembly are great and needn't clash with this newsgroup's goal of
    standard C - they can quite easily remain distinct. I should add the
    caveat that I have only a rudimentary assembly knowledge so I couldn't
    properly evaluate all of the examples for their 'unusualness' but there is
    nothing unusual on the website in his C usage. On matters of personal
    taste/style/programming religion I very much agree with his opinion on
    goto usage and his suggestions on how to learn programming.

    In short I don't see the point in censoring the URL - the site is a good
    resource.
     
    Netocrat, Jul 7, 2005
    #13
  14. When looking at the (optimized) assembly output from my compiler, I saw
    that it used multiplication in cases like '(a - '0') * pow16',
    instead of bit shifting. Since bit shifting is supposed to be faster,
    I've changed the code a little. But there are probably other
    optimizations that would matter more than this, that I haven't
    discovered yet.

    int hextodecimal(char a[], int n)
    {
    int ds = 0;
    int shift = 0;
    int i, tmp;

    for (i = n - 1; i >= 0; i--)
    {
    //if (a >= '0' && a <= '9')
    if (isdigit(a))
    {
    ds += (a - '0') << shift;
    }
    else
    {
    tmp= a;
    #if 1 // with topper()
    if ((tmp = toupper(a)) >= 'A' && tmp <= 'F')
    {
    ds += (10 + tmp - 'A') << shift;
    }
    else
    {
    return -1; // ERROR!
    }

    #else // without toupper()
    if (tmp >= 'a' && tmp <= 'f')
    {
    tmp += 'A' - 'a';
    }

    if (tmp >= 'A' && tmp <= 'F')
    {
    ds += (10 + tmp - 'A') << shift;
    }
    else
    {
    return -1; // ERROR!
    }
    #endif
    }
    shift += 4;
    }

    return ds;
    }
     
    Tydr Schnubbis, Jul 7, 2005
    #14
  15. In article <>,
    Christian Bau <> wrote:

    >Usually people will tell you not to worry about optimisation. The rule
    >is:
    >
    > 1. Don't optimise.
    > 2. Don't optimise yet.


    There's also a corollary:

    c. Leave the micro-optimization to the compiler.

    And a meta-corollary:
    c'. If a (reasonably intelligent) person (who has taken a close look at
    it) has trouble understanding the code, the compiler will probably
    have trouble optimizing it.


    dave

    --
    Dave Vandervies
    More proof that the surefire way to discover the answer to your question
    is to ask it in a public forum.
    --Peter Ammon in comp.lang.c
     
    Dave Vandervies, Jul 7, 2005
    #15
  16. chellappa

    Malcolm Guest

    "chellappa" <> wrote
    > suppose like this function ,,,
    > i want optimize to exceute more fast....
    > please give some optimization techiques for this routine and also give
    > some ideas for c programming optimzation for
    > 1.complier optimzation
    > 2.programming optimzation
    >
    > int hextodecimal(char a[],int no)
    > {
    > int ds=0, pw=0;
    > int k;
    > for(k=no-1;k>=0;k--)
    > {
    > switch (a[k])
    > {
    > case '0' :{ds=ds+(0*(pow(16,pw)));break;}
    > case '1' :{ds=ds+(1*(pow(16,pw)));break;}
    > case '2' :{ds=ds+(2*(pow(16,pw)));break;}
    > case '3' :{ds=ds+(3*(pow(16,pw)));break;}
    > case '4' :{ds=ds+(4*(pow(16,pw)));break;}
    > case '5' :{ds=ds+(5*(pow(16,pw)));break;}
    > case '6' :{ds=ds+(6*(pow(16,pw)));break;}
    > case '7' :{ds=ds+(7*(pow(16,pw)));break;}
    > case '8' :{ds=ds+(8*(pow(16,pw)));break;}
    > case '9' :{ds=ds+(9*(pow(16,pw)));break;}
    > case 'a': case 'A':{ds=ds+(10*(pow(16,pw)));break;}
    > case 'b': case 'B':{ds=ds+(11*(pow(16,pw)));break;}
    > case 'c': case 'C':{ds=ds+(12*(pow(16,pw)));break;}
    > case 'd': case 'D':{ds=ds+(13*(pow(16,pw)));break;}
    > case 'e': case 'E':{ds=ds+(14*(pow(16,pw)));break;}
    > case 'f': case 'F':{ds=ds+(15*(pow(16,pw)));break;}
    > }
    > pw=pw+1;
    > }
    > return ds;
    >


    The function is so grossly inefficient I can only presume it was given as a
    homework exercise.

    The most important point is that no one wants to call a hex to decimal
    converter with the last digit as an argument. You want

    int hextodecimal(char *str)

    secondly, you don't convert for hex to deimla at all, but from hex to
    machine representation, which is binary.

    so you want one function

    int xtoi(char *str)

    and either call sprintf("%d") to get decimal, or write an

    void itoa(char *out, int x)


    The other main problem is of course the call to pow(). Hexadecimal numers
    are very easily converted to binary format by shifting.

    DEADBEEF (hex) 1101 1110 1010 1101 1011 1110 1110 1111 (binary)

    look up the value for each digit, and then use the shift operators and
    logical operations to create the number.

    Finally you need to consider what to do if passed illegal input, such as a
    vaild hex number too big to fit in an integer. There isn't necessarily any
    right answer in cases like this, but you should document what the behaviour
    of your function is.

    (It is not normally sensible to try to optimise away the switch() by
    building a lookup table or similar. You don't compilcate code for this sort
    of micro-optimisation that may actually run slower on some platforms).
     
    Malcolm, Jul 7, 2005
    #16
  17. chellappa

    Guest

    Clark S. Cox III wrote:
    > On 2005-07-07 09:40:08 -0400, said:
    >
    > > 2. switch() is a relatively slow operation (can be slower than a
    > > function call, and is always slower than a single if()).

    >
    > That is simply not true, and demonstrably so. Given the following code:


    I meant to say "slower or equal".

    > > So let's see what can be done about removing it. Each of your cases
    > > is of the form:
    > >
    > > ds=ds+(<some constant>*(pow(16,pw)));
    > >
    > > So the obvious first simplification is:
    > >
    > > ds += SomeTable[(unsigned char) a[k]] * (1 << (4*pw));
    > >
    > > Where "SomeTable" has been initialized to all 0's except for '0'-'9',
    > > 'A'-'F' and 'a'-'f', as 0-9, 10-15 and 10-15 respectively. The cast to
    > > unsigned char is kind of important for safety reasons. Well ok, but
    > > even this can be simplified further:

    >
    > The optimization of using a lookup table is very likely premature, as
    > most compilers are smart enough to do that for you behind the scenes.


    Ok, so can you point me to even one compiler that successfully makes
    this optimization? I am highly skeptical, as it requires that the
    compiler see the mathematical optimization of putting in 0 in all the
    default cases as being equivalent to doing nothing, as well as pattern
    matching each case and finding just the right parameter.

    > [snip]
    >
    > > There have been other comments that suggest you simply should not do
    > > any of this. That optimizing is the root of all evil, etc.

    >
    > Optimization is not the root of all evil, *premature* optimization is.
    > Given clear code that communicates the programmer's intent, it is
    > unlikely that you will beat a good compiler in the general case.


    Personally, I have rarely ever *not* beaten the compiler. So you can
    imagine that coupled with the simplification comment I make later, that
    I have little sympathy for this point of view.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , Jul 8, 2005
    #17
  18. chellappa

    Jack Klein Guest

    On 6 Jul 2005 23:16:19 -0700, "chellappa" <>
    wrote in comp.lang.c:

    > hi
    > suppose like this function ,,,
    > i want optimize to exceute more fast....
    > please give some optimization techiques for this routine and also give
    > some ideas for c programming optimzation for
    > 1.complier optimzation
    > 2.programming optimzation
    >
    > int hextodecimal(char a[],int no)
    > {
    > int ds=0, pw=0;
    > int k;
    > for(k=no-1;k>=0;k--)
    > {
    > switch (a[k])
    > {
    > case '0' :{ds=ds+(0*(pow(16,pw)));break;}
    > case '1' :{ds=ds+(1*(pow(16,pw)));break;}
    > case '2' :{ds=ds+(2*(pow(16,pw)));break;}
    > case '3' :{ds=ds+(3*(pow(16,pw)));break;}
    > case '4' :{ds=ds+(4*(pow(16,pw)));break;}
    > case '5' :{ds=ds+(5*(pow(16,pw)));break;}
    > case '6' :{ds=ds+(6*(pow(16,pw)));break;}
    > case '7' :{ds=ds+(7*(pow(16,pw)));break;}
    > case '8' :{ds=ds+(8*(pow(16,pw)));break;}
    > case '9' :{ds=ds+(9*(pow(16,pw)));break;}
    > case 'a': case 'A':{ds=ds+(10*(pow(16,pw)));break;}
    > case 'b': case 'B':{ds=ds+(11*(pow(16,pw)));break;}
    > case 'c': case 'C':{ds=ds+(12*(pow(16,pw)));break;}
    > case 'd': case 'D':{ds=ds+(13*(pow(16,pw)));break;}
    > case 'e': case 'E':{ds=ds+(14*(pow(16,pw)));break;}
    > case 'f': case 'F':{ds=ds+(15*(pow(16,pw)));break;}
    > }
    > pw=pw+1;
    > }
    > return ds;


    Let me get this straight...

    You're the one who showed began posting in this group less than 48
    hours ago, and started these threads:

    "Running time of program"
    "about char pointer"
    "how to compare"
    "Hardware Programming"
    "Certificate for C Programmer"
    "Time command"

    ....and who stated in one post:

    > i dont want read such kind of books..
    > ttell me through userner
    > by
    > chells


    ....and in another post:

    > I am new for computer science


    You are so far away from being ready to think about optimization that
    the gulf is frightening. Go learn the C language and library inside
    and out, then start worrying about optimization.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Jul 8, 2005
    #18
  19. chellappa

    Chris Torek Guest

    >"chellappa" <> wrote:
    >> read this web site http://www.azillionmonkeys.com/qed/optimize.html


    In article <4all.nl>
    Richard Bos <> wrote:
    >Or, perhaps, do not. It's written by Paul Hsieh, whose opinions on what
    >is good C are... let's be generous and call them unusual in this group.


    Mr Hsieh *is* actually a pretty smart guy. What he lacks is a
    sense of "code taste". :) (But hey, some people like "modern"
    furniture, too, or almonds in their chocolate: There is room in
    the world for variation.)

    Just be aware that what he means by "optimization" is often far
    beyond what is appropriate for many programmers, and -- at least
    from what I have seen of it -- is also sometimes targeted too
    specifically at some particular trend in CPU design. Many years
    ago, for instance, it was often important to use fewer assembly-level
    instructions, even if that meant using complicated instructions
    like the 80x86 "enter" and "exit"; today, you often find that the
    code runs faster if you ignore the fancy instructions, and split
    out the operations into several separate instructions that can all
    run in parallel or pipeline well. In other words, something that
    saved 2 cycles ten years ago may *cost* 20 cycles today.
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Jul 8, 2005
    #19
    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. Edison
    Replies:
    2
    Views:
    1,668
    Jonathan Bromley
    Jun 30, 2003
  2. yuyazhang
    Replies:
    14
    Views:
    734
    yuyazhang
    Apr 29, 2006
  3. Mike Wahler
    Replies:
    1
    Views:
    380
    Az Tech
    Aug 2, 2003
  4. grocery_stocker
    Replies:
    10
    Views:
    651
    Keith Thompson
    May 25, 2005
  5. spasmous

    Parentheses and compiler optimzation

    spasmous, Apr 10, 2008, in forum: C Programming
    Replies:
    15
    Views:
    483
    Anonymous
    Apr 13, 2008
Loading...

Share This Page