Add statistics to bitmaps

Daniel Berlin dberlin@dberlin.org
Tue Aug 8 08:26: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 :)



More information about the Gcc-patches mailing list