Re: [PATCH] Make completions almost instantaneous

[Daniel Berlin <dberlin at redhat dot com>]

Andrew Cagney <ac131313@cygnus.com> writes:

> Daniel Berlin wrote:
> 
> > -   /* Clip any symbol names that we've already considered.  (This is a
> > -      time optimization)  */
> > -
> > -   for (i = 0; i < return_val_index; ++i)
> > -     {
> > -       if (STREQ (symname, return_val[i]))
> > -       {
> > -         return;
> > -       }
> > -     }
> > -
> 
> It probably should have said ``space optimization''.  I'd take a guess
> that this dates back to a time when readline didn't remove duplicates
> and when people were more worried about memory.
> 
> I suspect that someone might eventually re-tweek the code so that it
> does an O(log(n)) sorted insertion and that way eliminates
> duplicates. 
I tried this last night, it's not as fast as you would think.
Remember, strcmp is O(n) on the max of the lengths of the strings
being compared, so O (log n) is really O (log mn). It also involves an
O(n) worst case memmove, depending on where in the array the string
goes (if it's the new second string, we have to move the entire rest
of the array by one pointer position), which makes the O(log n)
insertion not buy you anything at all.
Compared to O(1), it's still very slow. You only started getting any
kind of significant difference with >10k completions, and it was still
too slow (1-2 minutes vs 15 minutes vs 3 seconds for the way my patch
makes it).

I was really just trying to tweak this without changing the data structure.
The real thing to do is to change to a binary tree, or a ternary
search tree, do all the insertions (which will be O(log mn), but no
O(n) memmove is necesssary), and delete the tree at the end, filling
in the array pointers in the right order as you delete the tree.

This is much more work, and it just wasn't worth it.  You'd get a lot
more memory savings by bcaching the symbol names it's putting in the
list (which would make the duplicate strings just duplicate pointers
anyway, and only wasting one pointer a piece, rather than the length
of the string), then you would trying to fix the code here.

IMHO, of course.

> However, given that Eli (i.e. dos) is happy with change, I don't see
> that happening soon.

As I said, the best way to remove duplicates here without touching the
existing char ** structure is to bcache the symbol names in all the
readers, thus making almost all of the duplicates in the completion
list (there is no way for a duplicate to be anything but of a symbol,
since those are the only things we can find in symtabs, psymtabs, and
minsyms), waste a lot less memory.

You'd also get a general memory usage decrease too from the change.

> 
> As Elena said, nice catch.
> 
> 	Andrew

-- 
I looked out my apartment window, and I saw a bird wearing
sneakers and a button saying, "I ain't flying no where."  I
said, "What's your problem buddy?"  He said, "I'm sick of this
stuff -- winter here, summer there, winter here, summer there.