[PATCH] Make completions almost instantaneous

[Elena Zannoni]

Ok, Approved. Please check it in.  Just to be anal, I ran the
testsuite on solaris w/o seeing any regressions.

Nice catch.

Thanks
Elena


Daniel Berlin writes:
 > Okay, this has pissed me off for years.
 > You accidently hit tab at the wrong time, and boom, you wait forever for
 > completion to tell you it found 7000 symbols.
 > Literally forever (~29 seconds, 16k symbols takes ~1:30. the program i
 > compliled was one line. Real programs end up with *way* too many symbols.
 > I let one sit for 10 minutes before giving up once, because i didn't want
 > to recreate the situation i had gotten to)
 > 
 > This is all due to a "time optimization" performed in completion_list_add_symbol.
 > 
 > Where time optimization is defined as "To save time, increases the order
 > of magnitude of the algorithm by n, even when unncessary"
 > 
 > What the heck am i talking about?
 > 
 > Well, it clips symbols by running through the entire current completion
 > list, maybe twice, comparing the string we are going to insert against
 > them.
 > 
 > That way, we don't insert duplicates.
 > Of course, this is the wrong way to do it (since you get murdered when
 > your list starts getting large, seeing as how you'll do n-1->2n-2 string
 > compares, just to do *one* insertion)  but seeing as how the code was
 > there, I wasted about 2 hours trying to find a faster way to not insert
 > duplicates (binary search the list of completions, for starters, and then
 > do  a sorted insert using binary search again to find the place, and then
 > memmove to  shift the array up, etc) , and then decided to ignore them
 > and do it at the end, since it was obvious it was all the strcmps and
 > moving was almost as expensive in practice, and thus, it would be better
 > to just do it once in a sort, after we had the entire list, and remove the
 > duplicates
 > 
 > But here's the kicker. When i went to go just make it do one sort at the
 > end, and then just not output/remove  the duplicates, i noticed something:
 > readline already does that (remove_duplicate_matches in complete.c, called
 > from postprocess_matches if rl_ignore_completion_duplicates is 1, which it
 > always is for gdb, since we never turn it off)
 > 
 > In other words, all this god damn time is wasted to make sure we don't
 > insert duplicates, and it won't output duplicates *anyway*, because it
 > removes duplicate matches (strangely, using almost exactly the same code i
 > had been ready to add, minus the binary search).
 > 
 > Result:
 > pushing tab twice at the wrong time used to take 1:30 if it
 > geenrated
 > 16k completions (I compiled a very minimal c++, broke on main, ran, and
 > hit "b " tab. I also did the same for "b _" <tab>, which gives me 7k
 > completions).
 > It now takes ~3 seconds.
 > 
 > I'm not joking.
 > 
 > There's obviously no difference in the output, since it was removing
 > duplicates anyway.
 > 
 > No longer do i kill off gdbs because it's faster to re set 15 breakpoints
 > than wait for completion to tell me i screwed up.
 > 
 > 
 > All this patch does is remove code.
 > 
 > Remember kids, premature optimization is the root of all evil.
 > 
 > Since it's unclear to me whether this is an obvious fix, i'll wait for
 > approval from Elena or Jim.
 > 
 > --Dan
 > 
 > 2001-03-30  Daniel Berlin  <dberlin@redhat.com>
 > 
 > 	* symtab.c (completion_list_add_name): Remove duplicate string checks,
 > 	readline already does this, and it's much faster at it, too.
 > 
 > Index: symtab.c
 > ===================================================================
 > RCS file: /cvs/src/src/gdb/symtab.c,v
 > retrieving revision 1.28
 > diff -c -3 -p -r1.28 symtab.c
 > *** symtab.c	2001/01/30 02:49:36	1.28
 > --- symtab.c	2001/03/30 08:48:30
 > *************** completion_list_add_name (char *symname,
 > *** 2836,2852 ****
 >         return;
 >       }
 > 
 > -   /* 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;
 > - 	}
 > -     }
 > -
 >     /* We have a match for a completion, so add SYMNAME to the current list
 >        of matches. Note that the name is moved to freshly malloc'd space. */
 > 
 > --- 2869,2874 ----
 > *************** completion_list_add_name (char *symname,
 > *** 2870,2888 ****
 >   	strncpy (new, word, sym_text - word);
 >   	new[sym_text - word] = '\0';
 >   	strcat (new, symname);
 > -       }
 > -
 > -     /* Recheck for duplicates if we intend to add a modified symbol.  */
 > -     if (word != sym_text)
 > -       {
 > - 	for (i = 0; i < return_val_index; ++i)
 > - 	  {
 > - 	    if (STREQ (new, return_val[i]))
 > - 	      {
 > - 		xfree (new);
 > - 		return;
 > - 	      }
 > - 	  }
 >         }
 > 
 >       if (return_val_index + 3 > return_val_size)
 > --- 2892,2897 ----
 >