Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

[Jim Meyering]

Bruno Haible <address@hidden> wrote:
> Jim Meyering wrote:
>> +    if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
>> +        && !sp->fts_compar
>> +        && dirent_inode_sort_may_be_useful (sp)) {
>> +            sp->fts_compar = fts_compare_ino;
>> +            head = fts_sort (sp, head, nitems);
>> +            sp->fts_compar = NULL;
>> +    }
>
> This uses fts_sort, which uses qsort, which is O(n^2) in the worst case.
> (Even the implementation in glibc can be O(n^2), if it guesses that mergesort
> takes too much memory.)
>
> Couldn't this be avoided by using Paul's mpsort module, and changing fts_sort
> to allocate 50% more room, as scratch space for mpsort?

Good point!
That would make a fine improvement, as a separate patch.

The new use of qsort in the code I've just proposed for
rm would benefit from the same treatment.