BitArray - preview of what's to come?

[Dmitry Olshansky]

On 30.05.2012 23:25, Era Scarecrow wrote:
> On Wednesday, 30 May 2012 at 11:19:43 UTC, Dmitry Olshansky wrote:
>> It all went nice and well...
>> Ouch why 36 bytes?
>
> Well for the whole normal size it was 32bytes, or 24 if I drop the ulong
> 'reserved' which does a minor optimization so it can expand rather than
> duping every time it expands (but slices know not to expand and dup).
> Otherwise...
>
> auto x = BitArray(1000);
> auto y = x[256 .. 700];
>
> x ~= true; //expands without resizing (Leftover space)
> y ~= true; //overwrite bit 701 in x? Dups instead
>
> There's also much faster prepending of bits (Thanks to slice support).
> So...
>
> x = true ~ x; //dups & reallocates once, but not O(n) slow
> x = false ~ x; //uses reserved space at beginning used, so O(1)
>
> Let's see, 32bit systems if we have 24 bytes, and 4 bytes for the
> overhead, 20*8, 160 bits would be available, or 32bytes with 28 bytes
> extra at 228 bits
>
That overhead is for concatenation ? Did it ever occured to you that 
arrays do sometimes reallocate on append. And of course a ~ b should 
produce new copy (at least semantically).
Why bit array shouldn't follow the same design?

I fail to see how the whole 4 byte word has to be wasted.
Obviously you can denote 1 byte for small length. Or maximum 2bytes in 
both cases.

> On 64bit systems, you'll have 32bytes, 24 avaliable, so 192 bits. or
> 40bytes with 32, giving 256 bits. I will the current to at least match
> the regular/normal one equally so some space isn't lost, but it won't be
> by much.
>

Same thought where these 8 bytes go ? Why would I pay 8 bytes for 
possible concatenation if I happen to use fixed sizes or resize them 
rarely? Pay as you go is the most sane principle.
(built-in arrays do have append cache if you didn't know so they already 
reserve space in advance(!))

> If you drop it down to a simple pointer (like the original),
than slices
> and extra features and optimizations go away.

Slice could be another type BTW. That type should be implicitly 
convertible to BitArray on assignment. Thus slice would have start/end 
pair of ulongs while array itself wouldn't.
Sounds good?

-- 
Dmitry Olshansky