Date: Thu, 15 Mar 2007 16:51:51 +0200 From: Diomidis Spinellis <dds@aueb.gr> To: Ivan Voras <ivoras@fer.hr> Cc: freebsd-threads@freebsd.org, freebsd-arch@freebsd.org Subject: Re: Multithreaded qsort(3) Message-ID: <45F95D87.9070108@aueb.gr> In-Reply-To: <etbe0r$7hg$1@sea.gmane.org> References: <45F906ED.8070100@aueb.gr> <etbe0r$7hg$1@sea.gmane.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?45F95D87.9070108>