Bug in qsort-function under Solaris 2.4 ?
Frank Merfort
Hello everybody,
I'm programming under TCL/TK. Now I have observed that the interpreter
sometimes quits with a Segmentation Fault. After examining this fault I
found out that the qsort-function which is used by TCL produced this
fault.
Program:
--------
int listArgc;
char **listArgv;
.
.
.
for(i = 0; i < listArgc; i++)
printf("%d %x\n", i, (int)&listArgv[i]);
qsort((VOID *) listArgv, listArgc, sizeof (char *), SortCompareProc);
.
.
.
SortCompareProc(first, second)
CONST VOID *first, *second;
{
printf("SortCompareProc: %x %x\n", (int)first, (int)second );
.
.
.
This produced the following output:
0 dfb38
1 dfb3c
2 dfb40
3 dfb44
4 dfb48
5 dfb4c
6 dfb50
7 dfb54
8 dfb58
9 dfb5c
10 dfb60
11 dfb64
12 dfb68
13 dfb6c
14 dfb70
15 dfb74
16 dfb78
17 dfb7c
18 dfb80
19 dfb84
20 dfb88
21 dfb8c
22 dfb90
23 dfb94
24 dfb98
25 dfb9c
26 dfba0
27 dfba4
28 dfba8
29 dfbac
30 dfbb0
31 dfbb4
32 dfbb8
SortCompareProc: dfb38 dfb78
SortCompareProc: dfb78 dfbb8
SortCompareProc: dfb38 dfbb8
SortCompareProc: dfb38 dfb78
SortCompareProc: dfb78 dfbb8
SortCompareProc: dfb3c dfb78
SortCompareProc: dfb78 dfbb4
.
.
.
SortCompareProc: dfb60 dfb64
SortCompareProc: dfb38 dfb3c
SortCompareProc: dfb3c dfb40
SortCompareProc: dfb3c dfb44
SortCompareProc: dfb38 dfb3c
SortCompareProc: dfb34 dfb3c
Segmentation Fault - core dumped
The last address (dfb34) isn't a valid address in the array.
Has anyone observed the same effect? What's wrong with qsort?
Greetings
Frank Merfort
email: 10072...@compuserve.com
John Carr
Many versions of qsort will fail badly if the sort function returns
inconsistent results. Given the same inputs, the function must always
indicate the same order.
--
John Carr (j...@mit.edu)
w...@groupsys.com
In article <52bk6e$o...@senator-bedfellow.mit.edu>,
John Carr <j...@mit.edu> wrote:
>Many versions of qsort will fail badly if the sort function returns
>inconsistent results. Given the same inputs, the function must always
>indicate the same order.
"Consistent" also means that (*compar)(a, b) == - (*compar)(b, a) must
always be true.
In other words, when (*compar)(a, b) is -1 then (*compar)(b, a) must be 1,
etc.
I've stumbled across this problem on more than one occasion.
Unfortunately, the more complicated your compar function is, the
harder it is to find such an inconsistency.
--
William LeFebvre
Group sys Consulting
<w...@groupsys.com>
+1 770 813 3224
Ben Chase
: John Carr <j...@mit.edu> wrote:
: >Many versions of qsort will fail badly if the sort function returns
: >inconsistent results. Given the same inputs, the function must always
: >indicate the same order.
w...@groupsys.com wrote:
: "Consistent" also means that (*compar)(a, b) == - (*compar)(b, a) must
: always be true.
: In other words, when (*compar)(a, b) is -1 then (*compar)(b, a) must be 1,
: etc.
: I've stumbled across this problem on more than one occasion.
: Unfortunately, the more complicated your compar function is, the
: harder it is to find such an inconsistency.
(Howdy, Bill, :-)
The need to have a consistent comparison function seemed obvious
enough to me. But I recently had an interesting experience with qsort
(Solaris2.3, SPARC 20/502, 64Mbytes RAM, if it matters). I needed to
sort 200,000 records, each 12 bytes each. I initially coded my
comparison function incorrectly, so it used 18 bits of info to order
the records. This took about 7-8 seconds. Then I corrected my
comparison function, to use only 13 bits of the original 18 bits (that
is, many more records were considered to be equal than before).
Sorting the same data now takes 45 seconds, about 6x as long. I was
rather surprised by this difference, and still have difficultly
believing I haven't fumbled something somewhere. (Yes, the records
are definitely in random order, otherwise why would I be sorting them?
:-)
Richard Jones
w...@groupsys.com writes:
>In article <52bk6e$o...@senator-bedfellow.mit.edu>,
>John Carr <j...@mit.edu> wrote:
>>Many versions of qsort will fail badly if the sort function returns
>>inconsistent results. Given the same inputs, the function must always
>>indicate the same order.
>"Consistent" also means that (*compar)(a, b) == - (*compar)(b, a) must
>always be true.
>In other words, when (*compar)(a, b) is -1 then (*compar)(b, a) must be 1,
>etc.
>I've stumbled across this problem on more than one occasion.
>Unfortunately, the more complicated your compar function is, the
>harder it is to find such an inconsistency.
ok, does the following code totally miss the point? :
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int compare_word(void *s1[],void *s2[]);
int compare_letter(void *let1,void *let2);
void main()
{
int i,j,k;
char *string_array[]={"apple","banana","orange","pear","redberry"};
for (i=0;i<5;i++)
{
for (j=0;j<strlen(string_array[i]);j++)
{
for (k=0;k<strlen(string_array[i]);k++)
{
if (compare_letter(&string_array[i][j],&string_array[i][k]) !=
-compare_letter(&string_array[i][k],&string_array[i][j]))
{
printf("Compare Letter function bad\n");
fflush(stdout);
exit(1);
}
}
}
}
printf("Compare Letter function OK\n");
fflush(stdout);
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
if (compare_word((void *)string_array[i],(void *)string_array[j]) !=
-compare_word((void *)string_array[j],(void *)string_array[i]))
{
printf("Compare function bad\n");
fflush(stdout);
exit(1);
}
}
}
printf("Compare function OK\n");
fflush(stdout);
qsort(string_array,5,sizeof(char *),compare_word);
for (i=0;i<5;i++)
printf("%s\n",string_array[i]);
}
int compare_word(void *s1[],void *s2[])
{
char *s1_temp;
char *s2_temp;
s1_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
s2_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
strcpy(s1_temp,(char *)*s1);
strcpy(s2_temp,(char *)*s2);
qsort(s1_temp,strlen(s1_temp),sizeof(char),compare_letter);
qsort(s2_temp,strlen(s2_temp),sizeof(char),compare_letter);
return(strcmp(s1_temp,s2_temp));
}
int compare_letter(void *let1,void *let2)
{
if (*(char *)let1 < *(char *)let2)
{
return -1;
}
else
{
if (*(char *)let1 > *(char *)let2)
return 1;
else
return 0;
}
}
under solaris and sunos it produces this:
79> ./test
Compare Letter function OK
Segmentation fault
80>
however under linux it produces this:
$ ./test
Compare Letter function OK
Compare function OK
banana
orange
apple
pear
redberry
$
unless i've totally missed something this *is* a bug in suns libc
oh btw the above was compiled with gcc on all 3 platforms..
Andrew Gierth
>>>>> "Richard" == Richard Jones <jon...@latcs1.cs.latrobe.edu.au> writes:
Richard> ok, does the following code totally miss the point? :
...
Richard> int compare_word(void *s1[],void *s2[]);
... ^^^^^^^^^^
Richard> void main()
Richard> {
Richard> int i,j,k;
Richard> char *string_array[]={"apple","banana","orange","pear","redberry"};
...
Richard> if (compare_word((void *)string_array[i],(void *)string_array[j]) !=
Richard> -compare_word((void *)string_array[j],(void *)string_array[i]))
... ^^^^^^^^^^^^^^^^^^^^^^^
Richard> int compare_word(void *s1[],void *s2[])
Richard> {
Richard> char *s1_temp;
Richard> char *s2_temp;
Richard> s1_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
Richard> s2_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
^^^^^^^^^^^^^^^^^^^^^^^
Richard> strcpy(s1_temp,(char *)*s1);
Richard> strcpy(s2_temp,(char *)*s2);
... ^^^^^^^^^^^
Richard> under solaris and sunos it produces this:
Richard> 79> ./test
Richard> Compare Letter function OK
Richard> Segmentation fault
Richard 80>
Richard> however under linux it produces this:
Richard> $ ./test
Richard> Compare Letter function OK
Richard> Compare function OK
Richard> banana
Richard> orange
Richard> apple
Richard> pear
Richard> redberry
Richard> $
Richard> unless i've totally missed something this *is* a bug in suns libc
You've totally missed something.
You are taking an expression of type char*, converting it to void*,
converting that to void **, dereferencing that (which you think gives
you a void*, but in fact gives garbage), then you're converting that
back to a (meaningless) char*. Is it any surprise that you get SEGV as
soon as you try to use it?
It just so happens that Intel chips are naturally more tolerant of bogus
pointers than SPARCs (since alignment of data is never enforced).
Try changing "(void *)string_array[i]" to "(void **)(string_array+i)" and
see what happens.
--
Andrew Gierth (and...@microlise.co.uk)
"Ceterum censeo Microsoftam delendam esse" - Alain Knaff in nanam
Dik T. Winter
In article <ufwwxdk...@zen.microlise.co.uk> and...@microlise.co.uk (Andrew Gierth) writes:
> Richard> void main()
> Try changing "(void *)string_array[i]" to "(void **)(string_array+i)" and
> see what happens.
Let him at the same time change "void main" to "int main".
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Bruce Adler [Contractor]
In article <jonesr.8...@lion.cs.latrobe.edu.au>,
Richard Jones <jon...@latcs1.cs.latrobe.edu.au> wrote:
> ...
>ok, does the following code totally miss the point? :
[ code deleted ]
> ...
>unless i've totally missed something this *is* a bug in suns libc
>
>oh btw the above was compiled with gcc on all 3 platforms..
The latest Solaris compiler generates lots of warnings on your original
code. I found three problems:
1. compare_word() derefs variables which aren't pointers.
2. compare_word() compares the modified strings, s1_temp and s2_temp,
rather than strings passed in from qsort(), *s1 and *s2.
3. The version of qsort in the 2.4 libc is not reenterant. It was fixed
for the Solaris 2.5.1 release.
With the following diffs I get the correct output on Solaris 2.5.1 (on
SPARC and x86). When run on Solaris 2.4 and 2.5 it still core dumps
because the version of qsort() on those releases incorrectly saves
several values in static variables. If I remove the qsort() calls from
within the compare_word() it works on all releases.
5,6c5,6
< int compare_word(void *s1[],void *s2[]);
< int compare_letter(void *let1,void *let2);
---
> int compare_word(const void *s1,const void *s2);
> int compare_letter(const void *let1,const void *let2);
36,37c36,37
< if (compare_word((void *)string_array[i],(void *)string_array[j]) !=
< -compare_word((void *)string_array[j],(void *)string_array[i]))
---
> if (compare_word((void *)&string_array[i],(void *)&string_array[j]) !=
> -compare_word((void *)&string_array[j],(void *)&string_array[i]))
55c55
< int compare_word(void *s1[],void *s2[])
---
> int compare_word(const void *s1,const void *s2)
62,63c62,63
< s1_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
< s2_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
---
> s1_temp=malloc((strlen(*(char **)s1)+1)*sizeof(char));
> s2_temp=malloc((strlen(*(char **)s1)+1)*sizeof(char));
65,66c65,66
< strcpy(s1_temp,(char *)*s1);
< strcpy(s2_temp,(char *)*s2);
---
> strcpy(s1_temp,*(char **)s1);
> strcpy(s2_temp,*(char **)s2);
73,74c73
<
< return(strcmp(s1_temp,s2_temp));
---
> return(strcmp(*(char **)s1,*(char **)s2));
77c76
< int compare_letter(void *let1,void *let2)
---
> int compare_letter(const void *let1,const void *let2)
BA
Richard Jones
jon...@latcs1.cs.latrobe.edu.au (Richard Jones) writes:
>w...@groupsys.com writes:
>>In article <52bk6e$o...@senator-bedfellow.mit.edu>,
>>John Carr <j...@mit.edu> wrote:
>>>Many versions of qsort will fail badly if the sort function returns
>>>inconsistent results. Given the same inputs, the function must always
>>>indicate the same order.
>>"Consistent" also means that (*compar)(a, b) == - (*compar)(b, a) must
>>always be true.
>>In other words, when (*compar)(a, b) is -1 then (*compar)(b, a) must be 1,
>>etc.
>>I've stumbled across this problem on more than one occasion.
>>Unfortunately, the more complicated your compar function is, the
>>harder it is to find such an inconsistency.
>ok, does the following code totally miss the point? :
[SNIPS bug ridden code]
well as pointed out to me by 4 e-mails the original
example was full of bugs, here is some code that has less
(perhaps even none!):
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
int compare_word(char **s1,char **s2);
int compare_letter(char *let1,char *let2);
void main()
{
int i,j,k;
char *string_array[]={"apple","banana","orange","pear","redberry"};
for (i=0;i<5;i++)
{
for (j=0;j<strlen(string_array[i]);j++)
{
for (k=0;k<strlen(string_array[i]);k++)
{
if (compare_letter(&string_array[i][j],&string_array[i][k]) !=
-compare_letter(&string_array[i][k],&string_array[i][j]))
{
printf("Compare Letter function bad\n");
fflush(stdout);
exit(1);
}
}
}
}
printf("Compare Letter function OK\n");
fflush(stdout);
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
if (compare_word(&string_array[i],&string_array[j]) !=
-compare_word(&string_array[j],&string_array[i]))
{
printf("Compare function bad\n");
fflush(stdout);
exit(1);
}
}
}
printf("Compare function OK\n");
fflush(stdout);
qsort(string_array,5,sizeof(char *),compare_word);
for (i=0;i<5;i++)
printf("%s\n",string_array[i]);
}
int compare_word(char **s1,char **s2)
{
char *s1_temp;
char *s2_temp;
int result;
s1_temp=strdup(*s1);
s2_temp=strdup(*s1);
qsort(s1_temp,strlen(s1_temp),sizeof(char),compare_letter);
qsort(s2_temp,strlen(s2_temp),sizeof(char),compare_letter);
result=strcmp(s1_temp,s2_temp);
free(s1_temp);
free(s2_temp);
return(result);
}
int compare_letter(char *let1,char *let2)
{
if (*let1 < *let2)
{
return -1;
}
else
{
if (*let1 > *let2)
return 1;
else
return 0;
}
}
produces:
5> ./test2
Compare Letter function OK
Compare function OK
Segmentation fault
still works fine under linux.
>unless i've totally missed something this *is* a bug in suns libc
>oh btw the above was compiled with gcc on all 3 platforms..
as above
Richard Jones
ad...@West.Sun.COM (Bruce Adler [Contractor]) writes:
>In article <jonesr.8...@lion.cs.latrobe.edu.au>,
>Richard Jones <jon...@latcs1.cs.latrobe.edu.au> wrote:
>> ...
>>ok, does the following code totally miss the point? :
>[ code deleted ]
>The latest Solaris compiler generates lots of warnings on your original
>code. I found three problems:
[SNIPPED evidence of my stupidity]
>With the following diffs I get the correct output on Solaris 2.5.1 (on
>SPARC and x86). When run on Solaris 2.4 and 2.5 it still core dumps
>because the version of qsort() on those releases incorrectly saves
>several values in static variables. If I remove the qsort() calls from
>within the compare_word() it works on all releases.
[SNIP]
>BA
Yup and if you remove the qsort() calls from within compare_word()
the program no longer works as required, anyways the bottom line is
that the latest version of qsort() works?
(btw the man page on the solaris box I tried this one said that the qsort
call was thread safe, I doubt it.)
Richard Jones
Casper H.S. Dik
jon...@latcs1.cs.latrobe.edu.au (Richard Jones) writes:
>int compare_word(void *s1[],void *s2[]);
>int compare_letter(void *let1,void *let2);
> char *string_array[]={"apple","banana","orange","pear","redberry"};
> if (compare_word((void *)string_array[i],(void *)string_array[j]) !=
> -compare_word((void *)string_array[j],(void *)string_array[i]))
> printf("Compare function OK\n");
>int compare_word(void *s1[],void *s2[])
>{
> s1_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
> s2_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
>
>under solaris and sunos it produces this:
>79> ./test
>Compare Letter function OK
>Segmentation fault
>unless i've totally missed something this *is* a bug in suns libc
You miss something.
Re-read the code I quoted.
Then ask your self: if I pass a "char*" to compare_word() and then
dereference it to get an argument to strlen(), what do I get?
The answer is: a core dump. ("appl" is not a valid pointer_.
Had you used a debugger, you would have noticed that your program
crashed like this:
[1] strlen(0x6170706c, 0x42, 0x1b, 0x11024, 0x11024, 0x0), at 0xef763bb8
=>[2] compare_word(s1 = 0x211cc, s2 = 0x211cc), line 62 in "cmp.c"
[3] main(), line 37 in "cmp.c"
No involvement of qsort at all. How Linux lets you get away with this,
I wonder.
Casper
--
Casper Dik - Sun Microsystems - via my guest account at the University
of Amsterdam. My work e-mail address is: Caspe...@Holland.Sun.COM
Statements on Sun products included here are not gospel.
Unsolicited e-mail advertisements will be proofread for $250.
John Winters
In article <jonesr.8...@lion.cs.latrobe.edu.au>,
Richard Jones <jon...@latcs1.cs.latrobe.edu.au> wrote:
>
>>w...@groupsys.com writes:
>
>>>In article <52bk6e$o...@senator-bedfellow.mit.edu>,
>>>John Carr <j...@mit.edu> wrote:
>>>>Many versions of qsort will fail badly if the sort function returns
>>>>inconsistent results. Given the same inputs, the function must always
>>>>indicate the same order.
>
>>>"Consistent" also means that (*compar)(a, b) == - (*compar)(b, a) must
>>>always be true.
>
>>>In other words, when (*compar)(a, b) is -1 then (*compar)(b, a) must be 1,
>>>etc.
>
>>>I've stumbled across this problem on more than one occasion.
>>>Unfortunately, the more complicated your compar function is, the
>>>harder it is to find such an inconsistency.
>
>
>
>well as pointed out to me by 4 e-mails the original
>example was full of bugs, here is some code that has less
>(perhaps even none!):
[SNIP still bug ridden code]
Since you say you're using gcc, try compiling with "gcc -Wall -pedantic".
This will point out several more bugs for you, which you really should
remove before attempting any conclusions about the state of your run-time
library.
John
comp.lang.tcl removed from newsgroups.
--
John Winters. Wallingford, Oxon, England.
Bruce Adler [Contractor]
In article <jonesr.8...@lion.cs.latrobe.edu.au>,
Richard Jones <jon...@latcs1.cs.latrobe.edu.au> wrote:
>the program no longer works as required,
If this is a real problem and not just a hypothetical example you'll
either have to contact your Solaris support person and request a patch
to get it fixed on 2.4, or upgrade to 2.5.1.
>anyways the bottom line is that the latest version of qsort() works?
Yes, I ran your test routine on a Solaris 2.5.1 SPARC system and on a
Solaris 2.5.1 x86 system. It works correctly on both.
>(btw the man page on the solaris box I tried this one said that the qsort
>call was thread safe, I doubt it.)
MT safe and reentrant aren't the same thing.
BA
Jeff Bonwick
In article <jonesr.8...@lion.cs.latrobe.edu.au> jon...@latcs1.cs.latrobe.edu.au (Richard Jones) writes:
> (btw the man page on the solaris box I tried this one said that
> the qsort call was thread safe, I doubt it.)
The terminology in this area is annoyingly fluid, but generally speaking
"thread-safe" and "reentrant" don't mean quite the same thing, and neither
one is what you're looking for: the property you want is "recursive."
Thread-safe simply means that multiple threads can call the routine
without wrecking each other; this is indeed true of the earlier
(Solaris 2.4 and 2.5) qsort(3C) implementations.
Reentrant is stronger: it means that multiple threads can execute the
routine *at the same time*. Thus thread T1 can sort array A1 on cpu1
while T2 sorts A2 on cpu2. There's no process-wide 'qsort lock' on
which the threads have to serialize. The 2.5.1 qsort() is reentrant.
Meanwhile, the property you actually want is recursion, i.e. qsort()
calls your compare function, which calls back into qsort(). A qsort
implementation that is only thread-safe will not tolerate recursive
calls, because you'll end up trying to acquire a lock you already own.
(If you link your example program with -lthread, so the mutexes aren't
no-ops, it will hang forever.)
The 2.5.1 version of qsort() is both reentrant and recursive. However,
if you're trying to write portable code, you don't want to rely on this.
Calling qsort() from within a qsort comparison routine is asking for trouble.
Jeff Bonwick
Solaris Performance
Richard Pettit [Principle Associate]
Enclosed please find:
1) Your code, modified to correctness.
2) A replacement qsort() function which is:
*) reentrant
*) faster than the libc version
As was pointed out by Bruce Adler, the qsort() you're using isn't reentrant.
This program dumps core on my 5.5 x86 box as well.
It does not when using my qsort().
(BTW, the version shipped with Borland C isn't reentrant either :-)
Rich
+- + -- + -+
Richard Pettit | Richard...@West.Sun.COM | 15821 Ventura Blvd #270
SMCC Engineer | "Macrosolutions to Megaproblems" | Encino, CA 91436
{S(=@[length,%1]->id;apndl@[1,S@tl]@(while not@!and@&<=@distl@[1,tl] rotr))}
# This is a shell archive. Remove anything before this line,
# then unpack it by saving it in a file and typing "sh file".
#
# Wrapped by richp on Mon Sep 30 09:07:37 PDT 1996
# Contents: bad_code.c quick.c
echo x - bad_code.c
sed 's/^@//' > "bad_code.c" <<'@//E*O*F bad_code.c//'
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int compare_word (const void *a, const void *b);
static int compare_letter(const void *a, const void *b);
main()
{
int i;
int j;
int k;
char *string_array[] = {
"apple", "banana", "orange", "pear", "redberry"
};
for (i=0; i<5; i++) {
for (j=0; j<strlen(string_array[i]); j++) {
for (k=0; k<strlen(string_array[i]); k++) {
if (compare_letter(&string_array[i][j], &string_array[i][k]) !=
-compare_letter(&string_array[i][k], &string_array[i][j])) {
puts("Compare Letter function bad");
exit(1);
}
}
}
}
puts("Compare Letter function OK");
for (i=0; i<5; i++) {
for (j=0; j<5; j++) {
if (compare_word(&string_array[i], &string_array[j]) !=
-compare_word(&string_array[j], &string_array[i])) {
puts("Compare function bad");
exit(1);
}
}
}
puts("Compare function OK");
qsort(string_array, 5, sizeof(char *), compare_word);
for (i=0; i<5; i++)
puts(string_array[i]);
exit(0);
}
static int compare_word(const void *a, const void *b)
{
char **ap = (char **) a;
char **bp = (char **) b;
char abuf[BUFSIZ];
char bbuf[BUFSIZ];
strcpy(abuf, *ap);
strcpy(bbuf, *bp);
qsort(abuf, strlen(*ap), sizeof(char), compare_letter);
qsort(bbuf, strlen(*bp), sizeof(char), compare_letter);
return strcmp(abuf, bbuf);
}
int compare_letter(const void *a, const void *b)
{
char *ap = (char *) a;
char *bp = (char *) b;
return *ap - *bp;
}
@//E*O*F bad_code.c//
chmod u=rw,g=r,o=r bad_code.c
echo x - quick.c
sed 's/^@//' > "quick.c" <<'@//E*O*F quick.c//'
/*
* single-thread quick-sort. See man page for qsort(3c) for info.
*
* Written by: Richard Pettit (Richard...@West.Sun.COM)
*
* Copyright(c) 1994-1996 Richard Pettit
*
* Commercial reuse of this source code by authority of the author only.
*/
#include <stdlib.h>
#include <sys/types.h>
#define SUB(a, n) ((void *) (((unsigned char *) (a)) + ((n) * width)))
#define SWAP(a, i, j, width) \
{ \
int n; \
unsigned char uc; \
unsigned short us; \
unsigned long ul; \
unsigned long long ull; \
\
if (SUB(a, i) == pivot) \
pivot = SUB(a, j); \
else if (SUB(a, j) == pivot) \
pivot = SUB(a, i); \
\
/* one of the more convoluted swaps I've done */ \
switch(width) { \
case 1: \
uc = *((unsigned char *) SUB(a, i)); \
*((unsigned char *) SUB(a, i)) = *((unsigned char *) SUB(a, j)); \
*((unsigned char *) SUB(a, j)) = uc; \
break; \
case 2: \
us = *((unsigned short *) SUB(a, i)); \
*((unsigned short *) SUB(a, i)) = *((unsigned short *) SUB(a, j)); \
*((unsigned short *) SUB(a, j)) = us; \
break; \
case 4: \
ul = *((unsigned long *) SUB(a, i)); \
*((unsigned long *) SUB(a, i)) = *((unsigned long *) SUB(a, j)); \
*((unsigned long *) SUB(a, j)) = ul; \
break; \
case 8: \
ull = *((unsigned long long *) SUB(a, i)); \
*((unsigned long long *) SUB(a,i)) = *((unsigned long long *) SUB(a,j)); \
*((unsigned long long *) SUB(a, j)) = ull; \
break; \
default: \
for(n=0; n<width; n++) { \
uc = ((unsigned char *) SUB(a, i))[n]; \
((unsigned char *) SUB(a, i))[n] = ((unsigned char *) SUB(a, j))[n]; \
((unsigned char *) SUB(a, j))[n] = uc; \
} \
break; \
} \
}
void
qsort(void *a, size_t n, size_t width,
int (*compar)(const void *, const void *))
{
register int i;
register int j;
int z;
void *t;
void *b[3];
void *pivot = 0;
switch(n) {
case 1:
return;
case 2:
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
return;
case 3:
/* three sort */
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
SWAP(a, 2, 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
SWAP(a, 1, 0, width);
}
return;
default:
/* find the pivot point */
b[0] = SUB(a, 0);
b[1] = SUB(a, n / 2);
b[2] = SUB(a, n - 1);
/* three sort */
if ((*compar)(b[0], b[1]) > 0) {
t = b[0];
b[0] = b[1];
b[1] = t;
}
/* the first two are now ordered, now order the second two */
if ((*compar)(b[2], b[1]) < 0) {
t = b[1];
b[1] = b[2];
b[2] = t;
}
/* should the second be moved to the first? */
if ((*compar)(b[1], b[0]) < 0) {
t = b[0];
b[0] = b[1];
b[1] = t;
}
if ((*compar)(b[0], b[2]) != 0)
if ((*compar)(b[0], b[1]) < 0)
pivot = b[1];
else
pivot = b[2];
break;
}
if (pivot == 0)
for(i=1; i<n; i++) {
z = (*compar)(SUB(a, 0), SUB(a, i));
if (z != 0) {
pivot = (z > 0) ? SUB(a, 0) : SUB(a, i);
break;
}
}
if (pivot == 0)
return;
/* sort */
i = 0;
j = n - 1;
while(i <= j) {
while((*compar)(SUB(a, i), pivot) < 0)
++i;
while((*compar)(SUB(a, j), pivot) >= 0)
--j;
if (i < j) {
SWAP(a, i, j, width);
++i;
--j;
}
}
/* sort the sides judiciously */
switch(i) {
case 1:
break;
case 2:
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
break;
case 3:
/* three sort */
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
SWAP(a, 2, 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
SWAP(a, 1, 0, width);
}
break;
default:
qsort(a, i, width, compar);
break;
}
j = n - i;
switch(j) {
case 1:
break;
case 2:
if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
SWAP(a, i, i + 1, width);
}
break;
case 3:
/* three sort */
if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
SWAP(a, i, i + 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, i + 2), SUB(a, i + 1)) < 0) {
SWAP(a, i + 2, i + 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, i + 1), SUB(a, i)) < 0) {
SWAP(a, i + 1, i, width);
}
break;
default:
qsort(SUB(a, i), j, width, compar);
break;
}
}
@//E*O*F quick.c//
chmod u=rw,g=r,o=r quick.c
exit 0
Peter Seebach
I am unable to see why comp.lang.tcl is included here; perhaps it shouldn't
be?
In article <jonesr.8...@lion.cs.latrobe.edu.au>,
Richard Jones <jon...@latcs1.cs.latrobe.edu.au> wrote:
>ok, does the following code totally miss the point? :
Sure does.
>#include <stdio.h>
>#include <stdlib.h>
>#include <malloc.h>
What's that supposed to mean? malloc() is declared in <stdlib.h>, and
including <malloc.h> is not defined by the C language. Bad mojo; remove it.
>int compare_word(void *s1[],void *s2[]);
>int compare_letter(void *let1,void *let2);
These functions are intended for qsort; why are they mistyped? The arguments
should be "const void *".
Remember, you should always use "-ansi -pedantic -Wall" with gcc, and with
that set of flags, it will detect this error, which turns out to be your
problem.
>void main()
15 demerits for gross stupidity. main() has had a return type of int since
somewhere around 1972.
>{
> int i,j,k;
> char *string_array[]={"apple","banana","orange","pear","redberry"};
> for (i=0;i<5;i++)
> {
> for (j=0;j<strlen(string_array[i]);j++)
> {
> for (k=0;k<strlen(string_array[i]);k++)
> {
>
> if (compare_letter(&string_array[i][j],&string_array[i][k]) !=
> -compare_letter(&string_array[i][k],&string_array[i][j]))
> {
> printf("Compare Letter function bad\n");
> fflush(stdout);
> exit(1);
While flushing output you want the user to see is laudable, it's stupid when
followed immediately by exit(), which flushes all output streams. Also,
exit(1) is not meaningful; use EXIT_FAILURE, to avoid inadvertently indicating
success.
> }
> }
> }
> }
> printf("Compare Letter function OK\n");
> fflush(stdout);
>
> for (i=0;i<5;i++)
> {
> for (j=0;j<5;j++)
> {
> if (compare_word((void *)string_array[i],(void *)string_array[j]) !=
> -compare_word((void *)string_array[j],(void *)string_array[i]))
This is completely, utterly, and totally wrong.
compare_word takes, as arguments, a pair of pointer-to-pointer-to-void. Don't
let the [] in the declaration fool you; it means the same thing as a pointer
declaration when used in a function argument.
So, we are taking a "char *", which is by no means a pointer to any sort of a
pointer, and passing it to a function expecting a pointer-to-pointer.
Unsurprisingly, we need the otherwise blatantly wrong cast at this point.
You should *NEVER* cast to (void *) (except when passing a void * to a
variadic function, ala printf("%p", ...)), and especially not when you are
planning to pass something other than (void *).
> {
> printf("Compare function bad\n");
> fflush(stdout);
> exit(1);
> }
> }
> }
> printf("Compare function OK\n");
> fflush(stdout);
Obviously, we never get here.
So, why are you blaming Sun's library when it's quite clear you aren't
*calling* it?
> qsort(string_array,5,sizeof(char *),compare_word);
This generates a compiler warning (as it should) for passing the wrong type of
argument to qsort. Also, "sizeof(char *)" is 1, because sizeof() gives you
sizes in sizeof(char) units.
>int compare_word(void *s1[],void *s2[])
>{
> char *s1_temp;
> char *s2_temp;
> s1_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
> s2_temp=malloc((strlen((char *)*s1)+1)*sizeof(char));
This is where it dumps core. On the very first call, you'll be passing, as
s1, a pointer to the character sequence
'a', 'p', 'p', 'l', 'e', '\0'
You now try to dereference that pointer (getting a pointer to void,
maybe), cast it to (char *) (which is blatantly stupid, as void * doesn't need
to be cast to assign to any kind of object pointer, and you *do* remember to
include <string.h> when doing this, right?), calculate a result, and multiply
it by an obfuscated 1.
This dumps core.
If you eliminate the false indirection, you may be able to get past this.
> qsort(s1_temp,strlen(s1_temp),sizeof(char),compare_letter);
> qsort(s2_temp,strlen(s2_temp),sizeof(char),compare_letter);
This is an extremely unlikely thing to want to do, but we'll let it pass.
Once again, you get a compiler warning if you haven't fixed compare_letter.
> return(strcmp(s1_temp,s2_temp));
You forgot to free the memory. Sure, Unix will probably clean up after you,
but it's stull stupid.
>}
>int compare_letter(void *let1,void *let2)
>{
> if (*(char *)let1 < *(char *)let2)
> {
> return -1;
> }
> else
> {
> if (*(char *)let1 > *(char *)let2)
> return 1;
> else
> return 0;
> }
>}
Apart from the absent const qualifiers, this is correct.
>under solaris and sunos it produces this:
>79> ./test
>Compare Letter function OK
>Segmentation fault
>80>
Right. Notice how your "Compare Word" printf isn't reached?
>however under linux it produces this:
>$ ./test
>Compare Letter function OK
>Compare function OK
>banana
>orange
>apple
>pear
>redberry
>$
Possible, although it seems like sheer chance.
>unless i've totally missed something this *is* a bug in suns libc
Doesn't look like it. I've found a bug or two in Sun's compiler, and maybe
even one in the standard library, but this isn't one of them.
(I'm disregarding, for the sake of argument, the blatantly mislabled "C
compiler" and "C library" used in SunOS 4.x, both of which make no attempt at
conformance.)
>oh btw the above was compiled with gcc on all 3 platforms..
Not with real warnings enabled.
You have to stop using (void *) to shut up pointer mismatch errors; they're
real problems, and if you ignore them, you lose.
Another possible fix would be to pass compare_word the addresses of
your strings, using
compare_word(&string_array[i], &string_array[j])
... But even then, you have to declare it correctly.
That this code compiles is a mystery; that it runs is surprising. That it
produces "correct" output under any circumstances I attribute to chance.
-s
--
Peter Seebach - se...@solon.com - Copyright 1996 - http://www.solon.com/~seebs
Unix/C Wizard - send mail for help, or send money for consulting!
The *other* C FAQ, the hacker FAQ, et al. See web page above.
Unsolicited email (junk mail and ads) is unwelcome, and will be billed for.
Ron Natalie
Peter Seebach wrote:
> > qsort(string_array,5,sizeof(char *),compare_word);
>
> This generates a compiler warning (as it should) for passing the wrong type of
> argument to qsort. Also, "sizeof(char *)" is 1, because sizeof() gives you
> sizes in sizeof(char) units.
>
As long as we're picking nits here, sizeof (char *) is rarely 1. It's
implementation specific, and in fact, has value 4 on the Sun.
> You now try to dereference that pointer (getting a pointer to void,
> maybe), cast it to (char *) (which is blatantly stupid, as void * doesn't need
> to be cast to assign to any kind of object pointer, and you *do* remember to
> include <string.h> when doing this, right?),
It does shut up warnings on many compilers when doing assigning a void
ptr to another
pointer type (yes, even though a cast is exactly the same as what the
assignment
was doing anyhow).
> > qsort(s1_temp,strlen(s1_temp),sizeof(char),compare_letter);
> > qsort(s2_temp,strlen(s2_temp),sizeof(char),compare_letter);
>
> This is an extremely unlikely thing to want to do, but we'll let it pass.
> Once again, you get a compiler warning if you haven't fixed compare_letter.
Here's where you can nag the guy about sizeof(char).
> Unix/C Wizard - send mail for help, or send money for consulting!
I don't know why I would consult with an abusive know it all.
Tanmoy Bhattacharya
ri...@valley.West.Sun.COM (Richard Pettit [Principle Associate]) writes:
[Note crosspost!
Removed comp.lang.tcl and added comp.std.c]
<snip>
> As was pointed out by Bruce Adler, the qsort() you're using isn't reentrant.
> This program dumps core on my 5.5 x86 box as well.
>
> It does not when using my qsort().
>
> (BTW, the version shipped with Borland C isn't reentrant either :-)
The question is about whether the `compar' function (last argument of
qsort) is allowed to call the standard library, in particular qsort
itself. I can find nothing in the standard which prohibits this.
So, does the C standard require that qsort (and bsearch) be reentrant?
Cheers
Tanmoy
--
tan...@qcd.lanl.gov(128.165.23.46) DECNET: BETA::"tan...@lanl.gov"(1.218=1242)
Tanmoy Bhattacharya O:T-8(MS B285)LANL,NM87545 H:#9,3000,Trinity Drive,NM87544
Others see <gopher://yaleinfo.yale.edu:7700/00/Internet-People/internet-mail>,
<http://alpha.acast.nova.edu/cgi-bin/inmgq.pl>or<ftp://csd4.csd.uwm.edu/pub/
internetwork-mail-guide>. -- <http://nqcd.lanl.gov/people/tanmoy/tanmoy.html>
fax: 1 (505) 665 3003 voice: 1 (505) 665 4733 [ Home: 1 (505) 662 5596 ]
Peter Seebach
In article <52o4of$d...@engnews2.Eng.Sun.COM>,
Jeff Bonwick <bon...@cathy.eng.sun.com> wrote:
>The terminology in this area is annoyingly fluid, but generally speaking
>"thread-safe" and "reentrant" don't mean quite the same thing, and neither
>one is what you're looking for: the property you want is "recursive."
Huh?
"recursive" means "calling itself". *ALL* qsort implementations I've ever
seen are recursive. (At least partially.)
"reentrant" means "can be called while it's still in the middle of a call";
this is what the user thought he was having trouble with, but the code was so
broken it's hard to tell.
>Reentrant is stronger: it means that multiple threads can execute the
>routine *at the same time*. Thus thread T1 can sort array A1 on cpu1
>while T2 sorts A2 on cpu2. There's no process-wide 'qsort lock' on
>which the threads have to serialize. The 2.5.1 qsort() is reentrant.
Reentrant also applies to a given thread calling a given routine inside
another call to that routine. Most recursive functions must be reentrant
to be safe, but there are obvious exceptions.
>Meanwhile, the property you actually want is recursion, i.e. qsort()
>calls your compare function, which calls back into qsort(). A qsort
>implementation that is only thread-safe will not tolerate recursive
>calls, because you'll end up trying to acquire a lock you already own.
>(If you link your example program with -lthread, so the mutexes aren't
>no-ops, it will hang forever.)
This is silly; is your qsort normally iterative?
>The 2.5.1 version of qsort() is both reentrant and recursive. However,
>if you're trying to write portable code, you don't want to rely on this.
>Calling qsort() from within a qsort comparison routine is asking for trouble.
Nonsense. I see no claim in the standard that the comparison function may
not call qsort; the *ONLY* restrictions on a comparison function are that it
be of type int(*)(const void *, const void *), and that it returns an integer
less than, equal to, or greater than zero, based on the comparison of the
arguments.
The standard is always quite careful to say what the user may not assume (see,
for instance, the descriptions of signal handlers, or of how setjmp and
longjmp are used), and makes *no* restrictions on qsort.
A qsort in which the comparison function may not call qsort is, AFAICT,
broken.
(This is really unusual; you rarely see someone with test code that badly
broken complaining about an actual bug.)
-s
--
Peter Seebach - se...@solon.com - Copyright 1996 - http://www.solon.com/~seebs
Unix/C Wizard - send mail for help, or send money for consulting!
Peter Seebach
In article <jonesr.8...@lion.cs.latrobe.edu.au>,
Richard Jones <jon...@latcs1.cs.latrobe.edu.au> wrote:
>example was full of bugs, here is some code that has less
>(perhaps even none!):
Not even close.
>#include <stdio.h>
>#include <stdlib.h>
>#include <malloc.h>
Bzzt.
>#include <string.h>
>int compare_word(char **s1,char **s2);
>int compare_letter(char *let1,char *let2);
Correct internally, but not suitable to pass to qsort.
>void main()
Both stupid and wrong. Where do you folks *get* this crap?
(I know, Herbert Schildt. Sheesh.)
> qsort(string_array,5,sizeof(char *),compare_word);
This is wrong, because you're passing the wrong kind of function pointer
into qsort. It invokes undefined behavior.
>int compare_word(char **s1,char **s2)
>{
> s1_temp=strdup(*s1);
> s2_temp=strdup(*s1);
undefined behavior, because strdup() is not a defined function, and is in the
implementation namespace.
> qsort(s1_temp,strlen(s1_temp),sizeof(char),compare_letter);
> qsort(s2_temp,strlen(s2_temp),sizeof(char),compare_letter);
Wrong kind of function... And, of course, you're using "sizeof(char)"
which is simply (size_t) 1. (Which is useless, because small positive
integers are guaranteed to promote correctly into size_t.)
>still works fine under linux.
As noted above, you are invoking undefined behavior 8 ways.
However, none of your mistakes would explain a core dump on a sparc system,
so it may actually be a bug in qsort, or perhaps the standard has been
ammended to allow such a stupid implementation bug.
(Not that I'm in any position to talk, I have a sort routine which has
exactly the same bug, which makes me look sort of stupid for not noticing
it earlier. At least mine's not *expected* to conform to any standard.)
Mike Rubenstein
Tanmoy Bhattacharya <tan...@qcd.lanl.gov> wrote:
> ri...@valley.West.Sun.COM (Richard Pettit [Principle Associate]) writes:
>
> [Note crosspost!
> Removed comp.lang.tcl and added comp.std.c]
>
> <snip>
> > As was pointed out by Bruce Adler, the qsort() you're using isn't reentrant.
> > This program dumps core on my 5.5 x86 box as well.
> >
> > It does not when using my qsort().
> >
> > (BTW, the version shipped with Borland C isn't reentrant either :-)
>
> The question is about whether the `compar' function (last argument of
> qsort) is allowed to call the standard library, in particular qsort
> itself. I can find nothing in the standard which prohibits this.
>
> So, does the C standard require that qsort (and bsearch) be reentrant?
The title of the subclause is misleading, but doesn't ISO 5.2.3 say
that they need not be reentrant:
The functions in the standard library are not guaranteed to be
reentrant and may modify objects with static storage duration.
Michael M Rubenstein
Peter Seebach
In article <324FFB...@sensor.com>, Ron Natalie <r...@sensor.com> wrote:
>Peter Seebach wrote:
>> > qsort(string_array,5,sizeof(char *),compare_word);
>> This generates a compiler warning (as it should) for passing the wrong type of
>> argument to qsort. Also, "sizeof(char *)" is 1, because sizeof() gives you
>> sizes in sizeof(char) units.
I got this right in my original letter, but I managed to get it stunningly
wrong here.
>As long as we're picking nits here, sizeof (char *) is rarely 1. It's
>implementation specific, and in fact, has value 4 on the Sun.
Right; I'd say "I don't know what I was thinking", but it's clear that I
wasn't thinking at all.
>It does shut up warnings on many compilers when doing assigning a void
>ptr to another
>pointer type (yes, even though a cast is exactly the same as what the
>assignment
>was doing anyhow).
Yes, but those warnings are a sign of a poor implementation. (void *)
conversions are explicitly blessed, and I would be upset about an
implementation which tried to warn me about them, just as I'd dislike an
implementation which warned me about
int i = 'a';
>Here's where you can nag the guy about sizeof(char).
Yup. I had noticed that in my initial pass of compiles and tests, and then
attached the nag to the wrong part of the program. *sigh*.
I shouldn't post before lunch.
>> Unix/C Wizard - send mail for help, or send money for consulting!
>I don't know why I would consult with an abusive know it all.
Language lawyers are occasionally useful; for instance, a *corrected* version
of this program might well be able to convince a vendor of a bug, but no sane
vendor would have taken the time to extract it from the original.
People reporting bugs in C compilers have a responsibility to demonstrate that
the bug happens either to a strictly conforming program, or to one whose
behavior is documented and defined by the implementation.
Tanmoy Bhattacharya
mik...@ix.netcom.com (Mike Rubenstein) writes:
<snip>
> > The question is about whether the `compar' function (last argument of
> > qsort) is allowed to call the standard library, in particular qsort
> > itself. I can find nothing in the standard which prohibits this.
> >
> > So, does the C standard require that qsort (and bsearch) be reentrant?
>
> The title of the subclause is misleading, but doesn't ISO 5.2.3 say
> that they need not be reentrant:
>
> The functions in the standard library are not guaranteed to be
>
> reentrant and may modify objects with static storage duration.
Exactly what guarantee does this give me. If the compar function of qsort
cannot call qsort, can it still call bsearch: or can qsort and bsearch
modify the same object with static storage so that they interfere with
each other?
Can I call abs from such a function, or can abs modify the static
object assumed above and hence interfere with the sorting?
Kaz Kylheku
>>
>> This generates a compiler warning (as it should) for passing the wrong type of
>> argument to qsort. Also, "sizeof(char *)" is 1, because sizeof() gives you
>> sizes in sizeof(char) units.
>>
>
>implementation specific, and in fact, has value 4 on the Sun.
Knownig Seebach, I can make you a 100% guarantee that it's a typo, given
that April Fool's Day is half a year away.
>> You now try to dereference that pointer (getting a pointer to void,
>> maybe), cast it to (char *) (which is blatantly stupid, as void * doesn't need
>> to be cast to assign to any kind of object pointer, and you *do* remember to
>> include <string.h> when doing this, right?),
>
>It does shut up warnings on many compilers when doing assigning a void
>ptr to another
>pointer type (yes, even though a cast is exactly the same as what the
>assignment
>was doing anyhow).
No ANSI/ISO C compiler will emit diagnostics when a void * is implicitly
converted to a pointer of a different type, or vice versa (excluding function
pointers, of course).
One should never place a cast in an assignment which does such a conversion
because it can mask a potential error, like the use of malloc() without a
prototype.
In general, one should enable all the warnings that a compiler can muster,
rather than try to shut them up in dubious ways.
"Gee, this compiler is complaining about no return value from main().
I guess I should redeclare it void main()..."
Jeff Bonwick
In article <52p36g$j...@solutions.solon.com> se...@solon.com writes:
>
> "recursive" means "calling itself". *ALL* qsort implementations I've ever
> seen are recursive. (At least partially.)
Really? Then you've never seen a good qsort implementation. All of
the good ones use a simple stack mechanism to avoid recursion. It's
cheaper to 'push' the handful of things you need to remember than to
write out a complete stack frame.
> "reentrant" means "can be called while it's still in the middle of a call";
By another thread, operating on different data, certainly. The question
of whether this implies that the *same* thread can (unexpectedly) call
back into the function without recursive deadlock or TSD corruption is
a grey area, because TSD isn't generally thought of as global state.
And then there's signal-safety, which is another can of worms entirely.
I prefaced my comments with "the terminology is annoyingly fluid in this
area" in the hope of avoiding a flame war based on which OS text you used
in your formative years. If you can find two books that define reentrant
in exactly the same way, I'd love to hear about it. In fact you may recall
that the *original* meaning of this term was "non-self-modifying text."
> I see no claim in the standard that the comparison function may
> not call qsort;
Standards are written by people, not by gods. They can't anticipate
every silly thing someone might try to do.
> A qsort in which the comparison function may not call qsort is, AFAICT,
> broken.
Maybe you're right -- we'll have to let X/Open debate that one. But my
advice still stands: if you want to write portable code, don't do this.
Jeff Bonwick
Solaris Performance
Mike Rubenstein
Tanmoy Bhattacharya <tan...@qcd.lanl.gov> wrote:
> mik...@ix.netcom.com (Mike Rubenstein) writes:
>
> <snip>
> > > The question is about whether the `compar' function (last argument of
> > > qsort) is allowed to call the standard library, in particular qsort
> > > itself. I can find nothing in the standard which prohibits this.
> > >
> > > So, does the C standard require that qsort (and bsearch) be reentrant?
> >
> > The title of the subclause is misleading, but doesn't ISO 5.2.3 say
> > that they need not be reentrant:
> >
> > The functions in the standard library are not guaranteed to be
> >
> > reentrant and may modify objects with static storage duration.
>
> Exactly what guarantee does this give me. If the compar function of qsort
> cannot call qsort, can it still call bsearch: or can qsort and bsearch
> modify the same object with static storage so that they interfere with
> each other?
>
> Can I call abs from such a function, or can abs modify the static
> object assumed above and hence interfere with the sorting?
The statement is that the functions are not required to be reentrant.
I see nothing to indicate that the library as a whole is permitted to
be nonreentrant; i.e., that one may not call a library function while
another is active (there are a few exceptions in that some functions
are explicitly allowed to share statically allocated memory, but that
wouldn't apply here).
Lacking any statement to the contrary, I'd say that there is no
prohibition on calling other library functions from the comparison
functions.
This isn't enough. The question is not simply can abs() modify the
same static object as qsort() -- it's also can abs() call qsort()?
I'd say no since there is no prohibition (I can find) on calling abs()
from the comparison fucntion but this assumes an inconsistency in the
detail of the standard. The description of strtok() (7.11.5.8)
specifically says
The implmementation shall behave as if no library function
calls the strtok function.
I can find no such prohibition on qsort().
It certainly could be clearer. Perhaps a defect report is needed.
Michael M Rubenstein
Stephen Baynes
: <snip>
: > > The question is about whether the `compar' function (last argument of
: > > qsort) is allowed to call the standard library, in particular qsort
: > > itself. I can find nothing in the standard which prohibits this.
: > >
: > > So, does the C standard require that qsort (and bsearch) be reentrant?
: >
: > The title of the subclause is misleading, but doesn't ISO 5.2.3 say
: > that they need not be reentrant:
: >
: > The functions in the standard library are not guaranteed to be
: >
: > reentrant and may modify objects with static storage duration.
: Exactly what guarantee does this give me. If the compar function of qsort
: cannot call qsort, can it still call bsearch: or can qsort and bsearch
: modify the same object with static storage so that they interfere with
: each other?
Is it that individual functions are not rentrant or the library as a whole
is not rentrant. I read it as individual functions but it is not at all clear.
: Can I call abs from such a function, or can abs modify the static
: object assumed above and hence interfere with the sorting?
Can one call strcmp? Which is a function that is often used in compare
functions. If one cannot then a lot of code is broken. If one can then
there should be a general guarantee which would also cover qsort unless a
specific exception was made.
There are only two ways that a conforming C program can tell if library
functions are rentrant. One is by calling them from signal handlers, the other
is by calling them from compare functions. Signal handlers can potentially
renter any function, compare functions are more limited in what can be invoked
at the same time. In the case of signal handlers specific restrictions are made
on what can be called. In the case of compare functions no restrictions are
mentioned so there is an implication is there are no restrictions (except for
the general one on rentracy which is not clear.)
[Has this been solved in C++? Is the solution applicable/compatable with C?
The problem must be worse there as lots of things can be called behind ones
back and there are more ways that library code can call back into user code.]
I think a clarification would be useful.
--
Stephen Baynes bay...@ukpsshp1.serigate.philips.nl
Philips Semiconductors Ltd
Southampton My views are my own.
United Kingdom
Are you using ISO8859-1? Do you see © as copyright, ÷ as division and ½ as 1/2?
Pete Forman
>>>>> "Stephen" == Stephen Baynes <bay...@ukpsshp1.serigate.philips.nl> writes:
[earlier part of thread deleted]
Stephen> Can one call strcmp? Which is a function that is often
Stephen> used in compare functions. If one cannot then a lot of
Stephen> code is broken. If one can then there should be a general
Stephen> guarantee which would also cover qsort unless a specific
Stephen> exception was made.
Stephen> There are only two ways that a conforming C program can
Stephen> tell if library functions are rentrant. One is by calling
Stephen> them from signal handlers, the other is by calling them
Stephen> from compare functions. Signal handlers can potentially
Stephen> renter any function, compare functions are more limited
^^^^^^^^^^^^^^^^^^^
Stephen> in what can be invoked at the same time. In the case of
Stephen> signal handlers specific restrictions are made on what
Stephen> can be called. In the case of compare functions no
Stephen> restrictions are mentioned so there is an implication is
Stephen> there are no restrictions (except for the general one on
Stephen> rentracy which is not clear.)
Stephen> I think a clarification would be useful.
POSIX lists 72 functions which are safe to call in a signal-catching
function. This list excludes bsearch, qsort, and strcmp. Indeed
there were only two ANSI C functions: rename and time. I could not
find any comments about compare functions or reentrancy in general.
It looks as if strictly speaking one is rather constrained in what is
guaranteed to work safely.
--
Pete Forman
Western Geophysical
pete....@bedford.waii.com
Stephen Baynes
Kaz Kylheku (k...@vision.crest.nt.com) wrote:
: In article <324FFB...@sensor.com>, Ron Natalie <r...@sensor.com> wrote:
: No ANSI/ISO C compiler will emit diagnostics when a void * is implicitly
: converted to a pointer of a different type, or vice versa (excluding function
: pointers, of course).
Nit picking -- an ANSI/ISO C compiler must issue diagnostics in certain cases.
It can issue diagnostics at other times if it wishes. So for example
it can emit diagnostics when void * is implicity converted. It must however
complete the compilation and produce working code.
In fact I don't think that the standard even requires that you can tell
the differences between the diagnostics required by the standard and any
the compiler decides to produce for its own amusement.
Followups to comp.std.c only.
Peter Seebach
In article <32505468....@nntp.ix.netcom.com>,
Mike Rubenstein <mik...@ix.netcom.com> wrote:
>The statement is that the functions are not required to be reentrant.
What's odd is that it says it under the heading "Signals and interrupts" - I'm
not sure the intent was to discuss functions which, directly or indirectly,
end up calling themselves. I thought it was more along the lines of functions
which are already running being called, say, by signal handlers, and that this
is what was being forbidden.
I would certainly expect qsort to work with a comparison function which calls
qsort. I wouldn't expect it to survive a signal handler that calls qsort.
My interpretation, from the context in which the statement was made, would be
that functions are expected to clean everything up before giving control to
any user-defined function.
>It certainly could be clearer. Perhaps a defect report is needed.
Certainly is. If nothing else, 5.2.3 uses "comprise" backwards.
*sigh*.
Roberto Dorich
Ron Natalie (r...@sensor.com) wrote:
: Peter Seebach wrote:
: > > qsort(string_array,5,sizeof(char *),compare_word);
: >
: > This generates a compiler warning (as it should) for passing the wrong type of
: > argument to qsort. Also, "sizeof(char *)" is 1, because sizeof() gives you
: > sizes in sizeof(char) units.
: >
: As long as we're picking nits here, sizeof (char *) is rarely 1. It's
: implementation specific, and in fact, has value 4 on the Sun.
sizeof (char *) should never be 1!! Unless there are only 256 Bytes
of memory (or 1024 of addressable memory (aligned)). The other reason
could be that sizeof(char) > 1 which I highly doubt... that's why there
are wchar_t's in Sun.
Roberto
--
Roberto Dorich o SKI rdo...@ee.cornell.edu
Electrical Engineering /= EXTREME rdo...@tufts.edu
Cornell University __/__, dor...@ptc.com
----------------------------------------------------------------------
Tanmoy Bhattacharya
rdo...@emerald.tufts.edu (Roberto Dorich) writes:
<snip>
> sizeof (char *) should never be 1!! Unless there are only 256 Bytes
No: sizeof does not count in units of 8 bit bytes.
> of memory (or 1024 of addressable memory (aligned)). The other reason
> could be that sizeof(char) > 1 which I highly doubt... that's why there
sizeof counts in units of the smallest C-addressable data unit: and
that by definition is char. So, sizeof(char) is always 1.
> are wchar_t's in Sun.
Cheers
Mike Rubenstein
rdo...@emerald.tufts.edu (Roberto Dorich) wrote:
> Ron Natalie (r...@sensor.com) wrote:
> : Peter Seebach wrote:
>
> : > > qsort(string_array,5,sizeof(char *),compare_word);
> : >
> : > This generates a compiler warning (as it should) for passing the wrong type of
> : > argument to qsort. Also, "sizeof(char *)" is 1, because sizeof() gives you
> : > sizes in sizeof(char) units.
> : >
>
> : As long as we're picking nits here, sizeof (char *) is rarely 1. It's
> : implementation specific, and in fact, has value 4 on the Sun.
>
> sizeof (char *) should never be 1!! Unless there are only 256 Bytes
> of memory (or 1024 of addressable memory (aligned)). The other reason
> could be that sizeof(char) > 1 which I highly doubt... that's why there
> are wchar_t's in Sun.
I'm glad you doubt that sizeof(char) > 1 since in C sizeof(char) is
guaranteed to be 1. However, there is no requirement that a byte be
only 8 bits. If a byte is 32 bits, it would be quite reasonable for
sizeof(char*) == 1.
Michael M Rubenstein
Roberto Dorich
Thanks for the clarification Michael. Hence the synonymn for
8 bit bytes -> octects. My apologies.
Roberto
Mike Rubenstein (mik...@ix.netcom.com) wrote:
: rdo...@emerald.tufts.edu (Roberto Dorich) wrote:
: > Ron Natalie (r...@sensor.com) wrote:
: > : Peter Seebach wrote:
: >
: > : > > qsort(string_array,5,sizeof(char *),compare_word);
: > : >
: > : > This generates a compiler warning (as it should) for passing the wrong type of
: > : > argument to qsort. Also, "sizeof(char *)" is 1, because sizeof() gives you
: > : > sizes in sizeof(char) units.
: > : >
: >
: > : As long as we're picking nits here, sizeof (char *) is rarely 1. It's
: > : implementation specific, and in fact, has value 4 on the Sun.
: >
: > sizeof (char *) should never be 1!! Unless there are only 256 Bytes
: > of memory (or 1024 of addressable memory (aligned)). The other reason
: > could be that sizeof(char) > 1 which I highly doubt... that's why there
: > are wchar_t's in Sun.
: I'm glad you doubt that sizeof(char) > 1 since in C sizeof(char) is
: guaranteed to be 1. However, there is no requirement that a byte be
: only 8 bits. If a byte is 32 bits, it would be quite reasonable for
: sizeof(char*) == 1.
: Michael M Rubenstein
--
Frederic Bonnet
[blah deleted]
Hi folks,
All this discussion is _really_ interesting, but I don't think it
belongs
to comp.lang.tcl anymore (even though it began there).
Cheers, Fred
--
Frederic BONNET Ingenieur de l'Ecole des Mines de Nantes
fbo...@irisa.fr Scientifique du Contingent
IRISA Rennes - Projet Solidor
"Il ne faut jamais remettre au lendemain ce qu'on peut faire le
surlendemain"
Oscar WILDE
Ray Dunn
In referenced article, Peter Seebach says...
>Jeff Bonwick <bon...@cathy.eng.sun.com> wrote:
>>Reentrant is stronger: it means that multiple threads can execute the
>>routine *at the same time*. Thus thread T1 can sort array A1 on cpu1
>>while T2 sorts A2 on cpu2. There's no process-wide 'qsort lock' on
>>which the threads have to serialize. The 2.5.1 qsort() is reentrant.
>
>Reentrant also applies to a given thread calling a given routine
>inside another call to that routine.
[process and thread are used below in a general sense, not a specific
Unix sense - posted from comp.lang.c, not a Unix newsgroup]
If you mean a routine in the the _same_ thread (lets assume a simple
single threaded program) calling a routine which is currently active
(i.e. has not yet exited) then that is _recursion_, not re-entrancy.
Recursion doesn't imply the simplest interpretation of "calling itself"
(i.e. a function f which has a call of f in its own body). If f is
called by any function that f has called, no matter what the depth,
then that is also recursion.
Reentrancy always implies different threads or processes executing a
routine simultaneously.
>Most recursive functions must be reentrant
>to be safe, but there are obvious exceptions.
This is somewhat misleading. In most cases, the property of reentrancy
is handled by the underlying operating system, but whether a function
can properly recurse, is dependant on the programmer. Lets look at an
example:
int fred(int argument)
{ static int recurse = 0;
int retval;
recurse++;
if (ERROR_IN_ARGUMENT(argument))
{
recurse--;
if (recurse)
return(ERR_VAL_1);
else
return(ERR_VAL_2);
}
retval = fred(f(argument));
recurse--;
return(retval);
}
This is not a very useful function, but it demonstrates one way you
might detect a recursive call to a function and take different action
at the top level call from a recursive call.
On the face of it, it would appear that fred is not re-entrant, because
it uses a static variable, but that's not necessarily the case.
On a system like WindowsNT, which supports threads and processes, a
single shared copy of the above function could be called re-entrantly
by different processes, because they have their own copies of the
workspace, but not by different threads of the same process, which all
share the same copy of the workspace.
Whether a signal handler is calling currently active routines
recursively or reentrantly gets a little hazy. It depends on whether
you regard the signal handler as part of the interrupted thread or a
separate thread, and that depends on how the operating system allocates
the workspace for the handler. It's normal to think of this as
reentrancy though rather than recursion, even if the signal handler is
running in the same context as the interrupted thread.
Any function which only uses and affects workspace dynamically
allocated on entry (like automatic variables) can be called both
recursively and re-entrantly.
It's also possible to ensure reentrant capability by actively locking
out possible reentrant calls during "unsafe" parts of the execution
(using e.g. the critical section locks in Windows NT, or by disabling
interrupts in an operating system at critical times).
>>The 2.5.1 version of qsort() is both reentrant and recursive.
>>However, if you're trying to write portable code, you don't want to
>>rely on this.
>>Calling qsort() from within a qsort comparison routine is asking for
>>trouble.
>
>Nonsense. I see no claim in the standard that the comparison function
>may not call qsort; the *ONLY* restrictions on a comparison function
>are that it be of type int(*)(const void *, const void *), and that it
>returns an integer ...
I would disagree that it's nonsense. Definitions should be treated in
the opposite way to how you suggest IMO. The only guarantees you have
are in what the definition specifically states, all other assumptions
are risky. Unless the definition of qsort specifically states, or
clearly implies that it can be called from the comparison function, it
_may_ not work.
Having said that, of course, it's _very_ unlikely that a recursive call
of qsort from within the comparison function would fail (i.e. a
recursive call). It is possible to contrive a conforming
implementation of qsort that would fail though, IMO.
>The standard is always quite careful to say what the user may not
>assume (see, for instance, the descriptions of signal handlers, or of
>how setjmp and longjmp are used), and makes *no* restrictions on
>qsort.
It's virtually impossible to have an exhaustive list of things you
_can't_ assume, the standard is only pointing out common pitfalls.
>A qsort in which the comparison function may not call qsort is,
>AFAICT, broken.
A poor implementation, certainly, but not broken in the formal sense.
--
Ray Dunn (opinions are my own) | Phone: (514) 938 9050
Montreal | Phax : (514) 938 5225
r...@ultimate-tech.com | Home : (514) 630 3749
Ken Pizzini
In article <tuu3se6...@nemo.bedford.waii.com>,
Pete Forman <gse...@nemo.bedford.waii.com> wrote:
>POSIX lists 72 functions which are safe to call in a signal-catching
>function. This list excludes bsearch, qsort, and strcmp. Indeed
>there were only two ANSI C functions: rename and time. I could not
>find any comments about compare functions or reentrancy in general.
>It looks as if strictly speaking one is rather constrained in what is
>guaranteed to work safely.
Even those two are not guaranteed by the C standard. As I recall,
only assignment to a volatile sigatomic_t variable is guaranteed at
this level.
But surely the standard *could* dictate that certain functions must
be reentrant? For example, I don't see that it would burden an
implementation to require the following to be reentrant:
memchr memcmp strcmp strlen strchr strrchr strncmp strerror
--Ken Pizzini
Dennis Yelle
And the vast majority of the rest of them.
I think the standard needs to require that an implementation
provide a list of library functions that are NOT reentrant.
--
den...@netcom.com (Dennis Yelle)
"You must do the thing you think you cannot do." -- Eleanor Roosevelt
Bradd W. Szonye
Dennis Yelle <den...@netcom.com> wrote in article
<dennisDy...@netcom.com>...
> I think the standard needs to require that an implementation
> provide a list of library functions that are NOT reentrant.
The C++ working papers specify this:
17.3.4.5 Reentrancy [lib.reentrancy]
1 Which of the functions in the C++ Standard Library are not reentrant
subroutines is implementation-defined.
Unfortunately, I can't find any similar requirement (that is, that the
implementation define and document which functions are not reentrant) in
the C standard. This looks like a good candidate for inclusion in the
future revision of ISO C.
--
Bradd W. Szonye
bra...@concentric.net
http://www.concentric.net/~bradds
Pete Forman
>>>>> "Dennis" == Dennis Yelle <den...@netcom.com> writes:
Dennis> I think the standard needs to require that an
Dennis> implementation provide a list of library functions that
Dennis> are NOT reentrant.
This is unfortunately of limited use. It would only allow one to say
whether a program will run on a particular implementation. It would
still not be possible to write a portable program using reentrancy
that is guaranteed to run on all conforming implementations.
J. Kanze
bon...@cathy.eng.sun.com (Jeff Bonwick) writes:
> In article <52p36g$j...@solutions.solon.com> se...@solon.com writes:
> >
> > "recursive" means "calling itself". *ALL* qsort implementations I've ever
> > seen are recursive. (At least partially.)
>
> Really? Then you've never seen a good qsort implementation. All of
> the good ones use a simple stack mechanism to avoid recursion. It's
> cheaper to 'push' the handful of things you need to remember than to
> write out a complete stack frame.
Really? Have you benchmarked this?
I did once, on a Sun 3 (680x0 based, it was a long time ago). The
recursive version was slightly faster.
Most modern processors have either a single instruction, or an optimized
sequence of instructions, to set up a stack frame. If you use a hand
programmed simple stack mechanism, you don't use this optimized
sequence. (I'll admit that the results surprised me at the time,
but...)
--
James Kanze (+33) 88 14 49 00 email: ka...@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle --
-- Beratung in industrieller Datenverarbeitung
Dennis Yelle
In article <tubuejt...@nemo.bedford.waii.com> Pete Forman <gse...@nemo.bedford.waii.com> writes:
>>>>>> "Dennis" == Dennis Yelle <den...@netcom.com> writes:
>
> Dennis> I think the standard needs to require that an
> Dennis> implementation provide a list of library functions that
> Dennis> are NOT reentrant.
>
>This is unfortunately of limited use. It would only allow one to say
>whether a program will run on a particular implementation. It would
>still not be possible to write a portable program using reentrancy
>that is guaranteed to run on all conforming implementations.
While technically, you are correct, it would expose to ridicule
those implimentations with non-reentrant functions like qsort()
and .... In other words, eventually no one would buy the ones
with more than the minimum set of non-reentrant functions.
I think just the act of listing the non-reentrant functions
will give most implimenters sufficient encouragement to
make the list as short as possible. My understanding
is that other than the few functions that cannot be reentrant,
making the rest reentrant is easy.
Peter Holzer
mik...@ix.netcom.com (Mike Rubenstein) writes:
>This isn't enough. The question is not simply can abs() modify the
>same static object as qsort() -- it's also can abs() call qsort()?
:-)
#include <stdlib.h>
static int icompar(const void *a, const void *b) {
const int *aa = a, *bb = b;
if (*aa < *bb) return -1;
if (*aa > *bb) return 1;
return 0;
}
int abs(int a) {
int aa[2];
aa[0] = a;
aa[1] = -a;
qsort(aa, 2, sizeof(int), icompar);
return aa[1];
}
>I'd say no since there is no prohibition (I can find) on calling abs()
>from the comparison fucntion but this assumes an inconsistency in the
>detail of the standard. The description of strtok() (7.11.5.8)
>specifically says
> The implmementation shall behave as if no library function
> calls the strtok function.
>I can find no such prohibition on qsort().
This is because the strtok function has to keep state between subsequent
invocations. The qsort function does not.
hp
--
_ | Peter J. Holzer | If I were God, or better yet
|_|_) | Sysadmin WSR | Linus, I would ...
| | | h...@wsr.ac.at | -- Bill Davidsen
__/ | http://wsrx.wsr.ac.at/~hjp/ | (davi...@tmr.com)
Ben Chase
: bon...@cathy.eng.sun.com (Jeff Bonwick) wrote:
: > Really? Then you've never seen a good qsort implementation. All of
: > the good ones use a simple stack mechanism to avoid recursion. It's
: > cheaper to 'push' the handful of things you need to remember than to
: > write out a complete stack frame.
J. Kanze (ka...@gabi-soft.fr) replied:
: Really? Have you benchmarked this?
: I did once, on a Sun 3 (680x0 based, it was a long time ago). The
: recursive version was slightly faster.
You may want to benchmark it again on a Sparc microprocessor. Deep
recursion is expensive because of the register windows.
I am curious, though, if Sun's implementation of qsort does indeed
totally avoid direct recursion (that is, a call to qsort appearing
within the qsort function body, rather than within some function that
qsort calls, such as the comparison function). By going with a
directly recursive implementation, the qsort implementor does get to
avoid the issue of how deep to make the stack. Does Sun's
implementation of qsort call a dynamic allocation function such as
malloc or (gasp) alloca, or does it mostly avoid recursion through a
fixed-size stack declared as an automatic variable, but use recursion
as a backstop to get additional such stacks, or some third,
unimagineable implementation? Jeff Bonwick, can you comment?
- Ben Chase
Jeff Bonwick
> Does Sun's implementation of qsort call a dynamic allocation function
> such as malloc or (gasp) alloca, or does it mostly avoid recursion
> through a fixed-size stack declared as an automatic variable, but use
> recursion as a backstop to get additional such stacks, or some third,
> unimagineable implementation? Jeff Bonwick, can you comment?
Yes, I can. We employ a third, unimaginable technique. ;-)
The qsort stack size is constant -- 31 frames deep to be precise.
This is always sufficient because at each point where qsort splits
the array into two pieces we 'push' the larger half and process
the smaller half. Thus the stack can never get deeper than log2(N)
where N is the number of elements to sort. Since N cannot exceed
2^32 on a 32-bit OS, the maximum depth is 32 if you apply qsort all
the way down to one element. In reality we cut over to insertion
sort for very small arrays (the constants are better), so 31 frames
is always enough. (In Solaris-64 we'll up this to 63 frames. ;-))
Jeff Bonwick
Solaris Performance
Richard Pettit [Engineer]
In article <53f9lu$c...@ralph.vnet.net>, b...@jazzmin.vnet.net (Ben Chase) writes:
>I am curious, though, if Sun's implementation of qsort does indeed
>totally avoid direct recursion (that is, a call to qsort appearing
>within the qsort function body, rather than within some function that
>qsort calls, such as the comparison function). By going with a
>directly recursive implementation, the qsort implementor does get to
>implementation of qsort call a dynamic allocation function such as
>malloc or (gasp) alloca, or does it mostly avoid recursion through a
>fixed-size stack declared as an automatic variable, but use recursion
>as a backstop to get additional such stacks, or some third,
>unimagineable implementation? Jeff Bonwick, can you comment?
I'm hoping that after killing this topic we're not reincarnating it so we
can kill it *again*. Anyway...
Sun's qsort() implementation is not very good. For sets of 13 or less
elements it uses an insertion sort. For 14 or over it uses a poorly
written quick sort which is *not* recursive. The performance is ok until
you get to a large set at which point performance breaks down.
In a comparison between the qsort() that I posted earlier, a threaded
version of the same and the stock implementation, I got the following
results from sorting 1 million integers:
avg nonthreaded case = 7.05 seconds
avg threaded case = 3.47 seconds
avg stock case = 9.41 seconds
Tweaking of the non-threaded algorithm would yield even better results.
Recursion, though expensive, is a better solution than implementing
an overly complex non-recursive algorithm. After all, try to implement
this iteratively:
a(m,n) { return (!m)?(n+1):((!n)?(a(m-1,1)):(a(m-1,a(m,n-1)))); }
IMHO.
Rich
+- + -- + -+
Richard Pettit | Richard...@West.Sun.COM | 15821 Ventura Blvd #270
SMCC Engineer | "Macrosolutions to Megaproblems" | Encino, CA 91436
{S(=@[length,%1]->id;apndl@[1,S@tl]@(while not@!and@&<=@distl@[1,tl] rotr))}
Paul Eggert
ri...@valley.West.Sun.COM (Richard Pettit [Engineer]) writes:
>In a comparison between the qsort() that I posted earlier, a threaded
>version of the same and the stock implementation, I got the following
>results from sorting 1 million integers:
>avg nonthreaded case = 7.05 seconds
>avg threaded case = 3.47 seconds
>avg stock case = 9.41 seconds
Odd; when I tried the qsort implementation that you published in
<URL:news:52or40$2...@newsworthy.West.Sun.COM>, I got the following results:
nonthreaded case = 8.79 seconds
stock case = 5.01 seconds
I compiled it with SC4.0 (patch 102955-08) -O4 and ran it on an Ultra
1/170E under Solaris 2.5.1. I used the following test program and
timed it with ksh's `time' command.
int a[1000000];
extern long random();
static int compare (void *a, void *b) {
return *(int *)b - *(int *)a;
}
int main(argc, argv)
{
int i;
for (i = 0; i< 1000000; i++)
a[i] = random();
if (argc > 1)
qsort (a, 1000000, sizeof (int), compare);
}
Richard A. O'Keefe
Tanmoy Bhattacharya <tan...@qcd.lanl.gov> writes:
>The question is about whether the `compar' function (last argument of
>qsort) is allowed to call the standard library, in particular qsort
>itself. I can find nothing in the standard which prohibits this.
>So, does the C standard require that qsort (and bsearch) be reentrant?
Section 5.2.3 (you'd expect it to be in 7.something but it isn't):
The functions in the standard library are NOT guaranteed
to be reentrant amd MAY modify objects with static storage duration.
(my emphasis). So the C standard does NOT require that qsort() or
bsearch() be reentrant.
--
Mixed Member Proportional---a *great* way to vote!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
Richard A. O'Keefe
se...@solutions.solon.com (Peter Seebach) writes:
>I would certainly expect qsort to work with a comparison function which calls
>qsort. I wouldn't expect it to survive a signal handler that calls qsort.
I am aware of a commercial C implementation for MS-DOS where the qsort()
implementation uses static (file-local) variables, and most certainly
would _not_ work if the comparison function called qsort again.
>My interpretation, from the context in which the statement was made, would be
>that functions are expected to clean everything up before giving control to
>any user-defined function.
These days there are _three_ ways that a library function can be reentered:
- signal (C, POSIX.1)
- call-back (C, POSIX.2)
- thread (pthreads, isn't that POSIX.1a?)
UNIX has threads, the MacOS has threads, OS/2 has threads,
even Windows has threads. There were thread systems in use for C when
the C standard came out (Sequent, for example). There certainly were
when POSIX.1 came out.
The practical consequence of this is that even if the C standard _did_
mean "library functions must clean up before they issue a callback",
that _still_ would not make them usable in threads, thanks to the
explicit warning that library functions (_any_ standard library functions)
may use static objects, and so are not thread-safe.
If I have understood this aright, then anyone using strcmp() in a threaded
program (without ensuring that two threads never try to call it at around
the same time) is relying on something not guaranteed by the C standard...
For strcmp() this is probably frivolous, but efficient implementations of
strspn(), strcspn(), or strpbrk() *do* rely on modifying a global table;
this turns an O(m*n) operation into an O(m+n) one and is well worth doing.
There is a strtok_r operation proposed, but I am not aware of any strspn_r()
operation, which means that although strspn() *could* be O(m+n) it must be
O(m*n) or O(m+n+UCHAR_MAX) if it is to be thread-safe, so I don't use it any
more, I use my own similar function where I _know_ that it is both thread-
safe _and_ O(n) (once, setup) + O(m) (each call).
In short, even if it _were_ possible to read the C standard as requiring
qsort() to be reentrant in a single thread, that wouldn't be enough any more.
Barry Margolin
In article <53iel5$esl$1...@goanna.cs.rmit.edu.au>,
Richard A. O'Keefe <o...@goanna.cs.rmit.edu.au> wrote:
>For strcmp() this is probably frivolous, but efficient implementations of
>strspn(), strcspn(), or strpbrk() *do* rely on modifying a global table;
>this turns an O(m*n) operation into an O(m+n) one and is well worth doing.
While I understand why use of a table makes the implementation efficient,
and further that the standard allows this table to be a global variable, I
don't see why it's necessary for the table to be global to achieve the
efficiency. It could be allocated on the stack, or if it's too big for the
stack it could be malloc'ed on entry and freed on exit from those
functions. It's clear that this is slightly less efficient than not having
to allocate a new table each time, it's just a one-time expense for the
call, and still allows the inner loop to be fast.
--
Barry Margolin
BBN Planet, Cambridge, MA
bar...@bbnplanet.com - Phone (617) 873-3126 - Fax (617) 873-6351
(BBN customers, please call (800) 632-7638 option 1 for support)
Ben Chase
Richard Pettit [Engineer] (ri...@valley.West.Sun.COM) wrote:
: Sun's qsort() implementation is not very good. For sets of 13 or less
: elements it uses an insertion sort. For 14 or over it uses a poorly
: written quick sort which is *not* recursive. The performance is ok until
: you get to a large set at which point performance breaks down.
: In a comparison between the qsort() that I posted earlier, a threaded
: version of the same and the stock implementation, I got the following
: results from sorting 1 million integers:
: avg nonthreaded case = 7.05 seconds
: avg threaded case = 3.47 seconds
: avg stock case = 9.41 seconds
You're going to have to substantiate that first statement. In
particular, you need to describe the input that gave those running
times. Are you sorting 1 million integers, all of which are different
from each other, or 1 million integers, many of which may have the
same value? I've already bumped into a performance problem if many
elements of the input array are equal, and understand this problem,
and know how to avoid it. Is there something else to avoid?
If anyone can explain why the performance of Sun's implementation
allegedly breaks down on a large input, other than the obvious
n*log(n) performance penalty, I'd be interested in hearing why. (No
need to mention obvious things like overwhelming the data cache, or
paging caused by exceeded available physical memory, unless one of
these gotchas gets Sun's implementation worse than others.)
This thing you are calling "threaded case" -- are you talking about a
recursive implementation of qsort that creates new threads within
qsort as it recurses, a new one for each "<" case and ">" case?
My interest is (despite appearances) more than just academic. I
already know that I must write my own sort routine, for performance
reasons and am interested in avoiding additional pitfalls.
- Ben Chase, unix programmer guy
Bradd W. Szonye
Barry Margolin <bar...@tools.bbnplanet.com> wrote in article
<53jfcd$r...@tools.bbnplanet.com>...
> While I understand why use of a table makes the implementation efficient,
> and further that the standard allows this table to be a global variable,
I
> don't see why it's necessary for the table to be global to achieve the
> efficiency. It could be allocated on the stack, or if it's too big for
the
> stack it could be malloc'ed on entry and freed on exit from those
> functions. It's clear that this is slightly less efficient than not
having
> to allocate a new table each time, it's just a one-time expense for the
> call, and still allows the inner loop to be fast.
For thread-safe libraries, it's even more common to use a copy-on-write
strategy for the underlying memory and a pointer or inlined/intrinsic
function to access the "real" static data. That way you get speed when you
don't modify the statics and safety when you do.
This technique wasn't available on some older Unixes with weak
virtual-memory schemes. Now, most operating systems--even Windows--support
this technique.
Richard Pettit [Engineer]
In article <53jhhs$a...@ralph.vnet.net>, b...@jazzmin.vnet.net (Ben Chase) writes:
>Richard Pettit [Engineer] (ri...@valley.West.Sun.COM) wrote:
>: Sun's qsort() implementation is not very good. For sets of 13 or less
>: elements it uses an insertion sort. For 14 or over it uses a poorly
>: written quick sort which is *not* recursive. The performance is ok until
>: you get to a large set at which point performance breaks down.
>
>: In a comparison between the qsort() that I posted earlier, a threaded
>: version of the same and the stock implementation, I got the following
>: results from sorting 1 million integers:
>
>: avg nonthreaded case = 7.05 seconds
>: avg threaded case = 3.47 seconds
>: avg stock case = 9.41 seconds
>
>You're going to have to substantiate that first statement. In
>particular, you need to describe the input that gave those running
>times. Are you sorting 1 million integers, all of which are different
>from each other, or 1 million integers, many of which may have the
>same value? I've already bumped into a performance problem if many
>elements of the input array are equal, and understand this problem,
>and know how to avoid it. Is there something else to avoid?
Rather than describe it, I'll include a shell archive containing the source
code for running the test. Use the "ttest" script with a numeric argument
for how many ints to sort.
>If anyone can explain why the performance of Sun's implementation
>allegedly breaks down on a large input, other than the obvious
>n*log(n) performance penalty, I'd be interested in hearing why. (No
>need to mention obvious things like overwhelming the data cache, or
>paging caused by exceeded available physical memory, unless one of
>these gotchas gets Sun's implementation worse than others.)
It's just the way it's written. I'd call it a bad algorithm, but someone
will scan my code and tell me mine is too.
>This thing you are calling "threaded case" -- are you talking about a
>recursive implementation of qsort that creates new threads within
>qsort as it recurses, a new one for each "<" case and ">" case?
Instead of recursively calling itself, it creates a thread.
>My interest is (despite appearances) more than just academic. I
>already know that I must write my own sort routine, for performance
>reasons and am interested in avoiding additional pitfalls.
You may use mine unless for commercial purposes, under which case you must
pay me millions of dollars so I can retire and not worry about quick sorts
anymore.
> - Ben Chase, unix programmer guy
Rich Pettit, burnout guy
+- + -- + -+
Richard Pettit | Richard...@West.Sun.COM | 15821 Ventura Blvd #270
SMCC Engineer | "Macrosolutions to Megaproblems" | Encino, CA 91436
{S(=@[length,%1]->id;apndl@[1,S@tl]@(while not@!and@&<=@distl@[1,tl] rotr))}
--- yeah, here ya go, another shar file. gak. ---
# This is a shell archive. Remove anything before this line,
# then unpack it by saving it in a file and typing "sh file".
#
# Wrapped by richp on Thu Oct 10 20:28:13 PDT 1996
# Contents: README Makefile check.awk qstock.c qtest.c quick.c tquick.c ttest
echo x - README
sed 's/^@//' > "README" <<'@//E*O*F README//'
Files:
Makefile - builds test programs
check.awk - check the (optional) output of the test programs
qstock.c - test program that calls the libc qsort
qtest.c - test program that calls the new qsort (quicksort)
quick.c - single-thread quicksort
tquick.c - multi-thread quicksort
ttest - script that runs the tests
What to do:
% make
cc -xO4 -`fpversion -foption` -c qtest.c
cc -xO4 -`fpversion -foption` -c tquick.c
cc -xO4 -`fpversion -foption` -o thread qtest.o tquick.o -lthread -lkstat
cc -xO4 -`fpversion -foption` -c quick.c
cc -xO4 -`fpversion -foption` -o nonthread qtest.o quick.o
cc -xO4 -`fpversion -foption` -c qstock.c
cc -xO4 -`fpversion -foption` -o stock qstock.o
%
%
% ./ttest 500000 # this is how many ints to sort
@//E*O*F README//
chmod u=rw,g=r,o=r README
echo x - Makefile
sed 's/^@//' > "Makefile" <<'@//E*O*F Makefile//'
CFLAGS = -xO4
#CFLAGS = -O -fstrength-reduce -finline-functions
TOBJS = qtest.o tquick.o
NOBJS = qtest.o quick.o
SOBJS = qstock.o
SHFILES = README Makefile check.awk qstock.c qtest.c quick.c tquick.c ttest
LIBS = -lthread -lkstat
CC = cc
#CC = gcc
LDFLAGS =
#LDFLAGS = -L/usr/5lib
all: thread nonthread stock
thread: $(TOBJS)
$(CC) $(CFLAGS) -o thread $(TOBJS) $(LIBS)
nonthread: $(NOBJS)
$(CC) $(CFLAGS) -o nonthread $(NOBJS) $(LDFLAGS)
stock: $(SOBJS)
$(CC) $(CFLAGS) -o stock $(SOBJS) $(LDFLAGS)
clean:
/bin/rm -f *.o a.out thread nonthread stock
sort.sh:
shar $(SHFILES) > sort.sh
@//E*O*F Makefile//
chmod u=rw,g=r,o=r Makefile
echo x - check.awk
sed 's/^@//' > "check.awk" <<'@//E*O*F check.awk//'
BEGIN {
last = 0;
}
{
if ($NF < last)
printf("%s is out of order\n", $0);
last = $NF;
}
@//E*O*F check.awk//
chmod u=rw,g=r,o=r check.awk
echo x - qstock.c
sed 's/^@//' > "qstock.c" <<'@//E*O*F qstock.c//'
#include <unistd.h>
#include <stdlib.h>
#include <sys/times.h>
static int
compare(const void *a, const void *b)
{
return *((int *) a) - *((int *) b);
}
main(int argc, char *argv[])
{
int i;
int hz;
int size;
int *array;
clock_t start;
clock_t end;
struct tms tbuf;
if (argc != 2) {
printf("Use: %s array-size\n", argv[0]);
exit(1);
}
size = atoi(argv[1]);
if (size <= 0) {
printf("Bogus size: %d\n", size);
exit(1);
}
array = (int *) malloc(size * sizeof(int));
if (array == 0) {
perror("malloc");
exit(1);
}
srand(rand());
for(i=0; i<size; i++)
#if 1
array[i] = rand() % size;
#else
array[i] = size - i;
#endif
start = times(&tbuf);
qsort(array, size, sizeof(int), compare);
end = times(&tbuf);
hz = sysconf(_SC_CLK_TCK);
printf("%5.2f\n", (double) (end - start) / (double) hz);
#if 0
for(i=0; i<size; i++)
printf("array[%d] = %d\n", i, array[i]);
#endif
exit(0);
}
@//E*O*F qstock.c//
chmod u=rw,g=r,o=r qstock.c
echo x - qtest.c
sed 's/^@//' > "qtest.c" <<'@//E*O*F qtest.c//'
#include <unistd.h>
#include <stdlib.h>
#include <sys/times.h>
static int
compare(const void *a, const void *b)
{
return *((int *) a) - *((int *) b);
}
main(int argc, char *argv[])
{
int i;
int hz;
int size;
int *array;
clock_t start;
clock_t end;
struct tms tbuf;
if (argc != 2) {
printf("Use: %s array-size\n", argv[0]);
exit(1);
}
size = atoi(argv[1]);
if (size <= 0) {
printf("Bogus size: %d\n", size);
exit(1);
}
array = (int *) malloc(size * sizeof(int));
if (array == 0) {
perror("malloc");
exit(1);
}
hz = sysconf(_SC_CLK_TCK);
srand(rand());
for(i=0; i<size; i++)
#if 0
array[i] = rand() % size;
#else
array[i] = size - i;
#endif
start = times(&tbuf);
quicksort(array, size, sizeof(int), compare);
end = times(&tbuf);
printf("%5.2f\n", (double) (end - start) / (double) hz);
#if 0
for(i=0; i<size; i++)
printf("array[%d] = %d\n", i, array[i]);
#endif
exit(0);
}
@//E*O*F qtest.c//
chmod u=rw,g=r,o=r qtest.c
echo x - quick.c
sed 's/^@//' > "quick.c" <<'@//E*O*F quick.c//'
/*
* single-thread quick-sort. See man page for qsort(3c) for info.
*
* Written by: Richard Pettit (Richard...@West.Sun.COM)
*
* Copyright(c) 1996, Richard Pettit
*
* Commercial reuse by permission of author only.
*/
#include <stdlib.h>
#include <sys/types.h>
#define SUB(a, n) ((void *) (((unsigned char *) (a)) + ((n) * width)))
#define MIN(a, b) ((a < b) ? a : b)
#define SWAP(a, i, j, width) \
{ \
int n; \
unsigned char uc; \
unsigned short us; \
unsigned int ui; \
unsigned long long ull; \
\
if (SUB(a, i) == pivot) \
pivot = SUB(a, j); \
else if (SUB(a, j) == pivot) \
pivot = SUB(a, i); \
\
/* one of the more convoluted swaps I've done */ \
switch(width) { \
case 1: \
uc = *((unsigned char *) SUB(a, i)); \
*((unsigned char *) SUB(a, i)) = *((unsigned char *) SUB(a, j)); \
*((unsigned char *) SUB(a, j)) = uc; \
break; \
case 2: \
us = *((unsigned short *) SUB(a, i)); \
*((unsigned short *) SUB(a, i)) = *((unsigned short *) SUB(a, j)); \
*((unsigned short *) SUB(a, j)) = us; \
break; \
case 4: \
ui = *((unsigned int *) SUB(a, i)); \
*((unsigned int *) SUB(a, i)) = *((unsigned int *) SUB(a, j)); \
*((unsigned int *) SUB(a, j)) = ui; \
break; \
case 8: \
ull = *((unsigned long long *) SUB(a, i)); \
*((unsigned long long *) SUB(a,i)) = *((unsigned long long *) SUB(a,j)); \
*((unsigned long long *) SUB(a, j)) = ull; \
break; \
default: \
for(n=0; n<width; n++) { \
uc = ((unsigned char *) SUB(a, i))[n]; \
((unsigned char *) SUB(a, i))[n] = ((unsigned char *) SUB(a, j))[n]; \
((unsigned char *) SUB(a, j))[n] = uc; \
} \
break; \
} \
}
void
quicksort(void *a, size_t n, size_t width,
int (*compar)(const void *, const void *))
{
register int i;
register int j;
int z;
void *t;
void *b[3];
void *pivot = 0;
switch(n) {
case 0:
case 1:
return;
case 2:
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
return;
case 3:
/* three sort */
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
SWAP(a, 2, 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
SWAP(a, 1, 0, width);
}
return;
default:
/* find the pivot point */
if (n > 3) {
b[0] = SUB(a, 0);
b[1] = SUB(a, n / 2);
b[2] = SUB(a, n - 1);
/* three sort */
if ((*compar)(b[0], b[1]) > 0) {
t = b[0];
b[0] = b[1];
b[1] = t;
}
/* the first two are now ordered, now order the second two */
if ((*compar)(b[2], b[1]) < 0) {
t = b[1];
b[1] = b[2];
b[2] = t;
}
/* should the second be moved to the first? */
if ((*compar)(b[1], b[0]) < 0) {
t = b[0];
b[0] = b[1];
b[1] = t;
}
if ((*compar)(b[0], b[2]) != 0)
if ((*compar)(b[0], b[1]) < 0)
pivot = b[1];
else
pivot = b[2];
if (pivot == 0) {
for(i=1; i<n; i++) {
z = (*compar)(SUB(a, 0), SUB(a, i));
if (z != 0) {
pivot = (z > 0) ? SUB(a, 0) : SUB(a, i);
break;
}
}
}
}
break;
}
if (pivot == 0)
return;
/* sort */
i = 0;
j = n - 1;
while(i <= j) {
while((*compar)(SUB(a, i), pivot) < 0)
++i;
while((*compar)(SUB(a, j), pivot) >= 0)
--j;
if (i < j) {
SWAP(a, i, j, width);
++i;
--j;
}
}
/* sort the sides judiciously */
switch(i) {
case 1:
break;
case 2:
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
break;
case 3:
/* three sort */
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
SWAP(a, 2, 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
SWAP(a, 1, 0, width);
}
break;
default:
quicksort(a, i, width, compar);
break;
}
j = n - i;
switch(j) {
case 1:
break;
case 2:
if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
SWAP(a, i, i + 1, width);
}
break;
case 3:
/* three sort */
if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
SWAP(a, i, i + 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, i + 2), SUB(a, i + 1)) < 0) {
SWAP(a, i + 2, i + 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, i + 1), SUB(a, i)) < 0) {
SWAP(a, i + 1, i, width);
}
break;
default:
quicksort(SUB(a, i), j, width, compar);
break;
}
}
@//E*O*F quick.c//
chmod u=rw,g=r,o=r quick.c
echo x - tquick.c
sed 's/^@//' > "tquick.c" <<'@//E*O*F tquick.c//'
/*
* multiple-thread quick-sort. See man page for qsort(3c) for info.
* Works fine on uniprocessor machines as well.
*
* Written by: Richard Pettit (Richard...@West.Sun.COM)
*
* Copyright(c) 1996, Richard Pettit
*
* Commercial reuse by permission of author only.
*/
#include <unistd.h>
#include <stdlib.h>
#include <thread.h>
/* don't create more threads for less than this */
#define SLICE_THRESH 4096
/* how many threads per lwp */
#define THR_PER_LWP 4
/* cast the void to a one byte quanitity and compute the offset */
#define SUB(a, n) ((void *) (((unsigned char *) (a)) + ((n) * width)))
typedef struct {
void *sa_base;
int sa_nel;
size_t sa_width;
int (*sa_compar)(const void *, const void *);
} sort_args_t;
/* for all instances of quicksort */
static int threads_avail;
#define SWAP(a, i, j, width) \
{ \
int n; \
unsigned char uc; \
unsigned short us; \
unsigned int ui; \
unsigned long long ull; \
\
if (SUB(a, i) == pivot) \
pivot = SUB(a, j); \
else if (SUB(a, j) == pivot) \
pivot = SUB(a, i); \
\
/* one of the more convoluted swaps I've done */ \
switch(width) { \
case 1: \
uc = *((unsigned char *) SUB(a, i)); \
*((unsigned char *) SUB(a, i)) = *((unsigned char *) SUB(a, j)); \
*((unsigned char *) SUB(a, j)) = uc; \
break; \
case 2: \
us = *((unsigned short *) SUB(a, i)); \
*((unsigned short *) SUB(a, i)) = *((unsigned short *) SUB(a, j)); \
*((unsigned short *) SUB(a, j)) = us; \
break; \
case 4: \
ui = *((unsigned int *) SUB(a, i)); \
*((unsigned int *) SUB(a, i)) = *((unsigned int *) SUB(a, j)); \
*((unsigned int *) SUB(a, j)) = ui; \
break; \
case 8: \
ull = *((unsigned long long *) SUB(a, i)); \
*((unsigned long long *) SUB(a,i)) = *((unsigned long long *) SUB(a,j)); \
*((unsigned long long *) SUB(a, j)) = ull; \
break; \
default: \
for(n=0; n<width; n++) { \
uc = ((unsigned char *) SUB(a, i))[n]; \
((unsigned char *) SUB(a, i))[n] = ((unsigned char *) SUB(a, j))[n]; \
((unsigned char *) SUB(a, j))[n] = uc; \
} \
break; \
} \
}
static void *
_quicksort(void *arg)
{
sort_args_t *sargs = (sort_args_t *) arg;
register void *a = sargs->sa_base;
int n = sargs->sa_nel;
int width = sargs->sa_width;
int (*compar)(const void *, const void *) = sargs->sa_compar;
register int i;
register int j;
int z;
int thread_count = 0;
void *t;
void *b[3];
void *pivot = 0;
sort_args_t sort_args[2];
thread_t tid;
switch(n) {
case 0:
case 1:
return;
case 2:
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
return;
case 3:
/* three sort */
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
SWAP(a, 2, 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
SWAP(a, 1, 0, width);
}
return;
default:
/* find the pivot point */
if (n > 3) {
b[0] = SUB(a, 0);
b[1] = SUB(a, n / 2);
b[2] = SUB(a, n - 1);
/* three sort */
if ((*compar)(b[0], b[1]) > 0) {
t = b[0];
b[0] = b[1];
b[1] = t;
}
/* the first two are now ordered, now order the second two */
if ((*compar)(b[2], b[1]) < 0) {
t = b[1];
b[1] = b[2];
b[2] = t;
}
/* should the second be moved to the first? */
if ((*compar)(b[1], b[0]) < 0) {
t = b[0];
b[0] = b[1];
b[1] = t;
}
if ((*compar)(b[0], b[2]) != 0)
if ((*compar)(b[0], b[1]) < 0)
pivot = b[1];
else
pivot = b[2];
if (pivot == 0) {
for(i=1; i<n; i++) {
z = (*compar)(SUB(a, 0), SUB(a, i));
if (z != 0) {
pivot = (z > 0) ? SUB(a, 0) : SUB(a, i);
break;
}
}
}
}
break;
}
if (pivot == 0)
return;
/* sort */
i = 0;
j = n - 1;
while(i <= j) {
while((*compar)(SUB(a, i), pivot) < 0)
++i;
while((*compar)(SUB(a, j), pivot) >= 0)
--j;
if (i < j) {
SWAP(a, i, j, width);
++i;
--j;
}
}
/* sort the sides judiciously */
switch(i) {
case 1:
break;
case 2:
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
break;
case 3:
/* three sort */
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
SWAP(a, 2, 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
SWAP(a, 1, 0, width);
}
break;
default:
sort_args[0].sa_base = a;
sort_args[0].sa_nel = i;
sort_args[0].sa_width = width;
sort_args[0].sa_compar = compar;
if ((threads_avail > 0) && (i > SLICE_THRESH)) {
threads_avail--;
thr_create(0, 0, _quicksort, &sort_args[0], 0, &tid);
thread_count = 1;
} else
_quicksort(&sort_args[0]);
break;
}
j = n - i;
switch(j) {
case 1:
break;
case 2:
if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
SWAP(a, i, i + 1, width);
}
break;
case 3:
/* three sort */
if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
SWAP(a, i, i + 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, i + 2), SUB(a, i + 1)) < 0) {
SWAP(a, i + 2, i + 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, i + 1), SUB(a, i)) < 0) {
SWAP(a, i + 1, i, width);
}
break;
default:
sort_args[1].sa_base = SUB(a, i);
sort_args[1].sa_nel = j;
sort_args[1].sa_width = width;
sort_args[1].sa_compar = compar;
if ((thread_count == 0) && (threads_avail > 0) && (i > SLICE_THRESH)) {
threads_avail--;
thr_create(0, 0, _quicksort, &sort_args[1], 0, &tid);
thread_count = 1;
} else
_quicksort(&sort_args[1]);
break;
}
if (thread_count) {
thr_join(tid, 0, 0);
threads_avail++;
}
return 0;
}
void
quicksort(void *a, int n, int width,
int (*compar)(const void *, const void *))
{
static int ncpus = -1;
sort_args_t sort_args;
if (ncpus == -1) {
ncpus = sysconf( _SC_NPROCESSORS_ONLN);
/* lwp for each cpu */
if ((ncpus > 1) && (thr_getconcurrency() < ncpus))
thr_setconcurrency(ncpus);
/* thread count not to exceed THR_PER_LWP per lwp */
threads_avail = (ncpus == 1) ? 0 : (ncpus * THR_PER_LWP);
}
sort_args.sa_base = a;
sort_args.sa_nel = n;
sort_args.sa_width = width;
sort_args.sa_compar = compar;
(void) _quicksort(&sort_args);
}
@//E*O*F tquick.c//
chmod u=rw,g=r,o=r tquick.c
echo x - ttest
sed 's/^@//' > "ttest" <<'@//E*O*F ttest//'
#! /bin/sh
if [ $# -ne 1 ]; then
echo Use: $0 array-size
exit
fi
trap "/bin/rm -f /tmp/$$" 0
COUNT=$1
{
echo nonthread > /dev/tty
for i in 1 2 3 4 5
do
./nonthread $COUNT
done
echo thread > /dev/tty
for i in 1 2 3 4 5
do
./thread $COUNT
done
echo stock > /dev/tty
for i in 1 2 3 4 5
do
./stock $COUNT
done
} > /tmp/$$
awk '{
if (NR <= 5)
nonthread += $1;
else if (NR <= 10)
thread += $1;
else
stock += $1;
}
END {
printf("avg nonthreaded case = %5.2f seconds\n", nonthread / 5.0);
printf("avg threaded case = %5.2f seconds\n", thread / 5.0);
printf("avg stock case = %5.2f seconds\n", stock / 5.0);
}' < /tmp/$$
@//E*O*F ttest//
chmod u=rwx,g=rx,o=rx ttest
exit 0
D. J. Bernstein
I don't understand why people are spending all this time worrying about
the performance of a routine that (1) has a callback interface and (2)
is thus forced to use a slow algorithm such as quicksort.
On a much smaller machine, a Pentium-100, I can sort 1000000 32-bit ints
in 0.9 to 2.4 seconds, depending on the distribution of inputs.
(Most of the time is spent waiting for memory. The nominal time is under
half a second, independent of distribution; the code is reasonably
cache-friendly, with under 300 relevant memory lines at any moment; but
writing several million words to DRAM still takes a very long time.)
In contrast, the BSD/OS qsort() typically takes 9 seconds. A non-generic
qsort(), with 32-bit comparisons built in, takes 5 seconds.
I haven't done much SPARC asm, and I don't know how the UltraSPARC cache
is structured, but surely a competent SPARC programmer can blow away all
of the qsort() routines described here.
---Dan
Richard A. O'Keefe
bar...@tools.bbnplanet.com (Barry Margolin) writes:
>In article <53iel5$esl$1...@goanna.cs.rmit.edu.au>,
>Richard A. O'Keefe <o...@goanna.cs.rmit.edu.au> wrote:
>>For strcmp() this is probably frivolous, but efficient implementations of
>>strspn(), strcspn(), or strpbrk() *do* rely on modifying a global table;
>>this turns an O(m*n) operation into an O(m+n) one and is well worth doing.
>While I understand why use of a table makes the implementation efficient,
>and further that the standard allows this table to be a global variable, I
>don't see why it's necessary for the table to be global to achieve the
>efficiency. It could be allocated on the stack, or if it's too big for the
>stack it could be malloc'ed on entry and freed on exit from those
>functions. It's clear that this is slightly less efficient than not having
>to allocate a new table each time, it's just a one-time expense for the
>call, and still allows the inner loop to be fast.
Why not? Because for efficiency, the table must be *incrementally*
revised, not reinitialised from scratch each time.
Here's the trick, which I invented in about 1982 for use in my Emacs-like
editor "thief". It is probably well known.
unsigned char table[Alphabet_Size]; /* 7 or 8 bit alphabet */
unsigned char cycle = 0;
void set_up_table(unsigned char const *set, bool include_NUL) {
if (set != 0) { /* useful for strtok() too */
if (cycle == Alphabet_Size - 1) {
memset(table, 0, sizeof table);
cycle = 1;
} else {
cycle = cycle + 1;
}
while (*set) table[*set++] = cycle;
}
table[0] = include_NUL ? cycle : 0;
}
#define in_current_set(c) (table[c] == cycle)
size_t strspn(char const *src, char const *set) {
unsigned char const *s = (unsigned char const *)src;
size_t i;
assert(set != 0);
set_up_table((unsigned char const *)set, false);
for (i = 0; in_current_set(s[i]); i++) {}
return i;
}
size_t strcspn(char const *src, char const *set) {
unsigned char const *s = (unsigned char const *)src;
size_t i;
assert(set != 0);
set_up_table((unsigned char const *)set, true);
for (i = 0; !in_current_set(s[i]); i++) {}
return i;
}
with the other variations being obvious.
It is clear that the for() loops in str{,c}spn() are O(|src|).
It should also be clear that set_up_table() has one part that
takes O(|set|) time and another part that takes O(Alphabet_Size)
time but happens only once in every Alphabet_Size - 1 calls,
so the amortised cost is O(1) for that part. So each call to
str{,c}spn() takes O(|src| + |set| + 1) time.
If a new table were allocated on each call, the cost of this method
would soar to O(|src| + |set| + Alphabet_Size), which would not be
so good. It's not a case of "slightly" less efficient, it's a case
of DRAMATICALLY less efficient, with more time being spent setting
up the table than doing useful work.
The neat thing about the present scheme is that it scales to 16-bit
characters reasonably well if you make 'table' and 'cycle' unsigned
short. But reallocating a 128k table every time, whether on the stack
or not, would be too costly because of the need to initialise it.
I do not know whether any existing commercial implementations of C
use this incrementally-revised table technique for strspn(), strcpspn(),
strpbrk(), or strtok(). Timing tests I've done on a couple of UNIX
systems suggested to me that they didn't, which is why I don't actually
_use_ any of those functions (not to mention the brain-dead interface
of strtok()).
Ben Chase
D. J. Bernstein (d...@koobera.math.uic.edu) wrote:
: I don't understand why people are spending all this time worrying about
: the performance of a routine that (1) has a callback interface and
We do this because it is convenient to call a library routine to sort
data, rather than reimplement a sort routine every time something new
type of data must be sorted. By complaining about the implementation
of qsort, perhaps we can persuade the Unix vendors to provide a more
efficient implementation, thus reducing the number of times we must
write or refurbish for reuse better sort routines of our own.
: (2) is thus forced to use a slow algorithm such as quicksort.
Please share with us, O Wise One, the name of your sorting algorithm,
faster than quicksort, and only available if a callback interface is
not used. I assume you are not referring to radix sort, since you say
you are sorting 32-bit integers.
- Ben Chase
D. J. Bernstein
In article <54dr3u$a...@ralph.vnet.net>, Ben Chase <b...@katie.vnet.net> wrote:
> We do this because it is convenient to call a library routine to sort
> data, rather than reimplement a sort routine every time something new
> type of data must be sorted.
To sort a random data type with qsort(), you need to write a comparison
function, such as strcoll().
To sort a random data type with (say) the BSD 4.4 radixsort(), you need
to write a transformation function, such as strxfrm().
The idea that qsort() is generic, while radixsort() is not, is nonsense.
> By complaining about the implementation of qsort,
You're missing the point. If you care about speed, _don't use qsort()_.
Complaining about the slowness of qsort() is like complaining about the
insecurity of sendmail. It's inherent in the architecture.
> I assume you are not referring to radix sort, since you say
> you are sorting 32-bit integers.
Bytewise LSD radix sort. Pentium-100, 430FX chipset, wimpy cache.
500000 random 32-bit integers in 1.078 seconds.
1000000 random 32-bit integers in 2.154 seconds.
---Dan
Craig_E...@transarc.com
Excerpts from netnews.comp.unix.solaris: 20-Oct-96 Re: qsort performance
D. J. Bernstein@koobera. (1086)
> To sort a random data type with (say) the BSD 4.4 radixsort(), you need
> to write a transformation function, such as strxfrm().
How do I do that when I'm sorting data with more than 32 significant
bits, like unbounded strings?
D. J. Bernstein
<Craig_E...@transarc.com> wrote:
> How do I do that when I'm sorting data with more than 32 significant
> bits, like unbounded strings?
You do exactly what I said: you write a transformation function, such as
strxfrm().
Why don't you go look at what radixsort() does?
---Dan
Dann Corbit
You can always use counting sort, though. Counting sort
is linear, like radixsort variations. It's especially
good with memory mapped files, since it does sequential
scans of the data.
--
1. I speak for myself
2. I'm just a contractor, I don't work for Microsoft!
Matus Uhlar <uh...@ccnews.ke.sanet.sk> wrote in article
<54hsbg$on6$1...@ccnews.ke.sanet.sk>...
> -> > To sort a random data type with (say) the BSD 4.4 radixsort(), you
need
> -> > to write a transformation function, such as strxfrm().
>
> -> How do I do that when I'm sorting data with more than 32 significant
> -> bits, like unbounded strings?
>
> If you can't do that, you can't use radixsort...
> --
> E-mail: Matus...@tuke.sk WWW: http://ccsun.tuke.sk/users/uhlar
> IRC: fantomas, TALK: uh...@ccnews.ke.sanet.sk
> ...and if you think I'm talking for my employer, you're wrong...
>
Matus Uhlar
Ben Chase
Dann Corbit (a-c...@microsoft.com) wrote:
: Counting sort is linear, like radixsort variations. It's especially
: good with memory mapped files, since it does sequential scans of the
: data.
I am unfamiliar with "counting sort". Do you have a reference to some
book or article that describes this?
- Ben Chase