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

[Michael Matz <matz at suse dot de>]

Hi,

On Tue, 5 Mar 2013, Richard Biener wrote:

> > I haven't tested this patch at all, except making sure that it 
> > compiles. Just posting this for discussion, and for feedback on the 
> > idea. I know there have been many others before me who've tried 
> > different data structures for bitmaps, perhaps someone has already 
> > tried this before.
> 
> Definitely a nice idea.  Iteration should be easy to implement (without 
> actually splaying for each visited bit), the bit operations can use the 
> iteration as building block as well then.

Iteration isn't easy on trees without a pointer to the parent (i.e. 
enlarging each node), you need to remember variably sized context in the 
iterator (e.g. the current stack of nodes).

I do like the idea of reusing the same internal data structure to 
implement the tree.  And I'm wondering about performance impact, I 
wouldn't be surprised either way (i.e. that it brings about a large 
improvement, or none at all), most bitmap membership tests in GCC are 
surprisingly clustered so that the bitmaps cache of last accessed 
element can work its magic (not all of them, as the testcase shows of 
course :) ).


Ciao,
Michael.