From owner-freebsd-current@FreeBSD.ORG  Wed Jun  8 07:52:19 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 C0EB316A41C;
	Wed,  8 Jun 2005 07:52:19 +0000 (GMT)
	(envelope-from cperciva@freebsd.org)
Received: from pd4mo3so.prod.shaw.ca (shawidc-mo1.cg.shawcable.net
	[24.71.223.10])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 7789943D48;
	Wed,  8 Jun 2005 07:52:19 +0000 (GMT)
	(envelope-from cperciva@freebsd.org)
Received: from pd5mr5so.prod.shaw.ca
	(pd5mr5so-qfe3.prod.shaw.ca [10.0.141.181]) by l-daemon
	(Sun ONE Messaging Server 6.0 HotFix 1.01 (built Mar 15 2004))
	with ESMTP id <0IHR009CM9V6VT60@l-daemon>; Wed,
	08 Jun 2005 01:52:18 -0600 (MDT)
Received: from pn2ml4so.prod.shaw.ca ([10.0.121.148])
	by pd5mr5so.prod.shaw.ca (Sun ONE Messaging Server 6.0 HotFix 1.01
	(built Mar
	15 2004)) with ESMTP id <0IHR006519V6HN40@pd5mr5so.prod.shaw.ca>; Wed,
	08 Jun 2005 01:52:18 -0600 (MDT)
Received: from [192.168.0.60]
	(S0106006067227a4a.vc.shawcable.net [24.87.209.6]) by l-daemon
	(iPlanet Messaging Server 5.2 HotFix 1.18 (built Jul 28 2003))
	with ESMTP id <0IHR001079V5MA@l-daemon>;
	Wed, 08 Jun 2005 01:52:18 -0600 (MDT)
Date: Wed, 08 Jun 2005 00:52:17 -0700
From: Colin Percival <cperciva@freebsd.org>
In-reply-to: <20050608074613.GA979@orion.daedalusnetworks.priv>
To: Giorgos Keramidas <keramida@freebsd.org>
Message-id: <42A6A3B1.4090607@freebsd.org>
MIME-version: 1.0
Content-type: text/plain; charset=ISO-8859-1
Content-transfer-encoding: 7bit
X-Accept-Language: en-us, en
X-Enigmail-Version: 0.91.0.0
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>
	<20050608074613.GA979@orion.daedalusnetworks.priv>
User-Agent: Mozilla Thunderbird 1.0.2 (X11/20050406)
Cc: Randy Bush <randy@psg.com>, freebsd-fs@freebsd.org,
	FreeBSD Current <freebsd-current@freebsd.org>,
	Robert Watson <rwatson@freebsd.org>, Julian Elischer <julian@elischer.org>,
	Dag-Erling Sm?rgrav <des@des.no>, 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:52:19 -0000

Giorgos Keramidas wrote:
> On 2005-06-08 09:25, Dag-Erling Sm?rgrav <des@des.no> wrote:
>>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

How do you define "better"?  You can merge-sort a singly-linked list
quite easily, but converting it to an array and back would probably
be faster.

Colin Percival