Re: Add statistics to bitmaps

[Daniel Berlin <dberlin at dberlin dot org>]

Jan Hubicka wrote:
> Hi,
> since for example on testcase in PR rtl-optimization/28071 we still spend
> majority of memory in non-GGC stuff (GGC memory accounts for only roughtly
> 100MB, 10% of overall consumption), I've been looking into what gets out of
> controll.  Huge part (>500MB) are the bitmaps, other huge part seems to be the
> stack space.
> 
> I've added statistics code to the bitmaps similar we have for other
> datastructures.  It measure the overall amount of bitmaps created by each
> caller, memory allocatted to support the bitmap and also amount of walks in
> bitmap_find_bit to see how quadratically the datastructure behave.

So, for that purpose, i'm not sure how useful the per-search stats are
right now.

First, i would eliminate empty bitmaps from them.
This covers all the cases where searches >0 but walks == 0

This probably also heavily biases the other stats.

Second, it's not really the average number of searches vs walks that
matters, but how bad the bad ones are (IE when we don't hit the cache).

In particular, if we make 5 million cache hits, and 1 million 6 element
walk misses, the average will still end up with "1 search per walk" in
your current scheme, but i *guarantee* you the time spend doing those 1
million 6 element walks very heavily dominates the time spend in the
bitmap operation it's performing.

IIRC, Diego is running into issues on mem-ssa where bitmap finds in
aliasing and friends are taking up tons of time due to element cache
misses, but by your statistics code, i'd guess the average is still 0 or
1 walk per search.

--Dan