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

[Kim Storm]

On 2012-11-06 02:45, Stefan Monnier wrote:
> [ Hi Kim, can you give me your opinion on this?  ]
>
> > To try it, I just wrapped in it the "busy" part of `ido-set-matches-1' -
> > and indeed, no more waiting a several seconds after button
> > mashing. It's a bit buggy so far, but that's to be expected.
> To eliminate the buggy behavior, it should probably be put elsewhere,
> maybe directly in ido-exhibit (the post-command-hook).
Sounds right, but I a bit worried that some of the state information
may get corrupted if arbitrarily interrupted by user input.

If someone proposes a patch, I'll look at it.
> > The caching approach still feels faster in most cases, and is instantaneous
> > in cases when we're editing input and have few or no matches for the current
> > input (if we're backspacing, then only when no matches). It has room for
> > usability improvements, too.
> I'm not opposed to caching, actually.  I think the two are independent:
> it's important that a slow computation of the completion-data doesn't
> force the user to edit slowly.  But it's also good to optimize the
> computation itself such that interrupting the computation
> happens rarely.
>
> 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.

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 ?

I any case, I'm not opposed to adding some form of caching here,
and the proposed patch seems on the right track, but I'm not convinced
that it is the optimal approach.

Kim