Re: master e4896fc 1/2: Add a new 'flex' completion style

Re: master e4896fc 1/2: Add a new 'flex' completion style

[Robert Pluim]

Unknown <unknown@unknown.invalid> writes:

> diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
> index b757eb8..c1e3fdc 100644
> --- a/lisp/minibuffer.el
> +++ b/lisp/minibuffer.el
> @@ -788,6 +788,11 @@ Additionally the user can use the char \"*\" as a glob pattern.")
>  I.e. when completing \"foo_bar\" (where _ is the position of point),
>  it will consider all completions candidates matching the glob
>  pattern \"*foo*bar*\".")
> +    (flex
> +     completion-flex-try-completion completion-flex-all-completions
> +     "Completion of an in-order subset of characters.
> +When completing \"foo\" the glob \"*f*o*o*\" is used, so that
> +i.e. foo can complete to frodo.")

I think you can either drop the 'i.e.', or drop 'so that'.

>      (initials
>       completion-initials-try-completion completion-initials-all-completions
>       "Completion of acronyms and initialisms.
> @@ -3345,7 +3350,12 @@ the same set of elements."
>  ;;; Substring completion
>  ;; Mostly derived from the code of `basic' completion.
>  
> -(defun completion-substring--all-completions (string table pred point)
> +(defun completion-substring--all-completions
> +    (string table pred point &optional transform-pattern-fn)
> +  "Match the presumed substring STRING to the entries in TABLE.
> +Respect PRED and POINT.  The pattern used is a PCM-style
> +substring pattern, but it be massaged by TRANSFORM-PATTERN-FN, if
> +that is non-nil."

Iʼm all in favour of respect, but what does that mean in the context
of PRED and POINT?

What is 'PCM-style'? What does 'massaged' mean? What is the signature of
TRANSFORM-PATTERN-FN?

Robert

Re: master e4896fc 1/2: Add a new 'flex' completion style

[João Távora]

On Thu, Feb 14, 2019 at 12:38 PM Robert Pluim <rpluim@gmail.com> wrote:
>
> Unknown <unknown@unknown.invalid> writes:
>
> > diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
> > index b757eb8..c1e3fdc 100644
> > --- a/lisp/minibuffer.el
> > +++ b/lisp/minibuffer.el
> > @@ -788,6 +788,11 @@ Additionally the user can use the char \"*\" as a glob pattern.")
> >  I.e. when completing \"foo_bar\" (where _ is the position of point),
> >  it will consider all completions candidates matching the glob
> >  pattern \"*foo*bar*\".")
> > +    (flex
> > +     completion-flex-try-completion completion-flex-all-completions
> > +     "Completion of an in-order subset of characters.
> > +When completing \"foo\" the glob \"*f*o*o*\" is used, so that
> > +i.e. foo can complete to frodo.")
>
> I think you can either drop the 'i.e.', or drop 'so that'.

I see it's horrible style, but doesn't seem grammatically wrong.
I fixed it and added quotes to foo and frodo.

> >      (initials
> >       completion-initials-try-completion completion-initials-all-completions
> >       "Completion of acronyms and initialisms.
> > @@ -3345,7 +3350,12 @@ the same set of elements."
> >  ;;; Substring completion
> >  ;; Mostly derived from the code of `basic' completion.
> >
> > -(defun completion-substring--all-completions (string table pred point)
> > +(defun completion-substring--all-completions
> > +    (string table pred point &optional transform-pattern-fn)
> > +  "Match the presumed substring STRING to the entries in TABLE.
> > +Respect PRED and POINT.  The pattern used is a PCM-style
> > +substring pattern, but it be massaged by TRANSFORM-PATTERN-FN, if
> > +that is non-nil."
>
> Iʼm all in favour of respect, but what does that mean in the context
> of PRED and POINT?

It means M-x checkdoc shuts up about it, that's what it means :-)
(or rather flymake's checkdoc backend stops underlining it).

It also means I'll think twice about adding docstrings to functions
I modify, even internal functions.

> What is 'PCM-style'? What does 'massaged' mean? What is the signature of
> TRANSFORM-PATTERN-FN?

"It be" take a pattern, and it be return a pattern.

To be clear, I agree this isn't the best docstring in the world. Is it
better than what was before, which was nothing?  Perhaps that's
arguable and I shouldn't have added it in the first place, forcing
err inviting people like me to go read the source code.  Doing
a good docstring is hard and I usually reserve those efforts for
user-visible functions. You could have very well asked me
what exactly a "PCM-style substring pattern" is, since that's
just as loosely defined as everything else around those
parts.

-- 
João Távora

Re: master e4896fc 1/2: Add a new 'flex' completion style

[Eli Zaretskii]

> From: Robert Pluim <rpluim@gmail.com>
> Date: Thu, 14 Feb 2019 13:38:50 +0100
> Cc: João Távora <joaotavora@gmail.com>
> 
> > +    (flex
> > +     completion-flex-try-completion completion-flex-all-completions
> > +     "Completion of an in-order subset of characters.
> > +When completing \"foo\" the glob \"*f*o*o*\" is used, so that
> > +i.e. foo can complete to frodo.")
> 
> I think you can either drop the 'i.e.', or drop 'so that'.

I think João wanted to say "e.g.", not "i.e.".

Re: master e4896fc 1/2: Add a new 'flex' completion style

[Eli Zaretskii]

> From: João Távora <joaotavora@gmail.com>
> Date: Thu, 14 Feb 2019 13:50:15 +0000
> Cc: emacs-devel <emacs-devel@gnu.org>
> 
> > Iʼm all in favour of respect, but what does that mean in the context
> > of PRED and POINT?
> 
> It means M-x checkdoc shuts up about it, that's what it means :-)
> (or rather flymake's checkdoc backend stops underlining it).
> 
> It also means I'll think twice about adding docstrings to functions
> I modify, even internal functions.
> 
> > What is 'PCM-style'? What does 'massaged' mean? What is the signature of
> > TRANSFORM-PATTERN-FN?
> 
> "It be" take a pattern, and it be return a pattern.
> 
> To be clear, I agree this isn't the best docstring in the world. Is it
> better than what was before, which was nothing?  Perhaps that's
> arguable and I shouldn't have added it in the first place, forcing
> err inviting people like me to go read the source code.  Doing
> a good docstring is hard and I usually reserve those efforts for
> user-visible functions. You could have very well asked me
> what exactly a "PCM-style substring pattern" is, since that's
> just as loosely defined as everything else around those
> parts.

There's no reason to feel offended by Robert's comments.  They mean
well: to make our doc strings better.  They don't mean your change
wasn't an improvement, and surely weren't meant to offend you.

Thanks for making those changes.

Re: master e4896fc 1/2: Add a new 'flex' completion style

[João Távora]

On Thu, Feb 14, 2019 at 2:29 PM Eli Zaretskii <eliz@gnu.org> wrote:
>
> > From: Robert Pluim <rpluim@gmail.com>
> > Date: Thu, 14 Feb 2019 13:38:50 +0100
> > Cc: João Távora <joaotavora@gmail.com>
> >
> > > +    (flex
> > > +     completion-flex-try-completion completion-flex-all-completions
> > > +     "Completion of an in-order subset of characters.
> > > +When completing \"foo\" the glob \"*f*o*o*\" is used, so that
> > > +i.e. foo can complete to frodo.")
> >
> > I think you can either drop the 'i.e.', or drop 'so that'.
>
> I think João wanted to say "e.g.", not "i.e.".

Oh yeah, that was it. But Robert's suggestion applied
anyway.

João

Re: master e4896fc 1/2: Add a new 'flex' completion style

[João Távora]

On Thu, Feb 14, 2019 at 2:37 PM Eli Zaretskii <eliz@gnu.org> wrote:
>
> > From: João Távora <joaotavora@gmail.com>
> > Date: Thu, 14 Feb 2019 13:50:15 +0000
> > Cc: emacs-devel <emacs-devel@gnu.org>
> >
> > > Iʼm all in favour of respect, but what does that mean in the context
> > > of PRED and POINT?
> >
> > It means M-x checkdoc shuts up about it, that's what it means :-)
> > (or rather flymake's checkdoc backend stops underlining it).
> >
> > It also means I'll think twice about adding docstrings to functions
> > I modify, even internal functions.
> >
> > > What is 'PCM-style'? What does 'massaged' mean? What is the signature of
> > > TRANSFORM-PATTERN-FN?
> >
> > "It be" take a pattern, and it be return a pattern.
> >
> > To be clear, I agree this isn't the best docstring in the world. Is it
> > better than what was before, which was nothing?  Perhaps that's
> > arguable and I shouldn't have added it in the first place, forcing
> > err inviting people like me to go read the source code.  Doing
> > a good docstring is hard and I usually reserve those efforts for
> > user-visible functions. You could have very well asked me
> > what exactly a "PCM-style substring pattern" is, since that's
> > just as loosely defined as everything else around those
> > parts.
>
> There's no reason to feel offended by Robert's comments.  They mean
> well: to make our doc strings better.  They don't mean your change
> wasn't an improvement, and surely weren't meant to offend you.
>
> Thanks for making those changes.

Sorry, I didn't _feel_ offended.  Sorry if I _sounded_ offended
and/or aggressive.

Thanks Robert :-)

Re: master e4896fc 1/2: Add a new 'flex' completion style

[Robert Pluim]

João Távora <joaotavora@gmail.com> writes:

>> >      (initials
>> >       completion-initials-try-completion completion-initials-all-completions
>> >       "Completion of acronyms and initialisms.
>> > @@ -3345,7 +3350,12 @@ the same set of elements."
>> >  ;;; Substring completion
>> >  ;; Mostly derived from the code of `basic' completion.
>> >
>> > -(defun completion-substring--all-completions (string table pred point)
>> > +(defun completion-substring--all-completions
>> > +    (string table pred point &optional transform-pattern-fn)
>> > +  "Match the presumed substring STRING to the entries in TABLE.
>> > +Respect PRED and POINT.  The pattern used is a PCM-style
>> > +substring pattern, but it be massaged by TRANSFORM-PATTERN-FN, if
>> > +that is non-nil."
>>
>> Iʼm all in favour of respect, but what does that mean in the context
>> of PRED and POINT?
>
> It means M-x checkdoc shuts up about it, that's what it means :-)
> (or rather flymake's checkdoc backend stops underlining it).
>
> It also means I'll think twice about adding docstrings to functions
> I modify, even internal functions.
>
>> What is 'PCM-style'? What does 'massaged' mean? What is the signature of
>> TRANSFORM-PATTERN-FN?
>
> "It be" take a pattern, and it be return a pattern.
>
> To be clear, I agree this isn't the best docstring in the world. Is it
> better than what was before, which was nothing?  Perhaps that's
> arguable and I shouldn't have added it in the first place, forcing
> err inviting people like me to go read the source code.  Doing
> a good docstring is hard and I usually reserve those efforts for
> user-visible functions. You could have very well asked me
> what exactly a "PCM-style substring pattern" is, since that's
> just as loosely defined as everything else around those
> parts.

Doing good docstrings is hard, which is why there will always be
comments on them. Such comments are exactly that: comments, not
criticism.

Thank you for the changes in any case.

Robert

Re: master e4896fc 1/2: Add a new 'flex' completion style

[João Távora]

On Thu, Feb 14, 2019 at 2:47 PM Robert Pluim <rpluim@gmail.com> wrote:

> > To be clear, I agree this isn't the best docstring in the world. Is it
> > better than what was before, which was nothing?  Perhaps that's
> > arguable and I shouldn't have added it in the first place, forcing
> > err inviting people like me to go read the source code.  Doing
> > a good docstring is hard and I usually reserve those efforts for
> > user-visible functions. You could have very well asked me
> > what exactly a "PCM-style substring pattern" is, since that's
> > just as loosely defined as everything else around those
> > parts.
>
> Doing good docstrings is hard, which is why there will always be
> comments on them. Such comments are exactly that: comments, not
> criticism.

I apologize for that paragraph which reads harsher than it means.

I was also trying to get your opinion on what is better: writing a
subpar docstring for an internal function, or keeping it undocumented.

João

Re: master e4896fc 1/2: Add a new 'flex' completion style

[Robert Pluim]

João Távora <joaotavora@gmail.com> writes:

> On Thu, Feb 14, 2019 at 2:47 PM Robert Pluim <rpluim@gmail.com> wrote:
>
>> > To be clear, I agree this isn't the best docstring in the world. Is it
>> > better than what was before, which was nothing?  Perhaps that's
>> > arguable and I shouldn't have added it in the first place, forcing
>> > err inviting people like me to go read the source code.  Doing
>> > a good docstring is hard and I usually reserve those efforts for
>> > user-visible functions. You could have very well asked me
>> > what exactly a "PCM-style substring pattern" is, since that's
>> > just as loosely defined as everything else around those
>> > parts.
>>
>> Doing good docstrings is hard, which is why there will always be
>> comments on them. Such comments are exactly that: comments, not
>> criticism.
>
> I apologize for that paragraph which reads harsher than it means.

No worries: offense can only be taken, never given.

> I was also trying to get your opinion on what is better: writing a
> subpar docstring for an internal function, or keeping it undocumented.

'Incomplete', rather than 'subpar', I think. If a user is likely to
want to call that function directly, then I feel it should have a
docstring. If itʼs purely internal, then itʼs not
necessary. Distinguishing the two cases is hard.

Robert

RE: master e4896fc 1/2: Add a new 'flex' completion style

[Drew Adams]

> what is better: writing a subpar docstring for an
> internal function, or keeping it undocumented.

That depends on what makes it subpar.

A subpar doc string can be so just because it is slightly
incomplete or slightly incorrect or misleading.  In this
case it might well be better than no doc string.

But a subpar doc string can also be so because it gives
a very wrong idea of what the object is/does.  In this
case it might be worse than no doc string.

This should be obvious.  The devil is in the details.

In general, we should have doc strings - including for
"internal" functions (IMHO).  But the doc strings should
be accurate and helpful, not inaccurate or harmful.

(Not saying anything about the doc strings mentioned
in this thread.  Just responding to your wish for a
too-general rule/judgment as to which is better: bad
or none.)

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

[Dmitry Gutov]

Hi Joao,

Now that I've been seeing company-capf test failures mentioning 
completion-score for a while (e.g. see 
https://travis-ci.org/company-mode/company-mode/jobs/507061364), I 
really have to ask:

Why does a completion-pcm--??? function add the scores? And even does 
that unconditionally, and depends on the value of a flex-related 
variable. While the flex style isn't even used.

On 13.02.2019 23:24, Jo�o T�vora wrote:
> branch: master
> commit b0e318d27f10b820f1cfad6ea98793c11fc782a4
> Author: João Távora <joaotavora@gmail.com>
> Commit: João Távora <joaotavora@gmail.com>
> 
>      Score flex-style completions according to match tightness
>      
>      The new completion style needs to score completion matches so that we
>      can use it later on when sorting the completions.  This is because
>      "foo" can flex-match "foobar", "frodo" and "barfromsober" but we
>      probably want "foobar" to appear at the top of the completion list.
>      
>      This change introduces a scoring formula and adds scoring hints in the
>      candidate string's `completion-score' property.
>      
>      * lisp/minibuffer.el (completion-pcm--hilit-commonality): Propertize
>      completion with 'completion-score
>      (flex-score-falloff): New variable.

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

[João Távora]

On Sat, Mar 16, 2019 at 1:13 AM Dmitry Gutov <dgutov@yandex.ru> wrote:
>
> Hi Joao,
>
> Now that I've been seeing company-capf test failures mentioning
> completion-score for a while (e.g. see
> https://travis-ci.org/company-mode/company-mode/jobs/507061364),

I didn't read the test fully, but it seems you (or I? did I write it?)
are asserting
that there can only be a specific set of properties in the completion candidate.
This is wrong: there can be more unrelated to your package's use of those
candidate's properties, completion-score being one of them.

Though I do think `company.el` should start making use of
`completion-score` somehow.

> Why does a completion-pcm--??? function add the scores?

It adds them in the hope that they would be useful in the near future.
When I added this bit, I thought it would be a matter of days until we
found a suitable place for a sorting function to use those properties.
But it's been two months and a decision hasn't yet been reached.
So  there are currently no users of that functionality, and it
could very well be removed.  I put it in a separate commit so it could just
be "git revert"ed.  But since it is master, I encourage you to not
do it and find a solution that uses the scoring.

Regardless of the decision of where to put sorting function based
on flex scores, completion-pcm--... is a most suitable place to add the
scoring, since this is where the string is propertized (and the scoring
is closely related to that.

So my suggestion would be to fix the test in company not to make
those unreasonable assumptions and invest some effort in reaching
a consensus for where to associate flex's sorting function. (I suggested
earlier in the completion style, but I haven't followed the discussion
in-depth).

-- 
João Távora

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

[Stefan Monnier]

> It adds them in the hope that they would be useful in the near future.
> When I added this bit, I thought it would be a matter of days until we
> found a suitable place for a sorting function to use those properties.
> But it's been two months and a decision hasn't yet been reached.

Actually, I think we did reach a consensus, but I haven't gotten to
writing the code yet.

> So  there are currently no users of that functionality, and it
> could very well be removed.

Please leave it in.

> Regardless of the decision of where to put sorting function based
> on flex scores, completion-pcm--... is a most suitable place to add the
> scoring, since this is where the string is propertized (and the scoring
> is closely related to that.

Also, I think the scoring would be valuable for `partial-completion` and
`initialism` styles as well (i.e. for all users of PCM).


        Stefan

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

[João Távora]

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

On Sat, Mar 16, 2019, 13:35 Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> > Regardless of the decision of where to put sorting function based
> > on flex scores, completion-pcm--... is a most suitable place to add the
> > scoring, since this is where the string is propertized (and the scoring
> > is closely related to that.
>
> Also, I think the scoring would be valuable for `partial-completion` and
> `initialism` styles as well (i.e. for all users of PCM).
>

Yes, I forgot to mention before that I think so too.

João

>

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

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

[Dmitry Gutov]

On 16.03.2019 15:02, João Távora wrote:

> I didn't read the test fully, but it seems you (or I? did I write it?)
> are asserting
> that there can only be a specific set of properties in the completion candidate.
> This is wrong: there can be more unrelated to your package's use of those
> candidate's properties, completion-score being one of them.

You did, but that's neither here not there. A fix PR would be welcome, 
but I'll get around to it otherwise myself, no problem.

> Though I do think `company.el` should start making use of
> `completion-score` somehow.

Sure. But either completion-all-completions starts doing that 
automatically, or we'll need the new variable to appear in the core first.

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

[Dmitry Gutov]

On 16.03.2019 15:19, Stefan Monnier wrote:
>> It adds them in the hope that they would be useful in the near future.
>> When I added this bit, I thought it would be a matter of days until we
>> found a suitable place for a sorting function to use those properties.
>> But it's been two months and a decision hasn't yet been reached.
> 
> Actually, I think we did reach a consensus, but I haven't gotten to
> writing the code yet.

Agreed.

>> Regardless of the decision of where to put sorting function based
>> on flex scores, completion-pcm--... is a most suitable place to add the
>> scoring, since this is where the string is propertized (and the scoring
>> is closely related to that.
> 
> Also, I think the scoring would be valuable for `partial-completion` and
> `initialism` styles as well (i.e. for all users of PCM).
Shouldn't flex-score-match-tightness be renamed, then? So it doesn't 
leave an impression of being specific to just one completion style.

The first line of its docstring also seems misleading.

Further, purely theoretically, I'm a bit concerned that if we include 
scoring at this level, in the common function, it would be harder to 
tweak for each individual completion style. But that can be changed 
later if we so choose, of course.

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

[João Távora]

On Sun, Mar 17, 2019 at 5:51 PM Dmitry Gutov <dgutov@yandex.ru> wrote:
>
> On 16.03.2019 15:02, João Távora wrote:
> You did, but that's neither here not there. A fix PR would be welcome,
> but I'll get around to it otherwise myself, no problem.

I sent you a PR that should fix it.

> > Though I do think `company.el` should start making use of
> > `completion-score` somehow.
> Sure. But either completion-all-completions starts doing that
> automatically, or we'll need the new variable to appear in the core first.

That would be nice, of course, but it's not strictly required to
start making use of it in company.el: you can look for it and act
accordingly when it's found.

-- 
João Távora

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

[João Távora]

On Sun, Mar 17, 2019 at 6:07 PM Dmitry Gutov <dgutov@yandex.ru> wrote:
> > Also, I think the scoring would be valuable for `partial-completion` and
> > `initialism` styles as well (i.e. for all users of PCM).
> Shouldn't flex-score-match-tightness be renamed, then? So it doesn't
> leave an impression of being specific to just one completion style.
>
> The first line of its docstring also seems misleading.

Re the docstring, you must be refering to the "flex" mention there,
because "Controls how the style scores its matches" is pretty much
what the variable does (and all that can be crammed in columns).

As I said, when I added this, it was largely open to debate where
scoring would be plugged in.  At that point I thought the style,
particularly the flex style, would be the right spot, but the debate
evolved.  Regardless of making this more general, the flex style
still is the spot where such scoring is needed most urgently, and
I think we should keep it there for a while.

> Further, purely theoretically, I'm a bit concerned that if we include
> scoring at this level, in the common function, it would be harder to
> tweak for each individual completion style. But that can be changed
> later if we so choose, of course.

A handful of us should eventually start using it first before engaging
in such microtweaks.  I'm more wary of the performance hit that
flex-matching introduces (the matching, not the scoring).  I wonder
if ditching pcm's regexp based approach and coding something by
hand (perhaps in C) would be faster.  I haven't done any
measurements but the thing feels slow to me: so I wish more
people could experiment with it (and with company, too)

João

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

[Dmitry Gutov]

On 17.03.2019 21:09, João Távora wrote:

>> You did, but that's neither here not there. A fix PR would be welcome,
>> but I'll get around to it otherwise myself, no problem.
> 
> I sent you a PR that should fix it.

Thanks!

> That would be nice, of course, but it's not strictly required to
> start making use of it in company.el: you can look for it and act
> accordingly when it's found.

The sorting function to use should come from somewhere, right?

But if you just want to try and see how well the sorting works, you can 
add one to `company-transformers`.

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

[Dmitry Gutov]

On 17.03.2019 21:22, João Távora wrote:

>> The first line of its docstring also seems misleading.
> 
> Re the docstring, you must be refering to the "flex" mention there,
> because "Controls how the style scores its matches" is pretty much
> what the variable does (and all that can be crammed in columns).

Yes, and the flex in its name.

> As I said, when I added this, it was largely open to debate where
> scoring would be plugged in.  At that point I thought the style,
> particularly the flex style, would be the right spot, but the debate
> evolved.  Regardless of making this more general, the flex style
> still is the spot where such scoring is needed most urgently, and
> I think we should keep it there for a while.

Err, I hope that changes before the release, though.

I like for it to be clear what is affected by a variable, and what does 
not. Both from its name and its docstring.

>> Further, purely theoretically, I'm a bit concerned that if we include
>> scoring at this level, in the common function, it would be harder to
>> tweak for each individual completion style. But that can be changed
>> later if we so choose, of course.
> 
> A handful of us should eventually start using it first before engaging
> in such microtweaks.  I'm more wary of the performance hit that
> flex-matching introduces (the matching, not the scoring).

"Slow" had been my impression with flx (the third-party package), but 
didn't it come from scoring rather than matching?

As long as we're using the same approach for constructing the matching
regexp as ido-flex does, speed should be okay for most uses.

Another thing I'd like to note: with flex completion, RET doesn't select 
the current candidate anymore (working as intended, of course). But it's 
a bit disorienting.

> I wonder
> if ditching pcm's regexp based approach and coding something by
> hand (perhaps in C) would be faster.  I haven't done any
> measurements but the thing feels slow to me: so I wish more
> people could experiment with it (and with company, too)

...although it does feel a bit slower than the prefix matching. Maybe 
that's just to be expected.

I'm all for targeted speed optimizations, of course.

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

[João Távora]

[sorry for the double mail Dmitry]

On Sun, Mar 17, 2019 at 8:22 PM Dmitry Gutov <dgutov@yandex.ru> wrote:
>
> On 17.03.2019 21:09, João Távora wrote:
>
> >> You did, but that's neither here not there. A fix PR would be welcome,
> >> but I'll get around to it otherwise myself, no problem.
> >
> > I sent you a PR that should fix it.
>
> Thanks!
>
> > That would be nice, of course, but it's not strictly required to
> > start making use of it in company.el: you can look for it and act
> > accordingly when it's found.
>
> The sorting function to use should come from somewhere, right?

Yes, in this case it would come from company. I was thinking you
could sort by `completion-score` in descending order.

> But if you just want to try and see how well the sorting works, you can
> add one to `company-transformers`.

Thanks, I added

(defun sort-by-company-score (cands)
  (cl-sort cands
           #'>
           :key (lambda (cand) (or (get-text-property 0
'completion-score cand) 0)))

(add-to-list 'company-transformers 'sort-by-company-score)

And it behaves much better.  My idea is that something like this could be
be built-in into company (after the lexicographical sort).

João

On Sun, Mar 17, 2019 at 8:22 PM Dmitry Gutov <dgutov@yandex.ru> wrote:
>
> On 17.03.2019 21:09, João Távora wrote:
>
> >> You did, but that's neither here not there. A fix PR would be welcome,
> >> but I'll get around to it otherwise myself, no problem.
> >
> > I sent you a PR that should fix it.
>
> Thanks!
>
> > That would be nice, of course, but it's not strictly required to
> > start making use of it in company.el: you can look for it and act
> > accordingly when it's found.
>
> The sorting function to use should come from somewhere, right?
>
> But if you just want to try and see how well the sorting works, you can
> add one to `company-transformers`.



-- 
João Távora

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

[João Távora]

On Sun, Mar 17, 2019 at 8:32 PM Dmitry Gutov <dgutov@yandex.ru> wrote:
> I like for it to be clear what is affected by a variable, and what does
> not. Both from its name and its docstring.

Well, for now _nothing_ is affected by that variable. Let's change the
name when that changes.

> "Slow" had been my impression with flx (the third-party package), but
> didn't it come from scoring rather than matching?

No idea.  The slow in flex almost surely _doesn't_ come from the scoring.

> As long as we're using the same approach for constructing the matching
> regexp as ido-flex does, speed should be okay for most uses.

I haven't checked. But I remember either you or Stefan saying that it uses
a regexp similar to pcm's.

> Another thing I'd like to note: with flex completion, RET doesn't select
> the current candidate anymore (working as intended, of course). But it's
> a bit disorienting.

In what situation exactly? Emacs -Q + (setq completion-styles '(flex)) + what?

> > I wonder
> > if ditching pcm's regexp based approach and coding something by
> > hand (perhaps in C) would be faster.  I haven't done any
> > measurements but the thing feels slow to me: so I wish more
> > people could experiment with it (and with company, too)
>
> ...although it does feel a bit slower than the prefix matching. Maybe
> that's just to be expected.

You're right, more or less, at least judging from some benchmarks:

(benchmark-run-compiled 100
  (let ((completion-styles '(flex)))
    (completion-all-completions "kill" obarray nil 0))) ; => 4.76s

(benchmark-run-compiled 100
  (let ((completion-styles '(basic)))
    (completion-all-completions "kill" obarray nil 0))) ; => 3.7s

... and the first returns a much larger list.

I was expecting to see much larger differences, though, since my
icomplete and company-based experience is really sluggish. But
I wasn't using these much for the default completion style anyway.
Or maybe the sluggishness is coming from somewhere else.

Anyway, as I predicted, most of the work is the matching in
completion-pcm--all-completions.  I'll try to hack something
there when the pattern has some simple flex-like form.

João

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

[Dmitry Gutov]

On 17.03.2019 23:27, João Távora wrote:
> [sorry for the double mail Dmitry]

No problem!

> Yes, in this case it would come from company. I was thinking you
> could sort by `completion-score` in descending order.

But why do it that way? And anyway, the capf sorting will be 
customizable by the user. company-capf will need to honor that.

>> But if you just want to try and see how well the sorting works, you can
>> add one to `company-transformers`.
> 
> Thanks, I added
> 
> (defun sort-by-company-score (cands)
>    (cl-sort cands
>             #'>
>             :key (lambda (cand) (or (get-text-property 0
> 'completion-score cand) 0)))
> 
> (add-to-list 'company-transformers 'sort-by-company-score)
> 
> And it behaves much better.

That's good.

> My idea is that something like this could be
> be built-in into company (after the lexicographical sort).

No need to hurry before Stefan here, I think.

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

[Dmitry Gutov]

On 17.03.2019 23:46, João Távora wrote:

>> Another thing I'd like to note: with flex completion, RET doesn't select
>> the current candidate anymore (working as intended, of course). But it's
>> a bit disorienting.
> 
> In what situation exactly? Emacs -Q + (setq completion-styles '(flex)) + what?

+ input is not a prefix match. E.g. M-x describe-variable, then input 
'compst'. RET won't select the completion.

> You're right, more or less, at least judging from some benchmarks:
> 
> (benchmark-run-compiled 100
>    (let ((completion-styles '(flex)))
>      (completion-all-completions "kill" obarray nil 0))) ; => 4.76s
> 
> (benchmark-run-compiled 100
>    (let ((completion-styles '(basic)))
>      (completion-all-completions "kill" obarray nil 0))) ; => 3.7s
> 
> ... and the first returns a much larger list.

Try a smaller input, like just 'k'. The difference is more stark in that 
case, and the lists of completions are longer.

For the same reason (lots of matches), I'm afraid simply moving matching 
to C won't bring a noticeable improvement.

> I was expecting to see much larger differences, though, since my
> icomplete and company-based experience is really sluggish. But
> I wasn't using these much for the default completion style anyway.
> Or maybe the sluggishness is coming from somewhere else.
> 
> Anyway, as I predicted, most of the work is the matching in
> completion-pcm--all-completions.  I'll try to hack something
> there when the pattern has some simple flex-like form.

All right. Please let us know of the results.

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

[Dmitry Gutov]

On 18.03.2019 16:26, Dmitry Gutov wrote:
> + input is not a prefix match. E.g. M-x describe-variable, then input 
> 'compst'. RET won't select the completion.

Never mind. It's the same with prefix completion if the input is not a 
unique match and not a match itself.

I got too used to the Ido behavior.

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

[Stefan Monnier]

>> + input is not a prefix match. E.g. M-x describe-variable, then input
>> 'compst'. RET won't select the completion.
> Never mind. It's the same with prefix completion if the input is not
> a unique match and not a match itself.
> I got too used to the Ido behavior.

`icomplete-mode` gets you closer to that behavior.


        Stefan

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

[João Távora]

On Mon, Mar 18, 2019 at 2:27 PM Dmitry Gutov <dgutov@yandex.ru> wrote:

> On 17.03.2019 23:46, João Távora wrote:
>
> >> Another thing I'd like to note: with flex completion, RET doesn't select
> >> the current candidate anymore (working as intended, of course). But it's
> >> a bit disorienting.
> >
> > In what situation exactly? Emacs -Q + (setq completion-styles '(flex)) + what?
>
> + input is not a prefix match. E.g. M-x describe-variable, then input
> 'compst'. RET won't select the completion.

I must be missing something, because that doesn' work in vanilla
Emacs -Q, either, i.e. M-x describe-variable + something + RET will only
select "something" if it is completable to a sole candidate.  Flex works the
same way, though 'compst' will probably match more symbols than
with basic completion (where it matches none).

You might want to bind RET to "minibuffer-force-complete" or
"minibuffer-force-complete-and-exit", but that's orthogonal I think.

Or am I missing something?

> Try a smaller input, like just 'k'. The difference is more stark in that
> case, and the lists of completions are longer.
>
> For the same reason (lots of matches), I'm afraid simply moving matching
> to C won't bring a noticeable improvement.

You're partly right. With shorter input, the burden shifts considerably
from completion-pcm--all-completions (the matching) to
completion-pcm--hilit-commonality (the hilighting and scoring), but
according to the CPU profiler, the former is still dominant, so even a
modest improvement there could still have a large impact.

Capping max matches (after sorting) might bring more improvements
to parts of the code that I'm not profiling (like stuff that iterates all
matches, though I'm not sure what), or by releasing large parts of the
list early for the GC to reap.

As can other techniques like deferring the completion with an idle
timer which is reset on every keystroke.  I'm reasonably confortable
with this last technique and it is usually desirable regardless of other
speed improvements, so I might have a look at that first.

-- 
João Távora

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

[Dmitry Gutov]

On 18.03.2019 16:49, Stefan Monnier wrote:
>>> + input is not a prefix match. E.g. M-x describe-variable, then input
>>> 'compst'. RET won't select the completion.
>> Never mind. It's the same with prefix completion if the input is not
>> a unique match and not a match itself.
>> I got too used to the Ido behavior.
> 
> `icomplete-mode` gets you closer to that behavior.

All my testing is with 'icomplete-mode' on, so that's what I'm reporting on.

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

[João Távora]

On Mon, Mar 18, 2019 at 2:42 PM Dmitry Gutov <dgutov@yandex.ru> wrote:
>
> On 18.03.2019 16:26, Dmitry Gutov wrote:
> > + input is not a prefix match. E.g. M-x describe-variable, then input
> > 'compst'. RET won't select the completion.
>
> Never mind. It's the same with prefix completion if the input is not a
> unique match and not a match itself.

Oh, that explains it.

> I got too used to the Ido behavior.

I feel you.  You (we) should switch to icomplete-mode and help me
improve it.  Or at least try it out for a little while and give me
suggestions.

João

Who uses Icomplete-mode? Re: [Emacs-diffs] master b0e318d 2/2: Score flex-style completions according to match tightness

[João Távora]

On Mon, Mar 18, 2019 at 2:50 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> >> + input is not a prefix match. E.g. M-x describe-variable, then input
> >> 'compst'. RET won't select the completion.
> > Never mind. It's the same with prefix completion if the input is not
> > a unique match and not a match itself.
> > I got too used to the Ido behavior.
>
> `icomplete-mode` gets you closer to that behavior.

It also brings considerable pain for someone very used to Ido,
though I've been trying to work on that.

Which brings me to a question I've been meaning to ask: who
here uses Icomplete-mode and just how attached are you to its
interface?

Switching from ido.el to icomplete.el, I miss:

- A less cryptic left side hint as to what the "current" matched
  thing is (in ido.el it's pretty obvious, in icomplete.el not so much)
- A way to have RET exit the minibuffer with the current thing, except
  when finding files, where it should just enter the directory (though there
  should always be a binding for exiting the minibuffer with whatever
  the current input is).
- A way to delete buffers and kill files effectively without leaving
  the minibuffer prompt.
- Eliminate the need for icomplete-compute-delay, using while-no-input
  or maybe threads.
- Maybe more

Some of these can be achieved through customization, and some
would probably need more work.  Moreover, if there aren't a lot of
people overly attached to the current interface, we could choose
some new defaults.

Otherwise, I'd propose a new icomplete-ido-emulation-mode with
some less horrible name.

João

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

[Stefan Monnier]

>>>> + input is not a prefix match. E.g. M-x describe-variable, then input
>>>> 'compst'. RET won't select the completion.
>>> Never mind. It's the same with prefix completion if the input is not
>>> a unique match and not a match itself.
>>> I got too used to the Ido behavior.
>> `icomplete-mode` gets you closer to that behavior.
> All my testing is with 'icomplete-mode' on, so that's what I'm reporting on.

Duh, I misunderstood the description of the problem, indeed.
Sorry,


        Stefan

Re: Who uses Icomplete-mode? Re: [Emacs-diffs] master b0e318d 2/2: Score flex-style completions according to match tightness

[Stefan Monnier]

> Which brings me to a question I've been meaning to ask: who
> here uses Icomplete-mode and just how attached are you to its
> interface?

I don't use it all the time, but I often like to use it.

> - A less cryptic left side hint as to what the "current" matched
>   thing is (in ido.el it's pretty obvious, in icomplete.el not so much)

Not sure what you mean by that

> - A way to have RET exit the minibuffer with the current thing,

    (define-key icomplete-minibuffer-map [?\C-m]
      'icomplete-force-complete-and-exit)

should do the trick.

>   except when finding files, where it should just enter the directory

This is the one "feature" of Ido which drove me completely mad.  I might
have gotten used to some of the other parts of the Ido UI but this one
just makes no sense to me: I much prefer typing / than RET to enter the
directory (and with partial-completion style this works nicely).

>   (though there should always be a binding for exiting the minibuffer
>   with whatever the current input is).

    (define-key icomplete-minibuffer-map [?\C-j] 'exit-minibuffer)

?

> - A way to delete buffers and kill files effectively without leaving
>   the minibuffer prompt.

Hmm... I thought you coded this up already, but I don't see it in
icomplete.el.  Did I dream it?

This is sliding towards Helm territory and is difficult to provide in
a clean generic way (icomplete-mode is supposed to work for all
completions), but it might make sense to offer "category-specific" key
bindings and commands, yes.

> - Eliminate the need for icomplete-compute-delay, using while-no-input
>   or maybe threads.

Looks like you have your work cut out !

> Some of these can be achieved through customization, and some
> would probably need more work.  Moreover, if there aren't a lot of
> people overly attached to the current interface, we could choose
> some new defaults.

I like the fact that the key-bindings are pretty much the same with and
without icomplete, so I'm not looking forward to changing the default
RET binding in icomplete-mode.  But that's my opinion as icomplete user,
so if I'm in the minority I can live with it.

> Otherwise, I'd propose a new icomplete-ido-emulation-mode with
> some less horrible name.

That might actually be a good approach (especially if it's built as just
"icomplete-mode with different defaults" so the new features can also be
used from icomplete-mode modulo simple customizations), also because it
will be new and so could attract new users more effectively than
"icomplete-mode has slightly different default behavior".


        Stefan

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

[Dmitry Gutov]

On 18.03.2019 16:51, João Távora wrote:

>> Try a smaller input, like just 'k'. The difference is more stark in that
>> case, and the lists of completions are longer.
>>
>> For the same reason (lots of matches), I'm afraid simply moving matching
>> to C won't bring a noticeable improvement.
> 
> You're partly right. With shorter input, the burden shifts considerably
> from completion-pcm--all-completions (the matching) to
> completion-pcm--hilit-commonality (the hilighting and scoring), but
> according to the CPU profiler, the former is still dominant, so even a
> modest improvement there could still have a large impact.

I was actually comparing flex vs basic in this scenario, and the former 
was 2x slower. Which is, IDK, could be noticeable.

> Capping max matches (after sorting) might bring more improvements
> to parts of the code that I'm not profiling (like stuff that iterates all
> matches, though I'm not sure what), or by releasing large parts of the
> list early for the GC to reap.

Capping max matches is what all completion systems do in other editors, 
AFAIK. That feels kind of dirty, but could bring the most bang for the 
effort expended.

As long as we don't confuse any caches by doing this.

Also, the limit has to come *after* scoring and sorting, so for the 
performance improvement to arrive, it seems a lot of things would need 
to migrate to C.

> As can other techniques like deferring the completion with an idle
> timer which is reset on every keystroke.  I'm reasonably confortable
> with this last technique and it is usually desirable regardless of other
> speed improvements, so I might have a look at that first.

It's worth a try. But if filtering will happen right away after the user 
has stopped typing, that might mean higher CPU usage and lower battery 
life on a laptop. Just something to be on a lookout for.

Re: Who uses Icomplete-mode?

[Juri Linkov]

> Which brings me to a question I've been meaning to ask: who
> here uses Icomplete-mode and just how attached are you to its
> interface?

ido is more intrusive whereas icomplete is just an unobtrusive
addon over the default minibuffer behavior that adds more commands
for “inline completions”, i.e. for browsing completions
without showing the *Completions* window, nothing more fancy.

My only complaint about icomplete is its default keybindings.
I find it more usable with following customization:

  (define-key icomplete-minibuffer-map [(control left)]
             'icomplete-backward-completions)
  (define-key icomplete-minibuffer-map [(control right)]
             'icomplete-forward-completions)
  (define-key icomplete-minibuffer-map [(control return)]
             'icomplete-force-complete-and-exit)

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

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 18.03.2019 16:51, João Távora wrote:
>> You're partly right. With shorter input, the burden shifts considerably
>> from completion-pcm--all-completions (the matching) to
>> completion-pcm--hilit-commonality (the hilighting and scoring), but
>> according to the CPU profiler, the former is still dominant, so even a
>> modest improvement there could still have a large impact.
> I was actually comparing flex vs basic in this scenario, and the
> former was 2x slower. Which is, IDK, could be noticeable.

I understood that.  I was just saying that in the "2x slower" case, well
more than half of the time is still spent in
completion-pcm--all-completions.  This time is potentially spent
matching regexps (but maybe not, I haven't dug down from there).  But if
it is, it could be optimizable by hand-coding the matching code in C, so
there still seems to be an opportunity for considerably reducing that 2x
slowdown when comparing to basic.

> Also, the limit has to come *after* scoring and sorting, so for the
> performance improvement to arrive, it seems a lot of things would need
> to migrate to C.

I don't think that's practical.  As I said, if capping max matches is to
have any effects, it will be in parts of code that I haven't profiled,
i.e. parts that aren't as simple to profile as calling
completion-all-completion.  Those would presumably be in the UI's
(icomplete, company) and would somehow iterate all the list. But perhaps
there aren't that many parts.

>> As can other techniques like deferring the completion with an idle
>> timer which is reset on every keystroke.  I'm reasonably confortable
>> with this last technique and it is usually desirable regardless of other
>> speed improvements, so I might have a look at that first.
> It's worth a try. But if filtering will happen right away after the
> user has stopped typing, that might mean higher CPU usage and lower
> battery life on a laptop. Just something to be on a lookout for.

You're absolutely right.  And anyway I noticed icomplete _already_ has a
while-no-input there, so that technique has already been tried.  I guess
the most annoying thing here in terms of user experience is a variation
on this: C-h f RET typed in quick succession on an elisp functino will
see a considerable delay after typing the 'f' that really shouldn't be
there.  In other words, typing this very fast just means I know in
advance what the default will be and am OK with it, so I expect no
completions-related delay.  Bomehow even with the while-no-input and
with icomplete-compute-delay to 0 this still happens, so this is where
I'm going to investigate.

João

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

[Stefan Monnier]

>>> You're partly right. With shorter input, the burden shifts considerably
>>> from completion-pcm--all-completions (the matching) to
>>> completion-pcm--hilit-commonality (the hilighting and scoring), but
>>> according to the CPU profiler, the former is still dominant, so even a
>>> modest improvement there could still have a large impact.
>> I was actually comparing flex vs basic in this scenario, and the
>> former was 2x slower. Which is, IDK, could be noticeable.
> I understood that.  I was just saying that in the "2x slower" case, well
> more than half of the time is still spent in
> completion-pcm--all-completions.

FWIW, I think if basic is fast enough and flex is 2x slower, then flex
is likely fast enough as well (or the contrapositive: if flex is too
slow and basic is only 2x faster, then basic is also too slow).

>> It's worth a try. But if filtering will happen right away after the
>> user has stopped typing, that might mean higher CPU usage and lower
>> battery life on a laptop. Just something to be on a lookout for.
> You're absolutely right.  And anyway I noticed icomplete _already_ has a
> while-no-input there, so that technique has already been tried.

Not really: the while-no-input was added long after the rest of the code
was written and was mostly designed for the case where the completion
data takes a *very* long time to get, the main purpose being to be able
to enable icomplete for *all* completion tables rather than only for
those we know to be fast enough.


        Stefan

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

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> FWIW, I think if basic is fast enough and flex is 2x slower, then flex
> is likely fast enough as well (or the contrapositive: if flex is too
> slow and basic is only 2x faster, then basic is also too slow).

Hmmm, slightly confused, but I think we're currently in the
"contrapositive" side (at least given the UI problems that I describe
below).  Anyway, this is orthogonal, 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. I'd say it's worth a shot.  Depending on the "basic"
implementation, it could even be faster.

>>> It's worth a try. But if filtering will happen right away after the
>>> user has stopped typing, that might mean higher CPU usage and lower
>>> battery life on a laptop. Just something to be on a lookout for.
>> You're absolutely right.  And anyway I noticed icomplete _already_ has a
>> while-no-input there, so that technique has already been tried.
>
> Not really: the while-no-input was added long after the rest of the code
> was written and was mostly designed for the case where the completion
> data takes a *very* long time to get, the main purpose being to be able
> to enable icomplete for *all* completion tables rather than only for
> those we know to be fast enough.

I don't understand: while-no-input _is_ there, at least it is doing that
which I was going to attempt.  Or do you have some better use of it in
mind that I am not aware of?

Anyway, with the current approach, the problem seems to be that
throw-on-input is not being checked often enough.  I.e in this block:

          (let* (...
                 (text (while-no-input
                         (icomplete-completions
                          field-string
                          (icomplete--completion-table)
                          (icomplete--completion-predicate)
                          (if (window-minibuffer-p)
                              (not minibuffer-completion-confirm)))))
                 (buffer-undo-list t)
                 deactivate-mark)
	    ;; Do nothing if while-no-input was aborted.
            (when (stringp text) ... ))
            
text will often be t, meaning the call _was_ interrupted by
while-no-input, but icomplete-completions was still allowed to run to
completion (and that takes about one or two seconds with empty input).

If somehow while-no-input were able to detect interruptions at a more
finer grained level, I think icomplete-completions would be interrupted
earlier.  A (dumb) way to fix this is by simply adding a call to
input-pending-p to one of the critical sections:

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index c5d7148..37d1d91 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3049,7 +3049,9 @@ completion-pcm--all-completions
 	  compl
 	(let ((poss ()))
 	  (dolist (c compl)
-	    (when (string-match-p regex c) (push c poss)))
+	    (when (string-match-p regex c)
+              (input-pending-p)
+              (push c poss)))
 	  (nreverse poss))))))
 
 (defvar flex-score-match-tightness 100
 
If one tries C-h f <some-char> after evaluating this, <some-char>
shows almost immediately after the user typed it.  Now, this is quite
ugly and it still doesn't fix the C-h f RET delay for some reason (but
that shouldn't be very hard to fix, hopefully)

Furthermore, I think the problem pointed to by Dmitry regarding power
consumption is mostly unrelated to this, and targeted effectively by the
existing icomplete-compute-delay variable, which menas battery-wary
users should just set that to a higher value.

João

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

[Dmitry Gutov]

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.

I've seen that with Ido, for example.

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

[João Távora]

[-- 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 --]

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

[Stefan Monnier]

>> FWIW, I think if basic is fast enough and flex is 2x slower, then flex
>> is likely fast enough as well (or the contrapositive: if flex is too
>> slow and basic is only 2x faster, then basic is also too slow).
>
> Hmmm, slightly confused, but I think we're currently in the
> "contrapositive" side (at least given the UI problems that I describe
> below).  Anyway, this is orthogonal, 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. I'd say it's worth a shot.  Depending on the "basic"
> implementation, it could even be faster.

What I'm saying is that a slowdown of 2x is basically irrelevant here:
it's fast enough (maybe those rare people running on really slow machine
will simply not enable it, but I'm not worried).

> I don't understand: while-no-input _is_ there, at least it is doing that
> which I was going to attempt.

I thought you wanted to replace the icomplete-delay with while-no-input,
rather than just add while-no-input.  Sorry.

> If somehow while-no-input were able to detect interruptions at a more
> finer grained level, I think icomplete-completions would be interrupted
> earlier.  A (dumb) way to fix this is by simply adding a call to
> input-pending-p to one of the critical sections:

If it takes 2s to notice input, maybe it's a bug.  These things depend
on the OS you're running (IIRC we're much less good at it under MacOS),
but it's worth reporting it.


        Stefan

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

[Stefan Monnier]

> 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)

Completing the empty string is the worst case for the "highlight" part,
but not for the actual filtering.  For the filtering, you may like to
try completing a string like "eeeeel": `basic` will very quickly return
the empty set, whereas flex may take a lot longer, especially if your
completion table contains some long strings with lots and lots of `e`s
in it but no `l` (that should be enough to trigger the exponential
behavior of the backtracking regexp matcher)


        Stefan

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

[Dmitry Gutov]

On 21.03.2019 1:25, João Távora wrote:
> 
> (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.

I think it can help too.

Though not necessarily for icomplete (it seems to avoid showing the 
completions until you've typed at least one character).