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

["João Távora" <joaotavora@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 3743 bytes --]

On Sun, Jun 6, 2021, 23:20 Dmitry Gutov <dgutov@yandex.ru> wrote:

>
> >> 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)
>

Meant to write ML as in machine learning, not NL.

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 think you calculate the distance using one of these fancy multi-surname
algorithms , then do cutoff somewhere.

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.
>

But nothing algorithmically aberrant, I think.

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)
>


By the way, I think you should be running benchmarks multiple times to get
times in the seconds range, and reduce noise. Multiple levels of CPU cache
and other factors like temp thottling may skew results when running just
one time.

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).
>

Maybe in Elisp that's a good idea, in other lisps and other languages,
second-guessing the GC is a bad idea. I hear ours is so basic that indeed
it might be reasonable.

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)
>

That's nice! but are you sure you're not seeing noise, too?

Tried other things like moving the update-score-and-face lambda out of
> the mapcar loop - that didn't move a needle.


If a lambda is non capturing of stuff inside the loop, only one copy of it
is ever made, I think. So it doesn't suprise me.

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).


Might be noise, or you might be thrashing of CPU caches, who knows? If the
string length is on the same cache line as the contents of the string
you're reading, then evicting that to go read the value of a boxed integer
somewhere radically different is slow. Just speculation of course. Might
just be noise or something else entirely.

João

[-- Attachment #2: Type: text/html, Size: 6158 bytes --]