4
\$\begingroup\$

I'm trying to optimize a simple Euclidian distance function in C. It's for a DLL, and calculates distances from one point to many. I have:

Version 1:

int CalcDistance (int y1, int x1, int *y2, int *x2, int nb , int *distances)
{
    double dx,dy = 0;

    for (int i = 0;i<nb;i++)
    {
        dx = x2[i] - x1;
        dy = y2[i] - y1;

        distances[i]=(int)sqrt((dx*dx)+(dy*dy));
    }

    return nb;
}

Version 2:

int CalcDistance (int y1, int x1, int *y2, int *x2, int nb , int *distance)
{
    int dx,dy =0;

    for (int i = 0;i<nb;i++)
    {
        dx = x2[i] - x1;
        dy = y2[i] - y1;

        distances[i]=(int)sqrt((double)(dx*dx)+(dy*dy));
    }

    return nb;
}

Essentially, I don't need extra high precision, so that's why I'm cutting down to ints, not doubles. For my specific use case, the final distance will not be larger than what an int (Int32) can hold.

I was taken aback by how slow version 2 was. I figured that in Version 1 calculating dx and dy would implicitly cast to double twice, whereas in version 2 I'm just explicitly casting once. What's happening? And ultimately, what could be even faster?

(And I tried _hypot, which was oddly the slowest of all...)

\$\endgroup\$
4
  • \$\begingroup\$ what kind of size is nb typically? \$\endgroup\$ May 26, 2011 at 1:01
  • \$\begingroup\$ What is the reason for ordering the parameters y, x? I would think that x, y would be the natural order. Unless this is used in an environment where y,x is the norm it could be a source of mistakes. \$\endgroup\$
    – hultqvist
    May 26, 2011 at 8:24
  • \$\begingroup\$ @phq: I hadn't noticed I had carried that over to here. The original function creator had written "Lat,Lon", even though the values sent were not latitude and longitude but really coordinates from a planar projection, where latitude is really a Y coordinate, and longitude an X coordinate. It bugged me, so I replaced them with their correspondents. I realize now I should have simply made the call to the function with the right order and make it (x,y). There is no impact in the actual function here either way. \$\endgroup\$
    – MPelletier
    May 26, 2011 at 9:50
  • \$\begingroup\$ @KeithNicholas I finally have the answer. It's a wide range, from a few hundreds to 400-500k. There's no typical case, but I'm guessing a very ballpark median would be about 75k. \$\endgroup\$
    – MPelletier
    May 26, 2011 at 20:08

4 Answers 4

6
\$\begingroup\$
dstances[i]=(int)sqrt((dx*dx)+(dy*dy));

This only converts to double once. it will do all the math integer style and and then convert it to a double just before calling sqrt.

    distances[i]=(int)sqrt((double)(dx*dx)+(dy*dy));

This is actually the same as:

    distances[i]=(int)sqrt(  ((double)(dx*dx))   + (dy*dy));    

not:

    distances[i]=(int)sqrt((double)(  (dx*dx)) + (dy*dy)  );    

As a result it will convert dx*dx to double, then convert dy*dy to double then add them and the pass it off to sqrt.

In modern computers floating point numbers are really fast, in some cases even faster then integers. As a result, you well be much better off to use double throughout rather then converting from ints to doubles and back again. The conversion between int and double is expensive so avoiding it may actually be your best bet.

A common trick used in algorithms which need to work with distances is to rework the algorithm so that you can use the square of the distance. That way you can avoid the expensive sqrt call. This works because x*x < y*y iff x < y. Be careful though, whether or not you can do this depends on what you are doing with that distance.

\$\endgroup\$
1
  • \$\begingroup\$ The "keep the square only" trick is neat, one of my favourites. But this isn't a case where it can work. Thanks for the casting explanations :) \$\endgroup\$
    – MPelletier
    May 26, 2011 at 1:37
4
\$\begingroup\$

Even if the result fits in an int, dx*dx might overflow. Better cast before multiplying

sqrt((double)dx*dx+(double)dy*dy); 
\$\endgroup\$
1
  • \$\begingroup\$ I checked my max values, you're correct, it can overflow. Good catch. \$\endgroup\$
    – MPelletier
    May 26, 2011 at 20:49
1
\$\begingroup\$

Depending on the x,y values, you could consider using floats instead of doubles. This should help a bit.

\$\endgroup\$
0
\$\begingroup\$

If you really need the distance, I have no idea, but if you just need it to compare distances, you can omit the sqrt-function, which is oftten pretty costly. Of course you should rename the function for that purpose.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.