The attached patch adds a SparseBitmap implementation, which more or less works the same way as GCC's sparse bitmap. That is, we only store non-zero bits (broken up into elements of some bit size), and store the elements in a linked list. We keep track of the last accessed part of the linked list, so in-order tests/sets/resets are all constant time, rather than linear time. Set operations are all O(set bits). In the GCC world, we've tried a vast number of alternatives to this "linked list + current pointer", but we've not come up with a datastructure that performs faster in practice for random bit testing *and* doesn't have bad space behavior. For bitmap operations like &, |, etc, the fact that they are stored in a linked list makes no difference. The initial use of this structure will be for the new Andersens's points-to implementation. This is not the prettiest datastructure in the world. Sadly, there are a lot of annoying little corner cases needed to make it fast and small, so the code looks a bit ugly. Suggestions, criticisms, etc, are welcome. -------------- next part -------------- A non-text attachment was scrubbed... Name: sparsebitmap.diff Type: text/x-diff Size: 19140 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070831/419ba5f4/attachment.diff>
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.> +/// 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 thisI'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.> + SparseBitmapElement(unsigned Idx) {This misses an explicit keyword.> + if (Bitmap.Elements.empty()) > + { > + AtEnd = true; > + return; > + }Here and a few other places miss reformatting.> + 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.> + 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?> + SparseBitmapIterator(SparseBitmap<ElementSize> &RHS, > + bool end = false):Bitmap(RHS) {This appears to miss an explicit keyword. Dan -- Dan Gohman, Cray Inc.
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.