=== 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  <dgutov@yandex.ru>
+
+	* 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  <monnier@iro.umontreal.ca>
 
 	* 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)