[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs
From: |
Bruno Haible |
Subject: |
Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs |
Date: |
Thu, 25 Sep 2008 19:52:46 +0200 |
User-agent: |
KMail/1.5.4 |
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?
Bruno