Re: rm improvements from next rebased and pulled onto master

[Jim Meyering]

Andreas Schwab wrote:

> Ralf Wildenhues <address@hidden> 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 <address@hidden>
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