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

[Dmitry Gutov <dgutov@yandex.ru>]

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