C++: Why do we nreverse CLASSTYPE_TAGS

C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Hi,

  While working for a conservative solution (i.e. minimal patch) for
reducing excessive compile-time in GCC-3.3/cc1plus, I noted that we
are nreverse()ing the list of class-types or enums declared at a
class-scope in cp/class.c:unreverse_member_declarations().

As far as I can see, reversing the CLASSTYPE_TAGS is not necessary
since the whole purpose of CLASSTYPE_TAGS is serving as a database for
name lookup.

What am I missing?

-- Gaby

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Mark Mitchell]

On Mon, 2003-03-24 at 10:10, Gabriel Dos Reis wrote:
> 
> Hi,
> 
>   While working for a conservative solution (i.e. minimal patch) for
> reducing excessive compile-time in GCC-3.3/cc1plus, I noted that we
> are nreverse()ing the list of class-types or enums declared at a
> class-scope in cp/class.c:unreverse_member_declarations().
> 
> As far as I can see, reversing the CLASSTYPE_TAGS is not necessary
> since the whole purpose of CLASSTYPE_TAGS is serving as a database for
> name lookup.
> 
> What am I missing?

Nothing, really.  But:

(1) The order there may matter when doing template instantiation.  It
makes sense to instantiate the CLASSTYPE_TAGS in the order they appeared
in the source.

(2) In general, the IL ought to represent the source; source order here
makes sense.

(3) nreverse is pretty cheap.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Mark Mitchell <mark@codesourcery.com> writes:

| On Mon, 2003-03-24 at 10:10, Gabriel Dos Reis wrote:
| > 
| > Hi,
| > 
| >   While working for a conservative solution (i.e. minimal patch) for
| > reducing excessive compile-time in GCC-3.3/cc1plus, I noted that we
| > are nreverse()ing the list of class-types or enums declared at a
| > class-scope in cp/class.c:unreverse_member_declarations().
| > 
| > As far as I can see, reversing the CLASSTYPE_TAGS is not necessary
| > since the whole purpose of CLASSTYPE_TAGS is serving as a database for
| > name lookup.
| > 
| > What am I missing?
| 
| Nothing, really.  But:
| 
| (1) The order there may matter when doing template instantiation.  It
| makes sense to instantiate the CLASSTYPE_TAGS in the order they appeared
| in the source.

I thought of that.  But, when doing template instantiation, the order
in which the nested (possibly template) *type-names* are declared does not
matter.  I'm not that saying it does not make sense to instantiate in the
same order, I'm saying that that order does not matter.  

| (2) In general, the IL ought to represent the source; source order here
| makes sense.

While it would be nice to output something that follows as closely as
possible the original  program source, there is no requirement in this
specific case that the nested *type-names* be output in the same order.

| (3) nreverse is pretty cheap.

I do not doubt that nreverse() is cheap -- the point here isn't to win
some possible micro-seconds.  It is about datatype structures,
associated algorithms and operations.  The main point being that
it makes sense to use a hash-table for serving the purpose of
CLASSTYPE_TAGS, but then, it does not make sense to maintain a given
order or to reverse that order.  That is the fundamental reason for my
asking the original question. 


-- Gaby

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Mark Mitchell]

> I do not doubt that nreverse() is cheap -- the point here isn't to win
> some possible micro-seconds.  It is about datatype structures,
> associated algorithms and operations.  The main point being that
> it makes sense to use a hash-table for serving the purpose of
> CLASSTYPE_TAGS, but then, it does not make sense to maintain a given
> order or to reverse that order.  That is the fundamental reason for my
> asking the original question. 

OK, let's think in the broader context.

There should ideally be one data structure: a list of the members
declared in the class, with, if there are lots of members, a hash table
to index those things.

You need both the list and the dictionary; you want to be able to do
things like iterate through the list of FIELD_DECLs in order, and also
to find them quickly.

I don't think CLASSTYPE_TAGS should need to exist at all; everything
that you can find there should also be something you can find on
TYPE_FIELDS.

So, I'd suggest (1) eliminate CLASSTYPE_TAGS, and (2) add a hash table
for TYPE_FIELDs if there are lots of members.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Mark Mitchell <mark@codesourcery.com> writes:

| > I do not doubt that nreverse() is cheap -- the point here isn't to win
| > some possible micro-seconds.  It is about datatype structures,
| > associated algorithms and operations.  The main point being that
| > it makes sense to use a hash-table for serving the purpose of
| > CLASSTYPE_TAGS, but then, it does not make sense to maintain a given
| > order or to reverse that order.  That is the fundamental reason for my
| > asking the original question. 
| 
| OK, let's think in the broader context.
| 
| There should ideally be one data structure: a list of the members
| declared in the class, with, if there are lots of members, a hash table
| to index those things.
| 
| You need both the list and the dictionary; you want to be able to do
| things like iterate through the list of FIELD_DECLs in order, and also
| to find them quickly.

Right.

| I don't think CLASSTYPE_TAGS should need to exist at all; everything
| that you can find there should also be something you can find on
| TYPE_FIELDS.

OK.

| So, I'd suggest (1) eliminate CLASSTYPE_TAGS, and (2) add a hash table
| for TYPE_FIELDs if there are lots of members.

OK, I'll experiment with that approach.  What threasold would you put
for "lots"?

Another case I'm thinking of is when set CLASSTYPE_TAGS with
current_binding_level->tags, although I do not believe that would be a
real obstacle.

Thanks,

-- Gaby

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Mark Mitchell]

> OK, I'll experiment with that approach.  What threasold would you put
> for "lots"?

I dunno.  Probably 10 or so, to start.  With fewer than that, hashing
can't possibly be a win.  By the time you get to 100, I'm sure it will
be.
 
> Another case I'm thinking of is when set CLASSTYPE_TAGS with
> current_binding_level->tags, although I do not believe that would be a
> real obstacle.

Yes, that's a bit of complexity, but we should be able to lose that as
well.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Matt Austern]

On Monday, March 24, 2003, at 11:21 AM, Mark Mitchell wrote:

>> OK, I'll experiment with that approach.  What threasold would you put
>> for "lots"?
>
> I dunno.  Probably 10 or so, to start.  With fewer than that, hashing
> can't possibly be a win.

How expensive is the hash function?  Unless it's pretty extreme, I'd be 
surprised if you needed to get all the way to 10 to get a win.

			-Matt

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Matt Austern <austern@apple.com> writes:

| On Monday, March 24, 2003, at 11:21 AM, Mark Mitchell wrote:
| 
| >> OK, I'll experiment with that approach.  What threasold would you put
| >> for "lots"?
| >
| > I dunno.  Probably 10 or so, to start.  With fewer than that, hashing
| > can't possibly be a win.
| 
| How expensive is the hash function?  Unless it's pretty extreme, I'd
| be surprised if you needed to get all the way to 10 to get a win.

Actually, we have the hash function for free for the following reason:

   by caching the hash value, as suggested in a previous patch, we
   don't need to recompute it when we map a name to the associated
   type.  That hash is already computed as a result of calling
   get_identifier(). 

-- Gaby

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Matt Austern]

On Monday, March 24, 2003, at 12:04 PM, Gabriel Dos Reis wrote:
> | How expensive is the hash function?  Unless it's pretty extreme, I'd
> | be surprised if you needed to get all the way to 10 to get a win.
>
> Actually, we have the hash function for free for the following reason:
>
>    by caching the hash value, as suggested in a previous patch, we
>    don't need to recompute it when we map a name to the associated
>    type.  That hash is already computed as a result of calling
>    get_identifier().

If the hash function is free, then it's hard to imagine that a hash
table would ever be substantially more expensive than a list.  The
costs of a hash table are one mod or the moral equivalent (to get from
the hash function to a bucket index) and one extra pointer indirection
(to get to the head of the bucket).  How many linked list nodes to you
have to chase through to make up for a single integer division?  Not
very many, I'd think.

			--Matt

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Mike Stump]

On Monday, March 24, 2003, at 12:17 PM, Matt Austern wrote:
> On Monday, March 24, 2003, at 12:04 PM, Gabriel Dos Reis wrote:
>> | How expensive is the hash function?  Unless it's pretty extreme, I'd
>> | be surprised if you needed to get all the way to 10 to get a win.
>>
>> Actually, we have the hash function for free for the following reason:
>>
>>    by caching the hash value, as suggested in a previous patch, we
>>    don't need to recompute it when we map a name to the associated
>>    type.  That hash is already computed as a result of calling
>>    get_identifier().
>
> If the hash function is free, then it's hard to imagine that a hash
> table would ever be substantially more expensive than a list.  The
> costs of a hash table are one mod or the moral equivalent (to get from
> the hash function to a bucket index) and one extra pointer indirection
> (to get to the head of the bucket).  How many linked list nodes to you
> have to chase through to make up for a single integer division?  Not
> very many, I'd think.

While wild ass guesses are fairly common, they can be dangerous.  I put 
in a hash of an often used data structure and noticed a massive 
slowdown.  The slowdown was caused in part by the bzero cost in 
clearing the hash table itself.

The right answer is to perfect your ability to measure (use the time 
stamp register on x86 to drive timevar or some such), and then just 
measure the tradeoff on a `normal' processor and use it.  This is far 
better than just using the answer of 10.  You may have to create a 
synthetic testcase to measure it.  If you plot 0, 1, 2, 3, 5, 7, 9, 10, 
15, 20, 25, 35, 50, 75, 100 and see where things come out, you can then 
be a little more confident that the choice was the right one.

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Mark Mitchell]

On Mon, 2003-03-24 at 11:56, Matt Austern wrote:
> On Monday, March 24, 2003, at 11:21 AM, Mark Mitchell wrote:
> 
> >> OK, I'll experiment with that approach.  What threasold would you put
> >> for "lots"?
> >
> > I dunno.  Probably 10 or so, to start.  With fewer than that, hashing
> > can't possibly be a win.
> 
> How expensive is the hash function?  Unless it's pretty extreme, I'd be 
> surprised if you needed to get all the way to 10 to get a win.

Well, it's a hash *function*; you get to make an extra function call.

As opposed to roughly:

  for (x = TYPE_FIELDS (t); x; x = TREE_CHAIN (x))
   if (DECL_NAME (x) == name)
     break;

I guess it depends on how many cycles, exactly.

Hash tables take up a fair amount of memory; if we make a new hash table
per type, we'll pay a bit.  The other thing to do would be to make one
hash table for all classes: the key being the pair <class, field_name>.

Maybe that's the best of both worlds.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Jamie Lokier]

Mike Stump wrote:
> >How many linked list nodes to you
> >have to chase through to make up for a single integer division?  Not
> >very many, I'd think.

Hardly any if the size of your hash table is a power of two, as they
can be with a decent hash function.

> While wild ass guesses are fairly common, they can be dangerous.  I put 
> in a hash of an often used data structure and noticed a massive 
> slowdown.  The slowdown was caused in part by the bzero cost in 
> clearing the hash table itself.

You can start with a very small hash table.  For example 1 bucket.
Then enlarge as necessary.  Store n_buckets-1 in the data structure, so
it's ready for use as a mask.

Because mod-power-of-2 is a single AND operation, it's reasonable to do
it all the time even with a 1 bucket, 2 bucket, 4 bucket etc. size
table, provided you can have the hash value for free.

-- Jamie

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Mark Mitchell <mark@codesourcery.com> writes:

| On Mon, 2003-03-24 at 11:56, Matt Austern wrote:
| > On Monday, March 24, 2003, at 11:21 AM, Mark Mitchell wrote:
| > 
| > >> OK, I'll experiment with that approach.  What threasold would you put
| > >> for "lots"?
| > >
| > > I dunno.  Probably 10 or so, to start.  With fewer than that, hashing
| > > can't possibly be a win.
| > 
| > How expensive is the hash function?  Unless it's pretty extreme, I'd be 
| > surprised if you needed to get all the way to 10 to get a win.
| 
| Well, it's a hash *function*; you get to make an extra function call.
| 
| As opposed to roughly:
| 
|   for (x = TYPE_FIELDS (t); x; x = TREE_CHAIN (x))
|    if (DECL_NAME (x) == name)
|      break;

Agreed in principle.  But, as I pointed out previously, we don't
actually evaluate the hash function: We just re-use the result of the
initial computation (for interning into the identifier hash table).

Anyway, I'll play with replaing CLASSTYPE_TAGS with a hash-table and
report the result.   

Thanks,

-- Gaby

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Mark Mitchell <mark@codesourcery.com> writes:

[...]

| Hash tables take up a fair amount of memory; if we make a new hash table
| per type, we'll pay a bit.  The other thing to do would be to make one
| hash table for all classes: the key being the pair <class, field_name>.

What do you think about this one:  Make every class-type have a
cp_binding_level that is a snapshot of all bindings when we call
poplevel().  That way  we won't have to psuh_class_decls() each time
we (re-)enter a class-scope:  We just would have to push the class'
cp_binding_level the top of the bindin level stack.

-- Gaby

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Jason Merrill]

On 24 Mar 2003 13:02:26 -0800, Mark Mitchell <mark@codesourcery.com> wrote:

> On Mon, 2003-03-24 at 11:56, Matt Austern wrote:
>> On Monday, March 24, 2003, at 11:21 AM, Mark Mitchell wrote:
>> 
>> >> OK, I'll experiment with that approach.  What threasold would you put
>> >> for "lots"?
>> >
>> > I dunno.  Probably 10 or so, to start.  With fewer than that, hashing
>> > can't possibly be a win.
>> 
>> How expensive is the hash function?  Unless it's pretty extreme, I'd be 
>> surprised if you needed to get all the way to 10 to get a win.
>
> Well, it's a hash *function*; you get to make an extra function call.
>
> As opposed to roughly:
>
>   for (x = TYPE_FIELDS (t); x; x = TREE_CHAIN (x))
>    if (DECL_NAME (x) == name)
>      break;

Something that seems to have been missed in this discussion is that we
don't currently do a linear search for field lookups.  We do a binary
search, which should be plenty fast.

Jason

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Jason Merrill <jason@redhat.com> writes:

| On 24 Mar 2003 13:02:26 -0800, Mark Mitchell <mark@codesourcery.com> wrote:
| 
| > On Mon, 2003-03-24 at 11:56, Matt Austern wrote:
| >> On Monday, March 24, 2003, at 11:21 AM, Mark Mitchell wrote:
| >> 
| >> >> OK, I'll experiment with that approach.  What threasold would you put
| >> >> for "lots"?
| >> >
| >> > I dunno.  Probably 10 or so, to start.  With fewer than that, hashing
| >> > can't possibly be a win.
| >> 
| >> How expensive is the hash function?  Unless it's pretty extreme, I'd be 
| >> surprised if you needed to get all the way to 10 to get a win.
| >
| > Well, it's a hash *function*; you get to make an extra function call.
| >
| > As opposed to roughly:
| >
| >   for (x = TYPE_FIELDS (t); x; x = TREE_CHAIN (x))
| >    if (DECL_NAME (x) == name)
| >      break;
| 
| Something that seems to have been missed in this discussion is that we
| don't currently do a linear search for field lookups.  We do a binary
| search, which should be plenty fast.

Yes.  However, a linear search is done when looking for nested-types
in decl.c:lookup_tag().  Replacing current_binding_level->tags with a 
hash-table turned out to affect CLASSTYPE_TAGS also since we do some
random assignments here and there...

-- Gaby

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Jason Merrill]

On 25 Mar 2003 06:38:33 +0100, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:

> Yes.  However, a linear search is done when looking for nested-types
> in decl.c:lookup_tag().  Replacing current_binding_level->tags with a 
> hash-table turned out to affect CLASSTYPE_TAGS also since we do some
> random assignments here and there...

Do we still need to use current_binding_level->tags to find types?
Shouldn't that information be in the BINDING structures now?  We really
ought to unify the name lookup code.

Jason

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Jason Merrill <jason@redhat.com> writes:

| On 25 Mar 2003 06:38:33 +0100, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| 
| > Yes.  However, a linear search is done when looking for nested-types
| > in decl.c:lookup_tag().  Replacing current_binding_level->tags with a 
| > hash-table turned out to affect CLASSTYPE_TAGS also since we do some
| > random assignments here and there...
| 
| Do we still need to use current_binding_level->tags to find types?
| Shouldn't that information be in the BINDING structures now?  We really
| ought to unify the name lookup code.

I agree 100% with you.  And that is the road I took until I discovered
that the changes might be too invasive for acceptance into 3.3.  That
is the reason why I fall back to the more conservative solution of
replacing current_binding_level->tags with a hash-table, and later
(i.e. mainline) unify the code.  
In the course of unifying the name lookup code, I discovered many
lovely monstruosities :-)

In fact, I think we do not need to recreate the bindings each time we
push into the scope of a class; we should be able to reuse the snapshot
established  at popclass().

-- Gaby

Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Gabriel Dos Reis]

Jason Merrill <jason@redhat.com> writes:

| On 25 Mar 2003 06:38:33 +0100, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| 
| > Yes.  However, a linear search is done when looking for nested-types
| > in decl.c:lookup_tag().  Replacing current_binding_level->tags with a 
| > hash-table turned out to affect CLASSTYPE_TAGS also since we do some
| > random assignments here and there...
| 
| Do we still need to use current_binding_level->tags to find types?

Similarly, we don't need to have two separate bindings,
IDENTIFIER_BINDINGS and IDENTIFIER_NAMESPACE_BINDINGS. 

-- Gaby