From mboxrd@z Thu Jan 1 00:00:00 1970 From: Elena Zannoni To: Daniel Berlin Cc: Subject: Re: [PATCH] Make completions almost instantaneous Date: Fri, 30 Mar 2001 13:46:00 -0000 Message-id: <15044.65201.690950.656246@kwikemart.cygnus.com> References: X-SW-Source: 2001-03/msg00563.html 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 _" , 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 > > * 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 ---- >