[patch][RFC] bitmaps as lists *or* trees

Jan Hubicka hubicka@ucw.cz
Wed Mar 6 16:06:00 GMT 2013


> > 
> > An interesting question is, how can you identify bitmaps that could
> > benefit from viewing it as a tree (at least for some time). I have no
> > ideas here. Something with detailed memory stats, of course, but then
> > how to derive some measure for a trade-off between list or tree view.
> > Thoughts?
> 
> Well, I guess we can simply accumulate the counter on linked list walks (when
> the one element cache is missed) and divide it by number of iterations. Where
> this number thends to grow and not be counstant bounded, we have nonlinear
> behaviour, right?

And for the RFC, i also find it interesting experiment.  I implemented some
time ago splay tree based bitmap with API same as bitmap's but never attempted
to put it to mainline since Danny introduced his ebitmap and there was a lot of
discussion about whether one needs more than one bitmap in the compiler.  I
never experimented with bitmap.c change itself, just tested that replacing all
bitmaps by tree based ones causes quite some memory consumption on RA side
(with old RA) because bitmaps are pretty good for regsets they were introduced
for.

Honza
> 
> Honza



More information about the Gcc-patches mailing list