[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: rm improvements from next rebased and pulled onto master
From: |
Jim Meyering |
Subject: |
Re: rm improvements from next rebased and pulled onto master |
Date: |
Sun, 13 Sep 2009 12:12:37 +0200 |
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