Re: Common bitmap interface

[Daniel Berlin <dan at cgsoftware dot com>]

On Friday, December 7, 2001, at 11:08  PM, Michael Hayes wrote:

>
> I'd like to submit for review yet another bitmap implementation for
> GCC.  Yes, GCC already has too many bitmap implementations but the
> problem is that each implementation has its own interface.  What I
> would like to see in GCC is a _single_ consistent bitmap interface
> that allows us to bolt in a number of implementations; either
> optimised for speed or storage, etc.

The major problem with this is dealing with reload and other obstack 
usage of bitmaps.
It's not actually defining the interface or writing the implementations, 
it's getting rid of the existing "problem" uses.

>
> This patch is an attempt at producing a consistent bitmap interface to
> replace the current sbitmap.h and bitmap.h interfaces and to provide a
> mechanism where other bitmap implementations can be supported, such as
> Dan Berlin's ebitmap idea or dynamically resized bitmaps.  There are
> many advantages from using a single interface, not only from the
> maintainability of GCC but also in the peformance of GCC.  Ideally, I
> would like to see us add heuristics that would help select the bitmap
> implementation, say given some hints as to the size and density of the
> bitmaps.

I actually implemented this once in bitmaps, and it worked quite well.
However, tests also show that the sparse bitmap implementation we have 
doesn't miss enough, and doesn't get used in a "random test and set" 
enough to make a difference if you try to flat out replace them (Even 
minor changes, like determinstic skiplisting them in such a way that 
just added guarantees on complexity, made it slightly slower overall) .
F
>
> The approach I have used is for each implementation to provide a
> vector of operations that the common interface calls.  The timing
> tests I have performed to date show no additional penalty due to the
> indirection, in fact it seems to run faster.
>
You really still should static inline the test and set ops, in all 
bitmap implementations, these end up being almost completely swallowed 
by call overhead (even in bitmap_set_bit and bitmap_bit_p).


> To test the new code I have changed sbitmap.h to be a wrapper to the
> new interface and have replaced sbitmap.c.  The next stage would be to
> redo bitmap.c and then to replace the sbitmap and bitmap interfaces
> with the new interface.
>
And therein is the hard part.
Replacing bitmap.c isn't as easy as one would think.
You have to use reference counted bitmaps or a pool approach or 
something.

This is assuming you can't obstack allocate your particular bitmap 
implementation.
> At this stage I'm canvassing for comments and suggestions for
> improvements.  I'll knock up the ChangeLog entry if I get the green
> light.
>
>
> Michael.
>
>