Add statistics to bitmaps

Jan Hubicka jh@suse.cz
Tue Aug 8 13:15:00 GMT 2006


> Jan Hubicka wrote:
> >> 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...
> 
> Yeah, but you won't catch those either with your stats, because they
> will be more or less buried by the number of empty and 1/2 element
> bitmap queries :)

Why?  I am just computing the standard amortized work needed for the
search.  It seems OK to have access pattern where we do many more or
less sequential walks with occasional need for rewinding (as long as it
is not the number of queries killing us) as long as rewinding is not
dominating...

Also note that for the bigger testcases it is not big problem to see
higher amount of walks per search.

But if it seems useless, I can leave that bit out of the statistics
patch.

Honza



More information about the Gcc-patches mailing list