Re: Traversing typedef hierarchy in C/C++ tree

[Geoffrey Keating <geoffk at geoffk dot org>]

Ian Lance Taylor <iant@google.com> writes:

> Boris Kolpackov <boris@codesynthesis.com> writes:
> 
> > I was also thinking if adding an extra member would be a big deal,
> > memory usage-wise. This member is only going to be added to the
> > TYPE nodes (struct tree_type). I may be wrong, but I would expect
> > that there aren't that many such nodes in a typical translation
> > unit. Much fewer than, say, nodes that are used to build function
> > bodies. Let's say we have 10,000 such nodes. Then on a 64-bit
> > box we will use extra ~80Kb.
> 
> Unfortunately we have discovered over time that all the memory usage
> matters.  A rule of thumb for gcc is that compilation speed is roughly
> proportional to the amount of memory used.  One of the main reasons that
> clang is faster than gcc is that clang uses smaller data structures.

The reason for this, though, is that there's a lot of places in gcc
(fewer in g++, because we worked on removing them) where operations
are of the form

for (every declaration in the program)
  do something;

This causes these decls (or whatever the loop is looking
at---identifiers, RTL, whatever) to have to be fetched from main
memory, instead of L1 or L2 cache, and that's slow.  Usually the 'do
something' is very fast, perhaps only a single test most of the time,
which means performance is dominated by the time required to fetch the
decl, which is proportional to the size of the decl.

It's easy to find these places with a performance measurement tool,
just look for lines of code which cause a lot of L2 cache misses.