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