From owner-freebsd-current@FreeBSD.ORG  Wed Jun  8 07:46:29 2005
Return-Path: <owner-freebsd-current@FreeBSD.ORG>
X-Original-To: freebsd-current@freebsd.org
Delivered-To: freebsd-current@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id 318F616A41C;
	Wed,  8 Jun 2005 07:46:29 +0000 (GMT)
	(envelope-from keramida@freebsd.org)
Received: from kane.otenet.gr (kane.otenet.gr [195.170.0.95])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 72E6043D1D;
	Wed,  8 Jun 2005 07:46:28 +0000 (GMT)
	(envelope-from keramida@freebsd.org)
Received: from orion.daedalusnetworks.priv (aris.bedc.ondsl.gr [62.103.39.226])
	by kane.otenet.gr (8.13.4/8.13.4/Debian-1) with SMTP id j587kGGO006416; 
	Wed, 8 Jun 2005 10:46:16 +0300
Received: from orion.daedalusnetworks.priv (orion [127.0.0.1])
	by orion.daedalusnetworks.priv (8.13.3/8.13.3) with ESMTP id
	j587kF1F001054; Wed, 8 Jun 2005 10:46:15 +0300 (EEST)
	(envelope-from keramida@freebsd.org)
Received: (from keramida@localhost)
	by orion.daedalusnetworks.priv (8.13.3/8.13.3/Submit) id j587kEFC001053;
	Wed, 8 Jun 2005 10:46:14 +0300 (EEST)
	(envelope-from keramida@freebsd.org)
Date: Wed, 8 Jun 2005 10:46:14 +0300
From: Giorgos Keramidas <keramida@freebsd.org>
To: Dag-Erling Sm?rgrav <des@des.no>
Message-ID: <20050608074613.GA979@orion.daedalusnetworks.priv>
References: <17059.7150.269428.448187@roam.psg.com>
	<42A4D5D0.9040500@elischer.org> <42A59367.6060307@centtech.com>
	<20050607175242.D61131@fledge.watson.org>
	<86ll5lmhs3.fsf@xps.des.no>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <86ll5lmhs3.fsf@xps.des.no>
Cc: freebsd-fs@freebsd.org, Randy Bush <randy@psg.com>,
	FreeBSD Current <freebsd-current@freebsd.org>,
	Robert Watson <rwatson@freebsd.org>, Julian Elischer <julian@elischer.org>,
	Eric Anderson <anderson@centtech.com>
Subject: Re: you are in an fs with millions of small files
X-BeenThere: freebsd-current@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Discussions about the use of FreeBSD-current
	<freebsd-current.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>, 
	<mailto:freebsd-current-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current>
List-Post: <mailto:freebsd-current@freebsd.org>
List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Wed, 08 Jun 2005 07:46:29 -0000

On 2005-06-08 09:25, Dag-Erling Sm?rgrav <des@des.no> wrote:
>Robert Watson <rwatson@FreeBSD.org> writes:
>> - Some appliations behave poorly with large trees.  ls(1) is the classic
>>    example -- sorting 150,000 strings is expensive, and should be avoided.
>
> That's because fts's sorting code is brain-dead.  It starts by reading
> the entire directory into a linked list, then copies that list into an
> array which it passes to qsort(), and finally converts the array back
> into a linked list.

Is there a better way to sort a linked list (not necessarily a
singly-linked list, like the one fts_link is used for).  If it makes
things easier on the sorting side, we could always convert fts_link to a
real `LIST_ENTRY(FTSENT) fts_link', but I suspect that sorting would
still involve at least some sort of array, unless we stop using qsort().