On Wednesday, 30 May 2012 at 19:43:32 UTC, Dmitry Olshansky wrote:
On 30.05.2012 23:25, Era Scarecrow wrote:
That overhead is for concatenation ? Did it ever occurred 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?
Yes, a ~ b of course creates a new one. a ~= true or a ~= b is
different. To do slices I did a simple start/end position pair
and it keeps the current array (Not too unlike a regular array).
When you slice it just adjusts the starting/ending location, and
'reserved' gets truncated based on the slice. Course I might be
able to drop that to a single bit meaning it was a slice or the
original, but that still has to come from somewhere, due to
alignment it would likely still be a 32/64bit size_t, unless I
have other stuff to go with it.
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.
Truthfully only 2 bytes are wasted for the compact version (As a
flag), and 2 bytes are used for the start/ending locations.
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(!))
But unfortunately bit arrays aren't normal arrays. If you did
exactly the amount to fill the size_t types, then you won't have
extra space and it would have to be resized to concatenate
(assuming it could be). I can also only do what makes sense to
me. If I don't have a 'reserved' somehow, every concatenation
could require a resize/copy to ensure the slices don't overlap.
So a ~= true; a ~= true; would do 2 forced resizes/copies, which
is silly but would be required.
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?
Sounds workable... Although it increases the complexity a bit,
and even more functions to make just to cover the compatibility
and differences. Since the BitArray is a struct rather than a
class, if it were a class, then it would be easier to do some of
this, but the hidden overhead then becomes greater than the
struct overhead. Then there's also if you decide you want a
uneven array not divisible by size_t bits, you'd get stuck with a
slice anyways or the length would be wrong all the time.
a.length = 10;
assert(a == 10); //breaks! Length is 32/64
a.length = 32;
assert(a == 32); //okay on 32bit machines
a ~= true;
assert(a == 33); //Breaks! length is now 64/128
Choices choices.... Simpler seems
Having it implicitly convertible means any time you would want
to do a bitarray and a slice, the slice needs to reallocate so
it's beginning offset is 0 and not possible 0 - size_t*8, or
making a slice actually makes a unique copy each time, which is
it's own overhead but makes the structure smaller, or making a
slice version of a BitArray, but once again doubles complexity
and requires helper versions for all of them. The simple bitarray
suddenly is becoming very large and complex just to save a few
bytes.
When I did C programming before I was always anal about space
which I find now is rather silly. I would do something like
struct {
unsigned int a : 5;
unsigned int b : 5;
unsigned int c : 10;
unsigned int d : 2;
}
etc etc. Any time my requirements changed although I needed to
change a few bits, having the size difference between 4 bytes and
32 bytes depending on how many times the object is made seems
small and silly. I have gigs of memory free and only only a
handful of the objects made at any given time makes it seem silly.
Maybe I have it all wrong, or maybe there's much more to worry
about than originally thought.
