[PATCH] Make completions almost instantaneous

[Daniel Berlin <dberlin at redhat dot com>]

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 ----