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
next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling 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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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