[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Emacs-diffs] master b0e318d 2/2: Score flex-style completions accor

From: João Távora
Subject: Re: [Emacs-diffs] master b0e318d 2/2: Score flex-style completions according to match tightness
Date: Wed, 20 Mar 2019 23:25:08 +0000

[Again, sorry for the double email Dmitry]

On Wed, Mar 20, 2019 at 9:58 PM Dmitry Gutov <address@hidden> wrote:
On 20.03.2019 23:00, João Távora wrote:
> but I do think that flex can be
> made faster so that it is only, say 1.2x, slower than basic in the worst
> case

When collection contains very long strings (e.g. a list of project files
with VCR cassettes, if you know what I mean), flex can unavoidably
become noticeably slower.

Yes, but we've established that it's 2x slower than "basic" in the
worse cases of flex, at least for the collection in Emacs's
obarray, which is a nice benchmark:

(benchmark-run-compiled 5
  (let ((completion-styles '(flex)))
    (completion-all-completions "" obarray nil 0))); (6.105048999999999 15 3.9362529999999936)

(benchmark-run-compiled 5
  (let ((completion-styles '(basic)))
    (completion-all-completions "" obarray nil 0))); (3.322738 10 2.0635609999999787)

So it doesn't seem like an impossible task to make it as fast as "basic"
is now, especially for these cases of short input strings. For example, since

(equal (let ((completion-styles '(flex)))
         (completion-all-completions "" obarray nil 0))
       (let ((completion-styles '(basic)))
         (completion-all-completions "" obarray nil 0)))

is t, the null-string case, which is probably trivial to optimize ;-), would
bring a noticeable improvement to icomplete's UI, and probably

Of course for pathological (but reasonable) input, it will often
be much much slower, because by nature flex matches much
more candidates and manages around much more data.

(benchmark-run-compiled 5
  (let ((completion-styles '(flex)))
    (completion-all-completions "eeee" obarray nil 0))); (2.068143 5 1.151679999999999)

(benchmark-run-compiled 5
  (let ((completion-styles '(basic)))
    (completion-all-completions "eeee" obarray nil 0))); (0.333021 0 0.0)

(benchmark-run-compiled 5
  (let ((completion-styles '(flex)))
    (completion-all-completions "kill" obarray nil 0))); (0.7081639999999999 1 0.26370900000000574)

(benchmark-run-compiled 5
  (let ((completion-styles '(basic)))
    (completion-all-completions "kill" obarray nil 0))); (0.444207 0 0.0)

So while the slowdown due to a larger amount of candidates is something
we probably won't get around easily, a significant part of the slowdown
seems to be the matching logic, and that can probably be optimized,
with nice user-visible consequences.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]