View mode: basic / threaded / horizontal-split · Log in · Help
May 27, 2012
Re: BitArray - Is there one?
On Sunday, May 27, 2012 20:21:23 Era Scarecrow wrote:
> On Sunday, 27 May 2012 at 18:18:13 UTC, Era Scarecrow wrote:
> > On Sunday, 27 May 2012 at 17:26:33 UTC, Chris Cain wrote:
> >> And also std.container.Array ... it has a specialization that
> >> packs bools. It also appears to be more modern.
> >> 
> >  Unfortunately I'm not following, either in the documentation
> > 
> > or glancing over the sources.
> 
>   Nevermind, was looking in std.array and not std.container.
> 
>   So should I work on std.bitmanip.BitArray?

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.

- Jonathan M Davis
May 28, 2012
Re: BitArray - Is there one?
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.

 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.
May 28, 2012
Re: BitArray - Is there one?
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
May 29, 2012
Re: BitArray - Is there one?
On Monday, 28 May 2012 at 21:59:36 UTC, Dmitry Olshansky wrote:
>
> 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 :)

 Hmm well subs would all happen at the 1 bit level. So let's 
compare.
xor
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

sub
0 - 0 = 0
0 - 1 = -1 (or non-zero/true, truncates to 1)
1 - 0 = 1
1 - 1 = 0

 Sorry, seems the same unless we are going with carry rules, (at 
which point it is no longer bit arrays subs), it seems to follow 
the xor rules.

> 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.

 Union work. Could do it, but it then requires special rules. To 
do slices I have 2 longs representing the offset and ending bits 
within the size_t array, so we're looking at 192-256 bits. minus 
16 will still leave us with 128 workable bits.

 Dealing with the pointer seems like a bad idea, but my starting 
offset we can say the first two bytes are 255, dropping the 
usable range of the starting offset to about 2^64 - 2^32, That 
could work and keep almost all the functionality.

> 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? ;)

 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.

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

 Then I'll import it and Hope I don't get too much criticism from 
the community.
May 29, 2012
Re: BitArray - Is there one?
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.

 Annoying, twice I've tried to branch/fork to post updates in 
GitHub and twice it says 'no changes'. It's annoying things like 
this that make me not want to contribute. Doesn't help I'm not in 
a patient mood today :(
May 29, 2012
Re: BitArray - Is there one?
On Tuesday, May 29, 2012 04:09:48 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.
> 
>   Annoying, twice I've tried to branch/fork to post updates in
> GitHub and twice it says 'no changes'. It's annoying things like
> this that make me not want to contribute. Doesn't help I'm not in
> a patient mood today :(

Well, I'm afraid that that's completely out of our hands. Overall, git and 
github work quite well, but they're not perfect.

- Jonathan M Davis
May 29, 2012
Re: BitArray - Is there one?
>> That is, for one thing, sub is asymmetric :)
>
>  Hmm well subs would all happen at the 1 bit level. So let's 
> compare.
> xor
> 0 ^ 0 = 0
> 0 ^ 1 = 1
> 1 ^ 0 = 1
> 1 ^ 1 = 0
>
> sub
> 0 - 0 = 0
> 0 - 1 = -1 (or non-zero/true, truncates to 1)
> 1 - 0 = 1
> 1 - 1 = 0
>
>  Sorry, seems the same unless we are going with carry rules, 
> (at which point it is no longer bit arrays subs), it seems to 
> follow the xor rules.

I think you misunderstood. If you view a boolean as a one bit 
integer, then yes, xor is the same as subtraction. But what 
Dmitry probably meant is subtracting sets 
(http://en.wikipedia.org/wiki/Set_(mathematics)#Complements). So 
for bit arrays a and b the result of a - b would be a bit array 
where bit at index i is set if it is set in a and not set in b. 
That's also what documentation for std.bitmanip.BitArray 
currently says.
May 29, 2012
Re: BitArray - Is there one?
On 29.05.2012 6:09, 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.
>
> Annoying, twice I've tried to branch/fork to post updates in GitHub and
> twice it says 'no changes'. It's annoying things like this that make me
> not want to contribute. Doesn't help I'm not in a patient mood today :(

hm... http://git-scm.com/book


-- 
Dmitry Olshansky
May 29, 2012
Re: BitArray - Is there one?
On 29.05.2012 4:13, Era Scarecrow wrote:
> On Monday, 28 May 2012 at 21:59:36 UTC, Dmitry Olshansky wrote:
>>
>> 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 :)
>
> Hmm well subs would all happen at the 1 bit level. So let's compare.
> xor
> 0 ^ 0 = 0
> 0 ^ 1 = 1
> 1 ^ 0 = 1
> 1 ^ 1 = 0
>
> sub
> 0 - 0 = 0
> 0 - 1 = -1 (or non-zero/true, truncates to 1)
> 1 - 0 = 1
> 1 - 1 = 0

You surely haven't looked at the source code did you? :)
BitArray opSub(BitArray e2)
{
	BitArray result;
	
        result.length = len;
        for (size_t i = 0; i < dim; i++)
            result.ptr[i] = this.ptr[i] & ~e2.ptr[i];
        return result;
}
It's conceptualy non per bit '-', it's a set difference...

>
>> 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.
>
> Union work. Could do it, but it then requires special rules. To do
> slices I have 2 longs representing the offset and ending bits within the
> size_t array, so we're looking at 192-256 bits. minus 16 will still
> leave us with 128 workable bits.
>
> Dealing with the pointer seems like a bad idea, but my starting offset
> we can say the first two bytes are 255, dropping the usable range of the
> starting offset to about 2^64 - 2^32, That could work and keep almost
> all the functionality.
>

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

>> 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? ;)
>
> 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.

>> (and of course this optimization would be very welcome, I'll happily
>> bash any walls in front of such contribution making into Phobos)
>
> Then I'll import it and Hope I don't get too much criticism from the
> community.


-- 
Dmitry Olshansky
May 29, 2012
Re: BitArray - Is there one?
>
> 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
>
... in-place bit array. So it's cheap tag for your union.

-- 
Dmitry Olshansky
1 2 3 4
Top | Discussion index | About this forum | D home