make it faster

[Simply_Red]

Hi,

is there a way to make this function faster???

struct Points {
double X;
double Y;
};


double Dist(Points First, Points Last)
{
return pow( (First.X-Last.X)*(First.X-Last.X) + (First.Y -
Last.Y)*(First.Y - Last.Y) ,0.5);
}

 

[Kira Yamato]

Hi,

is there a way to make this function faster???

struct Points {
double X;
double Y;
};


double Dist(Points First, Points Last)
{
return pow( (First.X-Last.X)*(First.X-Last.X) + (First.Y -
Last.Y)*(First.Y - Last.Y) ,0.5);
}

google up 'fastsqrt' and see if it helps.

 

[Erik Wikström]

Hi,

is there a way to make this function faster???

struct Points {
double X;
double Y;
};


double Dist(Points First, Points Last)
{
return pow( (First.X-Last.X)*(First.X-Last.X) + (First.Y -
Last.Y)*(First.Y - Last.Y) ,0.5);
}

You could try to use the pow() instead of multiplying and using sqrt()
instead of pow(x, 0.5).

But more importantly, are you sure that Dist() is the function you need
to make faster?

 

[Simply_Red]

You could try to use the pow() instead of multiplying and using sqrt()
instead of pow(x, 0.5).

But more importantly, are you sure that Dist() is the function you need
to make faster?

I did a test and multiplying is faster than pow,
and what is strange, pow(x,0.5) is faster than sqrt(x).


I have to make my program working faster, so i try to find where it is
possible.

 

[Michael Angelo Ravera]

Hi,

is there a way to make this function faster???

struct Points {
        double X;
        double Y;

};

double Dist(Points First, Points Last)
{
    return pow( (First.X-Last.X)*(First.X-Last.X) + (First.Y -
Last.Y)*(First.Y - Last.Y) ,0.5);



}- Hide quoted text -

- Show quoted text -

Several ways:
1) sqrt is likely to be faster than pow
2) a #define is likely to be faster that a member function
3) most high level optimizers will compute the common subexpressions
only once, but maybe you could help it by

x_diff = First.X-Last.X;
x_diff *= x_diff;

y_diff = First.Y-Last.Y;
y_diff *= y_diff;

x_diff += y_diff;

return sqrt (x_diff);

You may be able to help it even more, if x_diff and y_diff can be kept
in registers.

 

[Victor Bazarov]

Several ways:
1) sqrt is likely to be faster than pow
2) a #define is likely to be faster that a member function
3) most high level optimizers will compute the common subexpressions
only once, but maybe you could help it by

x_diff = First.X-Last.X;
x_diff *= x_diff;

y_diff = First.Y-Last.Y;
y_diff *= y_diff;

x_diff += y_diff;

return sqrt (x_diff);

You may be able to help it even more, if x_diff and y_diff can be kept
in registers.

There is also a POSIX function _hypot, I believe. So you could try
doing

double Dist(Points const& First, Points const& Last)
{
return _hypot( First.X - Last.X, First.Y - Last.Y );
}

Note the use of 'const&' for arguments. Not sure if it's better, so
do test, it might be, on your system.

V

 

[Pete Becker]

I have to make my program working faster, so i try to find where it is
possible.

Passerby sees a drunk fumbling around under a streetlamp, asks him what
he's doing. Drunk answers, "looking for my car keys." Passerby asks,
"where did you drop them?" Drunk points ten yards away, says, "over
there." Passerby asks, "then why are you looking here?" Drunk answers,
"because the light's much better here."

If your program is too slow, you have to speed up the parts that are
making it slow.

 

[Victor Bazarov]

Passerby sees a drunk fumbling around under a streetlamp, asks him
what he's doing. Drunk answers, "looking for my car keys." Passerby
asks, "where did you drop them?" Drunk points ten yards away, says,
"over there." Passerby asks, "then why are you looking here?" Drunk
answers, "because the light's much better here."

If your program is too slow, you have to speed up the parts that are
making it slow.

.... and make the determination not by guessing but by measuring.

JMTC

V

 

[Simply_Red]

Passerby sees a drunk fumbling around under a streetlamp, asks him what
he's doing. Drunk answers, "looking for my car keys." Passerby asks,
"where did you drop them?" Drunk points ten yards away, says, "over
there." Passerby asks, "then why are you looking here?" Drunk answers,
"because the light's much better here."

If your program is too slow, you have to speed up the parts that are
making it slow.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Sometimes a small detail can make a code faster, i'm searching for all
math in my code and try to find if it can be faster.

 

[Simply_Red]

There is also a POSIX function _hypot, I believe. So you could try
doing

double Dist(Points const& First, Points const& Last)
{
return _hypot( First.X - Last.X, First.Y - Last.Y );
}

Note the use of 'const&' for arguments. Not sure if it's better, so
do test, it might be, on your system.

V

after a test, it's not better.

 

[Gianni Mariani]

Hi,

is there a way to make this function faster???

struct Points {
double X;
double Y;
};


double Dist(Points First, Points Last)

any particular reason why you pass these structs by value ?

{
return pow( (First.X-Last.X)*(First.X-Last.X) + (First.Y -
Last.Y)*(First.Y - Last.Y) ,0.5);
}

If your destination cpu has a vector processing unit, you can do 4 or
more at the same time.

The other thing, it may be that when you look at the profile, you see
that this function is a culprit but it may be cache misses.

Third thing - do you really need the sqrt ? In many cases you only need
the relative order of the results which are still preserved if you don't
take a sqrt.

 

[Simply_Red]

Hi,

is there a way to make this function faster???

struct Points {
double X;
double Y;

};

double Dist(Points First, Points Last)
{
return pow( (First.X-Last.X)*(First.X-Last.X) + (First.Y -
Last.Y)*(First.Y - Last.Y) ,0.5);

}

Dist is used at least 497235 time, so even a small change can make a
difference.

 

[Victor Bazarov]

after a test, it's not better.

Which suggests that your guess is not good. You're probably trying
to improve the part of the program that is not the culprit. Get
yourself a profiler and measure!

V

 

[Default User]

Sometimes a small detail can make a code faster, i'm searching for all
math in my code and try to find if it can be faster.

You have no way of knowing whether your efforts help, hinder, or make
no difference. If you are concerned about speed, get a profiler and
figure out where the problems are.




Brian

 

[Victor Bazarov]

Dist is used at least 497235 time, so even a small change can make a
difference.

Not if those half-a-million times end up being 0.1% of the overall
run time.

V

 

[James Kanze]

Dist is used at least 497235 time, so even a small change can
make a difference.

How much time does Dist actually take? (A quick check on my
machine says less than 50 nanoseconds. Which means that a half
a million times is still something to be measured in 10's of
milliseconds---hardly a problem, I would think.)

 

[Pavel Shved]

Simply_Red:

is there a way to make this function faster???

double Dist(Points First, Points Last)
{
return pow( (First.X-Last.X)*(First.X-Last.X) + (First.Y -
Last.Y)*(First.Y - Last.Y) ,0.5);
}

In addition to passing pointers, which was mentioned above, and
inlining, which is likely done (you're using -O3, aren't you?) you can
also get rid of geting square root. Check your program flow, as sqrt
may be redundant, that is, for example, you calculate the Dist and
then square it somewhere else.

 

[Simply_Red]

i found another function that take much more time

with this version i win 40% of time:

Points func_faster(Points* pt,double mu)
{
double mum1, mum13, mu3,mumCarre,muCarre;
Points p;
mum1 = 1 - mu;
mumCarre = mum1 * mum1;
mum13 = mumCarre * mum1;
muCarre = mu * mu;
mu3 = muCarre * mu;
double tempValue1 = 3 * mu * mumCarre;
double tempValue2 = 3 * muCarre * mum1;
p.X = mum13 * pt[0].X + tempValue1 * pt[1].X + tempValue2 * pt[2].X
+ mu3 * pt[3].X;
p.Y = mum13 * pt[0].Y + tempValue1 * pt[1].Y + tempValue2 * pt[2].Y
+ mu3 * pt[3].Y;
return p;
}


Points func(Points* pt,double mu)
{
double mum1, mum13, mu3;
Points p;
mum1 = 1 - mu;
mum13 = mum1 * mum1 * mum1;
mu3 = mu * mu * mu;

p.X = mum13 * pt[0].X + 3 * mu * mum1 * mum1 * pt[1].X + 3 * mu *
mu * mum1 * pt[2].X + mu3 * pt[3].X;
p.Y = mum13 * pt[0].Y + 3 * mu * mum1 * mum1 * pt[1].Y + 3 * mu *
mu * mum1 * pt[2].Y + mu3 * pt[3].Y;
return p;
}

 

[Default User]

How much time does Dist actually take? (A quick check on my
machine says less than 50 nanoseconds. Which means that a half
a million times is still something to be measured in 10's of
milliseconds---hardly a problem, I would think.)

This is exactly the problem with shotgun optimizations. One can spend a
lot of time, and obfuscate the code, for essentially no return.
Sometimes the efforts will actually slow things down, when you defeat a
built-in compiler optimization.



Brian

 

[Phil Endecott]

i found another function that take much more time

with this version i win 40% of time:

Points func_faster(Points* pt,double mu)
{
double mum1, mum13, mu3,mumCarre,muCarre;
Points p;
mum1 = 1 - mu;
mumCarre = mum1 * mum1;
mum13 = mumCarre * mum1;
muCarre = mu * mu;
mu3 = muCarre * mu;
double tempValue1 = 3 * mu * mumCarre;
double tempValue2 = 3 * muCarre * mum1;
p.X = mum13 * pt[0].X + tempValue1 * pt[1].X + tempValue2 * pt[2].X
+ mu3 * pt[3].X;
p.Y = mum13 * pt[0].Y + tempValue1 * pt[1].Y + tempValue2 * pt[2].Y
+ mu3 * pt[3].Y;
return p;
}


Points func(Points* pt,double mu)
{
double mum1, mum13, mu3;
Points p;
mum1 = 1 - mu;
mum13 = mum1 * mum1 * mum1;
mu3 = mu * mu * mu;

p.X = mum13 * pt[0].X + 3 * mu * mum1 * mum1 * pt[1].X + 3 * mu *
mu * mum1 * pt[2].X + mu3 * pt[3].X;
p.Y = mum13 * pt[0].Y + 3 * mu * mum1 * mum1 * pt[1].Y + 3 * mu *
mu * mum1 * pt[2].Y + mu3 * pt[3].Y;
return p;
}

So in the original code you used the sub-expression 3*mu*num1*num1
twice; when you modified it you stored it in tempValue1 and it went
faster. At first sight I'm surprised that your compiler did not do that
common sub-expression elimination for you. What do people think? Is it
because

y = a * b * c
is y = (a*b) * c
not y = a * (b*c)

and the compiler can't treat it as the latter in order to re-use (b*c)
because that would have different behaviour (overflow, rounding etc.) ?

Phil.