[PATCH,c++] convert arg_lookup.{classes,namespaces} to VECs

[Nathan Froyd]

On Wed, Jun 16, 2010 at 11:38:12PM +0200, Richard Guenther wrote:
> On Wed, Jun 16, 2010 at 11:19 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> > AS $SUBEJCT suggests.  Removal of TREE_LISTs in an area which has its
> > own timevar can't be a bad thing.
> >
> > The only interesting part of this patch is the middle-end changes, which
> > I need separate approval for.  vec_member can be used in other followup
> > patches as well.
> 
> Err - while this is sort-of a 1:1 transform the code looks quadratic and asks
> for some other data structure, no?

Err - maybe.  Compiling monotone (~70KLOC) with an instrumented g++ to
record the lengths of the namespace and classes VECs after finishing arg
lookup gave these stats for namespaces:

0 27444
1 39095
2 24602
3 8140
4 915
5 57
6 33
7 2
9 1

and for classes:

0 42909
1 18318
2 8790
3 15245
4 6882
5 3397
6 2026
7 859
8 623
9 758
10 217
11 112
12 59
13 17
21 2
14 22
22 1
15 12
16 8
23 1
17 26
24 1
18 4

(blame gawk for not sorting things properly.  I don't claim that
monotone is particularly representative of all C++ apps, but it's a
decent sized one that's easy to build)

Anyway, that's about 100K calls over the whole program.  99% of the
calls have 4 namespaces or less.  90% of the calls have 4 classes or
less.  I agree that using a vector for sets is not worst-case efficient,
but for the majority of uses here, I think a vector is just as efficient
as a pointer_set.

The patch as-is is a strict improvement.  I'm happy to rewrite it to use
pointer_sets, but I think they're a little bulky for this use (by
default 256+ words of memory vs. a svelte ~10 that might have been used
recently).

-Nathan