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

[Zack Weinberg <zack at wolery dot cumb dot org>]

On Thu, Aug 24, 2000 at 10:24:05PM -0700, Daniel Berlin wrote:
> >     Zack> Obviously that was worse.
> > 
> > I tried it too, using radix-sort (which has better asymptotic
> > complexity that qsort, although not necessarily better wall-clock
> > time), but I couldn't get a win, even on a case that was causing heavy
> > paging.  I think I just blew it somehow -- it should help.
> Actually, since we are sorting integers, we can do it in n log log n with
> nilsson's algorithm.
>  http://www.nada.kth.se/~snilsson/public/code/nloglogn.c
> If you look on his page, and A. Andersson's, they have papers on
> implementing radix sort well.
> Andersson's page is at http://www.csd.uu.se/~arnea

I think y'all misunderstood.  It wasn't because you can do better than
qsort.  I thought ggc_mark_trees worked like this:

  while (old pending list is nonempty)
  {
    for (each tree in old pending list)
    {
      mark tree
      add all referenced trees to new pending list
    }
    replace old pending list with new pending list 
    clear new pending list
  }

And I put a qsort(pending list) right after the while, because it was
a quick-n-dirty hack and I would go back and use a better algorithm if
it turned out to help.  Except that's not how ggc_mark_trees works.
It's really

  while (pending stack is nonempty)
  {
    pull top element off of pending stack
    mark it
    push all referenced trees onto pending stack
  }

so it would sort the entire list every time we got done with a tree.
Making a nice O(n) algorithm into O(n*(n log n)) or worse.  glibc's
qsort appears to use mergesort, which I don't think is pathological
for almost-sorted arrays, but still.

If we were gonna do this for real, I'd suggest (a) sort the roots list
once, after we get done adding them all; (b) use a priority queue
instead of stop-everything-and-sort; (c) do trees, RTL, and everything
else all at the same time.

There's also madvise(MADV_RANDOM), which might help the kernel out a
bit if we're paging.  Or not.  The Solaris manpage seems to be talking
only about behavior of file mappings.

zw