you are in an fs with millions of small files

[Giorgos Keramidas]

On 2005-06-08 09:25, Dag-Erling Sm?rgrav <des at des.no> wrote:
>Robert Watson <rwatson at FreeBSD.org> writes:
>> - Some appliations behave poorly with large trees.  ls(1) is the classic
>>    example -- sorting 150,000 strings is expensive, and should be avoided.
>
> 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 (not necessarily a
singly-linked list, like the one fts_link is used for).  If it makes
things easier on the sorting side, we could always convert fts_link to a
real `LIST_ENTRY(FTSENT) fts_link', but I suspect that sorting would
still involve at least some sort of array, unless we stop using qsort().