bug#48841: fido-mode is slower than ido-mode with similar settings

[Dmitry Gutov]

On 06.06.2021 02:20, João Távora wrote:
> My bet is that the remaining lag is due to sorting.  In a dumb but
> illustrative example, when given the pattern 'fmcro' flex-enabled
> ido-mode pops 'flymake--backend-state-p--cmacro' to the top, while fido
> mode selects the much more reasonable 'defmacro'.

Perhaps not sorting exactly, but the scoring part? Lowering the 
implementation into C might help, we discussed something like that in 
the past.

And/or pick a different algorithm. E.g. Jaro-Winkler, which apparently 
is used in a lot of "fuzzy matching" implementations out there, it's 
pretty fast.

I took an example like

  (setq s (all-completions "" obarray))
  (setq ss (cl-delete-if-not (lambda (s) (string-match-p "a" s)) s))

then

  (benchmark 1 '(completion-all-completions "a" ss nil 1))

prints 0.180s here, whereas a "pure Ruby" implementation of Jaro-Winkler 
takes about 0.060s on the exact same set of strings. But perhaps Ruby is 
just faster than Elisp, I don't have a good comparison.

(The only J-W implementation in Elisp I have found yet -- 
https://github.com/rdiankov/emacs-config/blob/master/.emacs-lisp/auto-complete-1.3.1/fuzzy.el#L70 
-- is slower than the current scoring algo).