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

[Dmitry Gutov <dgutov@yandex.ru>]

On 06.06.2021 09:54, João Távora wrote:

>> Perhaps not sorting exactly, but the scoring part? Lowering the
>> implementation into C might help, we discussed something like that in
>> the past.
> 
> Perhaps, all could be measured.  But I also remember explaining that
> scoring is basically free.  The flex algorithm search algorithm is
> greedy already, it doesn't backtrack.  Given a pattern 'foo' against
> 'fabrobazo', it takes 9 steps to see that it matches.  I can't see any
> other way to improve that, short of a something like a tottaly different
> string implementation.  The scoring's numeric calculations at each step
> are trivial.

Thanks, if it's indeed that fast, I might have a use for it as well, in 
a different context. ;-)

>> 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.
> 
> That may be useful, but for other purposes.  If I understand correctly,
> Jaro-Winkler is for finding the distante between two arbitrary strings,
> where the first in not a subsequence of the second.  I bet google uses
> stuff like that when you accitendally transpose characters.  Flex just
> gives up.  Those other others algos still catch the match (and Google
> than probably NL-scours your most intimate fears and checks with your
> local dictator before showing you typing suggestions)

I'm not crazy about shuffling completion, but some people did indeed ask 
for it. The filtering step has to be more complex, though (you can't 
just construct a straightforward regexp to filter with).

>> 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.
> 
> Go ahead and kill the scoring calculationg altogether in
> completion-pcm--hilit-commonality.  I bet it won't make a difference.
> If fact, for that experiment, try a simple substring search.

Same result, indeed. We should note, though, that 
completion-pcm--hilit-commonality has some steps that were added 
together with the 'flex' style, for it to work.

> I bet
> you're just seeing an inferior GC at work, or a string implementation
> that's made optimized for other stuff that Ruby's can't, like
> propertization.  Try making Ruby strings that mimic Elips if you've time
> to spare...

I did some instrumenting, replacing (completion-pcm--hilit-commonality 
pattern all) inside completion-flex-all-completions with 
(benchmark-progn (completion-pcm--hilit-commonality pattern all)). 
Recompiled between each change (interpreted mode gives very different 
numbers).

Unmodified, the call takes ~85ms:

   Elapsed time: 0.085520s (0.068406s in 4 GCs)

If I comment everything inside its first lambda except the returned 
value (making the function the same as #'identity), the time goes down 
to <1ms.

Uncomment the 'copy-sequence' and 'string-match' calls (which one might 
suspect of garbage generation):

   Elapsed time: 0.006380s

Tried binding gc-cons-threshold to a high value, and even galling 
garbage-collect-maybe (or not): that speeds it up, but adds some 
unpredictable GC pauses later (though it would be nice to be able to 
consolidate the pauses into one collection pass).

Long story short, the patch I just installed, to reuse the match data, 
brings the runtime down to

   Elapsed time: 0.066388s (0.050087s in 3 GCs)

Tried other things like moving the update-score-and-face lambda out of 
the mapcar loop - that didn't move a needle. Someone more familiar with 
the code might get further. But perhaps it's just the cost of executing 
this logic in Lisp 12000 times, and doing some of that in C would be the 
next step.

And a weird part: replacing all repeated (length str) calls with a 
reference to an existing local binding makes it *slower* (back to the 
original performance). Check this out:

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index d5a0118b7c..d7102245a2 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3544,7 +3544,7 @@ completion-pcm--hilit-commonality
                      score-numerator   (+ score-numerator (- b a)))
                     (unless (or (= a last-b)
                                 (zerop last-b)
-                               (= a (length str)))
+                               (= a end))
                       (setq
                        score-denominator (+ score-denominator
                                             1
@@ -3562,12 +3562,12 @@ completion-pcm--hilit-commonality
             ;; for that extra bit of match (bug#42149).
             (unless (= from match-end)
               (funcall update-score-and-face from match-end))
-           (if (> (length str) pos)
+           (if (> end pos)
                 (add-face-text-property
                  pos (1+ pos)
                  'completions-first-difference
                  nil str))
-           (unless (zerop (length str))
+           (unless (zerop end)
               (put-text-property
                0 1 'completion-score
                (/ score-numerator (* end (1+ score-denominator)) 1.0) 
str)))
@@ -3980,7 +3980,7 @@ completion-flex-all-completions
                    string table pred point
                    #'completion-flex--make-flex-pattern)))
        (when all
-        (nconc (completion-pcm--hilit-commonality pattern all)
+        (nconc (benchmark-progn (completion-pcm--hilit-commonality 
pattern all))
                 (length prefix))))))

  ;; Initials completion