Date: Wed, 8 Jun 2005 11:02:34 +0300 From: Giorgos Keramidas <keramida@freebsd.org> To: Colin Percival <cperciva@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 Message-ID: <20050608080234.GA1226@orion.daedalusnetworks.priv> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
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 :-)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050608080234.GA1226>