Re: [PATCH] `completing-read` - allow history=t, sorting improvements

[Daniel Mendler <mail@daniel-mendler.de>]

On 4/19/21 10:15 PM, Stefan Monnier wrote:
>> However in my Vertico package (and in other continuously updating
>> UIs), the big bottleneck of the UI still is the sorting for many
>> candidates, even when including optimizations.
>> Therefore I am using a vertico-sort-threshold there.
>> Maybe there are potential improvements on a lower level?
> 
> If O(N log N) is still too slow, then I think it's safe to say that the
> problem is that N is too large: we can try and shave off a factor of `c`
> or even the `log N` by optimizing the implementation, but that just
> pushes the "too large" a bit further and sooner or later you'll have to
> bite the bullet and introduce some "threshold" beyond which you reduce
> the functionality.

N is not that large. I want the sorting to be reasonably fast for the 
the candidate sets which occur now in Emacs. But if this get improved, 
people may throw more candidates at it and then we will end up again 
with a threshold.

> In theory, if we want to optimize the speed as much as possible without
> reducing the functionality, we could try to:
> - first partition the set of candidates between those that appear in the
>    history and those that don't.  This is linear time.
> - sort the ones that appear in the history based on their position
>    there: no need to check length or alphabetic order in this case.
>    This is O(N log N) but the N should be significantly smaller.
> - If you have enough candidates already to fill the display you can stop
>    at this point and just use those candidates.
> - the remaining candidates can be sorted by their length, putting
>    together same-length candidates into sublists.  This could even be
>    more-or-less linear time with some kind of bucket sort.
> - Finally sort each of those sublists according to lexicographic order
>    This is again O(N log N) but again the N should be significantly
>    smaller and we can stop as soon as we've found enough candidates to
> fill the display.

Yes, we can do bucketing/radix sort by length. However I was looking for 
a solution which cuts down the constants enough such that the solution 
is good enough for the candidate sets we have now. By moving more of the 
algorithm to elisp I will also get some larger constants which may 
neglect the benefits until one reaches a large N.

Daniel