Skip site navigation (1)Skip section navigation (2)
Date:      Thu, 15 Mar 2007 16:37:54 +0200
From:      Diomidis Spinellis <dds@aueb.gr>
To:        Garrett Wollman <wollman@khavrinen.csail.mit.edu>
Cc:        arch@freebsd.org
Subject:   Re: Multithreaded qsort(3)
Message-ID:  <45F95A42.7080104@aueb.gr>
In-Reply-To: <200703151334.l2FDYAfo024194@khavrinen.csail.mit.edu>
References:  <200703151334.l2FDYAfo024194@khavrinen.csail.mit.edu>

next in thread | previous in thread | raw e-mail | index | archive | help
Garrett Wollman wrote:
> In <45F906ED.8070100@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



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?45F95A42.7080104>