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

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

[Dmitry Gutov]

[-- Attachment #1: Type: text/plain, Size: 925 bytes --]

Tags: patch

Currently ido re-filters the full candidates list after every change in 
the minibuffer. With long candidates list and with flex matching enabled 
(like it's often the case with certain third-party packages, namely smex 
and ido-ubiquitous), as soon as ido switches to using flex matching, 
each update takes a noticeable fraction of a second. Even if there's no 
matches anymore for the current input.

If I decide to type quickly but make a typo in one of the first 
characters, I often need to wait a few seconds until I can fix the typo 
or start anew.

This patch adds a simple cache that keeps track of the current matching 
settings (prefix, regexp, or no), and checks the input against a 
previously entered string. If the latter is a prefix of the former (and 
regexp matching is disabled), then we can use the matches from the 
former input as the candidates list for the current one.

Any objections?

[-- Attachment #2: ido-speed.diff --]
[-- Type: text/plain, Size: 5295 bytes --]

=== modified file 'lisp/ChangeLog'
--- lisp/ChangeLog	2012-10-29 15:14:10 +0000
+++ lisp/ChangeLog	2012-11-04 04:55:08 +0000
@@ -1,3 +1,15 @@
+2012-11-04  Dmitry Gutov  <dgutov@yandex.ru>
+
+	* ido.el (ido-cache-prefix, ido-cache-matches, ido-cache-params):
+	New dynamic vars.
+	(ido-read-internal): Reset the above variables' values.
+	(ido-set-matches): Don't reverse the candidates list, leave it to
+	`ido-set-matches-1'.
+	(ido-use-matches-from-cache, ido-check-cache-params)
+	(ido-update-cache): New functions.
+	(ido-set-matches-1): Use the new functions; reverse the matches
+	list at the very end.
+
 2012-10-29  Stefan Monnier  <monnier@iro.umontreal.ca>
 
 	* vc/diff-mode.el (diff-context->unified): Don't get confused by "hunk

=== modified file 'lisp/ido.el'
--- lisp/ido.el	2012-10-05 07:38:05 +0000
+++ lisp/ido.el	2012-11-04 05:12:07 +0000
@@ -1143,6 +1143,11 @@
 ;; Dynamically bound in ido-read-internal.
 (defvar ido-completing-read)
 
+;; Matches cache data, only used when `ido-cur-item' is `list'.
+(defvar ido-cache-prefix)
+(defvar ido-cache-matches)
+(defvar ido-cache-params)
+
 ;;; FUNCTIONS
 
 (defun ido-active (&optional merge)
@@ -1852,6 +1857,9 @@
        ido-default-item
        ido-selected
        ido-final-text
+       ido-cache-prefix
+       ido-cache-matches
+       ido-cache-params
        (done nil)
        (icomplete-mode nil) ;; prevent icomplete starting up
        ;; Exported dynamic variables:
@@ -3692,7 +3700,7 @@
 
 ;;; FIND MATCHING ITEMS
 
-(defun ido-set-matches-1 (items &optional do-full)
+(defun ido-set-matches-1 (all-items &optional do-full)
   ;; Return list of matches in items
   (let* ((case-fold-search  ido-case-fold)
 	 (slash (and (not ido-enable-prefix) (ido-final-slash ido-text)))
@@ -3718,7 +3726,10 @@
 			     (not ido-process-ignore-lists)
 			     ido-enable-prefix
 			     (= (length ido-text) 0)))
-	 full-matches suffix-matches prefix-matches matches)
+         (items (if (ido-use-matches-from-cache)
+                    ido-cache-matches
+                  all-items))
+	 full-matches suffix-matches prefix-matches matches used-flex)
     (setq ido-incomplete-regexp nil)
     (condition-case error
         (mapc
@@ -3753,18 +3764,19 @@
     (when prefix-matches
       (ido-trace "prefix match" prefix-matches)
       ;; Bug#2042.
-      (setq matches (nconc prefix-matches matches)))
+      (setq matches (nconc matches prefix-matches)))
     (when suffix-matches
       (ido-trace "suffix match" (list text suffix-re suffix-matches))
-      (setq matches (nconc suffix-matches matches)))
+      (setq matches (nconc matches suffix-matches)))
     (when full-matches
       (ido-trace "full match" (list text full-re full-matches))
-      (setq matches (nconc full-matches matches)))
+      (setq matches (nconc matches full-matches)))
     (when (and (null matches)
 	       ido-enable-flex-matching
 	       (> (length ido-text) 1)
 	       (not ido-enable-regexp))
-      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*"))
+      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*")
+            used-flex t)
       (if ido-enable-prefix
 	  (setq re (concat "\\`" re)))
       (mapc
@@ -3772,16 +3784,51 @@
 	 (let ((name (ido-name item)))
 	   (if (string-match re name)
 	       (setq matches (cons item matches)))))
-       items))
+       (if (ido-check-cache-params t)
+           items
+         all-items)))
+    (setq matches (reverse matches))
+    (ido-update-cache matches used-flex)
     matches))
 
-
 (defun ido-set-matches ()
   ;; Set `ido-matches' to the list of items matching prompt
   (when ido-rescan
-    (setq ido-matches (ido-set-matches-1 (reverse ido-cur-list) (not ido-rotate))
+    (setq ido-matches (ido-set-matches-1 ido-cur-list (not ido-rotate))
 	  ido-rotate nil)))
 
+(defun ido-use-matches-from-cache ()
+  "Return t if `ido-set-matches-1' can use `ido-cache-matches'."
+  (and ido-cache-prefix (eq ido-cur-item 'list)
+       (not ido-enable-regexp)
+       (ido-check-cache-params)
+       (>= (length ido-text) (length ido-cache-prefix))
+       (string= ido-cache-prefix
+                (substring ido-text 0 (length ido-cache-prefix)))))
+
+(defun ido-check-cache-params (&optional flex)
+  "Check `ido-cache-params' against current parameters."
+  (let ((params ido-cache-params))
+    (if (and (or (not (plist-get params 'prefix)) ido-enable-prefix)
+             (or (plist-get params 'flex) (not flex)))
+        t
+      (setq ido-cache-prefix nil
+            ido-cache-matches nil))))
+
+(defun ido-update-cache (matches flex)
+  "Update values of `ido-cache-*' variables."
+  (when (and (or matches
+                 (zerop (length ido-cache-prefix)))
+             (eq ido-cur-item 'list)
+             (not ido-enable-regexp)
+             (<= (* 10 (length matches)) (length ido-cur-list)))
+    (setq ido-cache-prefix ido-text
+          ido-cache-matches matches)
+    (setq ido-cache-params
+          (plist-put (plist-put ido-cache-params
+                                'prefix ido-enable-prefix)
+                     'flex flex))))
+
 (defun ido-ignore-item-p (name re-list &optional ignore-ext)
   ;; Return t if the buffer or file NAME should be ignored.
   (or (member name ido-ignore-item-temp-list)

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

[Leo]

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

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

[Stefan Monnier]

> 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

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

[Dmitry Gutov]

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.

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

[Dmitry Gutov]

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

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

[Stefan Monnier]

[ 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

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

[Kim Storm]

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

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

[Dmitry Gutov]

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?

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

[Kim Storm]

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

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

[Dmitry Gutov]

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)

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

[Dmitry Gutov]

Leo <sdl.web@gmail.com> 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.

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

[Leo]

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

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

[Dmitry Gutov]

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.

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

[Leo]

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

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

[Dmitry Gutov]

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

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

[Leo]

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

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

[Stefan Monnier]

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

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

[Leo]

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

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

[Stefan Monnier]

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

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

[Dmitry Gutov]

With speed-up patches installed on both branches, I consider this fixed.

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

[Stefan Monnier]

> 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

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

[Dmitry Gutov]

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?

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

[Stefan Monnier]

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

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

[Lars Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> 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 <dgutov@yandex.ru> writes:

> Do you mean `when-no-input' and the lack of its use?

Stefan Monnier <monnier@iro.umontreal.ca> 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

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

[Stefan Monnier]

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

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

[Dmitry Gutov]

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.