Multithreaded qsort(3)

[Diomidis Spinellis]

Ivan Voras wrote:
> Diomidis Spinellis wrote:
>> I've added multhread support to our qsort implementation.  You can see 
>> the code at <http://people.freebsd.org/~dds/qsort_mt.c> and some 
> 
> Interesting idea. I remember talks about OpenMP in gcc 4.2 - maybe it 
> would be better to do it with OpenMP?

I'm not sure that OpenMP is mature and flexible enough for this.  My 
understanding is that the performance of a recursive algorithm, like 
qsort, would depend on the compiler's support for what is termed "nested 
parallelism".  It would certainly save me effort, but given that I've 
written it, this is now a moot point.

I compared my implementation against the qsort available in OmpSCR 
(OpenMP Source Code Repository) 
<http://sourceforge.net/projects/ompscr/> on a Sun Niagara 
(Sun-Fire-T200 - 4 processors with 4 cores each).  As you can see the 
speedup of the OpenMP implementation above two threads is nonexistent. 
Even for two threads, my implementation gets a speedup of 34% and the 
OpenMP one 26%.  Of course, this can well be a problem of the specific 
qsort implementation.

Sun C 5.8 Patch 121015-04 2007/01/10

OmpSCR c_qsort.par compiled with -xopenmp=parallel

         # THREADS       SIZE    STEPS   TIME (secs.)
         1               1000000 10      46.919788
         2               1000000 10      34.391163
         4               1000000 10      34.465052
         8               1000000 10      34.427057

qsort_mt compiles with cc -O qsort_mt.c -DTEST -xc99=all -o qsort_mt

         # THREADS       SIZE     STEPS   TIME (secs.)
         1               50000000 1       39.5
         2               50000000 1       26
         4               50000000 1       20.5
         8               50000000 1       16.6
        16               50000000 1       16.1

Diomidis