On 05/30/2015 12:41 AM, Stefan Monnier wrote:

> I see the first patch says that it takes 1.34s to build the obarray and
> 0.78s to build an equivalent list of strings, so we could change the
> code so as to keep the completion table as a pre-built list of strings
> instead of a pre-built obarray.  It will also save us a bit of memory.

Maybe. The difference isn't much, though, and it's a one-time thing.

> As for doing the search each time, the possible gain on the first
> completion (0.3s instead of 0.78s)

The possible gain is from 1.34s down to 0.78s. I haven't managed to 
bring the time to generate all completions for "" down any further.

> doesn't make up for the loss of going
> from 0.02s to 0.3s on subsequent completions.

I think you mean 0.02 to 0.2.

> So that seems like a non-starter, unless we can speed it up
> significantly.  It shouldn't be too hard to keep the worst case at
> 0.76s, but lowering the 0.3s seems harder.

Lowering 0.2 is not too hard if the prefix is at least 2-3 characters 
long: you drop [\n \t()=,;\177] from the first regexp and simply search 
for the string. This way, the search for completions for "test" takes 
only 0.05s (with 37 matches). Of course, that doesn't work at all for an 
empty prefix.

Seems like support for lookbehind in the regexp engine would help unify 
these cases.

However, the worst case is going to come up a lot. After all, that's 
what you trigger with `C-u M-. TAB'.

> Obviously we could get rid
> of the "looking-at" within the loop (fold it into the preceding
> re-search-forward), but it seems unlikely that this would gain us much
> when there are few matches.

Indeed. It brings us to 0.78 in the worst case and 0.26 in the best case 
(I'm blaming the regexp engine), with no easy opportunity for a speed-up 
when matching a longer string. Patch attached.