From owner-freebsd-current@FreeBSD.ORG Wed Jun 8 09:06:08 2005 Return-Path: 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 DD13F16A41C; Wed, 8 Jun 2005 09:06:08 +0000 (GMT) (envelope-from PeterJeremy@optushome.com.au) Received: from mail14.syd.optusnet.com.au (mail14.syd.optusnet.com.au [211.29.132.195]) by mx1.FreeBSD.org (Postfix) with ESMTP id 556D943D1D; Wed, 8 Jun 2005 09:06:08 +0000 (GMT) (envelope-from PeterJeremy@optushome.com.au) Received: from cirb503493.alcatel.com.au (c211-30-75-229.belrs2.nsw.optusnet.com.au [211.30.75.229]) by mail14.syd.optusnet.com.au (8.12.11/8.12.11) with ESMTP id j5895xsZ021098 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO); Wed, 8 Jun 2005 19:05:59 +1000 Received: from cirb503493.alcatel.com.au (localhost.alcatel.com.au [127.0.0.1]) by cirb503493.alcatel.com.au (8.12.10/8.12.10) with ESMTP id j5895wRx042275; Wed, 8 Jun 2005 19:05:59 +1000 (EST) (envelope-from pjeremy@cirb503493.alcatel.com.au) Received: (from pjeremy@localhost) by cirb503493.alcatel.com.au (8.12.10/8.12.9/Submit) id j5895w7f042274; Wed, 8 Jun 2005 19:05:58 +1000 (EST) (envelope-from pjeremy) Date: Wed, 8 Jun 2005 19:05:58 +1000 From: Peter Jeremy To: Giorgos Keramidas Message-ID: <20050608090558.GF39114@cirb503493.alcatel.com.au> 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> <86zmu1l223.fsf@xps.des.no> <20050608080304.GB1226@orion.daedalusnetworks.priv> <20050608082727.GA23674@orion.daedalusnetworks.priv> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20050608082727.GA23674@orion.daedalusnetworks.priv> User-Agent: Mutt/1.4.2i Cc: Dag-Erling Sm?rgrav , freebsd-current@freebsd.org 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 08 Jun 2005 09:06:09 -0000 On Wed, 2005-Jun-08 11:27:27 +0300, Giorgos Keramidas wrote: >On 2005-06-08 11:03, Giorgos Keramidas wrote: >>> The comparison function is known at the time the directory entries are >>> read, so it should be a simple matter to read them into a red-black >>> tree instead of a singly- linked list. I'm working on a patch. >> >> Thanks :) > >This would require updates/changes to all the users of fts.h too? That would seem to depend on how public the innards of FTS and FTSENT are supposed to be. Whilst refers to singly linked lists and pointers to arrays, consumers are not supposed to allocate either structure themselves and only traverse the list via fts_read() or fts_children() - and only ls(1), mtree(8) and ctm_dequeue(1) use fts_children(). At first glance, it should be fairly easy to change the underlying representation from a linked list to a red-black tree without affecting the API at all. -- Peter Jeremy