Velocity Reviews > Give some ideas for c Optimzation

Give some ideas for c Optimzation

chellappa
Guest
Posts: n/a

 07-07-2005
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
Guest
Posts: n/a

 07-07-2005
Hai
by
CHELLSKRISHNA

Suman
Guest
Posts: n/a

 07-07-2005

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.

Christian Bau
Guest
Posts: n/a

 07-07-2005
In article <(E-Mail Removed). com>,
"chellappa" <(E-Mail Removed)> 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.

0: Don't write completely brain-damaged code in the first place.

CBFalconer
Guest
Posts: n/a

 07-07-2005
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;

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

Mark
Guest
Posts: n/a

 07-07-2005
"chellappa" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
> hi
> suppose like this function ,,,
> i want optimize to exceute more fast....

then throw out that mess and use strtol();

Chris Dollin
Guest
Posts: n/a

 07-07-2005
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.

Richard Bos
Guest
Posts: n/a

 07-07-2005
"chellappa" <(E-Mail Removed)> 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

websnarf@gmail.com
Guest
Posts: n/a

 07-07-2005
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
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/

Clark S. Cox III
Guest
Posts: n/a

 07-07-2005
On 2005-07-07 09:40:08 -0400, http://www.velocityreviews.com/forums/(E-Mail Removed) 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
> can make it easier to read/maintain, and will lead you to have a better
> understanding of programming in general.

--
Clark S. Cox, III
(E-Mail Removed)