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

[Leo <sdl.web@gmail.com>]

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))