bug#41029: Improve ido-switch-buffer performance when many buffers are open

bug#41029: Improve ido-switch-buffer performance when many buffers are open

[Arnold Noronha]

[-- Attachment #1: Type: text/plain, Size: 465 bytes --]


Many of the buffer locals (in particular I think it's the
SYMBOL_FORWARDED types --- my terminoly may be off), appear to be O(n)
to bind, where n is the number of live buffers.

I tried to see if I can optimize that binding process directly, but
couldn't figure out a way to do it without changing current behavior,
so I opted to just optimize ido-switch-buffer directly.

After this patch, the performance is quite bearable at ~6000 buffers,
but still not ideal.

[-- Attachment #2: 0001-Avoid-binding-CASE-FOLD-SEARCH-in-tight-loop.patch --]
[-- Type: text/x-diff, Size: 3944 bytes --]

From 3bc4eb78c365f4b4a387451f0b55264076a97c4b Mon Sep 17 00:00:00 2001
From: Arnold Noronha <arnold@tdrhq.com>
Date: Sat, 2 May 2020 08:30:47 -0700
Subject: [PATCH] Avoid binding CASE-FOLD-SEARCH in tight loop

IDO-IGNORE-ITEM-P is called for every buffer when switching
buffers. However, that function binds CASE-FOLD-SEARCH, which
appears to be an O(n) operation where n is (length (buffer-list)).
So we avoid binding it if we know we don't need to as a workaround.

To test this, this this:

(loop for i from 0 to 6000
      do
      (find-file (format "/tmp/xy%d.txt" i)))

Then try switching buffers with and without this patch.
---
 lisp/ido.el | 67 ++++++++++++++++++++++++++++-------------------------
 1 file changed, 36 insertions(+), 31 deletions(-)

diff --git a/lisp/ido.el b/lisp/ido.el
index 81883402ad..d7a24ae1d7 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3408,7 +3408,7 @@ ido-make-merged-file-list
 (defun ido-make-buffer-list-1 (&optional frame visible)
   "Return list of non-ignored buffer names."
   (delq nil
-	(mapcar
+       (mapcar
 	 (lambda (x)
 	   (let ((name (buffer-name x)))
 	     (if (not (or (ido-ignore-item-p name ido-ignore-buffers) (member name visible)))
@@ -3823,36 +3823,41 @@ ido-ignore-item-p
       (and
        ido-process-ignore-lists re-list
        (save-match-data
-	 (let ((ext-list (and ignore-ext ido-ignore-extensions
-			      completion-ignored-extensions))
-	       (case-fold-search ido-case-fold)
-	       ignorep nextstr
-	       (flen (length name)) slen)
-	   (while ext-list
-	     (setq nextstr (car ext-list))
-	     (if (cond
-		  ((stringp nextstr)
-		   (and (>= flen (setq slen (length nextstr)))
-			(string-equal (substring name (- flen slen)) nextstr)))
-		  ((functionp nextstr) (funcall nextstr name))
-		  (t nil))
-		 (setq ignorep t
-		       ext-list nil
-		       re-list nil)
-	       (setq ext-list (cdr ext-list))))
-	   (while re-list
-	     (setq nextstr (car re-list))
-	     (if (cond
-		  ((stringp nextstr) (string-match nextstr name))
-		  ((functionp nextstr) (funcall nextstr name))
-		  (t nil))
-		 (setq ignorep t
-		       re-list nil)
-	       (setq re-list (cdr re-list))))
-	   ;; return the result
-	   (if ignorep
-	       (setq ido-ignored-list (cons name ido-ignored-list)))
-	   ignorep)))))
+         (flet ((inner ()
+                       (let ((ext-list (and ignore-ext ido-ignore-extensions
+			                    completion-ignored-extensions))
+	                     ignorep nextstr
+	                     (flen (length name)) slen)
+	                 (while ext-list
+	                   (setq nextstr (car ext-list))
+	                   (if (cond
+		                ((stringp nextstr)
+		                 (and (>= flen (setq slen (length nextstr)))
+			              (string-equal (substring name (- flen slen)) nextstr)))
+		                ((functionp nextstr) (funcall nextstr name))
+		                (t nil))
+		               (setq ignorep t
+		                     ext-list nil
+		                     re-list nil)
+	                     (setq ext-list (cdr ext-list))))
+	                 (while re-list
+	                   (setq nextstr (car re-list))
+	                   (if (cond
+		                ((stringp nextstr) (string-match nextstr name))
+		                ((functionp nextstr) (funcall nextstr name))
+		                (t nil))
+		               (setq ignorep t
+		                     re-list nil)
+	                     (setq re-list (cdr re-list))))
+	                 ;; return the result
+	                 (if ignorep
+	                     (setq ido-ignored-list (cons name ido-ignored-list)))
+	                 ignorep)))
+
+           (if (eq case-fold-search ido-case-fold)
+               (inner)
+             (let ((case-fold-search ido-case-fold))
+               (inner))))))))
 
 ;; Private variable used by `ido-word-matching-substring'.
 (defvar ido-change-word-sub)
-- 
2.20.1

bug#41029: Acknowledgement (Improve ido-switch-buffer performance when many buffers are open)

[Arnold Noronha]

[-- Attachment #1: Type: text/plain, Size: 155 bytes --]


Updated patch (FLET was causing warnings/errors even though it seemed
to work. I don't know enough of elisp's bootstrapping process to know
why exactly.)

[-- Attachment #2: 0001-Avoid-binding-CASE-FOLD-SEARCH-in-tight-loop.patch --]
[-- Type: text/x-diff, Size: 4027 bytes --]

From 3bb4ec9bb2ae503b059957e99234fb8155ca9857 Mon Sep 17 00:00:00 2001
From: Arnold Noronha <arnold@tdrhq.com>
Date: Sat, 2 May 2020 08:30:47 -0700
Subject: [PATCH] Avoid binding CASE-FOLD-SEARCH in tight loop

IDO-IGNORE-ITEM-P is called for every buffer when switching
buffers. However, that function binds CASE-FOLD-SEARCH, which
appears to be an O(n) operation where n is (length (buffer-list)).
So we avoid binding it if we know we don't need to as a workaround.

To test this, this this:

(loop for i from 0 to 6000
      do
      (find-file (format "/tmp/xy%d.txt" i)))

Then try switching buffers with and without this patch.
---
 lisp/ido.el | 67 ++++++++++++++++++++++++++++-------------------------
 1 file changed, 36 insertions(+), 31 deletions(-)

diff --git a/lisp/ido.el b/lisp/ido.el
index 81883402ad..a2394d1d37 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3408,7 +3408,7 @@ ido-make-merged-file-list
 (defun ido-make-buffer-list-1 (&optional frame visible)
   "Return list of non-ignored buffer names."
   (delq nil
-	(mapcar
+       (mapcar
 	 (lambda (x)
 	   (let ((name (buffer-name x)))
 	     (if (not (or (ido-ignore-item-p name ido-ignore-buffers) (member name visible)))
@@ -3823,36 +3823,41 @@ ido-ignore-item-p
       (and
        ido-process-ignore-lists re-list
        (save-match-data
-	 (let ((ext-list (and ignore-ext ido-ignore-extensions
-			      completion-ignored-extensions))
-	       (case-fold-search ido-case-fold)
-	       ignorep nextstr
-	       (flen (length name)) slen)
-	   (while ext-list
-	     (setq nextstr (car ext-list))
-	     (if (cond
-		  ((stringp nextstr)
-		   (and (>= flen (setq slen (length nextstr)))
-			(string-equal (substring name (- flen slen)) nextstr)))
-		  ((functionp nextstr) (funcall nextstr name))
-		  (t nil))
-		 (setq ignorep t
-		       ext-list nil
-		       re-list nil)
-	       (setq ext-list (cdr ext-list))))
-	   (while re-list
-	     (setq nextstr (car re-list))
-	     (if (cond
-		  ((stringp nextstr) (string-match nextstr name))
-		  ((functionp nextstr) (funcall nextstr name))
-		  (t nil))
-		 (setq ignorep t
-		       re-list nil)
-	       (setq re-list (cdr re-list))))
-	   ;; return the result
-	   (if ignorep
-	       (setq ido-ignored-list (cons name ido-ignored-list)))
-	   ignorep)))))
+         (let  ((inner (lambda ()
+                         (let ((ext-list (and ignore-ext ido-ignore-extensions
+			                      completion-ignored-extensions))
+	                       ignorep nextstr
+	                       (flen (length name)) slen)
+	                   (while ext-list
+	                     (setq nextstr (car ext-list))
+	                     (if (cond
+		                  ((stringp nextstr)
+		                   (and (>= flen (setq slen (length nextstr)))
+			                (string-equal (substring name (- flen slen)) nextstr)))
+		                  ((functionp nextstr) (funcall nextstr name))
+		                  (t nil))
+		                 (setq ignorep t
+		                       ext-list nil
+		                       re-list nil)
+	                       (setq ext-list (cdr ext-list))))
+	                   (while re-list
+	                     (setq nextstr (car re-list))
+	                     (if (cond
+		                  ((stringp nextstr) (string-match nextstr name))
+		                  ((functionp nextstr) (funcall nextstr name))
+		                  (t nil))
+		                 (setq ignorep t
+		                       re-list nil)
+	                       (setq re-list (cdr re-list))))
+	                   ;; return the result
+	                   (if ignorep
+	                       (setq ido-ignored-list (cons name ido-ignored-list)))
+	                   ignorep))))
+
+           (if (eq case-fold-search ido-case-fold)
+               (funcall inner)
+             (let ((case-fold-search ido-case-fold))
+               (funcall inner))))))))
 
 ;; Private variable used by `ido-word-matching-substring'.
 (defvar ido-change-word-sub)
-- 
2.20.1

bug#41029: Improve ido-switch-buffer performance when many buffers are open

[Arnold Noronha]

[-- Attachment #1: Type: text/plain, Size: 249 bytes --]


On Sat, May 02, 2020 at 08:40:55AM -0700, Arnold Noronha wrote:
> +         (flet ((inner ()

Updated patch (FLET was causing warnings/errors even though it seemed
to work. I don't know enough of elisp's bootstrapping process to know
why exactly.)

[-- Attachment #2: 0001-Avoid-binding-CASE-FOLD-SEARCH-in-tight-loop.patch --]
[-- Type: text/x-diff, Size: 4027 bytes --]

From 3bb4ec9bb2ae503b059957e99234fb8155ca9857 Mon Sep 17 00:00:00 2001
From: Arnold Noronha <arnold@tdrhq.com>
Date: Sat, 2 May 2020 08:30:47 -0700
Subject: [PATCH] Avoid binding CASE-FOLD-SEARCH in tight loop

IDO-IGNORE-ITEM-P is called for every buffer when switching
buffers. However, that function binds CASE-FOLD-SEARCH, which
appears to be an O(n) operation where n is (length (buffer-list)).
So we avoid binding it if we know we don't need to as a workaround.

To test this, this this:

(loop for i from 0 to 6000
      do
      (find-file (format "/tmp/xy%d.txt" i)))

Then try switching buffers with and without this patch.
---
 lisp/ido.el | 67 ++++++++++++++++++++++++++++-------------------------
 1 file changed, 36 insertions(+), 31 deletions(-)

diff --git a/lisp/ido.el b/lisp/ido.el
index 81883402ad..a2394d1d37 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3408,7 +3408,7 @@ ido-make-merged-file-list
 (defun ido-make-buffer-list-1 (&optional frame visible)
   "Return list of non-ignored buffer names."
   (delq nil
-	(mapcar
+       (mapcar
 	 (lambda (x)
 	   (let ((name (buffer-name x)))
 	     (if (not (or (ido-ignore-item-p name ido-ignore-buffers) (member name visible)))
@@ -3823,36 +3823,41 @@ ido-ignore-item-p
       (and
        ido-process-ignore-lists re-list
        (save-match-data
-	 (let ((ext-list (and ignore-ext ido-ignore-extensions
-			      completion-ignored-extensions))
-	       (case-fold-search ido-case-fold)
-	       ignorep nextstr
-	       (flen (length name)) slen)
-	   (while ext-list
-	     (setq nextstr (car ext-list))
-	     (if (cond
-		  ((stringp nextstr)
-		   (and (>= flen (setq slen (length nextstr)))
-			(string-equal (substring name (- flen slen)) nextstr)))
-		  ((functionp nextstr) (funcall nextstr name))
-		  (t nil))
-		 (setq ignorep t
-		       ext-list nil
-		       re-list nil)
-	       (setq ext-list (cdr ext-list))))
-	   (while re-list
-	     (setq nextstr (car re-list))
-	     (if (cond
-		  ((stringp nextstr) (string-match nextstr name))
-		  ((functionp nextstr) (funcall nextstr name))
-		  (t nil))
-		 (setq ignorep t
-		       re-list nil)
-	       (setq re-list (cdr re-list))))
-	   ;; return the result
-	   (if ignorep
-	       (setq ido-ignored-list (cons name ido-ignored-list)))
-	   ignorep)))))
+         (let  ((inner (lambda ()
+                         (let ((ext-list (and ignore-ext ido-ignore-extensions
+			                      completion-ignored-extensions))
+	                       ignorep nextstr
+	                       (flen (length name)) slen)
+	                   (while ext-list
+	                     (setq nextstr (car ext-list))
+	                     (if (cond
+		                  ((stringp nextstr)
+		                   (and (>= flen (setq slen (length nextstr)))
+			                (string-equal (substring name (- flen slen)) nextstr)))
+		                  ((functionp nextstr) (funcall nextstr name))
+		                  (t nil))
+		                 (setq ignorep t
+		                       ext-list nil
+		                       re-list nil)
+	                       (setq ext-list (cdr ext-list))))
+	                   (while re-list
+	                     (setq nextstr (car re-list))
+	                     (if (cond
+		                  ((stringp nextstr) (string-match nextstr name))
+		                  ((functionp nextstr) (funcall nextstr name))
+		                  (t nil))
+		                 (setq ignorep t
+		                       re-list nil)
+	                       (setq re-list (cdr re-list))))
+	                   ;; return the result
+	                   (if ignorep
+	                       (setq ido-ignored-list (cons name ido-ignored-list)))
+	                   ignorep))))
+
+           (if (eq case-fold-search ido-case-fold)
+               (funcall inner)
+             (let ((case-fold-search ido-case-fold))
+               (funcall inner))))))))
 
 ;; Private variable used by `ido-word-matching-substring'.
 (defvar ido-change-word-sub)
-- 
2.20.1

bug#41029: Improve ido-switch-buffer performance when many buffers are open

[Arnold Noronha]

[-- Attachment #1: Type: text/plain, Size: 243 bytes --]


Actually, I realized this could be cleaner. Nicer patch attached.

--Arnold

On Sat, May 02, 2020 at 10:05:21AM -0700, Arnold Noronha wrote:
>
> On Sat, May 02, 2020 at 08:40:55AM -0700, Arnold Noronha wrote:
> > +         (flet ((inner ()
>

[-- Attachment #2: 0001-Use-a-temporary-buffer-before-calling-ido-ignore-ite.patch --]
[-- Type: text/x-diff, Size: 1711 bytes --]

From 3dc513bc01decf9774f9ce5974abca30cbd71805 Mon Sep 17 00:00:00 2001
From: Arnold Noronha <arnold@tdrhq.com>
Date: Sat, 2 May 2020 11:24:22 -0700
Subject: [PATCH] Use a temporary-buffer before calling ido-ignore-item-p
 multiple times

And locally set CASE-FOLD-SEARCH. Setting CASE-FOLD-SEARCH 1000s of
times if CASE-FOLD-SEARCH is not locally set is super slow because it
would have to update the bindings in each buffer (or, that is my
understanding. See the warning at:
https://www.gnu.org/software/emacs/manual/html_node/elisp/Intro-to-Buffer_002dLocal.html#Intro-to-Buffer_002dLocal)
---
 lisp/ido.el | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/lisp/ido.el b/lisp/ido.el
index 81883402ad..22b3729097 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3407,13 +3407,18 @@ ido-make-merged-file-list
 
 (defun ido-make-buffer-list-1 (&optional frame visible)
   "Return list of non-ignored buffer names."
-  (delq nil
-	(mapcar
-	 (lambda (x)
-	   (let ((name (buffer-name x)))
-	     (if (not (or (ido-ignore-item-p name ido-ignore-buffers) (member name visible)))
-		 name)))
-	 (buffer-list frame))))
+  (with-temp-buffer
+    ;; Each call to ido-ignore-item-p LET-binds case-fold-search.
+    ;; That is slow if there's no buffer-local binding available,
+    ;; roughly O(number of buffers).  This hack avoids it.
+    (setq-local case-fold-search nil)
+    (delq nil
+	  (mapcar
+	   (lambda (x)
+	     (let ((name (buffer-name x)))
+	       (if (not (or (ido-ignore-item-p name ido-ignore-buffers) (member name visible)))
+		   name)))
+	   (buffer-list frame)))))
 
 (defun ido-make-buffer-list (default)
   "Return the current list of buffers.
-- 
2.20.1

bug#41029: Improve ido-switch-buffer performance when many buffers are open

[Dmitry Gutov]

On 02.05.2020 21:26, Arnold Noronha wrote:
> Actually, I realized this could be cleaner. Nicer patch attached.

Looks fine to me, thanks. Unless someone expresses any objections in a 
week or so, we should install it.

bug#41029: Improve ido-switch-buffer performance when many buffers are open

[Dmitry Gutov]

Version: 28.1

On 03.05.2020 05:03, Dmitry Gutov wrote:
> On 02.05.2020 21:26, Arnold Noronha wrote:
>> Actually, I realized this could be cleaner. Nicer patch attached.
> 
> Looks fine to me, thanks. Unless someone expresses any objections in a 
> week or so, we should install it.

Now pushed to master. Thank you!