www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Array expanding

reply RenatoL <rexlen gmail.com> writes:
Reading the book from Alexandrescu we can find this (page 103-104,
at least in my edition):

Expanding arrays has a couple of subtleties that concern possible
reallocation of the array. Consider:

auto a = [87, 40, 10, 2];
auto b = a; // Now a and b refer to the same chunk
a ~= [5, 17]; // Append to a
a[0] = 15; // Modify a[0]
assert(b[0] == 15); // Pass or fail?

it seems natural that the test is ok but it is not... if we read
more we find:
"D leaves~= the freedom of either expanding by reallocation or
opportunistically expanding in place if there is enough unused
memory at the end of the current array."

At a first glance this seems to be a serious issue... it seems hard
to accept that b can lost its connection to "a" in a silent mode due
to a reallocation

Is there a safe mode to do this for large arrays?
Dec 18 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/18/2011 11:12 PM, RenatoL wrote:

 Reading the book from Alexandrescu we can find this (page 103-104,
 at least in my edition):

 Expanding arrays has a couple of subtleties that concern possible
 reallocation of the array. Consider:

 auto a = [87, 40, 10, 2];
 auto b = a; // Now a and b refer to the same chunk
 a ~= [5, 17]; // Append to a
 a[0] = 15; // Modify a[0]
 assert(b[0] == 15); // Pass or fail?

 it seems natural that the test is ok but it is not... if we read
 more we find:
 "D leaves~= the freedom of either expanding by reallocation or
 opportunistically expanding in place if there is enough unused
 memory at the end of the current array."

 At a first glance this seems to be a serious issue... it seems hard
 to accept that b can lost its connection to "a" in a silent mode due
 to a reallocation

 Is there a safe mode to do this for large arrays?


Assuming 'safe' means preserving aliasing: No. How would you implement 
it? Anyway, this is not such a huge issue in practice. If you want 
aliasing, just don't append to the slices.
Dec 18 2011
parent reply RenatoL <rexlen gmail.com> writes:
Yes "in pratice" we can make in many different ways but "theoretically
speaking" it seems (to me) a very bug prone behavior.... not nice.
Dec 18 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
RenatoL Wrote:


 Yes "in pratice" we can make in many different ways but "theoretically
 speaking" it seems (to me) a very bug prone behavior.... not nice.


See also this program:

import std.stdio;
void main() {
    auto a = [87, 40, 10, 2];
    a.length -= 1;
    auto b = a; // Now a and b refer to the same chunk
    a.assumeSafeAppend();
    a ~= 5; // Append to a
    writeln(a, " ", b);
    a[0] = 15; // Modify a[0]
    writeln(a, " ", b);
}


Without assumeSafeAppend():
[87, 40, 10, 5] [87, 40, 10]
[15, 40, 10, 5] [87, 40, 10]

With assumeSafeAppend():
[87, 40, 10, 5] [87, 40, 10]
[15, 40, 10, 5] [15, 40, 10]

Bye,
bearophile
Dec 18 2011
parent RenatoL <rexlen gmail.com> writes:
This is interesting.... i didn't know assumesafeappend (as a beginner
i've still too much bugs)it is worth of investigation....
Dec 18 2011
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, December 18, 2011 22:12:07 RenatoL wrote:

 Reading the book from Alexandrescu we can find this (page 103-104,
 at least in my edition):
 
 Expanding arrays has a couple of subtleties that concern possible
 reallocation of the array. Consider:
 
 auto a = [87, 40, 10, 2];
 auto b = a; // Now a and b refer to the same chunk
 a ~= [5, 17]; // Append to a
 a[0] = 15; // Modify a[0]
 assert(b[0] == 15); // Pass or fail?
 
 it seems natural that the test is ok but it is not... if we read
 more we find:
 "D leaves~= the freedom of either expanding by reallocation or
 opportunistically expanding in place if there is enough unused
 memory at the end of the current array."
 
 At a first glance this seems to be a serious issue... it seems hard
 to accept that b can lost its connection to "a" in a silent mode due
 to a reallocation
 
 Is there a safe mode to do this for large arrays?


Read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle

It's the best article that there is on arrays and slices and how they work in 
D.

- Jonathan M Davis
Dec 18 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 18 Dec 2011 18:42:31 -0500, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 On Sunday, December 18, 2011 22:12:07 RenatoL wrote:

 Reading the book from Alexandrescu we can find this (page 103-104,
 at least in my edition):

 Expanding arrays has a couple of subtleties that concern possible
 reallocation of the array. Consider:

 auto a = [87, 40, 10, 2];
 auto b = a; // Now a and b refer to the same chunk
 a ~= [5, 17]; // Append to a
 a[0] = 15; // Modify a[0]
 assert(b[0] == 15); // Pass or fail?

 it seems natural that the test is ok but it is not... if we read
 more we find:
 "D leaves~= the freedom of either expanding by reallocation or
 opportunistically expanding in place if there is enough unused
 memory at the end of the current array."

 At a first glance this seems to be a serious issue... it seems hard
 to accept that b can lost its connection to "a" in a silent mode due
 to a reallocation

 Is there a safe mode to do this for large arrays?


 Read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle


In particular, this section covers the issue:

http://www.dsource.org/projects/dcollections/wiki/ArrayArticle#Determinism

And this section covers the additional functions that give you more info  
about the underlying array type:

http://www.dsource.org/projects/dcollections/wiki/ArrayArticle#SliceMembersandtheAppender

-Steve
Dec 19 2011