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

[João Távora]

[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

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