Package: emacs;
Reported by: Dmitry Gutov <dgutov <at> yandex.ru>
Date: Sat, 5 Jun 2021 01:40:01 UTC
Severity: normal
Done: João Távora <joaotavora <at> gmail.com>
Bug is archived. No further changes may be made.
View this message in rfc822 format
From: Dmitry Gutov <dgutov <at> yandex.ru> To: João Távora <joaotavora <at> gmail.com> Cc: monnier <at> iro.umontreal.ca, 48841 <at> debbugs.gnu.org Subject: bug#48841: fido-mode is slower than ido-mode with similar settings Date: Mon, 7 Jun 2021 01:20:13 +0300
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
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.