From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.bugs Subject: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Date: Sun, 04 Nov 2012 09:58:35 +0400 Message-ID: <5096040B.50002@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------040105020803080507020409" X-Trace: ger.gmane.org 1352008752 20571 80.91.229.3 (4 Nov 2012 05:59:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 4 Nov 2012 05:59:12 +0000 (UTC) To: 12796@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Nov 04 06:59:21 2012 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TUtEs-0001vH-Jn for geb-bug-gnu-emacs@m.gmane.org; Sun, 04 Nov 2012 06:59:18 +0100 Original-Received: from localhost ([::1]:33007 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUtEj-0002Og-NF for geb-bug-gnu-emacs@m.gmane.org; Sun, 04 Nov 2012 01:59:09 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:60652) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUtEg-0002OI-8X for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 01:59:07 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TUtEe-00067b-Oo for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 01:59:06 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:37691) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUtEe-00067T-LU for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 01:59:04 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1TUtHW-0002Kv-7M for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 01:02:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Dmitry Gutov Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 04 Nov 2012 06:02:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 12796 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.13520089048953 (code B ref -1); Sun, 04 Nov 2012 06:02:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 4 Nov 2012 06:01:44 +0000 Original-Received: from localhost ([127.0.0.1]:47942 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TUtHD-0002KM-UH for submit@debbugs.gnu.org; Sun, 04 Nov 2012 01:01:44 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:44511) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TUtHA-0002KD-BX for submit@debbugs.gnu.org; Sun, 04 Nov 2012 01:01:43 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TUtEG-0005y9-VW for submit@debbugs.gnu.org; Sun, 04 Nov 2012 01:58:42 -0400 Original-Received: from lists.gnu.org ([208.118.235.17]:42564) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUtEG-0005y5-Rm for submit@debbugs.gnu.org; Sun, 04 Nov 2012 01:58:40 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:60597) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUtEF-0002Lp-DI for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 01:58:40 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TUtED-0005xm-J0 for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 01:58:39 -0400 Original-Received: from forward10.mail.yandex.net ([77.88.61.49]:52629) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUtEC-0005xS-NV for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 01:58:37 -0400 Original-Received: from smtp8.mail.yandex.net (smtp8.mail.yandex.net [77.88.61.54]) by forward10.mail.yandex.net (Yandex) with ESMTP id 33AAF1020C6E for ; Sun, 4 Nov 2012 09:58:31 +0400 (MSK) Original-Received: from smtp8.mail.yandex.net (localhost [127.0.0.1]) by smtp8.mail.yandex.net (Yandex) with ESMTP id 1E7671B60256 for ; Sun, 4 Nov 2012 09:58:31 +0400 (MSK) Original-Received: from 127-240.nwlink.spb.ru (127-240.nwlink.spb.ru [178.252.127.240]) by smtp8.mail.yandex.net (nwsmtp/Yandex) with ESMTP id wUla3uFl-wUlmY5xD; Sun, 4 Nov 2012 09:58:30 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352008711; bh=Eg0+6rjvEK7ASpZUmxW5OYLy+BwEucg46opnL+7kxPc=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:Subject: Content-Type; b=TttCAER9h6JBOv5N76QPUc75qNAn3deN5ZcW4C9FliYDiYU9+CiVZ6BMlEQluwX2m Kt0tFx7LQme1dgbWBYeLgbuUI/370FJtj1wePdslXRsTgji1IwNXFgTmbmYFXB5Lk/ +ucNbe6LqW+U1whV/DvrRjXFcTim3DGk2CUIYt0I= User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.4.x-2.6.x [generic] [fuzzy] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:66425 Archived-At: This is a multi-part message in MIME format. --------------040105020803080507020409 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit 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? --------------040105020803080507020409 Content-Type: text/plain; charset=windows-1251; name="ido-speed.diff" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="ido-speed.diff" === 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 + + * 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 * 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) --------------040105020803080507020409--