qsort() results: implementation dependent?

[Max]

Hi everybody,

suppose you have to order a list of integers which refer to points
located in the 3D space. The compare() function is based on the
distance that these points have with respect to the origin (0,0,0). So,
using the standart qsort() function, I think this task should be
accomplished as follows:

qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function);

where

static int compare_function(void *b0, const void *b1)
{
double eps = 1e-6;

int pnt0 = *((int *)b0);
int pnt1 = *((int *)b1);

double d0 = get_distance(pnt0);
double d1 = get_distance(pnt1);

double dd = d0 - d1;

if(dd > eps)
return 1;
else if (dd < -eps)
return -1;
else
return 0.;

}

The question is: why two different qsort() implementations (AIX and
Linux) should give different results? In particular, the Linux
implementation seems to fail to to find the right order. Any hint?
Thanks
Max

[Keith Thompson]

"Max" <ip*******@gmail.com> writes:

suppose you have to order a list of integers which refer to points
located in the 3D space. The compare() function is based on the
distance that these points have with respect to the origin (0,0,0). So,
using the standart qsort() function, I think this task should be
accomplished as follows:

qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function);
If you have a visible prototype for qsort(), the cast is unnecessary.
where

static int compare_function(void *b0, const void *b1)
{
double eps = 1e-6;

int pnt0 = *((int *)b0);
int pnt1 = *((int *)b1);

double d0 = get_distance(pnt0);
double d1 = get_distance(pnt1);

double dd = d0 - d1;

if(dd > eps)
return 1;
else if (dd < -eps)
return -1;
else
return 0.;

}

The question is: why two different qsort() implementations (AIX and
Linux) should give different results? In particular, the Linux
implementation seems to fail to to find the right order. Any hint?

The comparison function has to be consistent. You're returning 0 for
points that are very close to each other but not actually equal.

For example, given:
x = 1.0e-6
y = 1.6e-6
z = 2.2e-6
you would report x == y, y == z, but x < z, which causes undefined
behavior in qsort().

I suggest dropping eps and just doing a comparison:

if (d0 < d1)
return -1;
else if (d0 == d1)
return 0;
else
return 1;

Some other oddities:

Both parameters of compare_function should be const.

"return 0.;" should be "return 0;". You're returning a floating-point
zero, which will be converted to int, so it has the same effect, but
it's cleaner just to return an int.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Duncan Muirhead]

On Wed, 28 Jun 2006 00:13:47 -0700, Max wrote:

Hi everybody,

suppose you have to order a list of integers which refer to points
located in the 3D space. The compare() function is based on the
distance that these points have with respect to the origin (0,0,0). So,
using the standart qsort() function, I think this task should be
accomplished as follows:

qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function);

where

static int compare_function(void *b0, const void *b1)
{
double eps = 1e-6;

int pnt0 = *((int *)b0);
int pnt1 = *((int *)b1);

double d0 = get_distance(pnt0);
double d1 = get_distance(pnt1);

double dd = d0 - d1;

if(dd > eps)
return 1;
else if (dd < -eps)
return -1;
else
return 0.;

}

The question is: why two different qsort() implementations (AIX and
Linux) should give different results? In particular, the Linux
implementation seems to fail to to find the right order. Any hint?
Thanks
Max

I'm not sure if this is specified for qsort but I've learnt not to use
it unless the compare function really is an order, ie unless the compare
function only returns 0 if the two arguments are identical. Otherwise, in
may experience at least, qsort can fail spectacularly (cause a core dump),
and anyway I'd suspect that if it returns the final order of the array,
(ie the order of the elements that are all equal as fare as the compare is
concerned) is not just implementation but phase-of-the-moon dependent if
the compare can return non zero for two different arguments
Could you perhaps extend your comparison, function, eg if two points
are the same distance from the origin, compare x then y
then z coordinates too?
Duncan

[Max]

Duncan Muirhead schrieb:

I'm not sure if this is specified for qsort but I've learnt not to use
it unless the compare function really is an order, ie unless the compare
function only returns 0 if the two arguments are identical.
You are right, but how to accomplish with that if you are dealing with
doubles? Such a routine is expected to order points belonging to two
different surfaces which are related by a geometrical transformation
(translation or rotation). Ordering them according to the distance from
the origin should store the pairs in sequence and make simple to split
the resulting ordered list in two vector. If you know other (cheap?)
algorithms, I will try them...
Otherwise, in
may experience at least, qsort can fail spectacularly (cause a core dump),
and anyway I'd suspect that if it returns the final order of the array,
(ie the order of the elements that are all equal as fare as the compare is
concerned) is not just implementation but phase-of-the-moon dependent if
the compare can return non zero for two different arguments
Could you perhaps extend your comparison, function, eg if two points
are the same distance from the origin, compare x then y
then z coordinates too?
Duncan

You are right and it is what the real code does. I gave an simpler
example (already tried) to focus on the topic.

Thanks
Max

[pete]

Max wrote:

Duncan Muirhead schrieb:

I'm not sure if this is specified for qsort
but I've learnt not to use
it unless the compare function really is an order,
ie unless the compare
function only returns 0 if the two arguments are identical.
You are right, but how to accomplish with that if you are dealing with
doubles?

If you know other (cheap?)
algorithms, I will try them...

Get rid of your epsilon and difference equations.
You don't want to equate near values
in an ordering function.
That's a bad thing to do.
If one number is just a smidgeon less than another,
then what's your objection to ordering it first?

static int compare_function(const void *b0, const void *b1)
{
int pnt0 = *((int *)b0);
int pnt1 = *((int *)b1);
double d0 = get_distance(pnt0);
double d1 = get_distance(pnt1);

return d1 > d0 ? -1 : d0 > d1;
}
--
pete

[Eric Sosman]

Max wrote:

[...]
You are right and it is what the real code does. I gave an simpler
example (already tried) to focus on the topic.

The simpler version has a bug, as has already been
explained. Now: Is that bug an artifact of the simplification
process, or is it also present in the original? Oh, drat: my
Ouija board is in the shop getting its phlogiston generator
repaired ...

--
Eric Sosman
es*****@acm-dot-org.invalid

[Max]

> [...]

The simpler version has a bug, as has already been
explained. Now: Is that bug an artifact of the simplification
process, or is it also present in the original?

If you refer to the undefined behaviour, yes, I have tried to test the
code dropping out eps. I have got a different point list but it is
still wrong. As I have already explained above, I have the possibility
to visually check if the point list is correct or not.

The line

return 0.;

was just a typing error here.

Bye
Max

[Keith Thompson]

"Max" <ip*******@gmail.com> writes:

[...]
The simpler version has a bug, as has already been
explained. Now: Is that bug an artifact of the simplification
process, or is it also present in the original?

If you refer to the undefined behaviour, yes, I have tried to test the
code dropping out eps. I have got a different point list but it is
still wrong. As I have already explained above, I have the possibility
to visually check if the point list is correct or not.

How is it "wrong"? Are you sure your get_distance function is
correct? Do the points that are mis-ordered have nearly identical
distances? Are you sure you're invoking qsort() correctly?

We can only point out flaws in code that you post. If you show us an
actual program that exhibits the problem, we can help. If not, we
can't guess.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Max]

How is it "wrong"? Are you sure your get_distance function is
correct? Do the points that are mis-ordered have nearly identical
distances? Are you sure you're invoking qsort() correctly?
Yes, the functions works correctly and they have been tested
extensively. The qsort() call is not an issue.

We can only point out flaws in code that you post. If you show us an
actual program that exhibits the problem, we can help. If not, we
can't guess.
I know what you mean, and you are right. Unfortunately the code is not
free and I am not allowed to distribute it...
Anyway, I will investigate better the "undefined behaviour" tip, since
this should be the problem. Up to now the algorithm has been used with
small lists and its application to larger vectors may results in such a
strange behaviour.
Thanks
Max


--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.