[RFA] delete BLOCK_SHOULD_SORT

[RFA] delete BLOCK_SHOULD_SORT

[David Carlton]

I'd like to delete all occurences of BLOCK_SHOULD_SORT from GDB; it's
really no longer necessary, and will get in the way of my dictionary
work.

The history, as I understand it, is that formerly symbols in blocks
were always stored linearly; but, for blocks where the order didn't
matter, the symbols were sorted to improve search time.  Then blocks
using hashtables were introduced; these are now used almost everywhere
that sorted linear blocks had been previously used.  In particular,
blocks produced by buildsym.c, which is the vast majority of blocks,
will never satisfy BLOCK_SHOULD_SORT.

Right now, I believe that there are only two situations where blocks
satisfying BLOCK_SHOULD_SORT can be produced:

* jv-lang.c builds one such block.  However, despite its satisfying
  the BLOCK_SHOULD_SORT predicate, the block in question _isn't_
  sorted, leading to a special case in lookup_block_symbol().

* mdebugread.c hasn't been converted over to use the buildsym.c
  mechanisms, so it's still producing sorted blocks in some
  situations.

So, basically, making this change will get rid of some cruft, make an
unnoticeable speed improvement to symbol manipulation stuff for normal
usage, and when debugging ECOFF files, symbol table lookup will be a
bit slower.  (But it will still be correct: this is removing an
optimization, but the unoptimized behavior will still work.)  If
anybody out there actually uses ECOFF and is bothered by this, clearly
the best thing would be for that person to convert mdebugread.c to use
the mechanisms in buildsym.c just like every other debugging format
reader.

I think the changes are pretty straightforward, though I'd appreciate
it if somebody more conversant with ada-lang.c than I am could make
sure I'm not missing anything with my change there.

David Carlton
carlton@math.stanford.edu

2002-09-18  David Carlton  <carlton@math.stanford.edu>

	* symtab.h: Delete BLOCK_SHOULD_SORT.
	* symtab.c (lookup_block_symbol): Assume non-hashed blocks aren't
	sorted.
	* ada-lang.c (ada_add_block_symbols): Ditto.
	* symfile.h: Delete prototypes for sort_block_syms and
	sort_symtab_syms.
	* symfile.c: Delete functions sort_block_syms and
	sort_symtab_syms.
	* coffread.c (coff_symfile_read): Remove call to
	sort_symtab_syms.
	* xcoffread.c (xcoff_psymtab_to_symtab_1): Ditto.
	* mdebugread.c (psymtab_to_symtab_1): Ditto.
	* hpread.c (hpread_psymtab_to_symtab_1): Ditto.
	* dwarfread.c (psymtab_to_symtab_1): Ditto.
	* dwarf2read.c (psymtab_to_symtab_1): Ditto.
	* dbxread.c (dbx_psymtab_to_symtab_1): Ditto.

Index: symtab.h
===================================================================
RCS file: /cvs/src/src/gdb/symtab.h,v
retrieving revision 1.39
diff -u -p -r1.39 symtab.h
--- symtab.h	12 Sep 2002 19:19:37 -0000	1.39
+++ symtab.h	18 Sep 2002 20:56:48 -0000
@@ -441,13 +441,6 @@ struct block
 	  for ((sym) = BLOCK_BUCKET ((bl), (i)); (sym);		\
 	       (sym) = (sym)->hash_next)
 
-/* Nonzero if symbols of block BL should be sorted alphabetically.
-   Don't sort a block which corresponds to a function.  If we did the
-   sorting would have to preserve the order of the symbols for the
-   arguments.  Also don't sort any block that we chose to hash.  */
-
-#define BLOCK_SHOULD_SORT(bl) (! BLOCK_HASHTABLE (bl) \
-			       && BLOCK_FUNCTION (bl) == NULL)
 \f
 
 /* Represent one symbol name; a variable, constant, function or typedef.  */

Index: symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.69
diff -u -p -r1.69 symtab.c
--- symtab.c	30 Aug 2002 03:24:00 -0000	1.69
+++ symtab.c	18 Sep 2002 20:56:53 -0000
@@ -1334,10 +1334,9 @@ lookup_block_symbol (register const stru
 		     const char *mangled_name,
 		     const namespace_enum namespace)
 {
-  register int bot, top, inc;
+  register int bot, top;
   register struct symbol *sym;
   register struct symbol *sym_found = NULL;
-  register int do_linear_search = 1;
 
   if (BLOCK_HASHTABLE (block))
     {
@@ -1354,103 +1353,27 @@ lookup_block_symbol (register const stru
 	}
       return NULL;
     }
-
-  /* If the blocks's symbols were sorted, start with a binary search.  */
-
-  if (BLOCK_SHOULD_SORT (block))
-    {
-      /* Reset the linear search flag so if the binary search fails, we
-         won't do the linear search once unless we find some reason to
-         do so */
-
-      do_linear_search = 0;
-      top = BLOCK_NSYMS (block);
-      bot = 0;
-
-      /* Advance BOT to not far before the first symbol whose name is NAME. */
-
-      while (1)
-	{
-	  inc = (top - bot + 1);
-	  /* No need to keep binary searching for the last few bits worth.  */
-	  if (inc < 4)
-	    {
-	      break;
-	    }
-	  inc = (inc >> 1) + bot;
-	  sym = BLOCK_SYM (block, inc);
-	  if (!do_linear_search && (SYMBOL_LANGUAGE (sym) == language_java))
-	    {
-	      do_linear_search = 1;
-	    }
-	  if (SYMBOL_SOURCE_NAME (sym)[0] < name[0])
-	    {
-	      bot = inc;
-	    }
-	  else if (SYMBOL_SOURCE_NAME (sym)[0] > name[0])
-	    {
-	      top = inc;
-	    }
-	  else if (strcmp (SYMBOL_SOURCE_NAME (sym), name) < 0)
-	    {
-	      bot = inc;
-	    }
-	  else
-	    {
-	      top = inc;
-	    }
-	}
-
-      /* Now scan forward until we run out of symbols, find one whose
-         name is greater than NAME, or find one we want.  If there is
-         more than one symbol with the right name and namespace, we
-         return the first one; I believe it is now impossible for us
-         to encounter two symbols with the same name and namespace
-         here, because blocks containing argument symbols are no
-         longer sorted.  The exception is for C++, where multiple functions
-	 (cloned constructors / destructors, in particular) can have
-	 the same demangled name.  So if we have a particular
-	 mangled name to match, try to do so.  */
-
-      top = BLOCK_NSYMS (block);
-      while (bot < top)
-	{
-	  sym = BLOCK_SYM (block, bot);
-	  if (SYMBOL_NAMESPACE (sym) == namespace
-	      && (mangled_name
-		  ? strcmp (SYMBOL_NAME (sym), mangled_name) == 0
-		  : SYMBOL_MATCHES_NAME (sym, name)))
-	    {
-	      return sym;
-	    }
-          if (SYMBOL_SOURCE_NAME (sym)[0] > name[0])
-            {
-              break;
-            }
-	  bot++;
-	}
-    }
-
-  /* Here if block isn't sorted, or we fail to find a match during the
-     binary search above.  If during the binary search above, we find a
-     symbol which is a Java symbol, then we have re-enabled the linear
-     search flag which was reset when starting the binary search.
-
-     This loop is equivalent to the loop above, but hacked greatly for speed.
-
-     Note that parameter symbols do not always show up last in the
-     list; this loop makes sure to take anything else other than
-     parameter symbols first; it only uses parameter symbols as a
-     last resort.  Note that this only takes up extra computation
-     time on a match.  */
-
-  if (do_linear_search)
+  else
     {
+      /* Note that parameter symbols do not always show up last in the
+	 list.  This loop makes sure to take anything else other than
+	 parameter symbols first; it only uses parameter symbols as a
+	 last resort.  Note that this only takes up extra computation
+	 time on a match.  */
       top = BLOCK_NSYMS (block);
       bot = 0;
       while (bot < top)
 	{
 	  sym = BLOCK_SYM (block, bot);
+	  /* If there is more than one symbol with the right name and
+	     namespace, we return the first one; I believe it is now
+	     impossible for us to encounter two symbols with the same
+	     name and namespace here, because blocks containing
+	     argument symbols are no longer sorted.  The exception is
+	     for C++, where multiple functions (cloned constructors /
+	     destructors, in particular) can have the same demangled
+	     name.  So if we have a particular mangled name to match,
+	     try to do so.  */
 	  if (SYMBOL_NAMESPACE (sym) == namespace
 	      && (mangled_name
 		  ? strcmp (SYMBOL_NAME (sym), mangled_name) == 0
@@ -1492,8 +1415,8 @@ lookup_block_symbol (register const stru
 	    }
 	  bot++;
 	}
+      return (sym_found);		/* Will be NULL if not found. */
     }
-  return (sym_found);		/* Will be NULL if not found. */
 }
 
 /* Given a main symbol SYM and ADDR, search through the alias

Index: ada-lang.c
===================================================================
RCS file: /cvs/src/src/gdb/ada-lang.c,v
retrieving revision 1.9
diff -u -p -r1.9 ada-lang.c
--- ada-lang.c	8 Sep 2002 17:43:26 -0000	1.9
+++ ada-lang.c	18 Sep 2002 20:53:52 -0000
@@ -3949,7 +3949,6 @@ ada_add_block_symbols (struct block *blo
   struct symbol *arg_sym;
   /* Set true when we find a matching non-argument symbol */
   int found_sym;
-  int is_sorted = BLOCK_SHOULD_SORT (block);
   struct symbol *sym;
 
   arg_sym = NULL;
@@ -3985,45 +3984,14 @@ ada_add_block_symbols (struct block *blo
     }
   else
     {
-      if (is_sorted)
-	{
-	  int U;
-	  i = 0;
-	  U = BLOCK_NSYMS (block) - 1;
-	  while (U - i > 4)
-	    {
-	      int M = (U + i) >> 1;
-	      struct symbol *sym = BLOCK_SYM (block, M);
-	      if (SYMBOL_NAME (sym)[0] < name[0])
-		i = M + 1;
-	      else if (SYMBOL_NAME (sym)[0] > name[0])
-		U = M - 1;
-	      else if (strcmp (SYMBOL_NAME (sym), name) < 0)
-		i = M + 1;
-	      else
-		U = M;
-	    }
-	}
-      else
-	i = 0;
-
-      for (; i < BLOCK_BUCKETS (block); i += 1)
-	for (sym = BLOCK_BUCKET (block, i); sym != NULL; sym = sym->hash_next)
+      ALL_BLOCK_SYMBOLS (block, i, sym)
 	  {
 	    if (SYMBOL_NAMESPACE (sym) == namespace)
 	      {
 		int cmp = strncmp (name, SYMBOL_NAME (sym), name_len);
 
-		if (cmp < 0)
-		  {
-		    if (is_sorted)
-		      {
-			i = BLOCK_BUCKETS (block);
-			break;
-		      }
-		  }
-		else if (cmp == 0
-			 && is_name_suffix (SYMBOL_NAME (sym) + name_len))
+		if (cmp == 0
+		    && is_name_suffix (SYMBOL_NAME (sym) + name_len))
 		  {
 		    switch (SYMBOL_CLASS (sym))
 		      {
@@ -4059,30 +4027,8 @@ ada_add_block_symbols (struct block *blo
     {
       arg_sym = NULL;
       found_sym = 0;
-      if (is_sorted)
-	{
-	  int U;
-	  i = 0;
-	  U = BLOCK_NSYMS (block) - 1;
-	  while (U - i > 4)
-	    {
-	      int M = (U + i) >> 1;
-	      struct symbol *sym = BLOCK_SYM (block, M);
-	      if (SYMBOL_NAME (sym)[0] < '_')
-		i = M + 1;
-	      else if (SYMBOL_NAME (sym)[0] > '_')
-		U = M - 1;
-	      else if (strcmp (SYMBOL_NAME (sym), "_ada_") < 0)
-		i = M + 1;
-	      else
-		U = M;
-	    }
-	}
-      else
-	i = 0;
 
-      for (; i < BLOCK_BUCKETS (block); i += 1)
-	for (sym = BLOCK_BUCKET (block, i); sym != NULL; sym = sym->hash_next)
+      ALL_BLOCK_SYMBOLS (block, i, sym)
 	  {
 	    struct symbol *sym = BLOCK_SYM (block, i);
 
@@ -4098,16 +4044,8 @@ ada_add_block_symbols (struct block *blo
 		      cmp = strncmp (name, SYMBOL_NAME (sym) + 5, name_len);
 		  }
 
-		if (cmp < 0)
-		  {
-		    if (is_sorted)
-		      {
-			i = BLOCK_BUCKETS (block);
-			break;
-		      }
-		  }
-		else if (cmp == 0
-			 && is_name_suffix (SYMBOL_NAME (sym) + name_len + 5))
+		if (cmp == 0
+		    && is_name_suffix (SYMBOL_NAME (sym) + name_len + 5))
 		  {
 		    switch (SYMBOL_CLASS (sym))
 		      {

Index: symfile.h
===================================================================
RCS file: /cvs/src/src/gdb/symfile.h,v
retrieving revision 1.13
diff -u -p -r1.13 symfile.h
--- symfile.h	22 Apr 2002 10:19:04 -0000	1.13
+++ symfile.h	18 Sep 2002 20:56:41 -0000
@@ -198,12 +198,6 @@ extern struct partial_symtab *start_psym
 						    struct partial_symbol **,
 						    struct partial_symbol **);
 
-/* Sorting your symbols for fast lookup or alphabetical printing.  */
-
-extern void sort_block_syms (struct block *);
-
-extern void sort_symtab_syms (struct symtab *);
-
 /* Make a copy of the string at PTR with SIZE characters in the symbol obstack
    (and add a null character at the end in the copy).
    Returns the address of the copy.  */

Index: symfile.c
===================================================================
RCS file: /cvs/src/src/gdb/symfile.c,v
retrieving revision 1.65
diff -u -p -r1.65 symfile.c
--- symfile.c	1 Aug 2002 17:18:32 -0000	1.65
+++ symfile.c	18 Sep 2002 20:56:34 -0000
@@ -275,38 +275,6 @@ sort_pst_symbols (struct partial_symtab 
 	 compare_psymbols);
 }
 
-/* Call sort_block_syms to sort alphabetically the symbols of one block.  */
-
-void
-sort_block_syms (register struct block *b)
-{
-  qsort (&BLOCK_SYM (b, 0), BLOCK_NSYMS (b),
-	 sizeof (struct symbol *), compare_symbols);
-}
-
-/* Call sort_symtab_syms to sort alphabetically
-   the symbols of each block of one symtab.  */
-
-void
-sort_symtab_syms (register struct symtab *s)
-{
-  register struct blockvector *bv;
-  int nbl;
-  int i;
-  register struct block *b;
-
-  if (s == 0)
-    return;
-  bv = BLOCKVECTOR (s);
-  nbl = BLOCKVECTOR_NBLOCKS (bv);
-  for (i = 0; i < nbl; i++)
-    {
-      b = BLOCKVECTOR_BLOCK (bv, i);
-      if (BLOCK_SHOULD_SORT (b))
-	sort_block_syms (b);
-    }
-}
-
 /* Make a null terminated copy of the string at PTR with SIZE characters in
    the obstack pointed to by OBSTACKP .  Returns the address of the copy.
    Note that the string at PTR does not have to be null terminated, I.E. it

Index: coffread.c
===================================================================
RCS file: /cvs/src/src/gdb/coffread.c,v
retrieving revision 1.29
diff -u -p -r1.29 coffread.c
--- coffread.c	22 Aug 2002 05:50:11 -0000	1.29
+++ coffread.c	18 Sep 2002 20:55:11 -0000
@@ -637,15 +637,6 @@ coff_symfile_read (struct objfile *objfi
 
   coff_symtab_read ((long) symtab_offset, num_symbols, objfile);
 
-  /* Sort symbols alphabetically within each block.  */
-
-  {
-    struct symtab *s;
-
-    for (s = objfile->symtabs; s != NULL; s = s->next)
-      sort_symtab_syms (s);
-  }
-
   /* Install any minimal symbols that have been collected as the current
      minimal symbols for this objfile.  */
 

Index: xcoffread.c
===================================================================
RCS file: /cvs/src/src/gdb/xcoffread.c,v
retrieving revision 1.20
diff -u -p -r1.20 xcoffread.c
--- xcoffread.c	12 Jul 2002 18:30:15 -0000	1.20
+++ xcoffread.c	18 Sep 2002 20:56:59 -0000
@@ -1768,7 +1768,6 @@ xcoff_psymtab_to_symtab_1 (struct partia
       old_chain = make_cleanup (really_free_pendings, 0);
 
       read_xcoff_symtab (pst);
-      sort_symtab_syms (pst->symtab);
 
       do_cleanups (old_chain);
     }

Index: mdebugread.c
===================================================================
RCS file: /cvs/src/src/gdb/mdebugread.c,v
retrieving revision 1.28
diff -u -p -r1.28 mdebugread.c
--- mdebugread.c	29 Jul 2002 22:55:26 -0000	1.28
+++ mdebugread.c	18 Sep 2002 20:56:25 -0000
@@ -3981,10 +3981,6 @@ psymtab_to_symtab_1 (struct partial_symt
 	  end_stabs ();
 	}
 
-      /* Sort the symbol table now, we are done adding symbols to it.
-         We must do this before parse_procedure calls lookup_symbol.  */
-      sort_symtab_syms (st);
-
       /* There used to be a call to sort_blocks here, but this should not
          be necessary for stabs symtabs.  And as sort_blocks modifies the
          start address of the GLOBAL_BLOCK to the FIRST_LOCAL_BLOCK,
@@ -4178,9 +4174,6 @@ psymtab_to_symtab_1 (struct partial_symt
       pop_parse_stack ();
 
       st->primary = 1;
-
-      /* Sort the symbol table now, we are done adding symbols to it. */
-      sort_symtab_syms (st);
 
       sort_blocks (st);
     }

Index: hpread.c
===================================================================
RCS file: /cvs/src/src/gdb/hpread.c,v
retrieving revision 1.22
diff -u -p -r1.22 hpread.c
--- hpread.c	4 Aug 2002 19:11:12 -0000	1.22
+++ hpread.c	18 Sep 2002 20:56:18 -0000
@@ -2729,7 +2729,6 @@ hpread_psymtab_to_symtab_1 (struct parti
 	hpread_expand_symtab (pst->objfile, LDSYMOFF (pst), LDSYMLEN (pst),
 			      pst->textlow, pst->texthigh - pst->textlow,
 			      pst->section_offsets, pst->filename);
-      sort_symtab_syms (pst->symtab);
 
       do_cleanups (old_chain);
     }

Index: dwarfread.c
===================================================================
RCS file: /cvs/src/src/gdb/dwarfread.c,v
retrieving revision 1.14
diff -u -p -r1.14 dwarfread.c
--- dwarfread.c	1 Aug 2002 17:18:32 -0000	1.14
+++ dwarfread.c	18 Sep 2002 20:58:30 -0000
@@ -2364,7 +2364,6 @@ psymtab_to_symtab_1 (struct partial_symt
 		  wrap_here ("");
 		  gdb_flush (gdb_stdout);
 		}
-	      sort_symtab_syms (pst->symtab);
 	      do_cleanups (old_chain);
 	    }
 	  pst->readin = 1;

Index: dwarf2read.c
===================================================================
RCS file: /cvs/src/src/gdb/dwarf2read.c,v
retrieving revision 1.66
diff -u -p -r1.66 dwarf2read.c
--- dwarf2read.c	3 Sep 2002 17:32:11 -0000	1.66
+++ dwarf2read.c	18 Sep 2002 20:56:12 -0000
@@ -1606,7 +1606,6 @@ psymtab_to_symtab_1 (struct partial_symt
     }
   pst->symtab = symtab;
   pst->readin = 1;
-  sort_symtab_syms (pst->symtab);
 
   do_cleanups (back_to);
 }

Index: dbxread.c
===================================================================
RCS file: /cvs/src/src/gdb/dbxread.c,v
retrieving revision 1.34
diff -u -p -r1.34 dbxread.c
--- dbxread.c	29 Jul 2002 22:55:26 -0000	1.34
+++ dbxread.c	18 Sep 2002 20:55:59 -0000
@@ -2477,7 +2477,6 @@ dbx_psymtab_to_symtab_1 (struct partial_
       /* Read in this file's symbols */
       bfd_seek (pst->objfile->obfd, SYMBOL_OFFSET (pst), SEEK_SET);
       read_ofile_symtab (pst);
-      sort_symtab_syms (pst->symtab);
 
       do_cleanups (old_chain);
     }

Re: [RFA] delete BLOCK_SHOULD_SORT

[Daniel Jacobowitz]

On Wed, Sep 18, 2002 at 03:15:40PM -0700, David Carlton wrote:
> I'd like to delete all occurences of BLOCK_SHOULD_SORT from GDB; it's
> really no longer necessary, and will get in the way of my dictionary
> work.
> 
> The history, as I understand it, is that formerly symbols in blocks
> were always stored linearly; but, for blocks where the order didn't
> matter, the symbols were sorted to improve search time.  Then blocks
> using hashtables were introduced; these are now used almost everywhere
> that sorted linear blocks had been previously used.  In particular,
> blocks produced by buildsym.c, which is the vast majority of blocks,
> will never satisfy BLOCK_SHOULD_SORT.

...

> So, basically, making this change will get rid of some cruft, make an
> unnoticeable speed improvement to symbol manipulation stuff for normal
> usage, and when debugging ECOFF files, symbol table lookup will be a
> bit slower.  (But it will still be correct: this is removing an
> optimization, but the unoptimized behavior will still work.)  If
> anybody out there actually uses ECOFF and is bothered by this, clearly
> the best thing would be for that person to convert mdebugread.c to use
> the mechanisms in buildsym.c just like every other debugging format
> reader.
> 
> I think the changes are pretty straightforward, though I'd appreciate
> it if somebody more conversant with ada-lang.c than I am could make
> sure I'm not missing anything with my change there.

For what it's worth, it all looks good (and worth doing!) to me.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: [RFA] delete BLOCK_SHOULD_SORT

[Paul N. Hilfinger]

> I think the changes are pretty straightforward, though I'd appreciate
> it if somebody more conversant with ada-lang.c than I am could make
> sure I'm not missing anything with my change there.

David,

OK; let me explain what Ada is up to in the various places it does
symbol lookup, and you can decide if we (ahem) need a conversation on
this (vis-a-vis this thread or the other "dictionary" threads), or if
our needs introduce no new requirements.

The problem is that some of our symbol lookups essentially require searches for 
regular expressions of the form

    (.*__)?<NAME>(___.*)?

or for 

    <NAME>(___.*)?

Not much you can do about the former, of course, with the current
setup, except scan all symbols, and that's what we do.  The second
pattern, however, can benefit for sorted blocks in an obvious way---
hence the ada-lang.c code you mentioned in an earlier message---but
doesn't need them.  That is, we take advantage of BLOCK_SHOULD_SORT
when possible.  I don't have measurements of the impact of not having
it.  There are obvious ways to use caching when performance becomes a
problem (and we currently use them).

The other property of Ada is that when we have to search global or 
all file-scope symbols, we generally want ALL matches to these patterns, or
ALL matches from a given block.

Paul Hilfinger

Re: [RFA] delete BLOCK_SHOULD_SORT

[Daniel Jacobowitz]

On Thu, Sep 19, 2002 at 01:04:10AM -0700, Paul N. Hilfinger wrote:
> 
> > I think the changes are pretty straightforward, though I'd appreciate
> > it if somebody more conversant with ada-lang.c than I am could make
> > sure I'm not missing anything with my change there.
> 
> David,
> 
> OK; let me explain what Ada is up to in the various places it does
> symbol lookup, and you can decide if we (ahem) need a conversation on
> this (vis-a-vis this thread or the other "dictionary" threads), or if
> our needs introduce no new requirements.
> 
> The problem is that some of our symbol lookups essentially require searches for 
> regular expressions of the form
> 
>     (.*__)?<NAME>(___.*)?
> 
> or for 
> 
>     <NAME>(___.*)?
> 
> Not much you can do about the former, of course, with the current
> setup, except scan all symbols, and that's what we do.  The second
> pattern, however, can benefit for sorted blocks in an obvious way---
> hence the ada-lang.c code you mentioned in an earlier message---but
> doesn't need them.  That is, we take advantage of BLOCK_SHOULD_SORT
> when possible.  I don't have measurements of the impact of not having
> it.  There are obvious ways to use caching when performance becomes a
> problem (and we currently use them).
> 
> The other property of Ada is that when we have to search global or 
> all file-scope symbols, we generally want ALL matches to these patterns, or
> ALL matches from a given block.

Paul, David,

I believe that the right thing to do with this code is actually to
tranform it into calls to search_symbols and let that handle the
details.  We have a regexp symbol matching interface... and it's not
significantly slower, given that almost no symbol tables are sorted now
anyway.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: [RFA] delete BLOCK_SHOULD_SORT

[Andrew Cagney]

> On Thu, Sep 19, 2002 at 01:04:10AM -0700, Paul N. Hilfinger wrote:

> Paul, David,
> 
> I believe that the right thing to do with this code is actually to
> tranform it into calls to search_symbols and let that handle the
> details.  We have a regexp symbol matching interface... and it's not
> significantly slower, given that almost no symbol tables are sorted now
> anyway.

Yes.

If someone comes forward with evidence demonstrating that the lookup is 
a bottle neck, then the symbol database internals can be adjusted to 
address the performance problem.  I don't think core GDB (ignoring 
!@*$(&*#@&$* stabs) should be worried about the table sort order.

David,

Watch out for things like info symbols.  From memory their behavior is 
affected by this - something DanielJ and ElenaZ hit problems with when 
playing with this before.

Andrew

Re: [RFA] delete BLOCK_SHOULD_SORT

[David Carlton]

On Thu, 19 Sep 2002 01:04:10 -0700, "Paul N. Hilfinger" <hilfingr@otisco.mckusick.com> said:

> OK; let me explain what Ada is up to in the various places it does
> symbol lookup, and you can decide if we (ahem) need a conversation
> on this (vis-a-vis this thread or the other "dictionary" threads),
> or if our needs introduce no new requirements.
...
> The second pattern, however, can benefit for sorted blocks in an
> obvious way--- hence the ada-lang.c code you mentioned in an earlier
> message---but doesn't need them.  That is, we take advantage of
> BLOCK_SHOULD_SORT when possible.  I don't have measurements of the
> impact of not having it.

I see; thanks for the explanation.  Then I agree with Daniel: it
should probably be converted to search_symbols, and removing
BLOCK_SHOULD_SORT won't hurt you: the performance gains that you had
been getting were already lost in the earlier conversion from sorted
lists to hashtables, unless the debugging info happens to be in ECOFF
format.  So the only question is whether or not I slipped up when
converting those loops to ALL_BLOCK_SYMBOLS.

David Carlton
carlton@math.stanford.edu

Re: [RFA] delete BLOCK_SHOULD_SORT

[Jim Blandy]

It looks good to me.

However, before we commit this, I'd really like to know how much worse
it makes mdebug-based targets.  For example, if the test suite starts
timing out a lot after this patch is applied because symbol lookup is
so slow, then I think we need to buildsym-ify mdebugread first.
However backwards we may find them, people are still using mdebug, and
making the test suite unusable would make it impossible for a company
like Red Hat to give them a code drop when they need one.

You'll need to be testing your namespace work on at least one
mdebug-based target anyway, so this shouldn't be much of an additional
burden.

> I think the changes are pretty straightforward, though I'd appreciate
> it if somebody more conversant with ada-lang.c than I am could make
> sure I'm not missing anything with my change there.

I don't know ada-lang.c, but they look mechanically correct to me.

>        top = BLOCK_NSYMS (block);
>        bot = 0;
>        while (bot < top)
>  	{
>  	  sym = BLOCK_SYM (block, bot);
> +	  /* If there is more than one symbol with the right name and
> +	     namespace, we return the first one; I believe it is now
> +	     impossible for us to encounter two symbols with the same
> +	     name and namespace here, because blocks containing
> +	     argument symbols are no longer sorted.  The exception is
> +	     for C++, where multiple functions (cloned constructors /
> +	     destructors, in particular) can have the same demangled
> +	     name.  So if we have a particular mangled name to match,
> +	     try to do so.  */

This comment still refers to sorted blocks.  And the rationale for
believing that it won't encounter two symbols with the right name and
namespace doesn't apply any more: this comment isn't describing code
that deals only with sorted blocks any more.  This is the code which
can encounter duplicates.

(It's odd to talk about "namespaces" (by which the comment means
symtab.h's namespace_enum) and C++ in the same paragraph.  It might be
nice to clarify that while you're at it.)