Re: Add statistics to bitmaps

[Jan Hubicka <jh at suse dot cz>]

> 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.

Yep, the memory miss issues are different problem.  What I was looking
for are basically bitmap algorithms that do some kind of stupid queries
to bitmap causing the walk to happen frequently...

Honza
> 
> 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
> 
>