From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 04 01:01:44 2012 Received: (at submit) by debbugs.gnu.org; 4 Nov 2012 06:01:44 +0000 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 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 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 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=unavailable version=3.3.2 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 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 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 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 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) 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) 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= Message-ID: <5096040B.50002@yandex.ru> Date: Sun, 04 Nov 2012 09:58:35 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: bug-gnu-emacs@gnu.org Subject: Optimize `ido-completing-read' for larger lists with flex matching enabled Content-Type: multipart/mixed; boundary="------------040105020803080507020409" 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-Received-From: 208.118.235.17 X-Spam-Score: -3.5 (---) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.5 (---) 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-- From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 04 03:35:44 2012 Received: (at submit) by debbugs.gnu.org; 4 Nov 2012 08:35:44 +0000 Received: from localhost ([127.0.0.1]:48053 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TUvgF-0005hX-Vy for submit@debbugs.gnu.org; Sun, 04 Nov 2012 03:35:44 -0500 Received: from eggs.gnu.org ([208.118.235.92]:53256) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TUvgD-0005hQ-BU for submit@debbugs.gnu.org; Sun, 04 Nov 2012 03:35:42 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TUvdJ-0007Xo-Qy for submit@debbugs.gnu.org; Sun, 04 Nov 2012 03:32:42 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-5.7 required=5.0 tests=BAYES_00,FREEMAIL_FROM, RCVD_IN_DNSWL_HI,RCVD_NUMERIC_HELO autolearn=ham version=3.3.2 Received: from lists.gnu.org ([208.118.235.17]:57298) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUvdJ-0007Xk-NM for submit@debbugs.gnu.org; Sun, 04 Nov 2012 03:32:41 -0500 Received: from eggs.gnu.org ([208.118.235.92]:53316) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUvdJ-0003VL-0k for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 03:32:41 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TUvdI-0007XT-6z for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 03:32:40 -0500 Received: from plane.gmane.org ([80.91.229.3]:35296) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TUvdI-0007XN-0m for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 03:32:40 -0500 Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1TUvdL-0000oa-OI for bug-gnu-emacs@gnu.org; Sun, 04 Nov 2012 09:32:43 +0100 Received: from 182.48.109.8 ([182.48.109.8]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 04 Nov 2012 09:32:43 +0100 Received: from sdl.web by 182.48.109.8 with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 04 Nov 2012 09:32:43 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: bug-gnu-emacs@gnu.org From: Leo Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Date: Sun, 04 Nov 2012 16:32:24 +0800 Lines: 7 Message-ID: References: <5096040B.50002@yandex.ru> Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: 182.48.109.8 Face: iVBORw0KGgoAAAANSUhEUgAAACgAAAAoAgMAAADxkFD+AAAADFBMVEUvT09qWs3/pQD///+J kUVcAAAAAWJLR0QAiAUdSAAAAAlwSFlzAAALEwAACxMBAJqcGAAAAAd0SU1FB9cBBwMLOd3veKQA AACuSURBVBjTldE9CgIxEAXgB+lEyFUC2wo5ikdZ8DSypxhMY7H9VuIVwlqkGRgnm59VsHGafIQ3 CZlAtmKIRaHETgYa12lqvEsPYKf8wXHsPGfqPaUM0g9aJPKFXkmNQmSDqwzz4Fpgpz+6WAPY2z5o uPJJpu0uypcl4nyCibMLQ8lCiVjayLoQvw5LsVKQuHPRR958HZbOcVsKeepcLxpByjycGvnKmY+c MBvrtyjfe0vmuLvdq/kAAAAASUVORK5CYII= User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2) Cancel-Lock: sha1:EXhd2RbntWWeOl4/xMD4Xx5KgiM= X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 208.118.235.17 X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.0 (---) On 2012-11-04 13:58 +0800, Dmitry Gutov wrote: > Any objections? This is special-cased optimisation which doesn't address the root cause of the slowness. We need a better solution. Leo From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 04 08:57:06 2012 Received: (at 12796) by debbugs.gnu.org; 4 Nov 2012 13:57:06 +0000 Received: from localhost ([127.0.0.1]:48186 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TV0hC-0005II-DE for submit@debbugs.gnu.org; Sun, 04 Nov 2012 08:57:05 -0500 Received: from pruche.dit.umontreal.ca ([132.204.246.22]:46872) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TV0hA-0005Ht-Jn for 12796@debbugs.gnu.org; Sun, 04 Nov 2012 08:57:01 -0500 Received: from fmsmemgm.homelinux.net (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.1/8.14.1) with ESMTP id qA4Drxe9014283; Sun, 4 Nov 2012 08:53:59 -0500 Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848) id 0E278AE1F7; Sun, 4 Nov 2012 08:53:58 -0500 (EST) From: Stefan Monnier To: Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Message-ID: References: <5096040B.50002@yandex.ru> Date: Sun, 04 Nov 2012 08:53:58 -0500 In-Reply-To: <5096040B.50002@yandex.ru> (Dmitry Gutov's message of "Sun, 04 Nov 2012 09:58:35 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 1 Rules triggered RV4392=0 X-NAI-Spam-Version: 2.2.0.9309 : core <4392> : streams <851555> : uri <1259935> X-Spam-Score: -1.2 (-) X-Debbugs-Envelope-To: 12796 Cc: 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.5 (--) > 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. `while-no-input' (which AFAICT is used by ido) is supposed to interrupt the computation as soon as you type the next input so you don't need to wait. Are you saying that while-no-input doesn't work? Stefan From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 04 12:08:18 2012 Received: (at 12796) by debbugs.gnu.org; 4 Nov 2012 17:08:18 +0000 Received: from localhost ([127.0.0.1]:49202 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TV3gH-0001Im-PK for submit@debbugs.gnu.org; Sun, 04 Nov 2012 12:08:18 -0500 Received: from forward20.mail.yandex.net ([95.108.253.145]:57656) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TV3gD-0001Ia-Rq for 12796@debbugs.gnu.org; Sun, 04 Nov 2012 12:08:16 -0500 Received: from smtp18.mail.yandex.net (smtp18.mail.yandex.net [95.108.252.18]) by forward20.mail.yandex.net (Yandex) with ESMTP id 2ECD0104076C; Sun, 4 Nov 2012 21:05:10 +0400 (MSK) Received: from smtp18.mail.yandex.net (localhost [127.0.0.1]) by smtp18.mail.yandex.net (Yandex) with ESMTP id 09FE818A04CE; Sun, 4 Nov 2012 21:05:09 +0400 (MSK) Received: from 127-240.nwlink.spb.ru (127-240.nwlink.spb.ru [178.252.127.240]) by smtp18.mail.yandex.net (nwsmtp/Yandex) with ESMTP id 59jqZctN-59jWHp84; Sun, 4 Nov 2012 21:05:09 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352048709; bh=Dbkz45DHxCJAPt9HXzXdko8s0niL4WuZvx+2X4AomOI=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=CwOLy7cKzVUogzSiqAem0UMdqSMq93LQSZeaoXL9wGvt9WnbAS554bDonF7kOZu0V Fw1tzTS0L26oLzDSt63tOAkx86Zt/juEmF3XRvOGc7u2+UUjc/G2ODi1rFnE2NjcNO JEtrmPcYMWiVo5bno3Sel4DyPnNPdHOO0LYDOqk4= Message-ID: <5096A046.6090908@yandex.ru> Date: Sun, 04 Nov 2012 21:05:10 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Stefan Monnier Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) On 04.11.2012 17:53, Stefan Monnier wrote: >> 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. > > `while-no-input' (which AFAICT is used by ido) is supposed to interrupt > the computation as soon as you type the next input so you don't need > to wait. > > Are you saying that while-no-input doesn't work? I only see `while-no-input' used in one place there: in `ido-make-merged-file-list', and that function is only used in `find-file' mode. So yeah, using it around matching loops in `ido-set-matches-1' might be another way to optimize, provided the overhead is not too much. From debbugs-submit-bounces@debbugs.gnu.org Mon Nov 05 00:41:01 2012 Received: (at 12796) by debbugs.gnu.org; 5 Nov 2012 05:41:01 +0000 Received: from localhost ([127.0.0.1]:49603 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVFQi-0004lU-HM for submit@debbugs.gnu.org; Mon, 05 Nov 2012 00:41:00 -0500 Received: from forward1h.mail.yandex.net ([84.201.187.146]:52357) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVFQc-0004lA-M6 for 12796@debbugs.gnu.org; Mon, 05 Nov 2012 00:40:57 -0500 Received: from smtp4h.mail.yandex.net (smtp4h.mail.yandex.net [84.201.186.21]) by forward1h.mail.yandex.net (Yandex) with ESMTP id 159DB9E1AA0; Mon, 5 Nov 2012 09:37:49 +0400 (MSK) Received: from smtp4h.mail.yandex.net (localhost [127.0.0.1]) by smtp4h.mail.yandex.net (Yandex) with ESMTP id D29442C006B; Mon, 5 Nov 2012 09:37:48 +0400 (MSK) Received: from 127-240.nwlink.spb.ru (127-240.nwlink.spb.ru [178.252.127.240]) by smtp4h.mail.yandex.net (nwsmtp/Yandex) with ESMTP id bltuBsgS-bmtiqsfq; Mon, 5 Nov 2012 09:37:48 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352093868; bh=eD01NLAyEycDPxrK/utr5dFH3cl3UQbbolNTj0eS6uo=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=nRQx67RKoYX6jg6ZDIGQe4/rS8Q965tYKoVLztj02aW74LpXb5qpt+wTehomgCn3I 8kPLXZoc+jKj4PoNhgefJcKScuhEQW5L1bKWGS2V3KdCMPCBS7a9XAI4NPOvCZqA5i ad/I0Ju8slwC5SPpEnUgyMDnVBVKc8eI/niHHHxg= Message-ID: <509750B0.2030000@yandex.ru> Date: Mon, 05 Nov 2012 09:37:52 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Stefan Monnier Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <5096A046.6090908@yandex.ru> In-Reply-To: <5096A046.6090908@yandex.ru> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) On 04.11.2012 21:05, Dmitry Gutov wrote: > On 04.11.2012 17:53, Stefan Monnier wrote: >>> 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. >> >> `while-no-input' (which AFAICT is used by ido) is supposed to interrupt >> the computation as soon as you type the next input so you don't need >> to wait. >> >> Are you saying that while-no-input doesn't work? > > I only see `while-no-input' used in one place there: in > `ido-make-merged-file-list', and that function is only used in > `find-file' mode. > > So yeah, using it around matching loops in `ido-set-matches-1' might be > another way to optimize, provided the overhead is not too much. Disregard the "overhead" remark, I misread what the macro does: it's not actually a looping construct. To try it, I just wrapped in it the "busy" part of `ido-set-matches-1' - and indeed, no more waiting a several seconds after button mashing. It's a bit buggy so far, but that's to be expected. The caching approach still feels faster in most cases, and is instantaneous in cases when we're editing input and have few or no matches for the current input (if we're backspacing, then only when no matches). It has room for usability improvements, too. I won't insist, though. I kind of decided to disable flex anyway and just use regexp matching sometimes. --Dmitry From debbugs-submit-bounces@debbugs.gnu.org Mon Nov 05 16:00:38 2012 Received: (at 12796) by debbugs.gnu.org; 5 Nov 2012 21:00:38 +0000 Received: from localhost ([127.0.0.1]:51107 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVTmf-0004hU-SH for submit@debbugs.gnu.org; Mon, 05 Nov 2012 16:00:38 -0500 Received: from forward5h.mail.yandex.net ([84.201.186.23]:51170) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVTma-0004h6-M9 for 12796@debbugs.gnu.org; Mon, 05 Nov 2012 16:00:35 -0500 Received: from smtp2h.mail.yandex.net (smtp2h.mail.yandex.net [84.201.187.145]) by forward5h.mail.yandex.net (Yandex) with ESMTP id 5BCA8D009AE; Tue, 6 Nov 2012 00:57:23 +0400 (MSK) Received: from smtp2h.mail.yandex.net (localhost [127.0.0.1]) by smtp2h.mail.yandex.net (Yandex) with ESMTP id 2AA5B17000D4; Tue, 6 Nov 2012 00:57:23 +0400 (MSK) Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp2h.mail.yandex.net (nwsmtp/Yandex) with ESMTP id vMNOwRCt-vMNO4jk1; Tue, 6 Nov 2012 00:57:23 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352149043; bh=UtCWFd5imMXqFNf/DuFVcIwh6xQPFJqJX59s5OTZzi0=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: Content-Type:Content-Transfer-Encoding; b=WGs0JhZt3yUh06SNVOvHZ9LLiqztFIYQaSogWRQVtsBZzLSgUict/oJPqMw6z0VFY 7LWfsJjTbXe8zEyVOszhaK3rR8gsg3KotOIE81yf7SYTuVf3oqUuAH3g6WB+L08F/r 9iJk5dQkz0wrPmUo6iFU97alkBSRV3oYKBZujLmw= Message-ID: <50982835.2050106@yandex.ru> Date: Tue, 06 Nov 2012 00:57:25 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: sdl.web@gmail.com Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) Leo writes: > On 2012-11-04 13:58 +0800, Dmitry Gutov wrote: >> Any objections? > > This is special-cased optimisation which doesn't address the root cause > of the slowness. We need a better solution. And the root cause is..? Doing some sort of preprocessing on the candidates list comes to mind (search tree?), but I don't immediately see a way of doing that for flex matching. From debbugs-submit-bounces@debbugs.gnu.org Mon Nov 05 20:48:24 2012 Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 01:48:25 +0000 Received: from localhost ([127.0.0.1]:51353 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVYHA-0003eI-FA for submit@debbugs.gnu.org; Mon, 05 Nov 2012 20:48:24 -0500 Received: from ironport2-out.teksavvy.com ([206.248.154.182]:3190) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVYH9-0003eC-Cz for 12796@debbugs.gnu.org; Mon, 05 Nov 2012 20:48:23 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0EAG6Zu0/O+LEi/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLNBIUGA0kAYgbBboJkEQDiEKIfoRqiWuDHoFYgwc X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="205886404" Received: from 206-248-177-34.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net) ([206.248.177.34]) by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA; 05 Nov 2012 20:45:14 -0500 Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848) id C5A30AE203; Mon, 5 Nov 2012 20:45:13 -0500 (EST) From: Stefan Monnier To: Kim F. Storm , Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Message-ID: References: <5096040B.50002@yandex.ru> <5096A046.6090908@yandex.ru> <509750B0.2030000@yandex.ru> Date: Mon, 05 Nov 2012 20:45:13 -0500 In-Reply-To: <509750B0.2030000@yandex.ru> (Dmitry Gutov's message of "Mon, 05 Nov 2012 09:37:52 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.8 (/) X-Debbugs-Envelope-To: 12796 Cc: 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.8 (/) [ Hi Kim, can you give me your opinion on this? ] > To try it, I just wrapped in it the "busy" part of `ido-set-matches-1' - > and indeed, no more waiting a several seconds after button > mashing. It's a bit buggy so far, but that's to be expected. To eliminate the buggy behavior, it should probably be put elsewhere, maybe directly in ido-exhibit (the post-command-hook). > The caching approach still feels faster in most cases, and is instantaneous > in cases when we're editing input and have few or no matches for the current > input (if we're backspacing, then only when no matches). It has room for > usability improvements, too. I'm not opposed to caching, actually. I think the two are independent: it's important that a slow computation of the completion-data doesn't force the user to edit slowly. But it's also good to optimize the computation itself such that interrupting the computation happens rarely. I'm not familiar with the ido.el code, so I find it difficult to judge if your approach to caching is right. Kim could you take a look (the patch can be seen at http://debbugs.gnu.org/12796)? Stefan From debbugs-submit-bounces@debbugs.gnu.org Tue Nov 06 06:07:03 2012 Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 11:07:03 +0000 Received: from localhost ([127.0.0.1]:51573 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVgzm-0007dN-TG for submit@debbugs.gnu.org; Tue, 06 Nov 2012 06:07:03 -0500 Received: from ispc3.dotserv.com ([178.20.216.13]:49257) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVgzl-0007cy-1F for 12796@debbugs.gnu.org; Tue, 06 Nov 2012 06:07:02 -0500 Received: from localhost (localhost [127.0.0.1]) by ispc3.dotserv.com (Postfix) with ESMTP id 95AF08042778C; Tue, 6 Nov 2012 12:03:49 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at ispc3.dotserv.com Received: from ispc3.dotserv.com ([127.0.0.1]) by localhost (ispc3.dotserv.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 13kbz3QZwPOg; Tue, 6 Nov 2012 12:03:46 +0100 (CET) Received: from [10.1.82.9] (1405ds6-amb.1.fullrate.dk [90.184.79.200]) (Authenticated sender: storm@cua.dk) by ispc3.dotserv.com (Postfix) with ESMTPSA id 1C71780121B23; Tue, 6 Nov 2012 12:03:46 +0100 (CET) Message-ID: <5098EE91.9000906@cua.dk> Date: Tue, 06 Nov 2012 12:03:45 +0100 From: Kim Storm User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Stefan Monnier Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <5096A046.6090908@yandex.ru> <509750B0.2030000@yandex.ru> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.8 (/) X-Debbugs-Envelope-To: 12796 Cc: 12796@debbugs.gnu.org, Dmitry Gutov X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.8 (/) On 2012-11-06 02:45, Stefan Monnier wrote: > [ Hi Kim, can you give me your opinion on this? ] > >> To try it, I just wrapped in it the "busy" part of `ido-set-matches-1' - >> and indeed, no more waiting a several seconds after button >> mashing. It's a bit buggy so far, but that's to be expected. > To eliminate the buggy behavior, it should probably be put elsewhere, > maybe directly in ido-exhibit (the post-command-hook). Sounds right, but I a bit worried that some of the state information may get corrupted if arbitrarily interrupted by user input. If someone proposes a patch, I'll look at it. > >> The caching approach still feels faster in most cases, and is instantaneous >> in cases when we're editing input and have few or no matches for the current >> input (if we're backspacing, then only when no matches). It has room for >> usability improvements, too. > I'm not opposed to caching, actually. I think the two are independent: > it's important that a slow computation of the completion-data doesn't > force the user to edit slowly. But it's also good to optimize the > computation itself such that interrupting the computation > happens rarely. > > I'm not familiar with the ido.el code, so I find it difficult to judge > if your approach to caching is right. Kim could you take a look (the > patch can be seen at http://debbugs.gnu.org/12796)? I looked at the caching patch, and it looks alright (in the sense that I don't think it will break ido behaviour.) I'm not sure how efficient the caching is though. As far as I can see, it only caches the most recent (non-empty) list of matches, i.e. the shortest list corresponding to the longest "successful" user input in the minibuffer. So if the user has to backtrack beyond that point, I don't really see how the caching will help, as the cache is then invalidated. Also, I don't quite understand why this condition is needed: (<= (* 10 (length matches)) (length ido-cur-list))) It seems to me to only cache a list of matches that has reduced the set of matches by a factor 10 - if the aim is to reduce processing time for long lists, even reducing by a factor of 2 may be noticable ? But maybe the intention of this line was to stop caching once the list has become short than 1/10th of the original list? In that case, the operator should be <= I think ? I any case, I'm not opposed to adding some form of caching here, and the proposed patch seems on the right track, but I'm not convinced that it is the optimal approach. Kim From debbugs-submit-bounces@debbugs.gnu.org Tue Nov 06 10:42:02 2012 Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 15:42:02 +0000 Received: from localhost ([127.0.0.1]:52654 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVlHu-0006M5-Ft for submit@debbugs.gnu.org; Tue, 06 Nov 2012 10:42:02 -0500 Received: from forward3.mail.yandex.net ([77.88.46.8]:36433) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVlHq-0006Le-AH for 12796@debbugs.gnu.org; Tue, 06 Nov 2012 10:42:01 -0500 Received: from smtp2.mail.yandex.net (smtp2.mail.yandex.net [77.88.46.102]) by forward3.mail.yandex.net (Yandex) with ESMTP id AF7F2B40B9A; Tue, 6 Nov 2012 19:38:44 +0400 (MSK) Received: from smtp2.mail.yandex.net (localhost [127.0.0.1]) by smtp2.mail.yandex.net (Yandex) with ESMTP id 77EC8E20610; Tue, 6 Nov 2012 19:38:44 +0400 (MSK) Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp2.mail.yandex.net (nwsmtp/Yandex) with ESMTP id chWqBJCk-chWCfVJr; Tue, 6 Nov 2012 19:38:43 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352216324; bh=Pzs//BhqK8tk72Py6tqDneGg283oDsmjGz+deTyqLpE=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=EbQRVXdFkfMf4/bX3x+g6Tn1Hzp8KkkWiqiuBKhXT/UgYr/ykejTHemI6BvY8dovQ YVOpFy/U640QfUD4nmud4wirdhG2nYRSY/3YrXV9x/aXKV9Uzm4TiKKbczsVt1PtIb ZHe0ypx+X364ykrVyVc6ozIbSzvgappnB0985zNs= Message-ID: <50992F05.5090108@yandex.ru> Date: Tue, 06 Nov 2012 19:38:45 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Kim Storm Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <5096A046.6090908@yandex.ru> <509750B0.2030000@yandex.ru> <5098EE91.9000906@cua.dk> In-Reply-To: <5098EE91.9000906@cua.dk> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: Stefan Monnier , 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) On 06.11.2012 15:03, Kim Storm wrote: >> I'm not familiar with the ido.el code, so I find it difficult to judge >> if your approach to caching is right. Kim could you take a look (the >> patch can be seen at http://debbugs.gnu.org/12796)? > > I looked at the caching patch, and it looks alright (in the sense that I > don't think > it will break ido behaviour.) > > I'm not sure how efficient the caching is though. As far as I can see, > it only > caches the most recent (non-empty) list of matches, i.e. the shortest list > corresponding to the longest "successful" user input in the minibuffer. > > So if the user has to backtrack beyond that point, I don't really see > how the > caching will help, as the cache is then invalidated. That's true, backtracking was not a priority. But see below. > Also, I don't quite understand why this condition is needed: > > (<= (* 10 (length matches)) (length ido-cur-list))) > > It seems to me to only cache a list of matches that has reduced > the set of matches by a factor 10 - if the aim is to reduce processing > time for long lists, even reducing by a factor of 2 may be noticable ? > > But maybe the intention of this line was to stop caching once the list > has become short than 1/10th of the original list? In that case, the > operator should be <= I think ? No, the idea is to limit memory consumption (which may be a bit premature) and make sure that the filtered matches list is smaller enough than the original to justify saving it. I probably should change 10 to a smaller constant, like 3 or 2. On the "stop caching" front, we can add a lower bound check, comparing the matches length to an absolute or relative value. This way, doing a few backspaces from a sufficiently narrowed state won't trigger a full recomputation. To go further than that, it shouldn't be hard to keep a stack of caches for the current input string as it's typed, but I suspect memory consumption may be a bigger concern in this case. WDYT? From debbugs-submit-bounces@debbugs.gnu.org Tue Nov 06 11:49:08 2012 Received: (at 12796) by debbugs.gnu.org; 6 Nov 2012 16:49:08 +0000 Received: from localhost ([127.0.0.1]:52714 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVmKp-0007pa-BN for submit@debbugs.gnu.org; Tue, 06 Nov 2012 11:49:08 -0500 Received: from ispc3.dotserv.com ([178.20.216.13]:47359) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVmKn-0007pT-No for 12796@debbugs.gnu.org; Tue, 06 Nov 2012 11:49:06 -0500 Received: from localhost (localhost [127.0.0.1]) by ispc3.dotserv.com (Postfix) with ESMTP id C62A38013006B; Tue, 6 Nov 2012 17:45:52 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at ispc3.dotserv.com Received: from ispc3.dotserv.com ([127.0.0.1]) by localhost (ispc3.dotserv.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lDY6tkrrDbnq; Tue, 6 Nov 2012 17:45:49 +0100 (CET) Received: from [10.1.82.9] (1405ds6-amb.1.fullrate.dk [90.184.79.200]) (Authenticated sender: storm@cua.dk) by ispc3.dotserv.com (Postfix) with ESMTPSA id 746AE80103D98; Tue, 6 Nov 2012 17:45:49 +0100 (CET) Message-ID: <50993EBC.7000502@cua.dk> Date: Tue, 06 Nov 2012 17:45:48 +0100 From: Kim Storm User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <5096A046.6090908@yandex.ru> <509750B0.2030000@yandex.ru> <5098EE91.9000906@cua.dk> <50992F05.5090108@yandex.ru> In-Reply-To: <50992F05.5090108@yandex.ru> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.8 (/) X-Debbugs-Envelope-To: 12796 Cc: Stefan Monnier , 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.8 (/) On 2012-11-06 16:38, Dmitry Gutov wrote: >> So if the user has to backtrack beyond that point, I don't really see >> how the >> caching will help, as the cache is then invalidated. > > That's true, backtracking was not a priority. But see below. That is what I thought was the primary purpose of your patch. But I now understand that it was aimed at supplying a shorter list of matches to start from "down the list". That's definitely worth doing! >> It seems to me to only cache a list of matches that has reduced >> the set of matches by a factor 10 - if the aim is to reduce processing >> time for long lists, even reducing by a factor of 2 may be noticable ? >> >> But maybe the intention of this line was to stop caching once the list >> has become short than 1/10th of the original list? In that case, the >> operator should be <= I think ? > > > No, the idea is to limit memory consumption (which may be a bit > premature) and make sure that the filtered matches list is smaller > enough than the original to justify saving it. I probably should > change 10 to a smaller constant, like 3 or 2. > I wouldn't worry that much about memory consumption these days - if you are really worried, create a ido-cache-max-matches custom variable with the max length of matches that you want to cache. default nil meaning no limit. So as long as the matches list is shorter than the original list and shorter than the max limit, just cache the list. > On the "stop caching" front, we can add a lower bound check, comparing > the matches length to an absolute or relative value. This way, doing a > few backspaces from a sufficiently narrowed state won't trigger a full > recomputation. Right -- if the cache is less than say 25 elements long, I wouldn't expect the speedup to be noticable. > To go further than that, it shouldn't be hard to keep a stack of > caches for the current input string as it's typed, but I suspect > memory consumption may be a bigger concern in this case. Yes, for the problem at hand, I think your approach is just fine, so with a few tweaks as discussed above, I support your patch. Kim From debbugs-submit-bounces@debbugs.gnu.org Tue Nov 06 21:27:54 2012 Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 02:27:54 +0000 Received: from localhost ([127.0.0.1]:53087 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVvMw-0006xy-Gi for submit@debbugs.gnu.org; Tue, 06 Nov 2012 21:27:54 -0500 Received: from mail-pb0-f44.google.com ([209.85.160.44]:55046) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVvMv-0006xr-6f for 12796@debbugs.gnu.org; Tue, 06 Nov 2012 21:27:53 -0500 Received: by mail-pb0-f44.google.com with SMTP id ro8so839049pbb.3 for <12796@debbugs.gnu.org>; Tue, 06 Nov 2012 18:27:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=L5P1pGT2F7kLyNVWh+EA86XVOMW3BccB6kofgv/3how=; b=v+fTmSDQlVoamlQqQYBvRtLk5VtIX5tz15oNh3IKMQ7u2dJkDuzxRX0xzyedOiOYf0 ZPMe7w371YQoUQ2kYqpw/vtf4xYIBNw85lDzBwukxITW+AbykIvtBRzEunxg1yS7D+hm XvHnJJBqg1S211Wu8uHhnICPq2XlyCuWCuoqAcxPB3B3WTb3TU2Ori5sgrBl0RomEyn2 qhVgL0Lx2JELFDGMhZxjoEOGAgKP8B6tySfLoXqFB44x83oTj2fqhZ11Ykm14xCe+gVM ExTj5rTvQPeJoJRvWvde8GXnJCSAx7pIDoN+V0de/MS0RhXk2AM9ZJEpm9i13b2vdD9i fmpw== Received: by 10.68.253.230 with SMTP id ad6mr2679639pbd.84.1352255278980; Tue, 06 Nov 2012 18:27:58 -0800 (PST) Received: from localhost ([119.255.41.67]) by mx.google.com with ESMTPS id nf9sm12852165pbc.17.2012.11.06.18.27.56 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 06 Nov 2012 18:27:57 -0800 (PST) From: Leo To: Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> Date: Wed, 07 Nov 2012 10:27:48 +0800 In-Reply-To: <50982835.2050106@yandex.ru> (Dmitry Gutov's message of "Tue, 06 Nov 2012 00:57:25 +0400") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) On 2012-11-06 04:57 +0800, Dmitry Gutov wrote: > And the root cause is..? I haven't looked. So maybe you could use a profiler to find where it is. It seems string-match in flex matching is slow. I think we should make sure the computation is optimised. There are third party libs such as ido-hacks.el which might have some ideas. > Doing some sort of preprocessing on the candidates list comes to mind > (search tree?), but I don't immediately see a way of doing that for flex > matching. Leo From debbugs-submit-bounces@debbugs.gnu.org Tue Nov 06 23:06:14 2012 Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 04:06:14 +0000 Received: from localhost ([127.0.0.1]:53155 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVwu6-0003Nl-Gl for submit@debbugs.gnu.org; Tue, 06 Nov 2012 23:06:14 -0500 Received: from forward2.mail.yandex.net ([77.88.46.7]:39775) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVwu1-0003NX-HZ for 12796@debbugs.gnu.org; Tue, 06 Nov 2012 23:06:12 -0500 Received: from smtp3.mail.yandex.net (smtp3.mail.yandex.net [77.88.46.103]) by forward2.mail.yandex.net (Yandex) with ESMTP id 71FB812A1434; Wed, 7 Nov 2012 08:06:13 +0400 (MSK) Received: from smtp3.mail.yandex.net (localhost [127.0.0.1]) by smtp3.mail.yandex.net (Yandex) with ESMTP id 2BAD91BA0832; Wed, 7 Nov 2012 08:06:13 +0400 (MSK) Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp3.mail.yandex.net (nwsmtp/Yandex) with ESMTP id 68BipxI4-6CBWkcXY; Wed, 7 Nov 2012 08:06:12 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352261173; bh=/L+/WInJ0MoHn3tbIyTsuq3JOqpKW9eYDvNrEMIXtZg=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=dg6/60HEUf+C/Gbdlv5XpGtA8Pu69bB4rRoTFKt02ArwoNk7dXM14UIrRI79CQxVZ TWB97ERqZz24DEImXLwjuSxtCQ5pEq1HZfPUIUh/x2LDZoWUVD1h+aDT+cLGd8c6ET TEaRnz/ZxfoldUclVs8z8r8fXtTzqdwzCj6mgdiY= Message-ID: <5099DE35.2060402@yandex.ru> Date: Wed, 07 Nov 2012 08:06:13 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Leo Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: Stefan Monnier , 12796@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) On 07.11.2012 6:27, Leo wrote: > On 2012-11-06 04:57 +0800, Dmitry Gutov wrote: >> And the root cause is..? > > I haven't looked. So maybe you could use a profiler to find where it is. > It seems string-match in flex matching is slow. I think we should make > sure the computation is optimised. There are third party libs such as > ido-hacks.el which might have some ideas. That was actually a good advice. As far as I can tell, most of the speed improvement comes from the following change: === modified file 'lisp/ido.el' --- lisp/ido.el 2012-10-05 07:38:05 +0000 +++ lisp/ido.el 2012-11-07 03:40:57 +0000 @@ -3764,7 +3764,7 @@ 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 "" t) ".*")) (if ido-enable-prefix (setq re (concat "\\`" re))) (mapc :) Then there's this (from ido-set-matches-1's defadvice's docstring): "This advice makes it a good deal faster, by caching narrowed choices lists." Which looks like it's doing something with hashtables similar to what I proposed to do with a stack. With approximately the same performance improvement (which is only visible with the change above reverted). Anyway, with my data sets (all Emacs functions or all Emacs vars, 12000 and 4000 items respectively), the one-line change makes flex matching about as fast as I can type, so I guess we'll leave implementing cache until someone else complains. Feel free to ping me then. I'm still going to see if I can make while-no-input work here, though. From debbugs-submit-bounces@debbugs.gnu.org Wed Nov 07 00:40:59 2012 Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 05:40:59 +0000 Received: from localhost ([127.0.0.1]:53284 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVyNm-0005Wm-NO for submit@debbugs.gnu.org; Wed, 07 Nov 2012 00:40:59 -0500 Received: from forward18.mail.yandex.net ([95.108.253.143]:41433) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TVyNg-0005Wb-Vu for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 00:40:56 -0500 Received: from smtp18.mail.yandex.net (smtp18.mail.yandex.net [95.108.252.18]) by forward18.mail.yandex.net (Yandex) with ESMTP id B49131781991; Wed, 7 Nov 2012 09:40:56 +0400 (MSK) Received: from smtp18.mail.yandex.net (localhost [127.0.0.1]) by smtp18.mail.yandex.net (Yandex) with ESMTP id 7B8F118A03E6; Wed, 7 Nov 2012 09:40:56 +0400 (MSK) Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp18.mail.yandex.net (nwsmtp/Yandex) with ESMTP id etji8vcK-eujWxrUI; Wed, 7 Nov 2012 09:40:56 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352266856; bh=UkTGooNT4neXz8FK5bApm6qrUrT9Cyaz+sBC3xzNZag=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=WuRS3tnaOHmNhOppEO8XWlwtv7tNsrhvLB/c1L1apSuSmBAo7/XId520+B8O9fpwU P2C6CxhIetq5z06oH1RoQLgX6SVdwbzj5B77s78MkTw5ja4l4VDu/0RL6LjJwBg4U9 v4HvtYNf9UbiuUJZcKQkaQKZHfcvY/9+79eBVknM= Message-ID: <5099F46C.7060301@yandex.ru> Date: Wed, 07 Nov 2012 09:41:00 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Kim Storm Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <5096A046.6090908@yandex.ru> <509750B0.2030000@yandex.ru> <5098EE91.9000906@cua.dk> In-Reply-To: <5098EE91.9000906@cua.dk> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: Stefan Monnier , 12796@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) On 06.11.2012 15:03, Kim Storm wrote: > On 2012-11-06 02:45, Stefan Monnier wrote: >> [ Hi Kim, can you give me your opinion on this? ] >> >>> To try it, I just wrapped in it the "busy" part of `ido-set-matches-1' - >>> and indeed, no more waiting a several seconds after button >>> mashing. It's a bit buggy so far, but that's to be expected. >> To eliminate the buggy behavior, it should probably be put elsewhere, >> maybe directly in ido-exhibit (the post-command-hook). > Sounds right, but I a bit worried that some of the state information > may get corrupted if arbitrarily interrupted by user input. > > If someone proposes a patch, I'll look at it. How does this look to you? I added a new var because ido-rescan is unconditionally set to nil in many places. By the way, is there a place where ido-rotate is set to anything but nil? Does this variable actually do anything? === modified file 'lisp/ido.el' --- lisp/ido.el 2012-10-05 07:38:05 +0000 +++ lisp/ido.el 2012-11-07 05:34:53 +0000 @@ -1020,6 +1020,9 @@ (defvar ido-rotate nil "Non-nil means we are rotating list of matches.") +(defvar ido-interrupted nil + "Non-nil means calculation of matches was interrupted by keyboard input.") + (defvar ido-text nil "Stores the users string as it is typed in.") @@ -3778,9 +3781,14 @@ (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)) - ido-rotate nil))) + (when (or ido-rescan ido-interrupted) + (setq ido-interrupted t) + (while-no-input + (setq ido-matches (ido-set-matches-1 (reverse ido-cur-list) + (not ido-rotate)) + ido-interrupted nil + ido-rotate nil)) + (when ido-interrupted (setq ido-matches nil)))) (defun ido-ignore-item-p (name re-list &optional ignore-ext) ;; Return t if the buffer or file NAME should be ignored. @@ -4513,11 +4521,12 @@ (exit-minibuffer))) ;; Insert the match-status information: - (ido-set-common-completion) - (let ((inf (ido-completions contents))) - (setq ido-show-confirm-message nil) - (ido-trace "inf" inf) - (insert inf)) + (unless ido-interrupted + (ido-set-common-completion) + (let ((inf (ido-completions contents))) + (setq ido-show-confirm-message nil) + (ido-trace "inf" inf) + (insert inf))) )))) (defun ido-completions (name) From debbugs-submit-bounces@debbugs.gnu.org Wed Nov 07 05:38:50 2012 Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 10:38:50 +0000 Received: from localhost ([127.0.0.1]:53461 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TW321-0003q5-Ig for submit@debbugs.gnu.org; Wed, 07 Nov 2012 05:38:50 -0500 Received: from mail-da0-f44.google.com ([209.85.210.44]:52392) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TW31z-0003pn-HY for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 05:38:48 -0500 Received: by mail-da0-f44.google.com with SMTP id h15so635732dan.3 for <12796@debbugs.gnu.org>; Wed, 07 Nov 2012 02:38:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=kHKVw9i/finU9phF3Di4Umhq9kmERbEIrhM503Z/Fr4=; b=cw9NhNpBeaYDspPioe8Yen8y3/vxwj3mO+0nVyZRQAPROf4EcXIuATnWRvFUI7PEoA cm+pO+3z5ndDbnkPc6rGeCpBbYdJjW5JcQbYO/YzE3u/TutEzs+9kYjYbxrGKTvWIVyq 1Lf1QFkHZ4Cez/5KdlKk5x/Abv2qd7Rhx7UfDHDfRxuZ+Rr6EWdnnu6jIth0XbePbeJx qJjuUYsOVV+luPwanvEJ+FJn3wBXxols1nrFz9bIQeeBW7/1I6hTw8oIt63323JBSekI b9T9hAEMh70fT1ha3aBUboKUS8+83IUYvVKcyMInA485fZOUXJPYYkulx/6oL2cTvfcb FgaQ== Received: by 10.68.217.201 with SMTP id pa9mr12385902pbc.45.1352284731154; Wed, 07 Nov 2012 02:38:51 -0800 (PST) Received: from localhost ([119.255.41.67]) by mx.google.com with ESMTPS id bd2sm14084425pab.36.2012.11.07.02.38.47 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 07 Nov 2012 02:38:50 -0800 (PST) From: Leo To: Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> Date: Wed, 07 Nov 2012 18:38:31 +0800 In-Reply-To: <5099DE35.2060402@yandex.ru> (Dmitry Gutov's message of "Wed, 07 Nov 2012 08:06:13 +0400") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: Stefan Monnier , 12796@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -0.7 (/) 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)) From debbugs-submit-bounces@debbugs.gnu.org Wed Nov 07 16:54:54 2012 Received: (at 12796) by debbugs.gnu.org; 7 Nov 2012 21:54:54 +0000 Received: from localhost ([127.0.0.1]:54904 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWDaH-0005KV-O9 for submit@debbugs.gnu.org; Wed, 07 Nov 2012 16:54:54 -0500 Received: from forward3.mail.yandex.net ([77.88.46.8]:39340) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWDaE-0005KK-36 for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 16:54:52 -0500 Received: from smtp2.mail.yandex.net (smtp2.mail.yandex.net [77.88.46.102]) by forward3.mail.yandex.net (Yandex) with ESMTP id D6329B416BD; Thu, 8 Nov 2012 01:54:49 +0400 (MSK) Received: from smtp2.mail.yandex.net (localhost [127.0.0.1]) by smtp2.mail.yandex.net (Yandex) with ESMTP id 915A5E205B2; Thu, 8 Nov 2012 01:54:49 +0400 (MSK) Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp2.mail.yandex.net (nwsmtp/Yandex) with ESMTP id smW4Phda-snW4xXLg; Thu, 8 Nov 2012 01:54:49 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352325289; bh=6o0CwF6hxdEg8l4hiBOqB9JYTGrYNVmaPh1/jHySJC4=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=Y/xpeAUw/4zPenLrYk7z9xDzcu2ttK7arahx4cNLP0JVbcvKHWgI4W/INK1SplNq4 N/79/eu+QvIWpCpAR4na3Je9xIPx/ms0zcKrg25vMG/biFt5rSfXRrKeH9TVIKDPQw ptUL6bAXX0mUBArxxtrpwB9DDHjNPOeWqSayHNt8= Message-ID: <509AD8AB.90703@yandex.ru> Date: Thu, 08 Nov 2012 01:54:51 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Leo Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: Stefan Monnier , 12796@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) On 07.11.2012 14:38, Leo wrote: > 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) > > ... I've done some testing, see the setup and numbers at the end. It looks like, with either patch, flex matching is not the bottleneck anymore. ido-hacks has some other functions changed or overridden, so if you're not satisfied with performance, you might want to look there. (defun random-string (len) (let ((chars "1234567890abcdefghijklmnopqrstyvwxyz")) (apply 'string (loop for i from 1 to len collect (aref chars (random (length chars))))))) (defun random-dataset (size len) (loop for i from 1 to size collect (random-string len))) (defmacro js2-time (form) "Evaluate FORM, discard result, and return elapsed time in sec" (declare (debug t)) (let ((beg (make-symbol "--js2-time-beg--")) (delta (make-symbol "--js2-time-end--"))) `(let ((,beg (current-time)) ,delta) ,form (/ (truncate (* (- (float-time (current-time)) (float-time ,beg)) 10000)) 10000.0)))) (defun ido-match-test (size len ido-text) (let ((items (random-dataset size len)) (ido-cur-item 'list)) (js2-time (ido-set-matches-1 items)))) ;; * size len input time ;; cis 9000 35 aaaaaaaaaa 0.06 ;; cis 18000 15 aaaaaaaaaa 0.055 ;; cis 18000 15 abcdefghzzzzz 0.057 ;; omt 9000 35 aaaaaaaaaa 0.055 \ ;; omt 18000 15 aaaaaaaaaa 0.054 + <- but the variance is bigger ;; omt 18000 15 abcdefghzzzzz 0.056 / ;; unp 9000 35 abcdefghzzzzz 0.82 ;; unp 18000 15 abcdefghzzzzz 0.31 ;; legend: ;; cis = ido-chars-in-string ;; ont = (split-string ido-text "" t) ;; unp = (split-string ido-text "") ;; bonus: ;; cis 18000 45 abcdefghzzz123 0.51 ;; omt 18000 45 abcdefghzzz123 0.15 ;; cis 18000 45 abcdefghzzz123 3.02 From debbugs-submit-bounces@debbugs.gnu.org Wed Nov 07 21:02:43 2012 Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 02:02:43 +0000 Received: from localhost ([127.0.0.1]:55055 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWHS6-0004Od-CL for submit@debbugs.gnu.org; Wed, 07 Nov 2012 21:02:42 -0500 Received: from mail-pb0-f44.google.com ([209.85.160.44]:55185) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWHS4-0004OW-Mm for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 21:02:41 -0500 Received: by mail-pb0-f44.google.com with SMTP id ro8so1635494pbb.3 for <12796@debbugs.gnu.org>; Wed, 07 Nov 2012 18:02:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=fC8Q+zbu12kiC1qEVjMbpi68LAn/UZSIJJ2uzPu+ho8=; b=JBLoI0vbhHsUvWotFhLPf4usqx3+g4HxtHNZmaeslq0vWq80bYBD0pWEETp+60PnxQ y1NqdEQeILQA+AIfUYRw2aW1TET7qCNycSh7V1xKfqP4JbZwpRj+lJxN7lLFDIHU5Dbm 6SIn+4tmJ/h5tM5i/MCV8BRstwRrKxFeHSU0vhXYPeIxNivplfaEeDiNNbBD3ibiwCue 9V6dAwZymo3TbiCR6Bwej66ZTLjs2mRe+f3PloMXBob6aeKfbEbdEA+GcY9Aon3h9QcG /Umrbswzzd4AIJlxBuosFH9BxekMvE+PDjS9Md53l24DmJyLo3Vh0GRq0AybLUvC7D+6 a3+g== Received: by 10.68.115.75 with SMTP id jm11mr4630143pbb.28.1352340160946; Wed, 07 Nov 2012 18:02:40 -0800 (PST) Received: from localhost ([119.255.41.67]) by mx.google.com with ESMTPS id x8sm15202762paw.16.2012.11.07.18.02.37 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 07 Nov 2012 18:02:39 -0800 (PST) From: Leo To: Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> Date: Thu, 08 Nov 2012 10:00:58 +0800 In-Reply-To: <509AD8AB.90703@yandex.ru> (Dmitry Gutov's message of "Thu, 08 Nov 2012 01:54:51 +0400") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 12796 Cc: Stefan Monnier , 12796@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) On 2012-11-08 05:54 +0800, Dmitry Gutov wrote: > It looks like, with either patch, flex matching is not the bottleneck > anymore. Excellent. The other patch is definitely simpler. So I prefer it. Stefan, for concluding this bug, I think we should make this change. >From this bit in ido-set-matches-1: (if ido-enable-prefix (setq re (concat "\\`" re))) It seems not including the leading and trailing .* is intended. So do you mind installing the following small change for 24.3 that greatly improves ido performance: diff --git a/lisp/ido.el b/lisp/ido.el index 31d5279d..c8bc0bb7 100644 --- a/lisp/ido.el +++ b/lisp/ido.el @@ -3783,7 +3783,7 @@ (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 "") ".*")) + (setq re (mapconcat #'regexp-quote (split-string ido-text "" t) ".*")) (if ido-enable-prefix (setq re (concat "\\`" re))) (mapc Leo From debbugs-submit-bounces@debbugs.gnu.org Wed Nov 07 21:05:57 2012 Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 02:05:57 +0000 Received: from localhost ([127.0.0.1]:55059 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWHVF-0004T8-6i for submit@debbugs.gnu.org; Wed, 07 Nov 2012 21:05:57 -0500 Received: from ironport2-out.teksavvy.com ([206.248.154.182]:61712) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWHVD-0004T0-1z for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 21:05:55 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0EAG6Zu0/O+LEi/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLDiYSFBgNJIgcBboJkEQDiEKacYFYgwc X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206712351" Received: from 206-248-177-34.dsl.teksavvy.com (HELO ceviche.home) ([206.248.177.34]) by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA; 07 Nov 2012 21:05:54 -0500 Received: by ceviche.home (Postfix, from userid 20848) id 5338A6610A; Wed, 7 Nov 2012 21:05:54 -0500 (EST) From: Stefan Monnier To: Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Message-ID: References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> Date: Wed, 07 Nov 2012 21:05:54 -0500 In-Reply-To: <5099DE35.2060402@yandex.ru> (Dmitry Gutov's message of "Wed, 07 Nov 2012 08:06:13 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.8 (/) X-Debbugs-Envelope-To: 12796 Cc: Leo , 12796@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.8 (/) > - (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*")) > + (setq re (mapconcat #'regexp-quote (split-string ido-text "" t) > ".*")) Sounds like a good change. Tho: (mapconcat (lambda (c) (regexp-quote (string c))) ido-text ".*") would work as well. You could try to speed up the regexp matching some more by eliminating backtracking (which should mostly eliminate a few pathological cases): (let ((first t)) (mapconcat (lambda (c) (if first (progn (setq first nil) (regexp-quote (string c))) (concat "[^" (string c) "]*" (regexp-quote (string c))))) ido-text "")) > I'm still going to see if I can make while-no-input work here, though. Yes, that'd be very welcome. Stefan From debbugs-submit-bounces@debbugs.gnu.org Wed Nov 07 23:14:46 2012 Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 04:14:46 +0000 Received: from localhost ([127.0.0.1]:55103 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWJVu-0007Mi-Ih for submit@debbugs.gnu.org; Wed, 07 Nov 2012 23:14:46 -0500 Received: from ironport2-out.teksavvy.com ([206.248.154.182]:31967) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWJVt-0007Mc-0l for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 23:14:45 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0EAG6Zu0/O+LEi/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLNBIUGA0kiBwFugmQRAOIQppxgViDBw X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206717905" Received: from 206-248-177-34.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net) ([206.248.177.34]) by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA; 07 Nov 2012 23:14:44 -0500 Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848) id B2DDCAE59E; Wed, 7 Nov 2012 23:14:44 -0500 (EST) From: Stefan Monnier To: Leo Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Message-ID: References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> Date: Wed, 07 Nov 2012 23:14:44 -0500 In-Reply-To: (Leo's message of "Thu, 08 Nov 2012 10:00:58 +0800") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 12796 Cc: Kim Storm , 12796@debbugs.gnu.org, Dmitry Gutov X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -1.9 (-) >> From this bit in ido-set-matches-1: > (if ido-enable-prefix > (setq re (concat "\\`" re))) > It seems not including the leading and trailing .* is intended. Indeed. This undesired behavior was introduced by the change to split-string introduced in Emacs-22, so the patch fixes a regression w.r.t Emacs-21. > So do you mind installing the following small change for 24.3 that > greatly improves ido performance: I guess it's OK, yes. Stefan From debbugs-submit-bounces@debbugs.gnu.org Wed Nov 07 23:29:34 2012 Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 04:29:34 +0000 Received: from localhost ([127.0.0.1]:55170 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWJkE-0007it-1p for submit@debbugs.gnu.org; Wed, 07 Nov 2012 23:29:34 -0500 Received: from forward1h.mail.yandex.net ([84.201.187.146]:33019) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWJk9-0007ii-KK for 12796@debbugs.gnu.org; Wed, 07 Nov 2012 23:29:32 -0500 Received: from smtp4h.mail.yandex.net (smtp4h.mail.yandex.net [84.201.186.21]) by forward1h.mail.yandex.net (Yandex) with ESMTP id EF2FA9E2959; Thu, 8 Nov 2012 08:29:15 +0400 (MSK) Received: from smtp4h.mail.yandex.net (localhost [127.0.0.1]) by smtp4h.mail.yandex.net (Yandex) with ESMTP id 7DB412C0110; Thu, 8 Nov 2012 08:29:15 +0400 (MSK) Received: from 98-87.nwlink.spb.ru (98-87.nwlink.spb.ru [178.252.98.87]) by smtp4h.mail.yandex.net (nwsmtp/Yandex) with ESMTP id TEtW8iBB-TFtKRTgH; Thu, 8 Nov 2012 08:29:15 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1352348955; bh=uSkpEhmIs18hUJgWn8sG7weQ9SI1bMug9Y8NIqTfOK4=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=bLTCLfmZBPv7vqQnTO2cXf5LDDFiMhrw4E29rUI+o2D+aQUAVNCJ3qkt6a+imarGY fV5Jgn2UfMvEhG+EvtqJuPArb69LlxTBgd+iuSeaZ8rUmFsBKtjS6P2EKMZu7OIacT ZZxJrIuwFdJxVrVNJmbbwZULxbTifG4vexCBR6U0= Message-ID: <509B351F.8040607@yandex.ru> Date: Thu, 08 Nov 2012 08:29:19 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Stefan Monnier Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796 Cc: Leo , 12796@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.1 (/) On 08.11.2012 6:05, Stefan Monnier wrote: >> - (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*")) >> + (setq re (mapconcat #'regexp-quote (split-string ido-text "" t) >> ".*")) > > Sounds like a good change. Tho: > > (mapconcat (lambda (c) (regexp-quote (string c))) ido-text ".*") > > would work as well. Indeed. A two-character change offering massive speedup looks cuter, though. And easier to understand for casual readers. > You could try to speed up the regexp matching some more by eliminating > backtracking (which should mostly eliminate a few pathological cases): > > (let ((first t)) > (mapconcat (lambda (c) > (if first > (progn (setq first nil) (regexp-quote (string c))) > (concat "[^" (string c) "]*" > (regexp-quote (string c))))) > ido-text "")) Yep, this adds some further speedup especially with longer string. To use the existing testing setup (numbers are a bit different in this session): ;; omt 18000 15 abcdefghzzzzz 0.042 ;; nbt 18000 15 abcdefghzzzzz 0.040 ;; omt 18000 45 abcdefghzzz123 0.127 ;; nbt 18000 45 abcdefghzzz123 0.087 >> I'm still going to see if I can make while-no-input work here, though. > > Yes, that'd be very welcome. I sent a patch that doesn't seem to break anything for me: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=12796#41 But in the light of the above numbers, it seems that (while-no-input) would almost always guard a section of code that takes 1/20th of a second to run, or less. Only useful when a user has floored "backspace", I think. From debbugs-submit-bounces@debbugs.gnu.org Thu Nov 08 02:36:38 2012 Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 07:36:38 +0000 Received: from localhost ([127.0.0.1]:55289 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWMfG-0003as-59 for submit@debbugs.gnu.org; Thu, 08 Nov 2012 02:36:38 -0500 Received: from mail-da0-f44.google.com ([209.85.210.44]:53336) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWMfE-0003al-1G for 12796@debbugs.gnu.org; Thu, 08 Nov 2012 02:36:36 -0500 Received: by mail-da0-f44.google.com with SMTP id h15so1060423dan.3 for <12796@debbugs.gnu.org>; Wed, 07 Nov 2012 23:36:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=U094xmsfdObyTNgChqjRXRJaWO3a9TR7sdHmMHOy928=; b=OCTOcA84pQJ/B+ImA7NtUjJo/HKJkl2b5cLzjv/RzbP12FZQHtJJ0n1fIN7oJeLKws NefnAJeR2ZcXbCwBJSnSvCoyuYfl5N7+nmVDD3lW3n1z/ntecQGmxcHcNqXJ2SKZVx5F nosW5qXlKfb+ipRoPjkbdPew39/CHvtEBA1vdQrjcjDgi7GsdPx0kNoW4XLnoZVeT6UM EyNqnZUsgsGBvj2Z2QgH/jxQkPV6yyxNQuod/WOgMJopldk+6qPOXWrfoWfyOvn1ZnbK qTAYfhjSZJpJIrJp/0JzKr0NCVpY6O3YApa9G22sXXppDOrx30NQVwETk41TObcSenlO BvjQ== Received: by 10.68.217.201 with SMTP id pa9mr21536340pbc.45.1352360195009; Wed, 07 Nov 2012 23:36:35 -0800 (PST) Received: from Shidais-iMac.local ([119.255.41.67]) by mx.google.com with ESMTPS id hs1sm15514747pbc.33.2012.11.07.23.36.31 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 07 Nov 2012 23:36:33 -0800 (PST) From: Leo To: Stefan Monnier Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> Date: Thu, 08 Nov 2012 15:36:23 +0800 In-Reply-To: (Stefan Monnier's message of "Wed, 07 Nov 2012 23:14:44 -0500") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (OS X 10.8.2) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 12796 Cc: Kim Storm , 12796@debbugs.gnu.org, Dmitry Gutov X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) On 2012-11-08 12:14 +0800, Stefan Monnier wrote: > Indeed. This undesired behavior was introduced by the change to > split-string introduced in Emacs-22, so the patch fixes a regression > w.r.t Emacs-21. Thanks for that information. > >> So do you mind installing the following small change for 24.3 that >> greatly improves ido performance: > > I guess it's OK, yes. Can I incorporate your suggestion on removing the backtracking issue? I have found cases where flex matching perform badly but with your suggestion, for example, cut the time from 4.8s to 0.3s. The patch could look like this: diff --git a/lisp/ido.el b/lisp/ido.el index 31d5279d..0a740b2a 100644 --- a/lisp/ido.el +++ b/lisp/ido.el @@ -3783,7 +3783,11 @@ (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 "") ".*")) + (setq re (concat (regexp-quote (string (aref ido-text 0))) + (mapconcat (lambda (c) + (concat "[^" (string c) "]*" + (regexp-quote (string c)))) + (substring ido-text 1) ""))) Leo From debbugs-submit-bounces@debbugs.gnu.org Thu Nov 08 09:05:19 2012 Received: (at 12796) by debbugs.gnu.org; 8 Nov 2012 14:05:19 +0000 Received: from localhost ([127.0.0.1]:55595 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWSjP-0004sL-IT for submit@debbugs.gnu.org; Thu, 08 Nov 2012 09:05:19 -0500 Received: from ironport2-out.teksavvy.com ([206.248.154.182]:55593) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TWSjN-0004sE-BO for 12796@debbugs.gnu.org; Thu, 08 Nov 2012 09:05:17 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0EAG6Zu0/O+LEi/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLNBIUGA0kiBwFugmQRAOIQppxgViDBw X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206731496" Received: from 206-248-177-34.dsl.teksavvy.com (HELO pastel.home) ([206.248.177.34]) by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA; 08 Nov 2012 09:05:14 -0500 Received: by pastel.home (Postfix, from userid 20848) id 5E92E59780; Thu, 8 Nov 2012 09:05:14 -0500 (EST) From: Stefan Monnier To: Leo Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Message-ID: References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> Date: Thu, 08 Nov 2012 09:05:14 -0500 In-Reply-To: (Leo's message of "Thu, 08 Nov 2012 15:36:23 +0800") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 12796 Cc: Kim Storm , 12796@debbugs.gnu.org, Dmitry Gutov X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -0.5 (/) >>> So do you mind installing the following small change for 24.3 that >>> greatly improves ido performance: >> I guess it's OK, yes. > Can I incorporate your suggestion on removing the backtracking issue? Not for 24.3, no, but on the trunk, of course, yes. > I have found cases where flex matching perform badly but with your > suggestion, for example, cut the time from 4.8s to 0.3s. Cool, Stefan From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 10 12:52:52 2012 Received: (at 12796-done) by debbugs.gnu.org; 10 Nov 2012 17:52:52 +0000 Received: from localhost ([127.0.0.1]:59741 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TXFEh-0003RJ-R4 for submit@debbugs.gnu.org; Sat, 10 Nov 2012 12:52:52 -0500 Received: from mail-la0-f44.google.com ([209.85.215.44]:46399) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TXFEe-0003RA-TQ for 12796-done@debbugs.gnu.org; Sat, 10 Nov 2012 12:52:49 -0500 Received: by mail-la0-f44.google.com with SMTP id d3so10832lah.3 for <12796-done@debbugs.gnu.org>; Sat, 10 Nov 2012 09:52:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=6oIVjOGUziKHtBJetzrKF93f/6WUWB9fBTPWw/2fg6g=; b=HJpwKiiBY+A1NfnW26q9uofkSqRQwdV4tE3F2crsfry/xhDft9TmnT2CwBdoAqVWce 6iaL09gyKUNnerIXyTSc7Rfy0gndNerSYRmwlBkkOSk4x0Lc30tl6c7m2J3cZWdH5MEE T49ZTDKoUU5rWcUT1sJagwv5VKUDMOySKIQ076aXj54eeiU5bnVw/lhJNKPTtm32GOnw UHHHL/swzyrw0Ne8FvZMb1z+KAifYqPR1cfPkUUwRhCSBgdhTGZs1yeo+FE52nLuJjoe 2IneLc953PyWysT7kMOVIo8S+g2yp1esr0uRymaGhF7AgKTRS1tw4MbDp05mFrMU8GYk OAvw== Received: by 10.112.30.227 with SMTP id v3mr5955581lbh.65.1352569953433; Sat, 10 Nov 2012 09:52:33 -0800 (PST) Received: from [192.168.1.2] ([178.252.98.87]) by mx.google.com with ESMTPS id ts2sm674015lab.10.2012.11.10.09.52.31 (version=SSLv3 cipher=OTHER); Sat, 10 Nov 2012 09:52:32 -0800 (PST) Message-ID: <509E945F.6010601@yandex.ru> Date: Sat, 10 Nov 2012 21:52:31 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: 12796-done@debbugs.gnu.org Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796-done Cc: Kim Storm , Stefan Monnier , Leo X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -0.7 (/) With speed-up patches installed on both branches, I consider this fixed. From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 10 17:51:26 2012 Received: (at 12796-done) by debbugs.gnu.org; 10 Nov 2012 22:51:26 +0000 Received: from localhost ([127.0.0.1]:60198 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TXJtd-0002Hv-So for submit@debbugs.gnu.org; Sat, 10 Nov 2012 17:51:26 -0500 Received: from ironport2-out.teksavvy.com ([206.248.154.182]:11300) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TXJtc-0002Hp-GF for 12796-done@debbugs.gnu.org; Sat, 10 Nov 2012 17:51:24 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0EAG6Zu09sr+ZY/2dsb2JhbABEtBGBCIIVAQEEAVYjBQsLDiYSFBgNJIgcBboJkEQDiEKacYFYgwc X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206908677" Received: from 108-175-230-88.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net) ([108.175.230.88]) by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA; 10 Nov 2012 17:51:08 -0500 Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848) id 00369AE4B5; Sat, 10 Nov 2012 17:51:07 -0500 (EST) From: Stefan Monnier To: Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Message-ID: References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> <509E945F.6010601@yandex.ru> Date: Sat, 10 Nov 2012 17:51:07 -0500 In-Reply-To: <509E945F.6010601@yandex.ru> (Dmitry Gutov's message of "Sat, 10 Nov 2012 21:52:31 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.8 (/) X-Debbugs-Envelope-To: 12796-done Cc: Leo , 12796-done@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -0.5 (/) > With speed-up patches installed on both branches, I consider this fixed. No, the use of with-local-quit is the main issue to solve. Stefan From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 10 18:01:35 2012 Received: (at 12796-done) by debbugs.gnu.org; 10 Nov 2012 23:01:35 +0000 Received: from localhost ([127.0.0.1]:60233 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TXK3S-0002XM-PG for submit@debbugs.gnu.org; Sat, 10 Nov 2012 18:01:35 -0500 Received: from mail-lb0-f172.google.com ([209.85.217.172]:42880) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TXK3Q-0002XE-Ln for 12796-done@debbugs.gnu.org; Sat, 10 Nov 2012 18:01:33 -0500 Received: by mail-lb0-f172.google.com with SMTP id y2so624134lbk.3 for <12796-done@debbugs.gnu.org>; Sat, 10 Nov 2012 15:01:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=avieI6OnLPbH30dmCvzOtRDRXJKX6fPNZgUPf5aDOlY=; b=NridZhMW+UUXYTu37JbAzq/7gy/2GiZCuPsxrcOZN9cUWgxPgdIIeI2dvWAaO6oLqn VppQdG5Fj2RJyW+YUKGwVei4MW81/KLG/5tQXRoxSyZb7ltIIHZilPUTdKsxsytoA/Lb GNu0OS6JkWbrbtijZ4UTP1W7Savm+MdjnpwMqokELAtJhg+lbn1eJdtRKKMkpVHDodPA eDWa/qAAHpIiCiLvpe/vDeWm+2w9hV9xD8n7TM20okgt2h9gvZgKXlzJn3wcpdU67cO6 XIna3iDtDj2jqHV2a1PI0bkRfIVgusQTneEtXhk4OoKx4EcUKF/hKn3N13pEKPgZskOm BIJQ== Received: by 10.152.106.212 with SMTP id gw20mr14294738lab.8.1352588474074; Sat, 10 Nov 2012 15:01:14 -0800 (PST) Received: from [192.168.1.2] ([178.252.98.87]) by mx.google.com with ESMTPS id z9sm287339lby.8.2012.11.10.15.01.12 (version=SSLv3 cipher=OTHER); Sat, 10 Nov 2012 15:01:13 -0800 (PST) Message-ID: <509EDCB9.7040103@yandex.ru> Date: Sun, 11 Nov 2012 03:01:13 +0400 From: Dmitry Gutov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 MIME-Version: 1.0 To: Stefan Monnier Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> <509E945F.6010601@yandex.ru> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Debbugs-Envelope-To: 12796-done Cc: Leo , 12796-done@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -0.7 (/) On 11.11.2012 2:51, Stefan Monnier wrote: >> With speed-up patches installed on both branches, I consider this fixed. > > No, the use of with-local-quit is the main issue to solve. Do you mean `when-no-input' and the lack of its use? From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 10 18:31:30 2012 Received: (at 12796-done) by debbugs.gnu.org; 10 Nov 2012 23:31:31 +0000 Received: from localhost ([127.0.0.1]:60286 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TXKWQ-0003E6-O7 for submit@debbugs.gnu.org; Sat, 10 Nov 2012 18:31:30 -0500 Received: from ironport2-out.teksavvy.com ([206.248.154.182]:58331) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TXKWN-0003Dz-Vf for 12796-done@debbugs.gnu.org; Sat, 10 Nov 2012 18:31:28 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0EAG6Zu09sr+ZY/2dsb2JhbABEtBGBCIIVAQEEAVYjEAsOJhIUGA0kiBwFugmQRAOIQppxgViDBw X-IronPort-AV: E=Sophos;i="4.75,637,1330923600"; d="scan'208";a="206909592" Received: from 108-175-230-88.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net) ([108.175.230.88]) by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA; 10 Nov 2012 18:31:11 -0500 Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848) id 6D837AE4B5; Sat, 10 Nov 2012 18:31:11 -0500 (EST) From: Stefan Monnier To: Dmitry Gutov Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled Message-ID: References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> <509E945F.6010601@yandex.ru> <509EDCB9.7040103@yandex.ru> Date: Sat, 10 Nov 2012 18:31:11 -0500 In-Reply-To: <509EDCB9.7040103@yandex.ru> (Dmitry Gutov's message of "Sun, 11 Nov 2012 03:01:13 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.8 (/) X-Debbugs-Envelope-To: 12796-done Cc: Leo , 12796-done@debbugs.gnu.org, Kim Storm X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -0.5 (/) >>> With speed-up patches installed on both branches, I consider this fixed. >> No, the use of with-local-quit is the main issue to solve. > Do you mean `when-no-input' and the lack of its use? Oh, yes, that's what I meant, Stefan From unknown Tue Aug 19 13:27:27 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: Did not alter fixed versions and reopened. Date: Sun, 11 Nov 2012 18:34:02 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # Did not alter fixed versions and reopened. thanks # This fakemail brought to you by your local debbugs # administrator From debbugs-submit-bounces@debbugs.gnu.org Sun Sep 13 12:14:21 2020 Received: (at 12796) by debbugs.gnu.org; 13 Sep 2020 16:14:21 +0000 Received: from localhost ([127.0.0.1]:51449 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kHUdx-0004h3-3j for submit@debbugs.gnu.org; Sun, 13 Sep 2020 12:14:21 -0400 Received: from quimby.gnus.org ([95.216.78.240]:46928) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kHUdu-0004gg-NG; Sun, 13 Sep 2020 12:14:19 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnus.org; s=20200322; h=Content-Type:MIME-Version:Message-ID:In-Reply-To:Date: References:Subject:Cc:To:From:Sender:Reply-To:Content-Transfer-Encoding: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=vN7+x0IMnq+9pq5n4vX8HqJ+7MzkQy7RfNCA+s59Q7Y=; b=RoBe6T7z8+7CNoCkCWYdI1mIoT RB+XMc98DrUFaF19KAMLxVqtnxoTeWUOOVykDdl27Sj/gz6cL0auMbww0qCiKE21B20eNyLwomwim wvw2oFdFwTqPWQvDHLfiR6pPNoOTWSadYWfzsRZbxsqwC2hJhry2f4OxuWFBxm4k6iiw=; Received: from cm-84.212.202.86.getinternet.no ([84.212.202.86] helo=xo) by quimby with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1kHUdk-0004xf-Ec; Sun, 13 Sep 2020 18:14:11 +0200 From: Lars Ingebrigtsen To: Stefan Monnier Subject: Re: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled References: <5096040B.50002@yandex.ru> <50982835.2050106@yandex.ru> <5099DE35.2060402@yandex.ru> <509AD8AB.90703@yandex.ru> <509E945F.6010601@yandex.ru> X-Now-Playing: Machinedrum's _Cached_: "Juggles From The Vault (Juggle Sentence 2)" Date: Sun, 13 Sep 2020 18:14:07 +0200 In-Reply-To: (Stefan Monnier's message of "Sat, 10 Nov 2012 17:51:07 -0500") Message-ID: <877dsxk628.fsf@gnus.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Report: Spam detection software, running on the system "quimby.gnus.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see @@CONTACT_ADDRESS@@ for details. Content preview: Stefan Monnier writes: >> With speed-up patches installed on both branches, I consider this fixed. > > No, the use of with-local-quit is the main issue to solve. Dmitry Gutov writes: Content analysis details: (-2.9 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -1.0 ALL_TRUSTED Passed through trusted hosts only via SMTP -1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1% [score: 0.0000] X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 12796 Cc: 12796-done@debbugs.gnu.org, Kim Storm , Leo , 12796@debbugs.gnu.org, Dmitry Gutov X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Stefan Monnier writes: >> With speed-up patches installed on both branches, I consider this fixed. > > No, the use of with-local-quit is the main issue to solve. Dmitry Gutov writes: > Do you mean `when-no-input' and the lack of its use? Stefan Monnier writes: > Oh, yes, that's what I meant, Or perhaps `while-no-input'? :-) Anyway, reading this bug report, the reported slowness itself was fixed. Stefan wondered why the `while-no-input' thing didn't do the right thing to break out of it all? I think? But as there is no way to reproduce the bug any more, it seems unlikely that we'll make any further progress in this bug report, and I'm re-closing it again. If somebody finds a way to reproduce this (seven years later), please open a new bug report. -- (domestic pets only, the antidote for overdose, milk.) bloggy blog: http://lars.ingebrigtsen.no From debbugs-submit-bounces@debbugs.gnu.org Sun Sep 13 12:14:27 2020 Received: (at control) by debbugs.gnu.org; 13 Sep 2020 16:14:27 +0000 Received: from localhost ([127.0.0.1]:51452 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kHUe3-0004hR-E4 for submit@debbugs.gnu.org; Sun, 13 Sep 2020 12:14:27 -0400 Received: from quimby.gnus.org ([95.216.78.240]:46944) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kHUe2-0004h0-18 for control@debbugs.gnu.org; Sun, 13 Sep 2020 12:14:26 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnus.org; s=20200322; h=Subject:From:To:Message-Id:Date:Sender:Reply-To:Cc: MIME-Version:Content-Type:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=BL+PuK30UUu5IpiKUJvO53PL+JWqKBXwGxENEdJi5Lo=; b=Pdp8p1FdrJw2nhkFHSlTB1HRDF IJliiPNoKe4T9ZdRVUaZQOS9peecE7ILx7+H3LfMamc+5+lhun1/YWhCFJGKqJm5cKnrwSbcfjkI8 L11VV1hDp1+lxlYDTWh40TodtHEAI4WC/ztE4V7SjPJ7dAhuOEnnquBx7ZsP4ruMPDdo=; Received: from cm-84.212.202.86.getinternet.no ([84.212.202.86] helo=xo) by quimby with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1kHUdu-0004xo-9B for control@debbugs.gnu.org; Sun, 13 Sep 2020 18:14:20 +0200 Date: Sun, 13 Sep 2020 18:14:17 +0200 Message-Id: <875z8hk61y.fsf@gnus.org> To: control@debbugs.gnu.org From: Lars Ingebrigtsen Subject: control message for bug #12796 X-Spam-Report: Spam detection software, running on the system "quimby.gnus.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see @@CONTACT_ADDRESS@@ for details. Content preview: close 12796 quit Content analysis details: (-2.9 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -1.0 ALL_TRUSTED Passed through trusted hosts only via SMTP -1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1% [score: 0.0000] X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) close 12796 quit From unknown Tue Aug 19 13:27:27 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Mon, 12 Oct 2020 11:24:12 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator