[Emacs-diffs] master 5c1ebfc: * src/insdel.c (make_gap): Increase enough to avoid O(N^2) behavior.

[Stefan Monnier]

branch: master
commit 5c1ebfc504bc0649a9e1105b1d9265c461739254
Author: Stefan Monnier <address@hidden>
Commit: Stefan Monnier <address@hidden>

    * src/insdel.c (make_gap): Increase enough to avoid O(N^2) behavior.
---
 src/insdel.c | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)

diff --git a/src/insdel.c b/src/insdel.c
index 3f933b0..8b684fd 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -560,7 +560,20 @@ void
 make_gap (ptrdiff_t nbytes_added)
 {
   if (nbytes_added >= 0)
-    make_gap_larger (nbytes_added);
+    /* With set-buffer-multibyte on a large buffer, we can end up growing the
+     * buffer *many* times.  Avoid an O(N^2) behavior by increasing by an
+     * amount at least proportional to the size of the buffer.
+     * On my test (a 223.9MB zip file on a Thinkpad T61):
+     * With /5    =>  24s
+     * With /32   =>  25s
+     * With /64   =>  26s
+     * With /128  =>  28s
+     * With /1024 =>  51s
+     * With /4096 => 131s
+     * With /∞    => gave up after 858s
+     * Of couse, ideally we should never call set-buffer-multibyte on
+     * a non-empty buffer (e.g. use buffer-swa-text instead).  */
+    make_gap_larger (max (nbytes_added, (Z - BEG) / 64));
 #if defined USE_MMAP_FOR_BUFFERS || defined REL_ALLOC || defined 
DOUG_LEA_MALLOC
   else
     make_gap_smaller (-nbytes_added);