[LLVMdev] [PATCH]: Add SparseBitmap implementation

[Daniel Berlin]

On 9/4/07, Dan Gohman <djg at cray.com> wrote:
> On Fri, Aug 31, 2007 at 08:10:33PM -0400, Daniel Berlin wrote:
> > Suggestions, criticisms, etc, are welcome.
>
> I haven't studied the implementation, but I have a few comments on
> the interface, and some style comments, below.
>
> > Index: include/llvm/ADT/SparseBitmap.h
> > ===================================================================
> > --- include/llvm/ADT/SparseBitmap.h   (revision 0)
> > +++ include/llvm/ADT/SparseBitmap.h   (revision 0)
> > @@ -0,0 +1,571 @@
> > +//===- llvm/ADT/SparseBitmap.h - Efficient Sparse Bitmap ----*- C++ -*-===//
>
> Add '-'s to make the first line line exactly 80 cols.
Will do

>
> > +/// SparseBitmap is an implementation of a bitvector that is sparse by only
> > +/// storing the elements that have non-zero bits set.  In order to make this
>
> I'd like to suggest the name SparseBitVector for this class, to
> correspond with the name of the existing BitVector class, which has
> a similar interface, but isn't sparse.

Sure, i have no problem with that.

>
> > +    SparseBitmapElement(unsigned Idx) {
>
> This misses an explicit keyword.
>
Fixed!

> > +        if (Bitmap.Elements.empty())
> > +          {
> > +            AtEnd = true;
> > +            return;
> > +          }
>
> Here and a few other places miss reformatting.

Fixed.  Anyone have a better .emacs for the indentation than the one in tools?
>
> > +  template <int ElementSize>
> > +  class SparseBitmap {
>
> Do you expect clients will often want custom ElementSize values? Otherwise,
> it seems like this template parameter should be given a default value, or
> even just removed from the API.

So, actually, at least in GCC, we discovered that we could speed up
some dataflow problems a lot with varying the element size to 256, and
on the other size, interference graphs could be reduced in space and
time a lot by varying the element size down to 64
I'm happy to give it a default value of 128.

>
> > +      bool AtEnd;
> > +
> > +      SparseBitmap<ElementSize> &Bitmap;
> > +
> > +      // Current element inside of bitmap
> > +      ElementListConstIter Iter;
> > +
> > +      // Current bit number inside of our bitmap
> > +      unsigned BitNumber;
> > +
> > +      // Current word number inside of our element
> > +      unsigned WordNumber;
> > +
> > +      // Current bits from the element.
> > +      typename SparseBitmapElement<ElementSize>::BitWord Bits;
>
> Can these SparseBitmapIterator members, and a few more that follow,
> be made private?

They were intended to be, sorry.

>
> > +      SparseBitmapIterator(SparseBitmap<ElementSize> &RHS,
> > +                           bool end = false):Bitmap(RHS) {
>
> This appears to miss an explicit keyword.

Fixed.