Comparison function in qsort()

[Spoon]

Hello,

I've come across the following comparison function used as the 4th
parameter in qsort()

int cmp(const void *px, const void *py)
{
const double *x = px, *y = py;
return (*x > *y) - (*x < *y);
}

It came "as-is" i.e. no comments.

Is it good style to write comparison functions that way?

Should the return values be made more explicit? Or would it be enough to
add comments explaining why the function (usually) works?

--
Regards, Spoon

[Michael Mair]

Spoon schrieb:

Hello,

I've come across the following comparison function used as the 4th
parameter in qsort()

int cmp(const void *px, const void *py)
{
const double *x = px, *y = py;
return (*x > *y) - (*x < *y);
}

It came "as-is" i.e. no comments.

Is it good style to write comparison functions that way?

Should the return values be made more explicit? Or would it be enough to
add comments explaining why the function (usually) works?

Depends. Possible points of view:
1) "Everyone" knows that relational operators in C return either 0
or 1, thus Everyone can figure it out.
2) If it is too complicated for Everyone, then it should be commented.
3) If it has to be explained so that Everyone understands it, then it
should not be written this way -- too clever for its own good.
4) Write the code as explicit and simple as possible:
- modern compilers on host PCs can optimise it better,
- there is no danger of misunderstanding
5) As 4) but if you found out by measuring that cmp() is a bottleneck,
then try this out as one alternative; use the alternative which is
fastest and comment it clearly and explain why you did what you did.
6) As 5) but consider that probably the problem is using qsort(), as
well; you have indirection and function call overhead. It may be better
to write a dedicated double array sort. This makes the above construct
once more unnecessary. Use a well-tested out-of-the-book/from-the-CD
algorithm.

Which alternative you use depends on the people you work with
and the constraints you work under (coding guidelines etc.).
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Fred Kleinschmidt]

"Spoon" <none> wrote in message
news:44***********************@news.free.fr...

Hello,

I've come across the following comparison function used as the 4th
parameter in qsort()

int cmp(const void *px, const void *py)
{
const double *x = px, *y = py;
return (*x > *y) - (*x < *y);
}

It came "as-is" i.e. no comments.

Is it good style to write comparison functions that way?

Should the return values be made more explicit? Or would it be enough to
add comments explaining why the function (usually) works?

--
Regards, Spoon

It's (almost) never a good style to write ANY function with no comments at
all.
Most software development groups have some sort of coding standards.
Mine require ALL functions to specify what the function is for,
describe all parameters, and describe the return value.
In addition, such show-off coding without explaining why it works
can often lead to trouble later on when someone else with less
expertise tries to modify the code, or port it to a different language
(where, for example, boolean true is not 1).

In the above case, the coding is rather silly.
return (*x - *y);
works just as well, with or without the parentheses,
if the function is used only as a qsort() comparer.

If the answer MUST be -1, 0, or +1 for some reason (like it is used
by in some other comparison that requires that), it should be
documented as such.
--
Fred L. Kleinschmidt
Boeing Associate Technical Fellow
Technical Architect, Software Reuse Project

[Keith Thompson]

"Fred Kleinschmidt" <fr******************@boeing.com> writes:

"Spoon" <none> wrote in message
news:44***********************@news.free.fr...

Hello,

I've come across the following comparison function used as the 4th
parameter in qsort()

int cmp(const void *px, const void *py)
{
const double *x = px, *y = py;
return (*x > *y) - (*x < *y);
}

It came "as-is" i.e. no comments.

Is it good style to write comparison functions that way?

Should the return values be made more explicit? Or would it be enough to
add comments explaining why the function (usually) works?

[snip] In the above case, the coding is rather silly.
return (*x - *y);
works just as well, with or without the parentheses,
if the function is used only as a qsort() comparer.

No, it wouldn't. Consider what happens if the subtraction overflows.
Or, since the operands are of type double, consider *x==0.5, *y==0.25;
the result of the subtraction is 0.25, which yields 0 when
(implicitly) converted to 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.

[Flash Gordon]

Fred Kleinschmidt wrote:

"Spoon" <none> wrote in message
news:44***********************@news.free.fr...

Hello,

I've come across the following comparison function used as the 4th
parameter in qsort()

int cmp(const void *px, const void *py)
{
const double *x = px, *y = py; ^^^^^^

Note that this is comparing doubles
return (*x > *y) - (*x < *y);
}

It came "as-is" i.e. no comments.

Is it good style to write comparison functions that way?

Should the return values be made more explicit? Or would it be enough to
add comments explaining why the function (usually) works?

--
Regards, Spoon
It's (almost) never a good style to write ANY function with no comments at
all.
Most software development groups have some sort of coding standards.
Mine require ALL functions to specify what the function is for,
describe all parameters, and describe the return value.

Agreed.
In addition, such show-off coding without explaining why it works
can often lead to trouble later on when someone else with less
expertise tries to modify the code,
In this case, as the function is being passed to qsort its purpose is
fairly obvious, and anyone who could not at least work out what it is
doing and how it works is not ready to be working on their own as a
maintenance programmer.
or port it to a different language
(where, for example, boolean true is not 1).
When translating between two languages it is better in my experience to
look at the purpose of regions of code and write appropriate
replacements than to simply translate on a function by function basis.
In the above case, the coding is rather silly.
return (*x - *y);
works just as well, with or without the parentheses,
if the function is used only as a qsort() comparer.
No it doesn't. Or do you think that 0.1 - 0 is guaranteed to produce a
positive number rather than 0?

Your suggestion is not even guaranteed for int, since INT_MIN - 1 will
overflow, and the behaviour on overflow is undefined.
If the answer MUST be -1, 0, or +1 for some reason (like it is used
by in some other comparison that requires that), it should be
documented as such.

Agreed, but IMHO the code was probably written that way for correctness
rather than to produce exactly +0, -1 or 0.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

[Keith Thompson]

Keith Thompson <ks***@mib.org> writes:

"Fred Kleinschmidt" <fr******************@boeing.com> writes:

"Spoon" <none> wrote in message
news:44***********************@news.free.fr...

Hello,

I've come across the following comparison function used as the 4th
parameter in qsort()

int cmp(const void *px, const void *py)
{
const double *x = px, *y = py;
return (*x > *y) - (*x < *y);
}

It came "as-is" i.e. no comments.

Is it good style to write comparison functions that way?

Should the return values be made more explicit? Or would it be enough to
add comments explaining why the function (usually) works?

[snip]

In the above case, the coding is rather silly.
return (*x - *y);
works just as well, with or without the parentheses,
if the function is used only as a qsort() comparer.

No, it wouldn't. Consider what happens if the subtraction overflows.
Or, since the operands are of type double, consider *x==0.5, *y==0.25;
the result of the subtraction is 0.25, which yields 0 when
(implicitly) converted to int.

The code above, "return (*x > *y) - (*x < *y);", is also probably
better-behaved in the presence of infinities and NaNs, at least quiet
NaNs.

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

[CBFalconer]

Fred Kleinschmidt wrote:

"Spoon" <none> wrote in message

I've come across the following comparison function used as the 4th
parameter in qsort()

int cmp(const void *px, const void *py)
{
const double *x = px, *y = py;
return (*x > *y) - (*x < *y);
}

It came "as-is" i.e. no comments.

Is it good style to write comparison functions that way?

Should the return values be made more explicit? Or would it be
enough to add comments explaining why the function (usually) works?

.... snip ...
In the above case, the coding is rather silly.
return (*x - *y);
works just as well, with or without the parentheses,
if the function is used only as a qsort() comparer.

No it doesn't. That is subject to overflow and undefined
behaviour. The recommended code may have been due to me, and
caters to avoidance of flushing of instruction streams. It
specifies the types being compared in exactly one place, and works
all the time.

IMO there are very few non-beginners who would not understand the
code. There are many coders who fail to understand the reasons for
the code.

--
"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
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[Robert Latest]

On Thu, 13 Apr 2006 00:37:39 +0100,
Flash Gordon <sp**@flash-gordon.me.uk> wrote
in Msg. <qi************@news.flash-gordon.me.uk>

In this case, as the function is being passed to qsort its purpose is
fairly obvious, and anyone who could not at least work out what it is
doing and how it works is not ready to be working on their own as a
maintenance programmer.

A side note: I always like to name my qsort cmp functions starting with
'by_' because it makes for better English:

qsort(customer, ..., by_name);

robert

[Richard Bos]

Robert Latest <bo*******@yahoo.com> wrote:

Flash Gordon <sp**@flash-gordon.me.uk> wrote

In this case, as the function is being passed to qsort its purpose is
fairly obvious, and anyone who could not at least work out what it is
doing and how it works is not ready to be working on their own as a
maintenance programmer.

A side note: I always like to name my qsort cmp functions starting with
'by_' because it makes for better English:

qsort(customer, ..., by_name);

Hey, that's not a bad idea at all! I might adopt that.

Richard

[Richard Heathfield]

Richard Bos said:

Robert Latest <bo*******@yahoo.com> wrote:

A side note: I always like to name my qsort cmp functions starting with
'by_' because it makes for better English:

qsort(customer, ..., by_name);
Hey, that's not a bad idea at all!

Very good idea, in fact. Nice one, Robert.
I might adopt that.

Too late. I already have the papers right here, signed by a judge.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Richard Tobin]

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:

The code above, "return (*x > *y) - (*x < *y);", is also probably
better-behaved in the presence of infinities and NaNs, at least quiet
NaNs.

And this is just the sort of thing that many programmers will not be
aware of, so the lack of a comment is inexcusable.

-- Richard

[Dik T. Winter]

In article <e2***********@pc-news.cogsci.ed.ac.uk> ri*****@cogsci.ed.ac.uk (Richard Tobin) writes:

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:

The code above, "return (*x > *y) - (*x < *y);", is also probably
better-behaved in the presence of infinities and NaNs, at least quiet
NaNs.

And this is just the sort of thing that many programmers will not be
aware of, so the lack of a comment is inexcusable.

What is better behaved? It depends on how the compiler works what is
returned in the case of NaNs, and it is not sure that what is returned
is also consistent. (And be aware that the comparison function must
be consistent, otherwise sorting can fail.) But it works well in the
case of infinities and when overflow occurs. Consider a compiler that
uses the compare greater instruction. If x is a NaN, both comparisons
will return false, and so the returned value is 0. Now when the
compiler uses the compare greater or uncomparable instruction, in that
case both comparisons return true, and the function will again return 0.
So with these scenarios the comparison function will tell a NaN is
equal to any other number.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Robert Latest]

On Tue, 18 Apr 2006 11:55:15 GMT,
Dik T. Winter <Di********@cwi.nl> wrote
in Msg. <Ix********@cwi.nl>

So with these scenarios the comparison function will tell a NaN is
equal to any other number.

....which is exactly as reasonable as making NaN greater or smaller than
any other number, or erratically switching between behaviors. I admit
the latter case is the worst because it's hard to debug, but in any case
an array with NaNs in it is unsortable by size anyway.

robert

[P.J. Plauger]

"Robert Latest" <bo*******@yahoo.com> wrote in message
news:4a************@individual.net...

On Tue, 18 Apr 2006 11:55:15 GMT,
Dik T. Winter <Di********@cwi.nl> wrote
in Msg. <Ix********@cwi.nl>

So with these scenarios the comparison function will tell a NaN is
equal to any other number.
...which is exactly as reasonable as making NaN greater or smaller than
any other number,

Uh, no it's not. If the comparison function doesn't impose a strict
weak ordering on all values, a typical sort can loop or overwrite
storage. NaN should be either greater or less than any finite value,
comparing equal only to another NaN.
or erratically switching between behaviors. I admit
the latter case is the worst because it's hard to debug, but in any case
an array with NaNs in it is unsortable by size anyway.

Not true. If you're lucky, your compiler will either:

a) evaluate x != x as true for a NaN, or

b) supply some form of the C99 isnan(x) generic-function macro.

You comparison function is messier, but writable. And robust in the
presence of NaNs.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

[Robert Latest]

On Tue, 18 Apr 2006 09:43:22 -0400,
P.J. Plauger <pj*@dinkumware.com> wrote
in Msg. <X6******************************@giganews.com>

You comparison function is messier, but writable. And robust in the
presence of NaNs.

After reading the C Standard and after a bit of thinking I decided
that you're right. A comparison function should compare NaNs greater or
smaller than any number, and comparison of two NaNs should evaluate as
equal.

robert