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

[Steven Bosscher <stevenb.gcc@gmail.com>]

On Wed, Mar 6, 2013 at 5:06 PM, Jan Hubicka wrote:
> 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

Right, I think the ebitmap.c experiment shows that there is *not* room
for another bitmap implementation. This is why I developed these
splay-tree bitmaps using the same data structures as the existing
linked-list sparse bitmaps: Not another bitmap, just another way of
looking at the existing bitmap. I required that changing the view of
the bitmap from linked-list to splay tree and vv. to be almost free.


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

Memory consumption as in higher peak memory? That cannot happen with
my splay-tree bitmaps. They take exactly the same amount of memory,
independent of whether the current view on the bitmap is linked-list
or splay tree. As for cache behavior or number of memory operations
(loads, stores) I think this is directly correlated to the lookup
success ratio, hence the access pattern, and so if the right view on
the bitmap is selected for the right circumstances then the number of
memory ops should also be no worse in splay tree view than in
linked-list view.

Another idea I'm currently (right now on gcc17 ;-) working on, is a
trivial speed-up for bitmaps used as regsets. The idea is that
bitmap_find_bit should look at head->first if head->current is not the
element containing the sought bit, and *not* update head->current if
head->first is the right element.  This speeds up regsets because a
common access pattern is to look at sets containing both pseudos and
hardregs, and on most targets all hardregs are in head->first.  Not
updating head->current preserves a pointer to the latest accessed
pseudos.

I'll implement this idea and come back with some timings.

Ciao!
Steven