diff options
author | Jim Meyering <meyering@redhat.com> | 2008-09-22 22:42:12 +0200 |
---|---|---|
committer | Jim Meyering <meyering@redhat.com> | 2008-09-27 00:10:08 +0200 |
commit | 24412edeaf556a96a5ee122851de7c3e37726bdb (patch) | |
tree | 54240c2ae7944434cb6ef9ed2ff69ba6c964c78b /NEWS | |
parent | a5111af33ea6a5d27c3f7ab67afdb2a5884c38b6 (diff) | |
download | coreutils-24412edeaf556a96a5ee122851de7c3e37726bdb.tar.xz |
rm -r: avoid O(n^2) performance for a directory with very many entries
This enhancement works around a problem that is specific to at least
ext3 and ext4 file systems. With them, it would take hours to remove
a two-million-entry directory. RAM-backed file systems (tmpfs) are
not affected, since there is no seek penalty.
* remove.c (rm_malloc, rm_free, compare_ino): New functions.
(dirent_count, preprocess_dir): New function.
[struct readdir_data]: New struct.
(remove_cwd_entries): Call preprocess_dir.
* tests/rm/ext3-perf: New file. Test for the performance fix.
* NEWS: mention the new feature
Diffstat (limited to 'NEWS')
-rw-r--r-- | NEWS | 7 |
1 files changed, 7 insertions, 0 deletions
@@ -9,6 +9,13 @@ GNU coreutils NEWS -*- outline -*- ** New features + chgrp, chmod, chown, chcon, du, rm: now all display linear performance, + even when operating on million-entry directories on ext3 and ext4 file + systems. Before, they would exhibit O(N^2) performance, due to linear + per-entry seek time cost when operating on entries in readdir order. + Rm was improved directly, while the others inherit the improvement + from the newer version of fts in gnulib. + comm now verifies that the inputs are in sorted order. This check can be turned off with the --nocheck-order option. |