Re: [rfa] Remove a silly looking symtab sort.

Re: [rfa] Remove a silly looking symtab sort.

[Elena Zannoni]

Daniel Berlin wrote:
> 
> > Daniel, I would prefer for the output of these functions to remain
> > sorted.
> 
> > If this is something necessary, wouldn't the hashing break it?
> No, we specifically test whether it is a function (and thus, the block is
> it's arguments) when building the blocks, and don't hash the argument
> blocks.
> They remain in the normal order.
> 

Ah, yes, I see that in the next patch.

Elena

Re: [rfa] Remove a silly looking symtab sort.

[Daniel Berlin]

>
> I am not sure about the reason for the 40 limit. Wonder what would
> happen if we got rid of that check. It predates our internal cvs repo
> (i.e. it has been there from before 1991).
I'm guessing It's only really there because it's slower to
sort 40 symbols  than it is to look through them.  We probably ended up
sorting a ton of  1-10 symbol small blocks for no good reason, wasting
tons of time during reading.

--Dan

Re: [rfa] Remove a silly looking symtab sort.

[Elena Zannoni]

Daniel Jacobowitz wrote:
> 
> On Mon, Nov 05, 2001 at 05:19:06PM -0500, Elena Zannoni wrote:
> >
> >
> > Daniel Jacobowitz wrote:
> > >
> > > The function search_symbols () does not seem to be used anywhere where
> > > the
> > > order of the returned functions matters, and the algorithm it searches
> > > with
> > > does not rely on any sorting.  The same thing seems to be true for
> > > gdb_listfuncs, but I haven't investigated as thoroughly.
> > >
> > > Both of these functions have a blurb like:
> > >   if (!BLOCK_SHOULD_SORT (b))
> > >     sort_block_syms (b);
> > >
> >
> > Daniel, I would prefer for the output of these functions to remain
> > sorted.
> > >From the gdb side, this produces sorted 'info function', 'info var',
> > 'info types' output, and from the gdbtk side, it builds the contents
> > of the function combobox at the bottom of the source window.
> 
> This makes sense.  It's not terribly well sorted to begin with, though,
> which is why I didn't sort them in the first version of this patch:
> 
> ALL_SYMTABS (objfile, s)
>  ...
>    for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
>      ...
>           if (!BLOCK_SHOULD_SORT (b))
>             sort_block_syms (b);
> 
> I.E.  they're only locally sorted.  I could be misinterpreting what is
> done with them though.
> 

Looking at the output of 'info function' they are sorted
alphabetically per compilation unit. Well, that maybe depends on the
particular executable I have used. But yes they are locally sorted.


> >     /* The symbols.  If some of them are arguments, then they must be
> >        in the order in which we would like to print them.  */
> >
> > and the comment for BLOCK_SHOULD_SORT:
> >
> > /* 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.  */
> >
> >
> > If this is something necessary, wouldn't the hashing break it?
> > I am not sure what would be screwed up based on the order of the
> > arguments, though.
> 
> > I agree that sorting something that was hashed makes no sense, but we
> > are
> > one step before that still. I would like to figure out why that change
> > by
> > Peter was necessary. I think it has to do with the fact that stabs emits
> > two symbols for each parameter (I don't have the stabs manual handy
> > at the moment).
> >
> 
> This is what confuses me.  I couldn't find where the symtab for a
> function block would be used in any order-sensitive way.  Reading the
> code in the attached patch reminds me, though.  Here's an example of
> what I think this is supposed to address:
> 
> int
> foo (int a, int b)
> {
>   return a / b;
> }
> 
> becomes:
> 
>         .align 4
> .stabs "foo:F(0,1)",36,0,0,foo
> .stabs "a:p(0,1)",160,0,0,8
> .stabs "b:p(0,1)",160,0,0,12
> .globl foo
>         .type    foo,@function
> foo:
>         pushl %ebp
>         movl %esp,%ebp
> .stabn 68,0,3,.LM1-foo
> .LM1:
>         movl 8(%ebp),%eax
> .stabn 68,0,4,.LM2-foo
> .LM2:
>         cltd
>         idivl 12(%ebp)
>         leave
>         ret
> .Lfe1:
>         .size    foo,.Lfe1-foo
> .stabs "a:r(0,1)",64,0,0,0
> 
> We read in the symtab and see this (s->blockvector->block[3] is the
> block for function foo):
> 
> (top-gdb) p *s->blockvector->block[3].sym[0]
> $16 = {ginfo = {name = 0x82328c8 "a", value = {ivalue = 8, block = 0x8,
>       bytes = 0x8 <Address 0x8 out of bounds>, address = 8, chain = 0x8}, language_specific = {
>       cplus_specific = {demangled_name = 0x0}, chill_specific = {demangled_name = 0x0}},
>     language = language_c, section = 0, bfd_section = 0x0}, type = 0x8232ae8,
>   namespace = VAR_NAMESPACE, aclass = LOC_ARG, line = 0, aux_value = {basereg = 0}, aliases = 0x0,
>   ranges = 0x0}
> (top-gdb) p *s->blockvector->block[3].sym[1]
> $17 = {ginfo = {name = 0x82328fc "b", value = {ivalue = 12, block = 0xc,
>       bytes = 0xc <Address 0xc out of bounds>, address = 12, chain = 0xc}, language_specific = {
>       cplus_specific = {demangled_name = 0x0}, chill_specific = {demangled_name = 0x0}},
>     language = language_c, section = 0, bfd_section = 0x0}, type = 0x8232ae8,
>   namespace = VAR_NAMESPACE, aclass = LOC_ARG, line = 0, aux_value = {basereg = 0}, aliases = 0x0,
>   ranges = 0x0}
> (top-gdb) p *s->blockvector->block[3].sym[2]
> $18 = {ginfo = {name = 0x8232930 "a", value = {ivalue = 0, block = 0x0, bytes = 0x0, address = 0,
>       chain = 0x0}, language_specific = {cplus_specific = {demangled_name = 0x0}, chill_specific = {
>         demangled_name = 0x0}}, language = language_c, section = 0, bfd_section = 0x0},
>   type = 0x8232ae8, namespace = VAR_NAMESPACE, aclass = LOC_REGISTER, line = 0, aux_value = {
>     basereg = 0}, aliases = 0x0, ranges = 0x0}
> 
> Note LOC_ARG and LOC_REGISTER in those.  We want to look it up in the
> context of the function and find that it is an argument, not a local.
> 
> ... aha.  I see why the sort is OK now.  This makes a lot more sense.
> The for loop is on the range [GLOBAL_BLOCK, STATIC_BLOCK] - i.e. it
> will never hit a function block.  So it's only interested in the <= 40
> check, which seems to be some sort of optimization.

Ah, yes. GLOBAL_BLOCK and STATIC_BLOCK only, no function blocks.

I am not sure about the reason for the 40 limit. Wonder what would
happen if we got rid of that check. It predates our internal cvs repo 
(i.e. it has been there from before 1991).

I think that the comments from Peter Schauer indicated that the REGISTER 
should come first. 

OK, I took out the stabs manual...  It says that if a parameter is
passed on the stack, then there is only one stab symbol for it, but if
it is passed in a register there are 2 symbols, like in your
example. One is the 'p' stab to indicate that it is a parameter, the
second is an 'r' stab to indicate it is in a register.  Quoting:
"Debuggers use the second one to find the value, and the first one to
know that it is an argument".

Arguments stored as local variables by the compiler are treated
similarly, with a 'p' symbol and an 'r' symbol.

The manual also says that the stabs for the parameters are in the
order in which the debugger should print them. Hence the 'don't sort'
requirement.

> 
> So I feel safe changing this code to not sort the blocks, and then sort
> the results afterwards, using compare_symbol.


Yes.

> 
> > > Is this patch OK to commit?  If someone disagrees with my assessment on
> > > the
> > > need for the results of these functions to be sorted, I can add code to
> > > sort
> > > them after searching.
> > >
> >
> > In theory it would be ok because the symbols shouldn't be sorted at
> > this stage. So we should sort the results instead.
> > If you can write something to sort the results we can get rid of these
> > sorts. Well, the one in symtab.c, the gdbtk one is not for me to
> > approve.
> 
> I'd be willing to commit the one to gdbtk as obvious, esp. since no one
> commented on it; the code is essentially a copy of the one in symtab.c.
> 

I don't want to step on anybody's toes. (CC-ing Keith...)

> > But before we go ahead with the hashing I want to understand the need
> > for
> > that condition on sorting. Have you tried the hashing on stabs?
> 
> Yup.
> 
> So, OK if I sort the results afterwards?
> 


Yep!

Elena

> --
> Daniel Jacobowitz                           Carnegie Mellon University
> MontaVista Software                         Debian GNU/Linux Developer

Re: [rfa] Remove a silly looking symtab sort.

[Daniel Berlin]

> Daniel, I would prefer for the output of these functions to remain
> sorted.

> If this is something necessary, wouldn't the hashing break it?
No, we specifically test whether it is a function (and thus, the block is
it's arguments) when building the blocks, and don't hash the argument
blocks.
They remain in the normal order.

> I am not sure what would be screwed up based on the order of the
> arguments, though.
>
> Looking at our internal repository, I can see that this 'do not sort'
> was introduced by Peter Schauer in 1993:
>
> Index: symtab.h
> ===================================================================
> RCS file: /cvs/cvsfiles/devo/gdb/symtab.h,v
> retrieving revision 1.69
> retrieving revision 1.70
> diff -u -r1.69 -r1.70
> --- symtab.h    1993/06/29 16:55:29     1.69
> +++ symtab.h    1993/06/29 20:18:41     1.70
> @@ -385,9 +385,12 @@
>  #define BLOCK_SUPERBLOCK(bl)   (bl)->superblock
>  #define BLOCK_GCC_COMPILED(bl) (bl)->gcc_compile_flag
>
> -/* Nonzero if symbols of block BL should be sorted alphabetically.  */
> +/* 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.  */
>
> -#define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40)
> +#define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40 && BLOCK_FUNCTION (bl)
> == NULL
> )
>
> Index: symfile.c
> ===================================================================
> RCS file: /cvs/cvsfiles/devo/gdb/symfile.c,v
> retrieving revision 1.82
> retrieving revision 1.83
> diff -u -p -r1.82 -r1.83
> --- symfile.c   1993/06/14 20:49:40     1.82
> +++ symfile.c   1993/06/29 20:18:35     1.83
> @@ -111,12 +111,7 @@ int symbol_reloading = 0;
>  #endif
>
>  ?
> -/* In the following sort, we always make sure that
> -   register debug symbol declarations always come before regular
> -   debug symbol declarations (as might happen when parameters are
> -   then put into registers by the compiler).
> -
> -   Since this function is called from within qsort, in an ANSI
> environment
> +/* Since this function is called from within qsort, in an ANSI
> environment
>     it must conform to the prototype for qsort, which specifies that the
>     comparison function takes two "void *" pointers. */
>
> @@ -126,17 +121,11 @@ compare_symbols (s1p, s2p)
>       const PTR s2p;
>  {
>    register struct symbol **s1, **s2;
> -  register int namediff;
>
>    s1 = (struct symbol **) s1p;
>    s2 = (struct symbol **) s2p;
> -
> -  namediff = STRCMP (SYMBOL_NAME (*s1), SYMBOL_NAME (*s2));
> -  if (namediff != 0) return namediff;
>
> -  /* For symbols of the same name, registers should come first.  */
> -  return ((SYMBOL_CLASS (*s2) == LOC_REGISTER)
> -         - (SYMBOL_CLASS (*s1) == LOC_REGISTER));
> +  return (STRCMP (SYMBOL_NAME (*s1), SYMBOL_NAME (*s2)));
>  }
>
> Index: symtab.c
> ===================================================================
> RCS file: /cvs/cvsfiles/devo/gdb/symtab.c,v
> retrieving revision 1.88
> retrieving revision 1.89
> diff -u -r1.88 -r1.89
> --- symtab.c    1993/06/25 03:47:17     1.88
> +++ symtab.c    1993/06/29 20:18:38     1.89
> @@ -839,8 +839,8 @@
>        /* 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.
> -        dbxread.c is careful to make sure that if one is a register
> then it
> -        comes first.  */
> +        Blocks containing argument symbols are no longer sorted so this
> +        doesn't matter.  */
>
>        top = BLOCK_NSYMS (block);
>        while (bot < top)
>
>
> > In that latter case, we certainly should not sort the symtab.  I have
> > never
> > run across this in practice, but the symbol hashing patch wants this to
> > be
> > cleaned up first.  Sorting a hash table's buckets is bad, mmkay?
> >
>
>
> I agree that sorting something that was hashed makes no sense, but we
> are
> one step before that still. I would like to figure out why that change
> by
> Peter was necessary. I think it has to do with the fact that stabs emits
> two symbols for each parameter (I don't have the stabs manual handy
> at the moment).
>
> > Is this patch OK to commit?  If someone disagrees with my assessment on
> > the
> > need for the results of these functions to be sorted, I can add code to
> > sort
> > them after searching.
> >
>
> In theory it would be ok because the symbols shouldn't be sorted at
> this stage. So we should sort the results instead.
> If you can write something to sort the results we can get rid of these
> sorts. Well, the one in symtab.c, the gdbtk one is not for me to
> approve.
>
> But before we go ahead with the hashing I want to understand the need
> for
> that condition on sorting. Have you tried the hashing on stabs?
>
>
> Elena
>
>
> > --
> > Daniel Jacobowitz                           Carnegie Mellon University
> > MontaVista Software                         Debian GNU/Linux Developer
> >
> > 2001-10-25  Daniel Jacobowitz  <drow@mvista.com>
> >
> >         * symtab.c (search_symbols): Do not attempt to sort a block
> >         if !BLOCK_SHOULD_SORT (b).
> >
> > 2001-10-25  Daniel Jacobowitz  <drow@mvista.com>
> >
> >         * generic/gdbtk-cmds (gdb_listfuncs): Do not attempt to sort a
> > block
> >         if !BLOCK_SHOULD_SORT (b).
> >
> > Index: gdb/symtab.c
> > ===================================================================
> > RCS file: /cvs/src/src/gdb/symtab.c,v
> > retrieving revision 1.44
> > diff -u -p -r1.44 symtab.c
> > --- gdb/symtab.c        2001/10/12 23:51:29     1.44
> > +++ gdb/symtab.c        2001/10/25 04:23:05
> > @@ -2475,9 +2475,6 @@ search_symbols (char *regexp, namespace_
> >        for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
> >         {
> >           b = BLOCKVECTOR_BLOCK (bv, i);
> > -         /* Skip the sort if this block is always sorted.  */
> > -         if (!BLOCK_SHOULD_SORT (b))
> > -           sort_block_syms (b);
> >           for (j = 0; j < BLOCK_NSYMS (b); j++)
> >             {
> >               QUIT;
> > Index: gdb/gdbtk/generic/gdbtk-cmds.c
> > ===================================================================
> > RCS file: /cvs/src/src/gdb/gdbtk/generic/gdbtk-cmds.c,v
> > retrieving revision 1.40
> > diff -u -p -r1.40 gdbtk-cmds.c
> > --- gdb/gdbtk/generic/gdbtk-cmds.c      2001/10/12 23:51:29     1.40
> > +++ gdb/gdbtk/generic/gdbtk-cmds.c      2001/10/25 04:23:06
> > @@ -1495,9 +1495,6 @@ gdb_listfuncs (clientData, interp, objc,
> >    for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
> >      {
> >        b = BLOCKVECTOR_BLOCK (bv, i);
> > -      /* Skip the sort if this block is always sorted.  */
> > -      if (!BLOCK_SHOULD_SORT (b))
> > -       sort_block_syms (b);
> >        ALL_BLOCK_SYMBOLS (b, j, sym)
> >         {
> >           if (SYMBOL_CLASS (sym) == LOC_BLOCK)
>

Re: [rfa] Remove a silly looking symtab sort.

[Daniel Jacobowitz]

On Mon, Nov 05, 2001 at 05:19:06PM -0500, Elena Zannoni wrote:
> 
> 
> Daniel Jacobowitz wrote:
> > 
> > The function search_symbols () does not seem to be used anywhere where
> > the
> > order of the returned functions matters, and the algorithm it searches
> > with
> > does not rely on any sorting.  The same thing seems to be true for
> > gdb_listfuncs, but I haven't investigated as thoroughly.
> > 
> > Both of these functions have a blurb like:
> >   if (!BLOCK_SHOULD_SORT (b))
> >     sort_block_syms (b);
> > 
> 
> Daniel, I would prefer for the output of these functions to remain
> sorted.
> >From the gdb side, this produces sorted 'info function', 'info var', 
> 'info types' output, and from the gdbtk side, it builds the contents 
> of the function combobox at the bottom of the source window.

This makes sense.  It's not terribly well sorted to begin with, though,
which is why I didn't sort them in the first version of this patch:

ALL_SYMTABS (objfile, s)
 ... 
   for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
     ...
          if (!BLOCK_SHOULD_SORT (b))
            sort_block_syms (b);

I.E.  they're only locally sorted.  I could be misinterpreting what is
done with them though.

>     /* The symbols.  If some of them are arguments, then they must be
>        in the order in which we would like to print them.  */
> 
> and the comment for BLOCK_SHOULD_SORT:
> 
> /* 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.  */
> 
> 
> If this is something necessary, wouldn't the hashing break it?
> I am not sure what would be screwed up based on the order of the
> arguments, though.

> I agree that sorting something that was hashed makes no sense, but we
> are
> one step before that still. I would like to figure out why that change
> by
> Peter was necessary. I think it has to do with the fact that stabs emits
> two symbols for each parameter (I don't have the stabs manual handy 
> at the moment).
> 

This is what confuses me.  I couldn't find where the symtab for a
function block would be used in any order-sensitive way.  Reading the
code in the attached patch reminds me, though.  Here's an example of
what I think this is supposed to address:

int
foo (int a, int b)
{
  return a / b;
}

becomes:

        .align 4
.stabs "foo:F(0,1)",36,0,0,foo
.stabs "a:p(0,1)",160,0,0,8
.stabs "b:p(0,1)",160,0,0,12
.globl foo
        .type    foo,@function
foo:
        pushl %ebp
        movl %esp,%ebp
.stabn 68,0,3,.LM1-foo
.LM1:   
        movl 8(%ebp),%eax
.stabn 68,0,4,.LM2-foo
.LM2:   
        cltd
        idivl 12(%ebp)
        leave
        ret
.Lfe1:  
        .size    foo,.Lfe1-foo
.stabs "a:r(0,1)",64,0,0,0


We read in the symtab and see this (s->blockvector->block[3] is the
block for function foo):

(top-gdb) p *s->blockvector->block[3].sym[0]
$16 = {ginfo = {name = 0x82328c8 "a", value = {ivalue = 8, block = 0x8,
      bytes = 0x8 <Address 0x8 out of bounds>, address = 8, chain = 0x8}, language_specific = {
      cplus_specific = {demangled_name = 0x0}, chill_specific = {demangled_name = 0x0}},
    language = language_c, section = 0, bfd_section = 0x0}, type = 0x8232ae8,
  namespace = VAR_NAMESPACE, aclass = LOC_ARG, line = 0, aux_value = {basereg = 0}, aliases = 0x0,
  ranges = 0x0}
(top-gdb) p *s->blockvector->block[3].sym[1]
$17 = {ginfo = {name = 0x82328fc "b", value = {ivalue = 12, block = 0xc,
      bytes = 0xc <Address 0xc out of bounds>, address = 12, chain = 0xc}, language_specific = {
      cplus_specific = {demangled_name = 0x0}, chill_specific = {demangled_name = 0x0}},
    language = language_c, section = 0, bfd_section = 0x0}, type = 0x8232ae8,
  namespace = VAR_NAMESPACE, aclass = LOC_ARG, line = 0, aux_value = {basereg = 0}, aliases = 0x0,
  ranges = 0x0}
(top-gdb) p *s->blockvector->block[3].sym[2]
$18 = {ginfo = {name = 0x8232930 "a", value = {ivalue = 0, block = 0x0, bytes = 0x0, address = 0,
      chain = 0x0}, language_specific = {cplus_specific = {demangled_name = 0x0}, chill_specific = {
        demangled_name = 0x0}}, language = language_c, section = 0, bfd_section = 0x0},
  type = 0x8232ae8, namespace = VAR_NAMESPACE, aclass = LOC_REGISTER, line = 0, aux_value = {
    basereg = 0}, aliases = 0x0, ranges = 0x0}

Note LOC_ARG and LOC_REGISTER in those.  We want to look it up in the
context of the function and find that it is an argument, not a local.



... aha.  I see why the sort is OK now.  This makes a lot more sense. 
The for loop is on the range [GLOBAL_BLOCK, STATIC_BLOCK] - i.e. it
will never hit a function block.  So it's only interested in the <= 40
check, which seems to be some sort of optimization.

So I feel safe changing this code to not sort the blocks, and then sort
the results afterwards, using compare_symbol.

> > Is this patch OK to commit?  If someone disagrees with my assessment on
> > the
> > need for the results of these functions to be sorted, I can add code to
> > sort
> > them after searching.
> > 
> 
> In theory it would be ok because the symbols shouldn't be sorted at 
> this stage. So we should sort the results instead.
> If you can write something to sort the results we can get rid of these
> sorts. Well, the one in symtab.c, the gdbtk one is not for me to
> approve.

I'd be willing to commit the one to gdbtk as obvious, esp. since no one
commented on it; the code is essentially a copy of the one in symtab.c.

> But before we go ahead with the hashing I want to understand the need
> for
> that condition on sorting. Have you tried the hashing on stabs?

Yup.

So, OK if I sort the results afterwards?

-- 
Daniel Jacobowitz                           Carnegie Mellon University
MontaVista Software                         Debian GNU/Linux Developer

Re: [rfa] Remove a silly looking symtab sort.

[Elena Zannoni]

Daniel Jacobowitz wrote:
> 
> The function search_symbols () does not seem to be used anywhere where
> the
> order of the returned functions matters, and the algorithm it searches
> with
> does not rely on any sorting.  The same thing seems to be true for
> gdb_listfuncs, but I haven't investigated as thoroughly.
> 
> Both of these functions have a blurb like:
>   if (!BLOCK_SHOULD_SORT (b))
>     sort_block_syms (b);
> 

Daniel, I would prefer for the output of these functions to remain
sorted.
From the gdb side, this produces sorted 'info function', 'info var', 
'info types' output, and from the gdbtk side, it builds the contents 
of the function combobox at the bottom of the source window.

> Note that this isn't something like "! BLOCK_SORTED" - it's "!
> BLOCK_SHOULD_SORT".  The condition for that currently is
> 
> #define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40 && BLOCK_FUNCTION (bl)
> == NULL)
> 

Yes, definitely this looks odd. We haven't sorted that block
before (while building the symtabs) but we are sorting it now. So, 
then, why bother with BLOCK_SHOULD_SORT in the first place? Basically
doing an 'info function' command changes the structure of the symtabs.
Seems wrong to me.

However, there are a couple of comments in symtab.h that make me think
we need to preserve the order of the symbols to preserve the position 
of the arguments:

    /* The symbols.  If some of them are arguments, then they must be
       in the order in which we would like to print them.  */

and the comment for BLOCK_SHOULD_SORT:

/* 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.  */


If this is something necessary, wouldn't the hashing break it?
I am not sure what would be screwed up based on the order of the
arguments, though.

Looking at our internal repository, I can see that this 'do not sort'
was introduced by Peter Schauer in 1993:

Index: symtab.h
===================================================================
RCS file: /cvs/cvsfiles/devo/gdb/symtab.h,v
retrieving revision 1.69
retrieving revision 1.70
diff -u -r1.69 -r1.70
--- symtab.h    1993/06/29 16:55:29     1.69
+++ symtab.h    1993/06/29 20:18:41     1.70
@@ -385,9 +385,12 @@
 #define BLOCK_SUPERBLOCK(bl)   (bl)->superblock
 #define BLOCK_GCC_COMPILED(bl) (bl)->gcc_compile_flag

-/* Nonzero if symbols of block BL should be sorted alphabetically.  */
+/* 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.  */

-#define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40)
+#define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40 && BLOCK_FUNCTION (bl)
== NULL
)

Index: symfile.c
===================================================================
RCS file: /cvs/cvsfiles/devo/gdb/symfile.c,v
retrieving revision 1.82
retrieving revision 1.83
diff -u -p -r1.82 -r1.83
--- symfile.c   1993/06/14 20:49:40     1.82
+++ symfile.c   1993/06/29 20:18:35     1.83
@@ -111,12 +111,7 @@ int symbol_reloading = 0;
 #endif

 ?
-/* In the following sort, we always make sure that
-   register debug symbol declarations always come before regular
-   debug symbol declarations (as might happen when parameters are
-   then put into registers by the compiler).
-
-   Since this function is called from within qsort, in an ANSI
environment
+/* Since this function is called from within qsort, in an ANSI
environment
    it must conform to the prototype for qsort, which specifies that the
    comparison function takes two "void *" pointers. */

@@ -126,17 +121,11 @@ compare_symbols (s1p, s2p)
      const PTR s2p;
 {
   register struct symbol **s1, **s2;
-  register int namediff;

   s1 = (struct symbol **) s1p;
   s2 = (struct symbol **) s2p;
-
-  namediff = STRCMP (SYMBOL_NAME (*s1), SYMBOL_NAME (*s2));
-  if (namediff != 0) return namediff;

-  /* For symbols of the same name, registers should come first.  */
-  return ((SYMBOL_CLASS (*s2) == LOC_REGISTER)
-         - (SYMBOL_CLASS (*s1) == LOC_REGISTER));
+  return (STRCMP (SYMBOL_NAME (*s1), SYMBOL_NAME (*s2)));
 }

Index: symtab.c
===================================================================
RCS file: /cvs/cvsfiles/devo/gdb/symtab.c,v
retrieving revision 1.88
retrieving revision 1.89
diff -u -r1.88 -r1.89
--- symtab.c    1993/06/25 03:47:17     1.88
+++ symtab.c    1993/06/29 20:18:38     1.89
@@ -839,8 +839,8 @@
       /* 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.
-        dbxread.c is careful to make sure that if one is a register
then it
-        comes first.  */
+        Blocks containing argument symbols are no longer sorted so this
+        doesn't matter.  */

       top = BLOCK_NSYMS (block);
       while (bot < top)


> In that latter case, we certainly should not sort the symtab.  I have
> never
> run across this in practice, but the symbol hashing patch wants this to
> be
> cleaned up first.  Sorting a hash table's buckets is bad, mmkay?
> 


I agree that sorting something that was hashed makes no sense, but we
are
one step before that still. I would like to figure out why that change
by
Peter was necessary. I think it has to do with the fact that stabs emits
two symbols for each parameter (I don't have the stabs manual handy 
at the moment).

> Is this patch OK to commit?  If someone disagrees with my assessment on
> the
> need for the results of these functions to be sorted, I can add code to
> sort
> them after searching.
> 

In theory it would be ok because the symbols shouldn't be sorted at 
this stage. So we should sort the results instead.
If you can write something to sort the results we can get rid of these
sorts. Well, the one in symtab.c, the gdbtk one is not for me to
approve.

But before we go ahead with the hashing I want to understand the need
for
that condition on sorting. Have you tried the hashing on stabs?


Elena


> --
> Daniel Jacobowitz                           Carnegie Mellon University
> MontaVista Software                         Debian GNU/Linux Developer
> 
> 2001-10-25  Daniel Jacobowitz  <drow@mvista.com>
> 
>         * symtab.c (search_symbols): Do not attempt to sort a block
>         if !BLOCK_SHOULD_SORT (b).
> 
> 2001-10-25  Daniel Jacobowitz  <drow@mvista.com>
> 
>         * generic/gdbtk-cmds (gdb_listfuncs): Do not attempt to sort a
> block
>         if !BLOCK_SHOULD_SORT (b).
> 
> Index: gdb/symtab.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/symtab.c,v
> retrieving revision 1.44
> diff -u -p -r1.44 symtab.c
> --- gdb/symtab.c        2001/10/12 23:51:29     1.44
> +++ gdb/symtab.c        2001/10/25 04:23:05
> @@ -2475,9 +2475,6 @@ search_symbols (char *regexp, namespace_
>        for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
>         {
>           b = BLOCKVECTOR_BLOCK (bv, i);
> -         /* Skip the sort if this block is always sorted.  */
> -         if (!BLOCK_SHOULD_SORT (b))
> -           sort_block_syms (b);
>           for (j = 0; j < BLOCK_NSYMS (b); j++)
>             {
>               QUIT;
> Index: gdb/gdbtk/generic/gdbtk-cmds.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/gdbtk/generic/gdbtk-cmds.c,v
> retrieving revision 1.40
> diff -u -p -r1.40 gdbtk-cmds.c
> --- gdb/gdbtk/generic/gdbtk-cmds.c      2001/10/12 23:51:29     1.40
> +++ gdb/gdbtk/generic/gdbtk-cmds.c      2001/10/25 04:23:06
> @@ -1495,9 +1495,6 @@ gdb_listfuncs (clientData, interp, objc,
>    for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
>      {
>        b = BLOCKVECTOR_BLOCK (bv, i);
> -      /* Skip the sort if this block is always sorted.  */
> -      if (!BLOCK_SHOULD_SORT (b))
> -       sort_block_syms (b);
>        ALL_BLOCK_SYMBOLS (b, j, sym)
>         {
>           if (SYMBOL_CLASS (sym) == LOC_BLOCK)

[rfa] Remove a silly looking symtab sort.

[Daniel Jacobowitz]

The function search_symbols () does not seem to be used anywhere where the
order of the returned functions matters, and the algorithm it searches with
does not rely on any sorting.  The same thing seems to be true for
gdb_listfuncs, but I haven't investigated as thoroughly.

Both of these functions have a blurb like:
  if (!BLOCK_SHOULD_SORT (b))
    sort_block_syms (b);

Note that this isn't something like "! BLOCK_SORTED" - it's "!
BLOCK_SHOULD_SORT".  The condition for that currently is

#define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40 && BLOCK_FUNCTION (bl) == NULL)

In that latter case, we certainly should not sort the symtab.  I have never
run across this in practice, but the symbol hashing patch wants this to be
cleaned up first.  Sorting a hash table's buckets is bad, mmkay?

Is this patch OK to commit?  If someone disagrees with my assessment on the
need for the results of these functions to be sorted, I can add code to sort
them after searching.

-- 
Daniel Jacobowitz                           Carnegie Mellon University
MontaVista Software                         Debian GNU/Linux Developer

2001-10-25  Daniel Jacobowitz  <drow@mvista.com>

	* symtab.c (search_symbols): Do not attempt to sort a block
	if !BLOCK_SHOULD_SORT (b).

2001-10-25  Daniel Jacobowitz  <drow@mvista.com>

	* generic/gdbtk-cmds (gdb_listfuncs): Do not attempt to sort a block
	if !BLOCK_SHOULD_SORT (b).

Index: gdb/symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.44
diff -u -p -r1.44 symtab.c
--- gdb/symtab.c	2001/10/12 23:51:29	1.44
+++ gdb/symtab.c	2001/10/25 04:23:05
@@ -2475,9 +2475,6 @@ search_symbols (char *regexp, namespace_
       for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
 	{
 	  b = BLOCKVECTOR_BLOCK (bv, i);
-	  /* Skip the sort if this block is always sorted.  */
-	  if (!BLOCK_SHOULD_SORT (b))
-	    sort_block_syms (b);
 	  for (j = 0; j < BLOCK_NSYMS (b); j++)
 	    {
 	      QUIT;
Index: gdb/gdbtk/generic/gdbtk-cmds.c
===================================================================
RCS file: /cvs/src/src/gdb/gdbtk/generic/gdbtk-cmds.c,v
retrieving revision 1.40
diff -u -p -r1.40 gdbtk-cmds.c
--- gdb/gdbtk/generic/gdbtk-cmds.c	2001/10/12 23:51:29	1.40
+++ gdb/gdbtk/generic/gdbtk-cmds.c	2001/10/25 04:23:06
@@ -1495,9 +1495,6 @@ gdb_listfuncs (clientData, interp, objc,
   for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
     {
       b = BLOCKVECTOR_BLOCK (bv, i);
-      /* Skip the sort if this block is always sorted.  */
-      if (!BLOCK_SHOULD_SORT (b))
-	sort_block_syms (b);
       ALL_BLOCK_SYMBOLS (b, j, sym)
 	{
 	  if (SYMBOL_CLASS (sym) == LOC_BLOCK)