[C++ patch] performance of store_bindings()

[Michael Matz]

Hi,

with the current cc1plus and a rather big test file, I get the following
gprof output (with -O0):

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 30.47      6.95     6.95     8589     0.81     0.83  store_bindings
  2.67      7.56     0.61  4257189     0.00     0.00  ggc_alloc
  2.24      8.07     0.51  1098479     0.00     0.00  get_base_distance_recursive
  2.19      8.57     0.50  1314726     0.00     0.00  push_class_binding
  1.89      9.00     0.43    68618     0.01     0.01  find_reloads

To compile it cc1plus needs 43 seconds real time (remeber, that it's
profiled build). store_bindings() uses a quadratic algorithm to merge two
lists, which the patch doesn't change, but currently the time needed is
O(n*n), with the patch O(n*o), where n is the number in NAMES and o the
number of trees in OLD_BNIDINGS, where usually o << n.

With the patch the gprof output is:

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
  4.03      0.65     0.65  4257189     0.00     0.00  ggc_alloc
  3.35      1.19     0.54  1314726     0.00     0.00  push_class_binding
  3.04      1.68     0.49  1326810     0.00     0.00  pop_binding
  2.86      2.14     0.46  1098479     0.00     0.00  get_base_distance_recursive
  2.48      2.54     0.40  1949640     0.00     0.00  comptypes
  2.48      2.94     0.40     8589     0.05     0.07  store_bindings

and it's only taking 35 seconds to compile.

The patch is only correct, if all trees in the NAMES argument of
store_bindings() are disjoint (with respect to ID). It mainly avoids to
search the just added bindings again in the same loop.

I tested the g++ testsuite without regressions, and some other C++ files,
which produce the same output with and without the patch. So I guess, the
above condition holds, but I can't prove it for myself, because I'm not
that fluent in the C++ frontend.

Btw. with the profiled cc1plus the testsuite needed 22 minutes without the
diff and 19 minutes with the diff. (This is cool, because most test are
small, so the lists in store_bindings() are short, so the diff shouldn't
make much difference).

Sorry for the mail longer than the diff ;-)


Ciao,
Michael.