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

Previous Next

Full log

View this message in rfc822 format

From: Dmitry Gutov <dgutov <at> yandex.ru>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Leo <sdl.web <at> gmail.com>, 12796 <at> debbugs.gnu.org, Kim Storm <storm <at> cua.dk>
Subject: bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled
Date: Thu, 08 Nov 2012 08:29:19 +0400

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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.