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

[Richard Biener <richard.guenther@gmail.com>]

On Tue, Mar 5, 2013 at 1:00 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Hello,
>
> A recurring problem with GCC's sparse bitmap data structure is that it
> performs poorly for random access patterns. Such patterns result in
> linked-list walks, and can trigger behavior quadratic in the number of
> linked-list member elements in the set.
>
> The attached patch is a first stab at an idea I've had for a while:
> Implement a "change of view" for bitmaps, such that a bitmap can be
> either a linked list, or a binary tree. I've implemented this idea
> with top-down splay trees because splay tree nodes do not need
> meta-data on (unlike e.g. color for RB-trees, rank for AVL trees,
> etc.) and top-down splay tree operations are very simple to implement
> (less than 200 lines of code). As far as I'm aware, this is the first
> attempt at allowing different views on bitmaps. The idea came from
> Andrew Macleod's tree-ssa-live implementation.
>
> The idea is to convert the bitmap to a tree view if the set
> represented by the bitmap is mostly used for membership testing, and
> not for iterations over the items (as e.g. for bitmap dataflow). A
> typical example of this is e.g. invalid_mode_changes, which just
> explodes for the test case of PR55135 at -O0.
>
> 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.

Now, an instrumented bitmap to identify bitmaps that would benefit
from the tree view would be nice ;)  [points-to sets are never modified
after being computed, but they are both random-tested and intersected]

What I missed often as well is a reference counted shared bitmap
implementation (we have various special case implementations).
I wonder if that could even use shared sub-trees/lists of bitmap_elts.

Richard.

> Ciao!
> Steven