Re: [boost] Dynamic Bitset Formal Review June 8-17

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2002-06-12 14:57:36

On Wednesday, June 12, 2002, at 02:37  PM, Alex Rosenberg wrote:

> on 6/12/02 9:18 AM, Jeremy Siek at jsiek_at_[hidden] wrote:
>
>> It sounds like you would like to see a class that has both iterators 
>> and
>> arithmetic operators. I am open to adding iterators (Howard Hinnant 
>> also
>> made this suggestions), however I have reservations. As I posted
>> previously, I think iterators over bits are a bad idea because they are
>> inherently slow.
>
> The standard model of iterating over each bit may be slow, but an 
> iteration
> model that returned the index of the next set bit could be fast. (c.f.
> PowerPC's cntlzw instruction and x86's BSR.)
>
> Such a model might fit better with typical uses of the arithmetic 
> operators
> on bitsets.

I think the slowness of iterating over bits may not be as bad as all 
that.  Compared to iterating over binary trees, bit iteration is 
probably faster.  Compared to deque::iterator, probably faster too 
(actually there are strong parallels between deque and bitvector).  A 
bit iterator that contained a word pointer and a word mask seems like a 
good design to me.  Dereference is just *word & mask.  Incrementing is 
just a rotate on the mask (often a single machine instruction) combined 
with an increment to the word pointer when the mask reaches an end 
condition (e.g. 1).  PowerPC's cntlzw can come in handy when computing 
the difference between two such iterators.

However if dyn_bitset is not meant to be a migration path from 
vector<bool> I think the argument is moot.
I'm guessing that C++0X will entertain the idea of deprecating 
vector<bool>.  I'm also guessing that said movement will be more likely 
to be successful if there is also a proposed bitvector for vector<bool> 
clients to migrate to.  dyn_bitset does not have to be that class though.

-Howard