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

[Dmitry Gutov <dgutov@yandex.ru>]

On 13.06.2021 17:55, João Távora wrote:

> I just confirmed it's not for correctness.  If one foregoes the copy, in
> fido-mode a C-h f followed by some input followed by C-g and an M-x and
> no input (empty pattern) will show interesting results, i.e. a list of
> propertized strings when nothing should be propertized.

That's also an example of correctness problem, just the more obvious 
kind. It probably happens in a number of situations, e.g. all (?) uses 
of completion-table-with-cache.

> But maybe that's a question of removing the propertization when the
> pattern is empty?  I'll try later.

That must add some performance penalty as well, for extra mutation. And 
wouldn't cover some potential other uses of the same set of strings. In 
IMenu, maybe?

The latter is hypothetical, of course.

>> Do we have any "frozen strings" in Emacs, which absolutely could not
>> be modified? Do we plan to?
> 
> Immutable strings? And error when one tries to?  Or just ignore the
> modification?  And how would that help here?

It wouldn't help. It would do the opposite: basically forbid the 
approach you suggest, mutation without copying.

>> I disagree it's a simpler technique, but it would indeed be a simpler
>> change, based on the current implementation.
> 
> simpler means simpler in my book :-)

One is simpler diff, another is simpler resulting code. Both have their 
upsides.

>> But I don't mind it myself, and happy to update Company. Either way
>> it's a step forward.
> 
> If Company and fido-mode and a couple more outside the core/Elpa are all
> that's needed, it's probably warranted.  But there are so many frontends
> right now, I don't know...  We'd need some "opt into the optimization",
> I think."

Since all other users are third-party (and thus have short release 
cycles), it shouldn't be too much of a problem. Some highlighting code 
would start to fail, but probably without disastrous results. And then 
people will issue updates to look for some new property when the old 
expected ones are all missing.

>>> 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.
> 
> I don't have these results.  I tried the previous experiment:
> 
>     ;; C-u C-x C-e C-m in quick succession
>     (benchmark-run (completing-read "bla" obarray))
> 
> And turned icomplete.el's while-no-input into a progn.
> 
> In an Emacs -Q where (length (all-completions "" obarray)) is about
> 20000.
> 
>     ;; with copy
>     (0.39647753 6 0.22811240199999983)
>     (0.431950471 7 0.263988651)
>     (0.451116177 6 0.2249686070000001)
>      
>     ;; without copy, small but measurable speedup
>     (0.29890632 2 0.08419541699999966)
>     (0.293501099 2 0.08622194699999985)
>     (0.306566633 3 0.0853211100000002)
> 
> In a loaded Emacs where (length (all-completions "" obarray)) is 64554
> 
>     ;; with copy
>     (2.869362171 6 2.3882547280000495)
>     (2.909661303 6 2.4209153659999743)
>     (2.845522439 6 2.3638140250000106)
>      
>     ;; without copy.  Huge speedup.
>     (0.79817337 1 0.4526993239999797)
>     (0.8231736510000001 1 0.4752496449999626)
>     (0.719004478 1 0.4016016420000028)

Even better.

My current session has 37559 symbols, so it's somewhere in the middle.