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