Andreas Schwab wrote: > Ralf Wildenhues <[email protected]> writes: > >> * Jim Meyering wrote on Sun, Sep 13, 2009 at 11:17:50AM CEST: >>> Ralf Wildenhues wrote: >>> > Jim Meyering writes: >>> >> Here's post-7.6 NEWS so far: >>> >> rm -r deletes deep hierarchies more efficiently. Before, it took >>> >> O(N^2) >>> >> time, now it takes O(N). >>> > >>> > What is N? The number of files removed, the number of directories >>> > removed, >>> > the maximal subdirectory depth? >> >>> It's the latter, as implied by the preceding "deep hierarchies". >> >> Thanks. I suggest adding >> , with N the subdirectory depth. >> >> to the NEWS entry. Still two lines, but much more precise now. :-) > > I'd suggest not to use the O notation, which is too technical for a NEWS > entry, IMHO. > > rm -r deletes deep hierarchies more efficiently. Before, execution > time was quadratic on the subdirectory depth, now it is merely > linear.
Sounds reasonable: >From f6f78f093b57f2abf82c2ba3d7bf65e533af6ae7 Mon Sep 17 00:00:00 2001 From: Jim Meyering <[email protected]> Date: Sun, 13 Sep 2009 12:11:57 +0200 Subject: [PATCH] doc: NEWS: say quadratic and linear, rather than O(N^2) and O(N) * NEWS: Use a slightly less technical description. Suggested by Andreas Schwab. --- NEWS | 13 +++++++------ 1 files changed, 7 insertions(+), 6 deletions(-) diff --git a/NEWS b/NEWS index ec41ca7..980fb54 100644 --- a/NEWS +++ b/NEWS @@ -13,12 +13,13 @@ GNU coreutils NEWS -*- outline -*- This makes rm -rf significantly faster (400-500%) in some pathological cases, and slightly slower (20%) in at least one pathological case. - rm -r deletes deep hierarchies more efficiently. Before, it took O(N^2) - time, now it takes O(N), where N is the depth of the hierarchy. However, - this improvement is not as pronounced as might be expected for very - deep trees, because prior to this change, for any relative name length - longer than 8KiB, rm -r would sacrifice official conformance to avoid the - disproportionate O(N^2) performance penalty. Leading to another improvement: + rm -r deletes deep hierarchies more efficiently. Before, execution time + was quadratic in the depth of the hierarchy, now it is merely linear. + However, this improvement is not as pronounced as might be expected for + very deep trees, because prior to this change, for any relative name + length longer than 8KiB, rm -r would sacrifice official conformance to + avoid the disproportionate quadratic performance penalty. Leading to + another improvement: rm -r is now slightly more standards-conformant when operating on write-protected files with relative names longer than 8KiB. -- 1.6.5.rc0.190.g15871
