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

[Leo]

On 2012-11-07 12:06 +0800, Dmitry Gutov wrote:
> That was actually a good advice. As far as I can tell, most of the
> speed improvement comes from the following change

I seem to have some speedup on the flex matching part with the following
patch.

(tested on a ~9000 list with each item containing ~35 chars)

diff --git a/ido.el b/ido.el
index 31d5279d..dc623110 100644
--- a/ido.el
+++ b/ido.el
@@ -3710,6 +3710,25 @@ (defun ido-get-bufname (win)
                (cons buf ido-bufs-in-frame)))))
 
 ;;; FIND MATCHING ITEMS
+(defun ido-chars-in-string (chars str &optional prefix)
+  (let ((p 0)
+       (len (length chars))
+       c)
+    (catch 'exit
+      (when (zerop len)
+       (throw 'exit t))
+      (when (zerop (length str))
+       (throw 'exit nil))
+      (setq c (aref chars 0))
+      (when (and prefix (/= c (aref str 0)))
+       (throw 'exit nil))
+      (dotimes (i (length str))
+       (when (eq (aref str i) c)
+         (setq p (1+ p))
+         (when (>= p len)
+           (throw 'exit t))
+         (setq c (aref chars p))))
+      (>= p len))))
 
 (defun ido-set-matches-1 (items &optional do-full)
   ;; Return list of matches in items
@@ -3783,13 +3802,10 @@ (defun ido-set-matches-1 (items &optional do-full)
               ido-enable-flex-matching
               (> (length ido-text) 1)
               (not ido-enable-regexp))
-      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*"))
-      (if ido-enable-prefix
-         (setq re (concat "\\`" re)))
       (mapc
        (lambda (item)
         (let ((name (ido-name item)))
-          (if (string-match re name)
+          (if (ido-chars-in-string ido-text name ido-enable-prefix)
               (setq matches (cons item matches)))))
        items))
     matches))