From owner-freebsd-current@FreeBSD.ORG Wed Jun 8 08:02:46 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 2A25716A41C; Wed, 8 Jun 2005 08:02:46 +0000 (GMT) (envelope-from keramida@freebsd.org) Received: from rosebud.otenet.gr (rosebud.otenet.gr [195.170.0.94]) by mx1.FreeBSD.org (Postfix) with ESMTP id 5DF2A43D53; Wed, 8 Jun 2005 08:02:44 +0000 (GMT) (envelope-from keramida@freebsd.org) Received: from orion.daedalusnetworks.priv (aris.bedc.ondsl.gr [62.103.39.226]) by rosebud.otenet.gr (8.13.4/8.13.4/Debian-1) with SMTP id j5882Z5r032677; Wed, 8 Jun 2005 11:02:36 +0300 Received: from orion.daedalusnetworks.priv (orion [127.0.0.1]) by orion.daedalusnetworks.priv (8.13.3/8.13.3) with ESMTP id j5882ZMW001281; Wed, 8 Jun 2005 11:02:35 +0300 (EEST) (envelope-from keramida@freebsd.org) Received: (from keramida@localhost) by orion.daedalusnetworks.priv (8.13.3/8.13.3/Submit) id j5882Ys7001280; Wed, 8 Jun 2005 11:02:34 +0300 (EEST) (envelope-from keramida@freebsd.org) Date: Wed, 8 Jun 2005 11:02:34 +0300 From: Giorgos Keramidas <keramida@freebsd.org> To: Colin Percival <cperciva@freebsd.org> Message-ID: <20050608080234.GA1226@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> <20050608074613.GA979@orion.daedalusnetworks.priv> <42A6A3B1.4090607@freebsd.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <42A6A3B1.4090607@freebsd.org> 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 08:02:46 -0000 On 2005-06-08 00:52, Colin Percival <cperciva@freebsd.org> wrote: > 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. Better, in this case, would be any of: a. faster b. faster and less demanding in memory The red-black tree des mentioned is certainly faster to traverse, but not necessarily less demanding in memory. The memory load when a red-black tree is used will be amortized to a range of "add FTSENT" operations, so it seems nice :-)