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
