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.