Re: Suggestion for improving C++ parser memory usage

[Roger Sayle <roger at eyesopen dot com>]

On Thu, 30 Dec 2004, Robert Dewar wrote:
> Steven Bosscher wrote:
> Regarding space. I have never seen a case where 5-10% was the issue.
> Rather, it has been cases where there is some algorithm in the compiler
> that is using up unpleasant non-linear amounts of memory, and where
> a relatively small change can make huge algorithmic differences in
> memory usage (in one case cutting down required memory from gigabytes
> to 10's of megabytes). Such changes are definitely worth while!

Clearly this slow-down/performance regression was noticeable or there
wouldn't have been two open PRs for it (not counting the duplicates).

But I'd also like to remind folks that my previous attempt to improve
this area http://gcc.gnu.org/ml/gcc-patches/2004-12/msg00409.html
by changing an O(n^2) algorithm to an O(n) algorithm resulted in a
180x speed-up on the pathological testcase.  My suggestion to avoid
unnecessary scopes in the C++ parser actually further improves the
situation by changing this same loop from O(n) to O(1).

Whilst not as visible or impressive as the earlier O(n^2) -> O(n),
improvement, cp_parser_implicitly_scoped_statement is called a lot
parsing C++ code, and the unnecessary calls to allocate/deallocate
entries on the scope stack aren't free.


Finally, in my defense, one of the reasons for suggesting this to
the C++ folks, is that both Mark and Jason have recently questioned
the memory impact of pacthes of mine that allocate new tree nodes
rather than overwrite/corrupt the original.  Avoiding unnecessary
C++ scopes would reduce memory usage significantly (several times?)
more than the overhead of doing things correctly in the middle-end.
i.e. it would improve my "credit" in the memory bloat witch-hunts :>

Roger
--