[PATCH]: New sparse bitmap implementation

[Zdenek Dvorak]

Hello,

> The attached patch implements a new sparse bitmap type for gcc.  The
> main advantage over linked list bitmaps is twofold:
> 
> 1. Individual bit testing is much faster, particularly for bits that
> are in completely zero words.
> 2. Because it uses a contiguous array to store the bits, it has much
> better locality for other operations (they are also easily
> vectorizable).  The _into versions (almost) only touch words in the
> contiguous array if the bits will exist in the destination (otherwise,
> they just touch the wordmask).
> 
> Testing shows it to be about 50-60% faster on random bit testing than
> our current sparse bitmap implementation.
> 
> Memory use currently depends on what the highest set bit is, which
> means it can be worse than bitmaps in terms of overhead in weird
> cases, but this is fixable by changing the word mask to be a bitmap
> instead of an sbitmap (more testing is necessary speed wise before
> doing this).
> 
> This is just an initial implementation.  There are plenty of
> optimizations that can be done to the various operations to make them
> faster.
>
> Bootstrapped and regtested on i686-pc-linux-gnu, i386-darwin, and
> x86-64-linux-gnu.

do you have some concrete places in the compiler in mind where this new
type of bitmaps should be used?  If so, it might be good to apply it to
them (either directly in the same patch or immediatelly in a followup
patch), so that the code gets some testing, and also to avoid the
situation that it would just stay unused forever.

Zdenek

> Okay for mainline?
> 
> 2007-03-20  Daniel Berlin  <dberlin@dberlin.org>
> 
> 	* ebitmap.h: New file
> 	* ebitmap.c: New file
> 	* Makefile.in (ebitmap.o): New target.