[LLVMdev] [PATCH]: Add SparseBitmap implementation

[Dan Gohman]

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

Interesting. Out of curiosity, do you happen to know roughly the sizes
and sparsities where using 256-bit elements was faster? 

Looking at the implementation a little more, I see ElementList is a list
of pointers to elements:

+    typedef std::list<SparseBitmapElement<ElementSize> *> ElementList;

The extra pointer indirection is unfortunate; It'd be nice to have just
a list of elements. I guess std::list's push_back always makes an
element copy, which might not be ideal, though that could be weighed
against the extra operator new call that the current code does. Another
option would be to use <llvm/ADT/ilist>, which looks like it can do
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.

Dan

-- 
Dan Gohman, Cray Inc.