[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: |
Jim Meyering |
Subject: |
Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs |
Date: |
Fri, 26 Sep 2008 14:15:22 +0200 |
Jim Meyering <address@hidden> wrote:
> Here is a patch that makes it so tools using fts,
> like chmod, chown, chgrp, chcon, du, and find are no
> longer susceptible to an O(n^2) performance penalty when
> processing very large directory-entry counts (as in millions).
> I first noticed the problem on ext3 and ext4 file systems,
> but the patch also improves performance on reiserfs and xfs,
> but not on tmpfs.
I've pushed that with a fix for the comparison function
problem that Ralf spotted:
http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=commitdiff;h=2f2978ede97205c49d3e568ccffa5a04fb53326b
then spotted a typo, and pushed the correction:
http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=commit;h=1d569ca4e7e6147793e6e6510e5a36a4139b2f31