search for: sparsebitmapelement

Displaying 5 results from an estimated 5 matches for "sparsebitmapelement".

2007 Sep 04
0
[LLVMdev] [PATCH]: Add SparseBitmap implementation
...or 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. > + 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 SparseB...
2007 Sep 01
2
[LLVMdev] [PATCH]: Add SparseBitmap implementation
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
2007 Sep 04
2
[LLVMdev] [PATCH]: Add SparseBitmap implementation
...e 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....
2007 Sep 04
0
[LLVMdev] [PATCH]: Add SparseBitmap implementation
...9;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...
2007 Sep 04
6
[LLVMdev] [PATCH]: Add SparseBitmap implementation
...a sparse bitmap that is more memory intensive but much faster at random bit testing, and it was a win here as well, but not worth the memory cost :) > > 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 ope...