From owner-freebsd-fs@FreeBSD.ORG Wed Jun 8 08:13:28 2005 Return-Path: X-Original-To: freebsd-fs@freebsd.org Delivered-To: freebsd-fs@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 587D716A421 for ; Wed, 8 Jun 2005 08:13:28 +0000 (GMT) (envelope-from arne_woerner@yahoo.com) Received: from web41206.mail.yahoo.com (web41206.mail.yahoo.com [66.218.93.39]) by mx1.FreeBSD.org (Postfix) with SMTP id 6471043D55 for ; Wed, 8 Jun 2005 08:13:27 +0000 (GMT) (envelope-from arne_woerner@yahoo.com) Received: (qmail 3457 invoked by uid 60001); 8 Jun 2005 08:13:26 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Message-ID:Received:Date:From:Subject:To:Cc:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=xkc42WyJ/hlPWd6MJYgpLoq6C06d7o9SI5Xx8rH0wSdvasjaQ+vQxyWPQH41KRUuW3ZVFkEY5++u3glEYqiwl7w1xCgElsuqfQmSwVygoBUzqgSGNTrZb9uaiPalmEmvw/O50zncRHVfj7NFh7g96a3nI+zf0Fv/iJPrBex52i4= ; Message-ID: <20050608081326.3455.qmail@web41206.mail.yahoo.com> Received: from [213.54.157.31] by web41206.mail.yahoo.com via HTTP; Wed, 08 Jun 2005 01:13:26 PDT Date: Wed, 8 Jun 2005 01:13:26 -0700 (PDT) From: Arne "Wörner" To: Giorgos Keramidas , Colin Percival In-Reply-To: <20050608080234.GA1226@orion.daedalusnetworks.priv> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Cc: freebsd-fs@freebsd.org, Randy Bush , FreeBSD Current , Robert Watson , Julian Elischer , Eric Anderson Subject: Re: you are in an fs with millions of small files X-BeenThere: freebsd-fs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Filesystems List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 08 Jun 2005 08:13:28 -0000 --- Giorgos Keramidas wrote: > 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 :-) > I just remembered or found this algorithm and data structure: 1. a dynamic array of char* L (resized by realloc or so) 2. a dynamic array of char D (resized by realloc or so) 3. the number of char* entries in L C 4. the first unused entry of D L's entries would point into the data in D D contains the data that should be sorted If ls(1) wants to insert a new directory entry, it adds the data to the tail of D, and it adds the pointer to the former tail of D at the right position in L. But I do not know if the shift operations in L are not so good... But the memory usage looks quite good to me... I say, the sort of the directory entries should have a time complexity of O(N*log(N))? Do you think, I should try to implement it? -Arne __________________________________ Discover Yahoo! Get on-the-go sports scores, stock quotes, news and more. Check it out! http://discover.yahoo.com/mobile.html