[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#48841: fido-mode is slower than ido-mode with similar settings
From: |
Dmitry Gutov |
Subject: |
bug#48841: fido-mode is slower than ido-mode with similar settings |
Date: |
Mon, 7 Jun 2021 01:20:13 +0300 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 |
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
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/04
- bug#48841: fido-mode is slower than ido-mode with similar settings, João Távora, 2021/06/05
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/05
- bug#48841: fido-mode is slower than ido-mode with similar settings, João Távora, 2021/06/05
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/05
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/05
- bug#48841: fido-mode is slower than ido-mode with similar settings, João Távora, 2021/06/06
- bug#48841: fido-mode is slower than ido-mode with similar settings,
Dmitry Gutov <=
- bug#48841: fido-mode is slower than ido-mode with similar settings, João Távora, 2021/06/06
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/06
- bug#48841: fido-mode is slower than ido-mode with similar settings, João Távora, 2021/06/07
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/10
- bug#48841: fido-mode is slower than ido-mode with similar settings, João Távora, 2021/06/11
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/11
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/11
- bug#48841: fido-mode is slower than ido-mode with similar settings, João Távora, 2021/06/13
- bug#48841: fido-mode is slower than ido-mode with similar settings, Dmitry Gutov, 2021/06/16
- bug#48841: fido-mode is slower than ido-mode with similar settings, João Távora, 2021/06/17