Share a draft: Fast resettable flag vector

[Thomas Young]

Hi guys,

Here's the draft for the next article in my vector and vector based containers series:
http://www.altdev.co/?p=31211&shareadraft=baba31211_53d61b774eb42
Feedback welcome!

Seems like the 'zero initialisation for classes' post got bumped back to a draft during migration somehow, so I'll publish that one again, as well..

Thomas

[Fabian Giesen]

On 7/28/2014 2:55 AM, Thomas Young wrote:
> Hi guys,
>
> Here's the draft for the next article in my vector and vector based
> containers series:
> http://www.altdev.co/?p=31211&shareadraft=baba31211_53d61b774eb42
> Feedback welcome!

Small nitpick: you're not using the ordering of tag values at all, so
referring to your current tag as "threshold" and talking about
greater-than comparisons in the text is a bit confusing, especially
since you're example code doesn't actually do it. I'd just refer to the
values as "tags" or "cookies" or something similar, and not talk about
their ordering at all, since it doesn't matter. (You need to do a clear
before you start recycling tag values, but that's it).

Interestingly, there's a related ingenious data structure that delivers
O(1) set membership testing, O(1) set insert, true O(1) clear, as well
as O(k) iteration over set elements, where k is the number of elements
in the set (bit vectors etc. take O(n), where n is the size of your
"universe" of possible values). The trade-off is spending even more
memory (twice what you would spend with a tagging scheme). It's a
beautifully simple idea. Description here:

http://research.swtch.com/sparse

-Fabian

[Thomas Young]

Hi Fabian,

Thanks for the feedback.

I think there is still *some* meaning in the use of 'threshold', even if not a perfect name, in that:
 - all the false entries have to be lower than this value (even if not explicitly tested in the code)
and
 - this is a value that increments with time (or, more precisely, each clear operation).
Not so keen on 'tag' or 'cookie', somehow, since these words also have other connotations of their own.
I'll have a look at clarifying the situation in the text where it talks about a greater than comparison, though, as this is definitely misleading.

The 'sparse sets' data structure is very neat, I wasn't aware of this, thanks for posting the link!
(This is one of the coolest parts of blogging.)

I'd expect this to most likely work out slower than cFastResetBitVector in the specific situation and use case shown, due to the more complicated conditional, and cache effects, but the fast set iteration and ordering properties are very nice and I can see how this could be very useful in some other situations..

Thomas

[Thomas Young]

Looks like the 'Custom Vector Allocation' post got lost as well, so re-published this one also.

[Thomas Young]

An updated draft can be found here:
http://www.altdev.co/?p=31211&shareadraft=baba31211_53d7be77da463
(I added a link to the sparse set data structure, also, at the end.)

[Fabian Giesen]

Hi Thomas,

> The 'sparse sets' data structure is very neat, I wasn't aware of this,
> thanks for posting the link!
> (This is one of the coolest parts of blogging.)
>
> I'd expect this to most likely work out slower than cFastResetBitVector
> in the specific situation and use case shown, due to the more
> complicated conditional, and cache effects, but the fast set iteration
> and ordering properties are very nice and I can see how this could be
> very useful in some other situations..

Yeah, it depends on what you're doing with it; the standard application
for this is algorithms that do lots of small traversals of a graph
that's static (at least for a while). That said, it really comes into
its own when you stop treating it as an opaque data structure; the trick
is that the elements in the "sparse" array are listed in insertion
order, which means it can be useful in its own right for some
algorithms. In particular, if you use sparse sets for a BFS, your
"sparse" array can do double-duty as the work list.

-Fabian