bug#12796: Optimize `ido-completing-read' for larger lists with flex matching enabled

[Dmitry Gutov <dgutov@yandex.ru>]

On 06.11.2012 15:03, Kim Storm wrote:
>> I'm not familiar with the ido.el code, so I find it difficult to judge
>> if your approach to caching is right.  Kim could you take a look (the
>> patch can be seen at http://debbugs.gnu.org/12796)?
>
> I looked at the caching patch, and it looks alright (in the sense that I
> don't think
> it will break ido behaviour.)
>
> I'm not sure how efficient the caching is though. As far as I can see,
> it only
> caches the most recent (non-empty) list of matches, i.e. the shortest list
> corresponding to the longest "successful" user input in the minibuffer.
>
> So if the user has to backtrack beyond that point, I don't really see
> how the
> caching will help, as the cache is then invalidated.

That's true, backtracking was not a priority. But see below.

> Also, I don't quite understand why this condition is needed:
>
> (<= (* 10 (length matches)) (length ido-cur-list)))
>
> It seems to me to only cache a list of matches that has reduced
> the set of matches by a factor 10 - if the aim is to reduce processing
> time for long lists, even reducing by a factor of 2 may be noticable ?
>
> But maybe the intention of this line was to stop caching once the list
> has become short than 1/10th of the original list?  In that case, the
> operator should be <= I think ?

No, the idea is to limit memory consumption (which may be a bit 
premature) and make sure that the filtered matches list is smaller 
enough than the original to justify saving it. I probably should change 
10 to a smaller constant, like 3 or 2.

On the "stop caching" front, we can add a lower bound check, comparing 
the matches length to an absolute or relative value. This way, doing a 
few backspaces from a sufficiently narrowed state won't trigger a full 
recomputation.

To go further than that, it shouldn't be hard to keep a stack of caches 
for the current input string as it's typed, but I suspect memory 
consumption may be a bigger concern in this case.

WDYT?