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

From: João Távora <[email-masked]>
Date: Mon, 7 Jun 2021 09:52:59 +0100

On Mon, Jun 7, 2021, 01:11 Dmitry Gutov <[email-masked]> wrote:

> On 07.06.2021 02:49, João Távora wrote:
>
> >     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.
>
> Just some stuff adding work to GC, I think.
>

O(n) stuff being a property and a number on each string, small in
comparison to the string.

Maybe moving all of them to parameters and return values (making it a
> static function and having the caller manage state) would help, I
> haven't tried that exactly.
>

Normally, in those adventures you end up with the same allocations
somewhere else, and uglier code. But you can try.

> 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.
>
> But the string value is boxed as well, right?

The key is locality. If the string length and data happen to live nearby in
memory (in the same box, so to speak), there's a decent chance that reading
one brings the other into the cache, and you get a nice hit depending on
your subsequent operation.

Here I'm just speculating, as I said. In managed languages such as Lisps,
it's somewhat unpredictable. It's also always hardware dependent. Though
given C/C++, a known processor and the right application, this will make a
world of a difference, and will yield truly "weird" results (which arent
weird at all after you understand the logic). Like, for example a vector
being much better at sorted insertion than a linked list. (!) Look it up.
Bjarne Stroustrup has one of those talks.

João