www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - .dup on an array of BitArray not duplicating

reply "ixid" <nuaccount gmail.com> writes:
Not sure if this is a bug or just rather counter-intuitive:

BitArray test;
test.length = 7;
BitArray test2 = test.dup;
test2[0] = 1;

This is fine, test is not modified.

BitArray test[7];
foreach(ref i;test)
     i.length = 7;
BitArray[7] test2 = test.dup;
test2[0] = 1;

test has been modified. Why doesn't dup work here?
May 15 2012
parent reply "Chris Cain" <clcain uncg.edu> writes:
On Tuesday, 15 May 2012 at 19:23:31 UTC, ixid wrote:

 Not sure if this is a bug or just rather counter-intuitive:

 BitArray test;
 test.length = 7;
 BitArray test2 = test.dup;
 test2[0] = 1;

 This is fine, test is not modified.

 BitArray test[7];
 foreach(ref i;test)
     i.length = 7;
 BitArray[7] test2 = test.dup;
 test2[0] = 1;

 test has been modified. Why doesn't dup work here?


dup doesn't make a deep copy. That is to say, you have a dup'd 
array of items that have not had dup called on them.

BitArray (? Are you using D1?) apparently uses pointer to its 
payload. In the first case, you're using BitArray's dup property 
which knows to create a new payload with the same values as the 
original.

The second case, you call dup on the static array of BitArrays 
which makes an exact bit-for-bit copy of the BitArray structs in 
the array. So, you're getting a new "BitArray" struct which has 
the exact same information (in this case, including a pointer) as 
the old BitArray.

So, when you call opAssign (using the test2[0] = 1;), it modifies 
the payload of the first BitArray, which transitively means that 
the first BitArray in test also sees the change (because it is 
using a pointer to the same payload).


Also, just as an aside, your first and second examples don't mean 
exactly the same thing when you do "test2[0] = 1;" In the first 
one, you're (probably) using BitArray's opIndexAssign and the 
second one, you're just using BitArray's opAssign.

An equivalent call for the second example would be:
test2[0][0] = 1;

Which would still have the same problem as you'd still be 
modifying the payload being pointed at. But it's just something 
to mention.
May 15 2012
next sibling parent reply "ixid" <nuaccount gmail.com> writes:
On Tuesday, 15 May 2012 at 20:16:28 UTC, Chris Cain wrote:

 On Tuesday, 15 May 2012 at 19:23:31 UTC, ixid wrote:

 Not sure if this is a bug or just rather counter-intuitive:

 BitArray test;
 test.length = 7;
 BitArray test2 = test.dup;
 test2[0] = 1;

 This is fine, test is not modified.

 BitArray test[7];
 foreach(ref i;test)
    i.length = 7;
 BitArray[7] test2 = test.dup;
 test2[0] = 1;

 test has been modified. Why doesn't dup work here?


 dup doesn't make a deep copy. That is to say, you have a dup'd 
 array of items that have not had dup called on them.

 BitArray (? Are you using D1?) apparently uses pointer to its 
 payload. In the first case, you're using BitArray's dup 
 property which knows to create a new payload with the same 
 values as the original.

 The second case, you call dup on the static array of BitArrays 
 which makes an exact bit-for-bit copy of the BitArray structs 
 in the array. So, you're getting a new "BitArray" struct which 
 has the exact same information (in this case, including a 
 pointer) as the old BitArray.

 So, when you call opAssign (using the test2[0] = 1;), it 
 modifies the payload of the first BitArray, which transitively 
 means that the first BitArray in test also sees the change 
 (because it is using a pointer to the same payload).


 Also, just as an aside, your first and second examples don't 
 mean exactly the same thing when you do "test2[0] = 1;" In the 
 first one, you're (probably) using BitArray's opIndexAssign and 
 the second one, you're just using BitArray's opAssign.

 An equivalent call for the second example would be:
 test2[0][0] = 1;

 Which would still have the same problem as you'd still be 
 modifying the payload being pointed at. But it's just something 
 to mention.


Sorry I made a typo in the second, it should be test2[0][0]. I'm 
using std.bitmanip in D2.
May 15 2012
parent reply "Chris Cain" <clcain uncg.edu> writes:
On Tuesday, 15 May 2012 at 20:26:12 UTC, ixid wrote:

 Sorry I made a typo in the second, it should be test2[0][0]. 
 I'm using std.bitmanip in D2.


Aha, I see! I'm somewhat surprised, normally I just use
Array!bool.

Well, you can look in the source to see some of how it works:
https://github.com/D-Programming-Language/phobos/blob/master/std/bitmanip.d#L475

So, when you call dup on the BitArray struct, it's duping the
payload pointer as well.

However, as I mentioned, duping a normal static array will not
"deep dup" everything.

You would have to do something like:

BitArray test[7];
foreach(ref i;test)
      i.length = 7;
BitArray[7] test2;
foreach(i, ref e; test)
      test2[i] = e.dup;
test2[0] = 1;

to get what you want done.
May 15 2012
parent "Chris Cain" <clcain uncg.edu> writes:
On Tuesday, 15 May 2012 at 20:44:16 UTC, Chris Cain wrote:

 test2[0] = 1;


and of course I mean test2[0][0] ... copy-pasta mistake :-)
May 15 2012
prev sibling parent reply "ixid" <nuaccount gmail.com> writes:
So if that will not work how would I efficiently copy an array of
BitArray? Looping through each bit is very slow. An array of bool
arrays is fine but I want to try to reduce the memory needed for
memoization of an algorithm.
May 15 2012
parent reply "Chris Cain" <clcain uncg.edu> writes:
On Tuesday, 15 May 2012 at 20:50:27 UTC, ixid wrote:

 So if that will not work how would I efficiently copy an array 
 of
 BitArray? Looping through each bit is very slow. An array of 
 bool
 arrays is fine but I want to try to reduce the memory needed for
 memoization of an algorithm.


That wouldn't be looping through each bit. That would be looping 
through each BitArray which contain multiple bits.

In other words, that's still efficient enough. Ideally if you 
know exactly how many bits you need (and it doesn't change), you 
could write your own struct that doesn't use the indirection 
(would use a static array) to get maximum performance and 
maximize the compression. However, many argue that's premature 
optimization ... but I think it's okay if you're trying to learn 
how to push the boundaries of the optimization of your algorithm.

Also, Array!bool is smart ... it compacts the bools down like 
BitArray does. I'm not sure which would be preferable, but they 
both operate somewhat similarly. For what it's worth, it appears 
Array!bool is newer and uses Ranges.
May 15 2012
parent "ixid" <nuaccount gmail.com> writes:
I'd typed the response before it displayed your reply that 
already answered the question. =) Sadly Array!bool doesn't seem 
to be memoizable, I assume memoization only sees container 
information or something like that. How would I go about creating 
an index accessible array using a struct of bits? Say for example 
I wanted it to be 250 bits long, rounded to the nearest 8. 
One-dimensional would be fine.
May 15 2012