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