Skip to content

When comparison functions go bad

October 26, 2005

Here is another golden oldie that came up this week. What is wrong with using this function as the comparison function for qsort(3c):


static int cmp1(void *a, void *b) { 	if (*(int *)a <= *(int *)b) 		return(-1); 	else 		return (1); } 

Well for the comparison of the inputs:


int a = 1; int b = 1; 

cmp(&a, &b) will return -1


and


cmp(&b, &a) will also return -1

Thus as far as qsort is concerned a < b and b < a, which clearly is impossible. The interesting part of this is the effect it has on the performance of qsort.


Comparing the performance of qsort using the above function with qsort with the correct function:


static int cmp2(const void *a, const void *b) {         return (*(int *)a – *(int *)b); } 

Sorting first a 1024 element array containing random values between 0 and 255


cmp1 called 10265 times

cmp2 called 8672 times


Well that is not so good. It gets worse if the values are limited to between 0 and 128, thus increasing the number of duplicates:


cmp1 called 10434 times

cmp2 called 7790 times


Which is even worse.


Anyway the morale of this story is to make sure your comparison functions return 0 if two keys are equal.

Advertisements

From → Solaris

2 Comments
  1. Vasileios Anagnostopoulos permalink

    Thanks Chris. Very good observation. I can’t wait for more gotchas.

  2. gavinm permalink

    Chris – I know you are a closet Perl fan, really.
    Maybe a future ANSI C revision could introduce
    the <=> operator as featured in Perl 🙂
    Gavin

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: