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

[Dmitry Gutov <dgutov@yandex.ru>]

On 11.06.2021 20:09, João Távora wrote:

>> The performance is basically the same, which seems to indicate that
>> either Elisp has to allocate very little for a compiled lambda code,
>> or it's optimized out (which would also make sense: the only thing
>> necessary for it is a new container for the current scope).
> 
> Which lambda are we talking about?  Is it ` update-score-and-face`?  If
> so, I would guess that the capture of `score-denominator` is what takes
> space, and that space is no bigger than another variable in that let
> scope.

Yes, that one.

> But `length` of a string, in any sane string implementation, _is_
> accessing "an already computed value".  Which likely lives just besides
> the data.  In Emacs, it seems to be two pointers (8 bytes) apart from
> the data.  In a system with 64bytes of L1/2/3 cache it still
> theoretically makes up to 52 bytes come in "for free" after you read the
> length.  But to be honest I tried a bit and haven't come up with
> benchmarks to help confirm -- or help dispel -- this theory.  Maybe you
> can distill your "weird" experiment down to a code snippet?

I've tried reproducing the effect with a small snippet, and failed. :-(

>> Anyway, looking at what else could be removed, now that the extra
>> allocation in 'match-data' is gone, what really speeds it up 2x-11x
>> (depending on whether GC kicks in, but it more often doesn't), is
>> commenting out the line:
>>
>>    (setq str (copy-sequence str))
>>
>> So if it were possible to rearrange completion-pcm--hilit-commonality
>> not to have to modify the strings (probably removing the function
>> altogether?), that would improve the potential performance of c-a-p-f
>> quite a bit, for fido-mode and other frontends (depending on how much
>> overhead the other layers add).
> 
> Very interesting.  I don't know what the matter is with modifying the
> string itself.  Is it because we want to protect its 'face' property?
> Maybe, but what's the harm in chaning it?

I imagine it's just a "correctness" thing. Text properties are part of 
the string's identity. We add text properties, so we make a copy because 
we don't own the original list (it might be saved to some constant and 
also used for, I don't know, IMenu items?)

> If we do want to protect the shared 'face' property -- and only 'face'
> -- then we could very add some other property about face that the
> frontend could read "just in time" before it itself makes a copy of the
> string to display to the user.

Yes, it's an option (though a less elegant one): apply some namespaced 
text properties with the necessary data. And then we'd also be able to 
fontify "just in time".

Do we have any "frozen strings" in Emacs, which absolutely could not be 
modified? Do we plan to?

> This technique appears to be slightly simpler than using the hash-table
> indirection you propose (we would need something like that if, for some
> reason, we absolutely could not touch the string's property list.)

I disagree it's a simpler technique, but it would indeed be a simpler 
change, based on the current implementation.

>> Anyway, these are musing for the much-discussed future iteration of
>> the API. With the current version, and tied by backward compatibility,
> 
> Maybe I'm missing something, but I don't see why my above idea requires
> changing _that_ much of the API (a bit would change yes).  It's a matter
> of letting frontends opt-out of the current readily-available
> face-propertized completions and opt-into a display-time facility that
> does this propertization.

Even your version is a breaking enough change to be a pain, but possibly 
not beneficial enough to bother all consumers with, until we also add 
some more awaited features, I guess.

But I don't mind it myself, and happy to update Company. Either way it's 
a step forward.

> But if the speedup is big, I'd revisit the rationale for requiring those
> copies to be performed in the first place.

With fido-vertical-mode, and with that particular input, it's

   Elapsed time: 0.130773s (0.031547s in 1 GCs)

without copy-sequence, and

   Elapsed time: 0.169842s (0.069740s in 4 GCs)

with it. Not game changing, but definitely measurable.

> In my (very brief) testing
> it doesn't hurt a bit to remove it.

Same. But it likely depends on where the strings came from. In the most 
usual case, of course, they are created at runtime.