From owner-freebsd-arch@FreeBSD.ORG Thu Mar 15 15:01:58 2007 Return-Path: X-Original-To: freebsd-arch@freebsd.org Delivered-To: freebsd-arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id CA2FF16A400; Thu, 15 Mar 2007 15:01:58 +0000 (UTC) (envelope-from dds@aueb.gr) Received: from blue.servers.aueb.gr (blue.servers.aueb.gr [195.251.255.132]) by mx1.freebsd.org (Postfix) with ESMTP id 8616413C448; Thu, 15 Mar 2007 15:01:58 +0000 (UTC) (envelope-from dds@aueb.gr) Received: from [195.251.254.141] ([::ffff:195.251.254.141]) by blue.servers.aueb.gr with esmtp; Thu, 15 Mar 2007 16:51:54 +0200 id 000D1229.45F95D8A.00002F17 Message-ID: <45F95D87.9070108@aueb.gr> Date: Thu, 15 Mar 2007 16:51:51 +0200 From: Diomidis Spinellis User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.0.9) Gecko/20061211 SeaMonkey/1.0.7 MIME-Version: 1.0 To: Ivan Voras References: <45F906ED.8070100@aueb.gr> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Cc: freebsd-threads@freebsd.org, freebsd-arch@freebsd.org Subject: Re: Multithreaded qsort(3) X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 15 Mar 2007 15:01:58 -0000 Ivan Voras wrote: > Diomidis Spinellis wrote: >> I've added multhread support to our qsort implementation. You can see >> the code at 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) 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