Re: PCH, and more generally C++ parser performance

[Mark Mitchell <mark at codesourcery dot com>]

>>>>> "Zack" == Zack Weinberg <zack@wolery.cumb.org> writes:

    Zack> It's been called 285,000 times.  It called make_node 90,000
    Zack> times.  That means that there were 90,000 unique identifiers
    Zack> in the sample code.  get_identifier's hash table has only
    Zack> 1000 slots; even with a perfect hash function, which it does
    Zack> not have, we would get 90-element chains.  (An ideal binary
    Zack> search tree would have depth 16.)

Funny -- Alex, Richard, Jason, Benjamin and I we were just talking
about this at lunch yesterday.  I was planning on doing something
about this -- but it's great if you will instead.

    Zack> And there is simply no fast way to mark and sweep 45
    Zack> megabytes of data.  We could bum cycles out of ggc_set_mark
    Zack> and ggc_mark_trees; I did a bit of that already, but the
    Zack> improvements are negligible.  Any real improvement's got to
    Zack> come from reducing the amount of memory GC has to inspect.

Right.  The things I have in mind are:

  - Use buckets that are the right sizes for `decl'.  That's where
    most of the memory is going.  That will reduce total memory
    usage.  It won't reduce GC time much, though -- unless you
    get to the point where you're paging.

  - Sort the pointers when marking to improve locality.

  - Reduce the total memory usage.  DECLs have gotten fat -- there's
    a lot of stuff that's only used for some DECLs, and not others.
    When inlining, we end up with lots of copies of what are
    abstractly the same VAR_DECLs.  Besides having different RTL,
    these things are pretty much the same.  Eliminating that waste
    (somehow) would account for some 30% in some of my tests.
    There is some stuff in the statement-trees that is just cruft;
    for example, COMPOUND_STMT could pretty much go at this point.
    Removing dead code on trees would win big -- there's a lot
    of code (especially where templates are involved) that is 
    dead.  TARGET_EXPR is also one of the evil things -- besides
    having rather horrid semantics, we create a VAR_DECL for
    every TARGET_EXPR -- even if we don't need it.

  - Reduce the number of branches we mark along.  For example, if
    we made it an invariant that all DECLs are reachable in some
    particular way, we can avoid marking them from the body of
    a function.  More simply, we could say that all RTL instruction
    chains have to be reachable from the front -- so we never
    have to follow PREV_INSN.

  - Doing some kind of "freeze" on memory isn't entirely unreasonable
    -- but it is hard.  That brings us back to many of the problems
    that we faced with obstacks.  You really want to ensure that
    the frozen memory cannot change, or there will be hard to find
    bugs.  The big problem here is that it's easy to know that
    some things will always be needed -- but that doesn't do you 
    much good unless you know what they point to won't change.

    Zack> never used.  If we could avoid parsing them in the first
    Zack> place, wouldn't that be nice?

The language really doesn't let you do that.  You have to parse
everything.  Example:

  template <class T> 
  struct S { 
    static int i;
  };

  template <class T>
  int S<T>::i = f();

  inline void g () { 
    S<int>.i = 7;
  }

This program requires you to instantiate `S<int>::i', even if you
don't need `g'.

    Zack> (3) The parser is also bloody slow; we're spending .79
    Zack> seconds just in yyparse.

I think this will be improved over the next year.  I can't say much
more than that, just yet.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com