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>