RE: Add user customization fido-completion-styles

[Drew Adams <drew.adams@oracle.com>]

> > As for performance, for `M-x' there certainly is
> > no problem.  `M-x' with no input pattern to match
> > shows the 6000-some candidates immediately.
> 
> Certainly it doesn't _show_ 6000 candidates, right?
> You must mean it calculates them quickly and shows
> the top-sorting set quickly.  That's great, I guess,
> and I join in asking if Emacs shouldn't do that.

No, it can show them all.  Sure, because of Emacs's
display code, it shows only as many as fit in the
`*Completions* window.  But I'm using a separate
frame for `*Completions*', and I can shrink its
font size to show zillions of them.  Yeah, at a
certain point the font size becomes too small (no
such font).  But there's no problem calculating
and showing lots of candidates.

However, with Icicles flx sorting, the score for
each candidate, when there's no input pattern,
i.e. (flx-score CANDIDATE ""), is nil.

And as I mentioned, when either of the flx scores
is nil the candidates are compared alphabetically.
`flx-score' (from `flx.el') is meaningless for
empty input.  (See my previous mail about this.)

Things are slower when an input pattern is used.
E.g. with `M-x b' I see a pause of a couple sec,
for 864 candidates.  So yeah, flx sorting isn't
super rapid.  But that's OK.  Icicles users can
change sort orders anytime, on the fly.

> I didnt' dig down very intensively, but my naive
> profiling shows the bulk of the work to be in
> `all-completions' or thereabouts to be the
> main sink of cpu time:

I was reporting about Icicles, not icomplete.  But
yes, Icicles uses `completion-all-completions' too
(in this context).

> As you know, all-completions is a C function.
> The 1% is suspicious, I don't know if I should
> trust it.
> 
> Anyway, I'm curious how Icycles evades this.

See above.  I was speaking of the empty-input
case, where `flx-score' returns nil, in which
case the sort predicate falls back to comparing
alphabetically.

Also, Icicles sorts (and displays candidates)
outside the standard completion code.  It sorts
the current set of completions at the end.

> Anyway2, I wasn't trying this in an Emacs -Q.
> When I do, and I set icomplete-compute-delay to 0,
> then M-x is practically instantaneous.
> 
> Maybe the default 0.3 value of that variable is
> excessively conservative.

(FWIW, Icicles's delay for the number of sec to
wait before updating *Completions* incrementally
is 0.7 sec, by default.  But there's no wait if
the number of candidates is =< the value of option
`icicle-incremental-completion-threshold', whose
default value is 1000.)

> So, to summarize: I do believe could be some
> shortcuts for the notable case of no input pattern
> to give a speed boost, maybe showing them them
> their relevant minibuffer history.

Yes, for that notable case.  I'd say no, to using
input-history order.  (And what do you do if two
candidates to compare can't be compared by flx and
one or both is not a previous input?)

In Icicles, one of the available sort orders is
sorting "by last use as input".  A user can
switch to that anytime during completion.  In
general (most cases), that's not a good default
sort order.  It all depends on the user, and on
what kind of candidates s?he's sorting, and why.

That last-use-as-input sort order is defined as:

 Non-nil means S1 was used as input more recently than S2.
 Also:
  S1 < S2 if S1 was used as input previously but S2 was not.
  S1 < S2 if neither was used as input previously
   and S1 `icicle-case-string-less-p' S2.

> I don't believe there's some kind
> of magical speed pickup to be had.

Agreed.  Sorry if I gave a false impression in
that regard.

FWIW, I'm a firm believer in giving users control
over this kind of thing, as opposed to trying to
bake in some optimal combination that an Emacs
developer thinks is a good idea in general, but
without giving users an easy way to override that.

Yes, a given command (given kind of completion
candidates) can call for a given kind of sorting
by default - that default sorting behavior should
be up to the designer of that command.

But past that, a user should be able to choose
the kind of (default) sorting to use, including
for a specific predefined command, and in general.

And beyond that, a user should be able to change
the current sort order on the fly, while completing.
(Icicles allows all of that.)

> Even the C rewrite of parts of
> completion-pcm--all-completions now seems dubious.

I can't speak to that.

> > This way of combining yes-no-maybe predicates is
> > described here:
> > https://www.emacswiki.org/emacs/ApplesAndOranges
> 
> Have you tried `fido-mode` and/or flex?  Can you
> think of specific ways to improve it?  If so,
> patches are very welcome.

No, sorry.  And I'm no expert on flex matching or
fuzzy matching (of any kind).  Icicles lets users
use different kinds of matching, some of which are
provided by other 3rd-party libraries, if you load
them.

> It's a bit harder, I admit, to try to learn Icicles
> and decide which features to migrate.  But if you
> can point some laser-targeted improvement to the
> flex algorithm (in efficiency of functionality)
> are very welcome.

I don't have anything to help wrt flex.  I just
enable Icicles to use library `flx.el' which has
been around for years.

I do the same for other kinds of matching.  See
this doc page:

https://www.emacswiki.org/emacs/Icicles_-_Completion_Methods_and_Styles

These are the matchings that require other
libraries, for use by Icicles:

* Swank fuzzy-symbol matching requires
  `el-swank-fuzzy.el'.

* Fuzzy matching requires `fuzzy-match.el'.

* Jaro-Winkler matching requires `fuzzy.el'
  (in package `autocomplete').

* Levenshtein matching requires `levenshtein.el'.
  (There are 2 kinds of Levenshtein matching.)

The only "fuzzy" matchings I define in Icicles
itself are these:

* Scatter matching (sometimes called "flex"
  elsewhere).  This is just regexp matching
  with `a.*b.*c’

* SPC-scatter matching (some other packages use
  this).  This matches input parts that are
  separated by SPC chars, matching arbitrary
  text at the separations between those parts.
  IOW, it's as if regexp `.*' were inserted in
  place of each substring of SPC chars.

HTH.