From: Dmitry Gutov <dgutov@yandex.ru>
To: 12796@debbugs.gnu.org
Subject: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled
Date: Sun, 04 Nov 2012 09:58:35 +0400 [thread overview]
Message-ID: <5096040B.50002@yandex.ru> (raw)
[-- Attachment #1: Type: text/plain, Size: 925 bytes --]
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?
[-- Attachment #2: ido-speed.diff --]
[-- Type: text/plain, Size: 5295 bytes --]
=== 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)
next reply other threads:[~2012-11-04 5:58 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-11-04 5:58 Dmitry Gutov [this message]
2012-11-04 8:32 ` bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Leo
2012-11-04 13:53 ` Stefan Monnier
2012-11-04 17:05 ` Dmitry Gutov
2012-11-05 5:37 ` Dmitry Gutov
2012-11-06 1:45 ` Stefan Monnier
2012-11-06 11:03 ` Kim Storm
2012-11-06 15:38 ` Dmitry Gutov
2012-11-06 16:45 ` Kim Storm
2012-11-07 5:41 ` Dmitry Gutov
2012-11-05 20:57 ` Dmitry Gutov
2012-11-07 2:27 ` Leo
2012-11-07 4:06 ` Dmitry Gutov
2012-11-07 10:38 ` Leo
2012-11-07 21:54 ` Dmitry Gutov
2012-11-08 2:00 ` Leo
2012-11-08 4:14 ` Stefan Monnier
2012-11-08 7:36 ` Leo
2012-11-08 14:05 ` Stefan Monnier
2012-11-10 17:52 ` Dmitry Gutov
2012-11-10 22:51 ` Stefan Monnier
2012-11-10 23:01 ` Dmitry Gutov
2012-11-10 23:31 ` Stefan Monnier
2020-09-13 16:14 ` Lars Ingebrigtsen
2012-11-08 2:05 ` Stefan Monnier
2012-11-08 4:29 ` Dmitry Gutov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=5096040B.50002@yandex.ru \
--to=dgutov@yandex.ru \
--cc=12796@debbugs.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).