On Tuesday, 29 May 2012 at 06:30:37 UTC, Dmitry Olshansky wrote:
> You surely haven't looked at the source code did you? :)
> It's conceptualy non per bit '-', it's a set difference...

 I recall looking at it, but to me that just didn't make sense. I could add subtract back and update it (Not many changes needed to keep it).

> Not at all. Once you established that it's not a pointer namely since every pointer to size_t is word aligned (unless constructed by hand).

> You could use it's lowest bit as marker then. It's 0 state won't disturb pointer usual semantics, when it's set to 1 it's obviously.

 I considered that, but then you actually limit your address space to 2^63, true that seems silly up until in the future when we use all 64bits for memory referencing and suddenly it's seg faulting for no understandable reason (Yes it's a long ways off, but this will long be forgotten about by that time). However referring to the internal offsets it only effects slices; and those are easy to fix.

 This will likely take a little time to think over and get working, I'd hate to have to make alternate versions of everything.

>> I don't see BitArray as a good replacement for the C flags. However I already made (and suggested) a flags struct that accepts and uses enums for it's flags.

> Cool. Eager to see that on the way to Phobos too.

 We'll see, once I sorta figure this all out.

On 29.05.2012 10:52, Era Scarecrow wrote:
> On Tuesday, 29 May 2012 at 06:30:37 UTC, Dmitry Olshansky wrote:
>> You surely haven't looked at the source code did you? :)
>> It's conceptualy non per bit '-', it's a set difference...
>
> I recall looking at it, but to me that just didn't make sense. I could
> add subtract back and update it (Not many changes needed to keep it).
>
>> Not at all. Once you established that it's not a pointer namely since
>> every pointer to size_t is word aligned (unless constructed by hand).
>
>> You could use it's lowest bit as marker then. It's 0 state won't
>> disturb pointer usual semantics, when it's set to 1 it's obviously.
>
> I considered that, but then you actually limit your address space to
> 2^63,

No you don't. Since pointer is already a pointer to word-sized object. It has 2 last bits == 0. Always. There is no escaping of this fact. And no your address space is intact. All it has to do is assuming proper alignment, and you sure have it since you _allocate_ it.
To be more specific most allocator go even farther and provide 8bytes aligned pointer.

true that seems silly up until in the future when we use all
> 64bits for memory referencing and suddenly it's seg faulting for no
> understandable reason (Yes it's a long ways off, but this will long be
> forgotten about by that time). However referring to the internal offsets
> it only effects slices; and those are easy to fix.
>
See the above.

> This will likely take a little time to think over and get working, I'd
> hate to have to make alternate versions of everything.
>


>> Cool. Eager to see that on the way to Phobos too.
>
> We'll see, once I sorta figure this all out.


-- 
Dmitry Olshansky

On Tuesday, 29 May 2012 at 06:56:40 UTC, Dmitry Olshansky wrote:
> On 29.05.2012 10:52, Era Scarecrow wrote:
>> I considered that, but then you actually limit your address space to
>> 2^63,
>
> No you don't. Since pointer is already a pointer to word-sized object. It has 2 last bits == 0. Always. There is no escaping of this fact. And no your address space is intact. All it has to do is assuming proper alignment, and you sure have it since you _allocate_ it.

> To be more specific most allocator go even farther and provide 8bytes aligned pointer.

 Don't you mean the first 2 bits? (being least significant). Even so, that seems more like its working out of coincidence, that or you can never use more than 25% of your memory in a single address space in your program (ever).

On 29.05.2012 11:25, Era Scarecrow wrote:
> On Tuesday, 29 May 2012 at 06:56:40 UTC, Dmitry Olshansky wrote:
>> On 29.05.2012 10:52, Era Scarecrow wrote:
>>> I considered that, but then you actually limit your address space to
>>> 2^63,
>>
>> No you don't. Since pointer is already a pointer to word-sized object.
>> It has 2 last bits == 0. Always. There is no escaping of this fact.
>> And no your address space is intact. All it has to do is assuming
>> proper alignment, and you sure have it since you _allocate_ it.
>
>> To be more specific most allocator go even farther and provide 8bytes
>> aligned pointer.
>
> Don't you mean the first 2 bits? (being least significant). Even so,
> that seems more like its working out of coincidence, that or you can
> never use more than 25% of your memory in a single address space in your
> program (ever).

Yes, least significant. no you memory is intact.
I think it's a classical case of you not getting how it works.
No problem, bear with me :)

Suppose you have array of size_t, let size_t.sizeof == 4.
Here it is:
data: 	a0 a1 a2 a3 a4 ...
addr:	20 24 28 32 36 ...

Noticed the pattern? Once first address is multiple of 4 (that is properly aligned) it can't become not a multiple of 4.
Meaning that 2 least significant bits are always == 0.

The memory is not wasted since address is incremented by 4 bytes at a time, and is read by a unit of 4 bytes.

-- 
Dmitry Olshansky

 Got some improvements, although the bulk work needs to be tested more otherwise it all seems to work quite well. Once I figure out how to post to GitHub I'll upload a version for everyone to play with and review. Code's not beautiful, but other than the length function, most of it is easy to follow.

 I'll see if I can post it tomorrow, depending on how much my brain wants to be my friend.

On Sunday, 27 May 2012 at 07:04:36 UTC, Alex Rønne Petersen wrote:
> It could definitely use some improvement. In particular:
>
> * It still uses the deprecated operator overload methods, rather than opBinary(Right) and opUnary.

 Fixed, except I can't seem to get around using opCat, beyond that it uses only the newer methods. and less code in those spots.

> * It's not quite const/immutable-friendly.

 It's const friendly now; which includes slices; That doesn't include immutable though as I'll probably have to make a whole bunch of new functions just to handle immutable but otherwise it doesn't seem like it's out of reach.

> * It forces the GC on you. Probably not easy to solve until Andrei comes up with an allocators design.

 With the compact version (up to 256 bits) the GC is not needed.

> * Needs more pure and nothrow.

 Since bitmanips templates (The version I have anyways) aren't pure/nothrow, neither can the rest of it be. If/when those get fixed I'll tag it as best I can.

> * Needs more @safe/@trusted.

 Tried to tag as much as I can. Half of it's @safe, the other half @trusted.

> * The init() methods are very unintuitive at first glance.

 Still not very intuitive; however constructors are also available that do as good if not better than init.

> * Should probably deprecate the reverse and sort properties.

 Depreciated.


 Other features: Slice operations available, so you can slice specific sets of bits. Since opDollar doesn't work right I can't rely on them just yet. uses and accepts ulong for the slices and opIndex. The BitArray footprint is about 36 bytes for 32bit systems, and likely 40bytes for 64bit systems.

 bool[4] x = [1, 1, 0, 0];
 BitArray ba = BitArray(x);

 ba = ba[2 .. ba.length]; //or BitArray(x, 2, x.length)
 assert(ba == x[2 .. $]);


// const

 ba = BitArray(x);
 const BitArray cba = ba;
 assert(cba == ba);

 const BitArray slice = ba[2 .. ba.length]; //slices work too!
 assert(ba[2 .. cba.length] == cba);
 ba[0 .. 2] = cba[];


// compact / GC-less.

 assert(ba.isCompact()); //if it's true, no GC involved.
 BitArray ca = ba;
 ca[0] = 0;
 assert(ca != ba);

 ba.length = 1000;
 assert(!ba.isCompact()); //GC'd
 ba = ba[0 .. 4];
 assert(!ba.isCompact()); //slice doesn't automatically convert to compact

 ca = ba;
 ca[0] = 0;
 assert(ba == ca); //like a regular slice, shares memory

On 30.05.2012 15:04, Era Scarecrow wrote:
[snip]
>
> Other features: Slice operations available, so you can slice specific
> sets of bits. Since opDollar doesn't work right I can't rely on them
> just yet. uses and accepts ulong for the slices and opIndex. The
> BitArray footprint is about 36 bytes for 32bit systems, and likely
> 40bytes for 64bit systems.

It all went nice and well...
Ouch why 36 bytes?

>
> bool[4] x = [1, 1, 0, 0];
> BitArray ba = BitArray(x);
>
> ba = ba[2 .. ba.length]; //or BitArray(x, 2, x.length)
> assert(ba == x[2 .. $]);
>
>
> // const
>
> ba = BitArray(x);
> const BitArray cba = ba;
> assert(cba == ba);
>
> const BitArray slice = ba[2 .. ba.length]; //slices work too!
> assert(ba[2 .. cba.length] == cba);
> ba[0 .. 2] = cba[];
>
>
> // compact / GC-less.
>
> assert(ba.isCompact()); //if it's true, no GC involved.
> BitArray ca = ba;
> ca[0] = 0;
> assert(ca != ba);
>
> ba.length = 1000;
> assert(!ba.isCompact()); //GC'd
> ba = ba[0 .. 4];
> assert(!ba.isCompact()); //slice doesn't automatically convert to compact
>
> ca = ba;
> ca[0] = 0;
> assert(ba == ca); //like a regular slice, shares memory

Cool.

-- 
Dmitry Olshansky

Dmitry Olshansky:

> Ouch why 36 bytes?

That sounds a bit too much. I think 2 - 3 words should be enough.

I also suggest the OP to take a look at Bugzilla:
http://d.puremagic.com/issues/buglist.cgi?quicksearch=BitArray

If you have questions feel free to ask :)

Bye,
bearophile

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

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.

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

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

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.