From mboxrd@z Thu Jan 1 00:00:00 1970 From: Daniel Berlin To: Andrew Cagney Cc: gdb-patches@sources.redhat.com Subject: Re: [PATCH] Make completions almost instantaneous Date: Fri, 30 Mar 2001 20:55:00 -0000 Message-id: References: <3AC51BB6.93AF768B@cygnus.com> X-SW-Source: 2001-03/msg00574.html Andrew Cagney 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.