Subject: bug#12796: closed (Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled)

From: [email-masked] (GNU bug Tracking System)
Date: Sat, 10 Nov 2012 17:53:02 +0000

Your bug report

#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled

which was filed against the emacs package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
12796: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=12796
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled
From: Dmitry Gutov <[email-masked]>
To: [email-masked]
Cc: Kim Storm <[email-masked]>, Stefan Monnier <[email-masked]>, Leo <[email-masked]>
Date: Sat, 10 Nov 2012 21:52:31 +0400
List-Id: <debbugs-submit.debbugs.gnu.org>

With speed-up patches installed on both branches, I consider this fixed.

Subject: Optimize `ido-completing-read' for larger lists with flex matching enabled
From: Dmitry Gutov <[email-masked]>
To: [email-masked]
Date: Sun, 04 Nov 2012 09:58:35 +0400
List-Id: <debbugs-submit.debbugs.gnu.org>

Tags: patch

Currently ido re-filters the full candidates list after every change in 
the minibuffer. With long candidates list and with flex matching enabled 
(like it's often the case with certain third-party packages, namely smex 
and ido-ubiquitous), as soon as ido switches to using flex matching, 
each update takes a noticeable fraction of a second. Even if there's no 
matches anymore for the current input.

If I decide to type quickly but make a typo in one of the first 
characters, I often need to wait a few seconds until I can fix the typo 
or start anew.

This patch adds a simple cache that keeps track of the current matching 
settings (prefix, regexp, or no), and checks the input against a 
previously entered string. If the latter is a prefix of the former (and 
regexp matching is disabled), then we can use the matches from the 
former input as the candidates list for the current one.

Any objections?
=== modified file 'lisp/ChangeLog'
--- lisp/ChangeLog	2012-10-29 15:14:10 +0000
+++ lisp/ChangeLog	2012-11-04 04:55:08 +0000
@@ -1,3 +1,15 @@
+2012-11-04  Dmitry Gutov  <[email-masked]>
+
+	* ido.el (ido-cache-prefix, ido-cache-matches, ido-cache-params):
+	New dynamic vars.
+	(ido-read-internal): Reset the above variables' values.
+	(ido-set-matches): Don't reverse the candidates list, leave it to
+	`ido-set-matches-1'.
+	(ido-use-matches-from-cache, ido-check-cache-params)
+	(ido-update-cache): New functions.
+	(ido-set-matches-1): Use the new functions; reverse the matches
+	list at the very end.
+
 2012-10-29  Stefan Monnier  <[email-masked]>
 
 	* vc/diff-mode.el (diff-context->unified): Don't get confused by "hunk

=== modified file 'lisp/ido.el'
--- lisp/ido.el	2012-10-05 07:38:05 +0000
+++ lisp/ido.el	2012-11-04 05:12:07 +0000
@@ -1143,6 +1143,11 @@
 ;; Dynamically bound in ido-read-internal.
 (defvar ido-completing-read)
 
+;; Matches cache data, only used when `ido-cur-item' is `list'.
+(defvar ido-cache-prefix)
+(defvar ido-cache-matches)
+(defvar ido-cache-params)
+
 ;;; FUNCTIONS
 
 (defun ido-active (&optional merge)
@@ -1852,6 +1857,9 @@
        ido-default-item
        ido-selected
        ido-final-text
+       ido-cache-prefix
+       ido-cache-matches
+       ido-cache-params
        (done nil)
        (icomplete-mode nil) ;; prevent icomplete starting up
        ;; Exported dynamic variables:
@@ -3692,7 +3700,7 @@
 
 ;;; FIND MATCHING ITEMS
 
-(defun ido-set-matches-1 (items &optional do-full)
+(defun ido-set-matches-1 (all-items &optional do-full)
   ;; Return list of matches in items
   (let* ((case-fold-search  ido-case-fold)
 	 (slash (and (not ido-enable-prefix) (ido-final-slash ido-text)))
@@ -3718,7 +3726,10 @@
 			     (not ido-process-ignore-lists)
 			     ido-enable-prefix
 			     (= (length ido-text) 0)))
-	 full-matches suffix-matches prefix-matches matches)
+         (items (if (ido-use-matches-from-cache)
+                    ido-cache-matches
+                  all-items))
+	 full-matches suffix-matches prefix-matches matches used-flex)
     (setq ido-incomplete-regexp nil)
     (condition-case error
         (mapc
@@ -3753,18 +3764,19 @@
     (when prefix-matches
       (ido-trace "prefix match" prefix-matches)
       ;; Bug#2042.
-      (setq matches (nconc prefix-matches matches)))
+      (setq matches (nconc matches prefix-matches)))
     (when suffix-matches
       (ido-trace "suffix match" (list text suffix-re suffix-matches))
-      (setq matches (nconc suffix-matches matches)))
+      (setq matches (nconc matches suffix-matches)))
     (when full-matches
       (ido-trace "full match" (list text full-re full-matches))
-      (setq matches (nconc full-matches matches)))
+      (setq matches (nconc matches full-matches)))
     (when (and (null matches)
 	       ido-enable-flex-matching
 	       (> (length ido-text) 1)
 	       (not ido-enable-regexp))
-      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*"))
+      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*")
+            used-flex t)
       (if ido-enable-prefix
 	  (setq re (concat "\\`" re)))
       (mapc
@@ -3772,16 +3784,51 @@
 	 (let ((name (ido-name item)))
 	   (if (string-match re name)
 	       (setq matches (cons item matches)))))
-       items))
+       (if (ido-check-cache-params t)
+           items
+         all-items)))
+    (setq matches (reverse matches))
+    (ido-update-cache matches used-flex)
     matches))
 
-
 (defun ido-set-matches ()
   ;; Set `ido-matches' to the list of items matching prompt
   (when ido-rescan
-    (setq ido-matches (ido-set-matches-1 (reverse ido-cur-list) (not ido-rotate))
+    (setq ido-matches (ido-set-matches-1 ido-cur-list (not ido-rotate))
 	  ido-rotate nil)))
 
+(defun ido-use-matches-from-cache ()
+  "Return t if `ido-set-matches-1' can use `ido-cache-matches'."
+  (and ido-cache-prefix (eq ido-cur-item 'list)
+       (not ido-enable-regexp)
+       (ido-check-cache-params)
+       (>= (length ido-text) (length ido-cache-prefix))
+       (string= ido-cache-prefix
+                (substring ido-text 0 (length ido-cache-prefix)))))
+
+(defun ido-check-cache-params (&optional flex)
+  "Check `ido-cache-params' against current parameters."
+  (let ((params ido-cache-params))
+    (if (and (or (not (plist-get params 'prefix)) ido-enable-prefix)
+             (or (plist-get params 'flex) (not flex)))
+        t
+      (setq ido-cache-prefix nil
+            ido-cache-matches nil))))
+
+(defun ido-update-cache (matches flex)
+  "Update values of `ido-cache-*' variables."
+  (when (and (or matches
+                 (zerop (length ido-cache-prefix)))
+             (eq ido-cur-item 'list)
+             (not ido-enable-regexp)
+             (<= (* 10 (length matches)) (length ido-cur-list)))
+    (setq ido-cache-prefix ido-text
+          ido-cache-matches matches)
+    (setq ido-cache-params
+          (plist-put (plist-put ido-cache-params
+                                'prefix ido-enable-prefix)
+                     'flex flex))))
+
 (defun ido-ignore-item-p (name re-list &optional ignore-ext)
   ;; Return t if the buffer or file NAME should be ignored.
   (or (member name ido-ignore-item-temp-list)