From owner-freebsd-arch@FreeBSD.ORG  Thu Mar 15 14:05:27 2007
Return-Path: <owner-freebsd-arch@FreeBSD.ORG>
X-Original-To: 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 8164316A400
	for <arch@freebsd.org>; Thu, 15 Mar 2007 14:05:27 +0000 (UTC)
	(envelope-from wollman@khavrinen.csail.mit.edu)
Received: from khavrinen.csail.mit.edu (khavrinen.csail.mit.edu [128.30.28.20])
	by mx1.freebsd.org (Postfix) with ESMTP id 2FBC613C46E
	for <arch@freebsd.org>; Thu, 15 Mar 2007 14:05:27 +0000 (UTC)
	(envelope-from wollman@khavrinen.csail.mit.edu)
Received: from khavrinen.csail.mit.edu (localhost.csail.mit.edu [127.0.0.1])
	by khavrinen.csail.mit.edu (8.13.6/8.13.6) with ESMTP id l2FDYDLU024196
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256
	verify=OK CN=khavrinen.csail.mit.edu issuer=Client+20CA);
	Thu, 15 Mar 2007 09:34:13 -0400 (EDT)
	(envelope-from wollman@khavrinen.csail.mit.edu)
Received: (from wollman@localhost)
	by khavrinen.csail.mit.edu (8.13.6/8.13.6/Submit) id l2FDYAfo024194;
	Thu, 15 Mar 2007 09:34:10 -0400 (EDT) (envelope-from wollman)
Date: Thu, 15 Mar 2007 09:34:10 -0400 (EDT)
From: Garrett Wollman <wollman@khavrinen.csail.mit.edu>
Message-Id: <200703151334.l2FDYAfo024194@khavrinen.csail.mit.edu>
To: dds@aueb.gr
In-Reply-To: <45F906ED.8070100@aueb.gr>
Organization: MIT Computer Science & Artificial Intelligence Laboratory
X-Greylist: Sender DNS name whitelisted, not delayed by milter-greylist-3.0
	(khavrinen.csail.mit.edu [127.0.0.1]);
	Thu, 15 Mar 2007 08:34:13 -0500 (EST)
Cc: 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 <freebsd-arch.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-arch>,
	<mailto:freebsd-arch-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-arch>
List-Post: <mailto:freebsd-arch@freebsd.org>
List-Help: <mailto:freebsd-arch-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-arch>,
	<mailto:freebsd-arch-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Thu, 15 Mar 2007 14:05:27 -0000

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?

-GAWollman