Multithreaded qsort(3)

[Diomidis Spinellis]

Garrett Wollman wrote:
> In <45F906ED.8070100 at aueb.gr> you write:
> 
>> $ qsort_mt -t -h 2 -n 100000000 -l	# Integers; qsort(3)
>> 46.5 46.2 0.314
>> $ ./qsort_mt  -t -h 2 -n 100000000	# Integers; qsort_mt
>> 27.5 46.3 0.301
> 
> "fancy algorithms have large constants, and N is usually small".
> 
> Do you have any reason to believe that N is large with sufficient
> frequency to justify the overhead?

My proposed implementation (separate routine) doesn't add any overhead, 
unless you explicitly link it in, in which case I presume you know what 
you're doing.  If I was implementing a BSD version of sort(1) (I will, 
one day) or using qsort in an RDBMS engine, calling qsort_mt would 
certainly be worthwhile.

Memory and disk sizes are growing while CPU speeds are stagnant.  This 
means larger data sizes without corresponding serial horsepower to tame 
them.  Therefore, N is increasing in absolute and in relative terms.

You do have a point though, in that parallelizing the C library isn't by 
itself going to save us.  I run dtrace on some builds (a task I'd like 
to see going faster), and the time spent in libc was below 10%.

Diomidis