you are in an fs with millions of small files
Giorgos Keramidas
keramida at freebsd.org
Wed Jun 8 08:02:46 GMT 2005
On 2005-06-08 00:52, Colin Percival <cperciva at freebsd.org> wrote:
> Giorgos Keramidas wrote:
> > On 2005-06-08 09:25, Dag-Erling Sm?rgrav <des at 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 :-)
More information about the freebsd-current
mailing list