BitArray - Is there one?

[Dmitry Olshansky]

On 29.05.2012 1:39, Era Scarecrow wrote:
> On Sunday, 27 May 2012 at 18:25:38 UTC, Jonathan M Davis wrote:
>> AFAIK, there are no plans to get rid of it due to the bool packing in
>> std.container.Array, so if there's anything that you can do to improve
>> it, go right ahead. Help is welcome.
>
> Well so far the biggest problem I have is trying to make const-friendly
> slice(s). Also minor issues with the built-in core.bitop functions as
> they accept size_t and not long, so beyond having to include my own
> versions everything else seems to be happy and passes. I wouldn't say
> it's cleaner, but should be an improvement.
>
> One functionality I fully removed was the subtract operator. Honestly it
> makes no sense; you may as well use xor. Originally I updated it to use
> ubyte rather than size_t, however seeing as there would be a big speed
> drop I ended up reverting it afterwards.

Check your math. Xor != sub.
  1 ^ 0 == 1, 0 ^ 1 == 1;
Compare with
  1 <sub> 0 == 1, 0 <sub> 1 == 0.

That is, for one thing, sub is asymmetric :)
>
> I'm not sure about merging it into GitHub, I'd prefer to have someone
> glance it over and give it a try before adding it back into the standard
> library.

I think it would be nice to rewrite operators to new style. Cut down of 
the sheer repetition is good enough reason to merge it.

Alas the other primary thing it lacks aside from set operators 
overloading is Small string optimization. Namely you have some 8bytes 
here, that's more then enough to store say 7*8=56 bits, and have 7 bits 
for length. Presumably you check if it's a small set by using lower bit 
of a pointer.
e.g. 0 == normal pointer, big set. if set to 1 == small set, everything 
else in next 3 bits of "pointer" are small-length, all other 7 bytes of 
the whole struct contain bit-array. You still can operate on it as 2 words.

Then it can have very interesting use cases. Like say completely replace 
usual nitty-gritty C-ish bit-flags. They sadly are too cost effective so 
that no suitable safe alternative came about yet. Time to make a game 
changer? ;)

(and of course this optimization would be very welcome, I'll happily 
bash any walls in front of such contribution making into Phobos)

-- 
Dmitry Olshansky