Re: [Emacs-diffs] master b0e318d 2/2: Score flex-style completions according to match tightness

["João Távora" <joaotavora@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2528 bytes --]

[Again, sorry for the double email Dmitry]

On Wed, Mar 20, 2019 at 9:58 PM Dmitry Gutov <dgutov@yandex.ru> 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
company's.

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.
João

[-- Attachment #2: Type: text/html, Size: 3957 bytes --]