diff options
| author | Paul Eggert <eggert@cs.ucla.edu> | 2016-10-25 21:57:56 -0700 |
|---|---|---|
| committer | Paul Eggert <eggert@cs.ucla.edu> | 2016-10-25 21:58:31 -0700 |
| commit | 68b82f6f8419a815cfcf962b3061352d414dc606 (patch) | |
| tree | 2b40c7be3eecaeed747b5247965b76b4eac11151 /doc | |
| parent | 571f01c069dfc7f860e5500a5d08ebfdaf9c3068 (diff) | |
| download | diffutils-68b82f6f8419a815cfcf962b3061352d414dc606.tar.gz | |
diff: fix big performance degradation in 3.4
* NEWS, doc/diffutils.texi (Overview): Document this.
* src/analyze.c (diff_2_files): Restore too_expensive heuristic,
but this time with a floor that is 16 times the old floor. This
should fix Bug#16848, by generating good-quality output for its
test case, while not introducing Bug#24715, by running nearly as
fast as diff-3.3 for that test case.
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/diffutils.texi | 5 |
1 files changed, 4 insertions, 1 deletions
diff --git a/doc/diffutils.texi b/doc/diffutils.texi index b478380..ceaf557 100644 --- a/doc/diffutils.texi +++ b/doc/diffutils.texi @@ -161,7 +161,10 @@ The algorithm was independently discovered as described by Esko Ukkonen in @c Date: Wed, 29 Sep 1993 08:27:55 MST @c Ukkonen should be given credit for also discovering the algorithm used @c in GNU diff. -Related algorithms are surveyed by Alfred V. Aho in +Unless the @option{--minimal} option is used, @command{diff} uses a +heuristic by Paul Eggert that limits the cost to @math{O(N^1.5 log N)} +at the price of producing suboptimal output for large inputs with many +differences. Related algorithms are surveyed by Alfred V. Aho in section 6.3 of ``Algorithms for Finding Patterns in Strings'', @cite{Handbook of Theoretical Computer Science} (Jan Van Leeuwen, ed.), Vol.@: A, @cite{Algorithms and Complexity}, Elsevier/MIT Press, |