search for: sparsebitmap

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

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

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

On Tue, Sep 04, 2007 at 10:35:10AM -0400, Daniel Berlin wrote: > On 9/4/07, Dan Gohman <djg at cray.com> wrote: > > On Fri, Aug 31, 2007 at 08:10:33PM -0400, Daniel Berlin wrote: > > > + 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...

...lvm.org/ > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > -------------- next part -------------- A non-text attachment was scrubbed... Name: sparsebitmap.diff Type: text/x-patch Size: 17857 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070907/f158cd31/attachment.bin>

On Sep 4, 2007, at 4:36 PM, Daniel Berlin wrote: > Also, someone on IRC asked about the weird function naming > conventions. I know most of llvm uses mixedCase, but i copied the > style of BitVector, which has a weird mix. I'm happy to change it :) Yes please. By default, it is a good idea to follow llvm coding conventions instead of copying violation of coding style from

On Sep 4, 2007, at 4:36 PM, Daniel Berlin wrote: [snip] Don't forget to update ProgrammersManual.html "Picking the Right Data Structure for a Task" section. :) - Devang

On 9/4/07, Devang Patel <dpatel at apple.com> wrote: > > On Sep 4, 2007, at 4:36 PM, Daniel Berlin wrote: > > [snip] > > Don't forget to update ProgrammersManual.html "Picking the Right > Data Structure for a Task" section. :) It doesn't talk about bitvector at all. I'm not sure whether i should add it to set like containers, or add a section

On Tue, 4 Sep 2007, Daniel Berlin wrote: >> insert/push_back without making copies. Either of these approaches would >> also fix what looks like a leak in operator&=, where elements are erased >> from the list without being deleted. > > I seriously considered not using indirection, but it made a lot of the > functions more annoying, and it didn't seem worth the

...rote: > On Tue, Sep 04, 2007 at 10:35:10AM -0400, Daniel Berlin wrote: > > On 9/4/07, Dan Gohman <djg at cray.com> wrote: > > > On Fri, Aug 31, 2007 at 08:10:33PM -0400, Daniel Berlin wrote: > > > > + 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 d...