BitArray/BitFields - Review

[Era Scarecrow]

On Sunday, 29 July 2012 at 14:41:48 UTC, bearophile wrote:
> As you guess I have had to use many arrays of bits in my 
> programs :-)

  I'll do what I can :)

>> 4124 - Set/reset all bits ie:
>>  BitArray ba = BitArray(100);
>>  ba[] = true;
>> Others haven't been done yet.
>
> Among those 4124 suggestions the most important, and very 
> simple to implement, are:
> - set n-th bit (this can be a little more efficient than 
> bs[n]=1;)
> - reset n-th bit (this can be a little more efficient than 
> bs[n]=1;)

  If it has to determine between compact and non-compact, then I 
really don't see how any speed improvement can be made, and if 
it's optimized it may be inlined which would be about as fast as 
you could get.

> Another commonly needed operation is a very fast bit count. 
> There are very refined algorithms to do this.

  Likely similar to the hamming weight table mentioned in TDPL. 
Combined with the canUseBulk I think I could make it fairly fast.

>> 7487 - Done. When prepending it extends the array to size_t 
>> extra and slowly backtracks until it needs to do it again.
>
> Leaving a bit of "capacity" at the beginning is a good idea.

  With how it's made for speed and slices, it had to :P

>> 7488 - Done, union used and is 'compact' version (by default 
>> or resized and can fit)
>
> Good, this makes BitArray usable in many other situations :-)

  Yes, currently a debate of it's partial ref/value issue is 
coming up. As it is it's usable, and if you want to be sure it's 
unique you can always dup it, otherwise as a previous suggestion 
I'll either make two array types for either full reference vs 
value, or take his separate slices (reference) idea.

>>> Related:
>>> http://d.puremagic.com/issues/show_bug.cgi?id=6697
>>
>> Not so sure. Could make a multi-dimentional one that returns 
>> slices to various sections, but  that's iffy. I'd need an 
>> example of how you'd use it with BitArray before I could build 
>> a solution.
>
> I have needed many times a fast BitMatrix, but I see it as a 
> data structure distinct from BitArray, so don't worry about 
> making them inter-operate.

  A Matrix is just a multidimensional array right? I'll have to 
read up on it a bit; doing simple division (Likely whole rows of 
32bit at a time) would do that job, but expanding width several 
times (compared to height) would be quite a bit slower; Although 
not too horrible.

> For me a BitMatrix must be as fast as possible, even if this 
> causes some waste of memory (see my implementation in the 
> attach of issue 6697) and I use it for medium and large bit 
> matrices. Generally I don't to count the set bits in a bit 
> matrix. So the two data structures need different capabilities 
> and they are better implemented in different ways (this means a 
> FastBitMatrix is not an array of a BitArray!).

  more likely bool array/matrix.. Although if you heavily use 
specific lines it could convert to bool[], and then back again, 
but if you go all over the place it would be worse than just 
using bool[].

> Taking a row of a FastBitMatrix and turning it into a a 
> BitArray sounds cute, but generally I don't need to do this 
> operation, so I don't care about this feature.