From owner-freebsd-current@FreeBSD.ORG Wed Jun 8 16:06:45 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 3D32216A41C; Wed, 8 Jun 2005 16:06:45 +0000 (GMT) (envelope-from cswiger@mac.com) Received: from smtpout.mac.com (smtpout.mac.com [17.250.248.70]) by mx1.FreeBSD.org (Postfix) with ESMTP id 3CBC943D48; Wed, 8 Jun 2005 16:06:44 +0000 (GMT) (envelope-from cswiger@mac.com) Received: from mac.com (smtpin07-en2 [10.13.10.152]) by smtpout.mac.com (Xserve/8.12.11/smtpout13/MantshX 4.0) with ESMTP id j58G6bIT014365; Wed, 8 Jun 2005 09:06:38 -0700 (PDT) Received: from [192.168.1.6] (pool-68-161-69-6.ny325.east.verizon.net [68.161.69.6]) (authenticated bits=0) by mac.com (Xserve/smtpin07/MantshX 4.0) with ESMTP id j58G6YKu028817; Wed, 8 Jun 2005 09:06:35 -0700 (PDT) In-Reply-To: <42A6A3B1.4090607@freebsd.org> 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 (Apple Message framework v730) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: Charles Swiger Date: Wed, 8 Jun 2005 12:06:32 -0400 To: Colin Percival X-Mailer: Apple Mail (2.730) Cc: freebsd-fs@freebsd.org, Randy Bush , FreeBSD Current , Robert Watson , Giorgos Keramidas , Dag-Erling Sm?rgrav , Eric Anderson , Julian Elischer 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 16:06:45 -0000 On Jun 8, 2005, at 3:52 AM, Colin Percival wrote: > Giorgos Keramidas wrote: >> On 2005-06-08 09:25, Dag-Erling Sm?rgrav 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"? Most people think "better" means "it runs faster". :-) > You can merge-sort a singly-linked list quite easily, but converting > it to an array and back would probably be faster. Ugh. Converting a list to an array and back simply to sort requires roughly twice the working memory, and the work you're doing to accomplish this conversion is time spent not actually solving anything useful. It's best to pick one data structure based on what the task requires and what the access patterns are. If you know that the number of elements is fixed and will never change, arrays are fine, but if the # of elements changes dynamicly, something like a list or red-black tree is a better bet. A list is more suitable for linear traversal, whereas a RB-tree handles random access better. qsort() is wonderful, but as the size of individual data elements grows, the overhead of copying them around in the array becomes large enough that you are better off rearranging list pointers rather than using an array representation. A long time ago, the break-even point for using lists rather than arrays was somewhere around sizeof(el) > 64, but it's been a while.... -- -Chuck