www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - shifting array slices

reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
I'm pretty sure this used to work:

import std.algorithm;

int[] ra;
copy(ra[5 .. 10], ra[4 .. 9]);

and would correctly shift the range [5 .. 10] down one
(unlike ra[4 .. 9] = ra[5 .. 10], which is prohibited by spec)

In dmd 2.057 of course it doesn't work; is this a bug or should I be 
looking elsewhere for this functionality?
Feb 11 2012
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, February 11, 2012 12:09:32 Ellery Newcomer wrote:

 I'm pretty sure this used to work:
 
 import std.algorithm;
 
 int[] ra;
 copy(ra[5 .. 10], ra[4 .. 9]);
 
 and would correctly shift the range [5 .. 10] down one
 (unlike ra[4 .. 9] = ra[5 .. 10], which is prohibited by spec)
 
 In dmd 2.057 of course it doesn't work; is this a bug or should I be
 looking elsewhere for this functionality?


copy uses array copying if it can, which is what I would expect it to do. In 
fact, a comment in copy's source states that doing so results in a 10x - 20x 
improvement in speed over the generic implementation. So, I would say that 
it's safe to say that you can't use copy to copy overlapping arrays. I'm not 
even sure it's a good idea to use overlapping ranges. I haven't dealt with 
output ranges enough to say without studying up on them again.

- Jonathan M Davis
Feb 11 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Feb 11, 2012 at 10:30:43AM -0800, Jonathan M Davis wrote:

 On Saturday, February 11, 2012 12:09:32 Ellery Newcomer wrote:

 I'm pretty sure this used to work:
 
 import std.algorithm;
 
 int[] ra;
 copy(ra[5 .. 10], ra[4 .. 9]);
 
 and would correctly shift the range [5 .. 10] down one
 (unlike ra[4 .. 9] = ra[5 .. 10], which is prohibited by spec)
 
 In dmd 2.057 of course it doesn't work; is this a bug or should I be
 looking elsewhere for this functionality?


 
 copy uses array copying if it can, which is what I would expect it to
 do. In fact, a comment in copy's source states that doing so results
 in a 10x - 20x improvement in speed over the generic implementation.
 So, I would say that it's safe to say that you can't use copy to copy
 overlapping arrays. I'm not even sure it's a good idea to use
 overlapping ranges. I haven't dealt with output ranges enough to say
 without studying up on them again.


[...]

This brings up an interesting point: what does the GC do if you have an
array that's continually appended to, and also shrunk from the front?
That is:

	ubyte[] buf;
	while ( ... ) {
		consumeData(buf[0]);
		buf = buf[1 .. $];

		ubyte x = getMoreData();
		buf ~= x;
	}

Will such a program "leak memory" in the sense that the memory chunk
allocated to buf will grow larger and larger, even though its initial
segment is never accessed again? Or is the GC smart enough to only
reallocate the needed size when the memory chunk is moved (at some point
when it has no more space to append x)?

If the GC is smart enough, then this kind of construct could be used
instead of copying overlapping ranges.


T

-- 
If lightning were to ever strike an orchestra, it'd always hit the conductor
first.
Feb 11 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, February 11, 2012 10:51:36 H. S. Teoh wrote:

 This brings up an interesting point: what does the GC do if you have an
 array that's continually appended to, and also shrunk from the front?
 That is:
 
 	ubyte[] buf;
 	while ( ... ) {
 		consumeData(buf[0]);
 		buf = buf[1 .. $];
 
 		ubyte x = getMoreData();
 		buf ~= x;
 	}
 
 Will such a program "leak memory" in the sense that the memory chunk
 allocated to buf will grow larger and larger, even though its initial
 segment is never accessed again? Or is the GC smart enough to only
 reallocate the needed size when the memory chunk is moved (at some point
 when it has no more space to append x)?
 
 If the GC is smart enough, then this kind of construct could be used
 instead of copying overlapping ranges.


The memory blocks don't grow. When an array no longer has enough room to 
increase its size, and you append to it, a new block is allocated, and the 
array is moved to there. Any slices which refer to the original block still 
refer to it. And when a garbage collection cycle is run and a memory block has 
no references to it, it's collected. The only "leaking" that occurs is that 
once no more slices refer to a particular portion of a memory block, that 
portion is no longer accessible until the block has been recycled.

If you haven't read this article yet, you really should:

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

- Jonathan M Davis
Feb 11 2012
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Feb 11, 2012 at 11:02:43AM -0800, Jonathan M Davis wrote:

 On Saturday, February 11, 2012 10:51:36 H. S. Teoh wrote:

 This brings up an interesting point: what does the GC do if you have an
 array that's continually appended to, and also shrunk from the front?
 That is:
 
 	ubyte[] buf;
 	while ( ... ) {
 		consumeData(buf[0]);
 		buf = buf[1 .. $];
 
 		ubyte x = getMoreData();
 		buf ~= x;
 	}
 
 Will such a program "leak memory" in the sense that the memory chunk
 allocated to buf will grow larger and larger, even though its
 initial segment is never accessed again? Or is the GC smart enough
 to only reallocate the needed size when the memory chunk is moved
 (at some point when it has no more space to append x)?
 
 If the GC is smart enough, then this kind of construct could be used
 instead of copying overlapping ranges.


 
 The memory blocks don't grow. When an array no longer has enough room
 to increase its size, and you append to it, a new block is allocated,
 and the array is moved to there. Any slices which refer to the
 original block still refer to it. And when a garbage collection cycle
 is run and a memory block has no references to it, it's collected. The
 only "leaking" that occurs is that once no more slices refer to a
 particular portion of a memory block, that portion is no longer
 accessible until the block has been recycled.


I know that. What I was asking is how the GC handles memory block
reallocations: does it copy the original block in its entirety, or just
the part referenced by the slice being appended to.



 If you haven't read this article yet, you really should:
 
 http://www.dsource.org/projects/dcollections/wiki/ArrayArticle


[...]

After reading this article, I think it's clear that only the portion of
the block referenced by buf gets copied, correct? And it gets copied to
the beginning of the new block, so there is no wasted space in the new
block and the old block will simply be GC'd. Cool.


T

-- 
Error: Keyboard not attached. Press F1 to continue. -- Yoon Ha Lee, CONLANG
Feb 11 2012
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 11 Feb 2012 14:24:53 -0500, H. S. Teoh <hsteoh quickfur.ath.cx>  
wrote:


 On Sat, Feb 11, 2012 at 11:02:43AM -0800, Jonathan M Davis wrote:

 On Saturday, February 11, 2012 10:51:36 H. S. Teoh wrote:

 This brings up an interesting point: what does the GC do if you have  


 an

 array that's continually appended to, and also shrunk from the front?
 That is:

 	ubyte[] buf;
 	while ( ... ) {
 		consumeData(buf[0]);
 		buf = buf[1 .. $];

 		ubyte x = getMoreData();
 		buf ~= x;
 	}

 Will such a program "leak memory" in the sense that the memory chunk
 allocated to buf will grow larger and larger, even though its
 initial segment is never accessed again? Or is the GC smart enough
 to only reallocate the needed size when the memory chunk is moved
 (at some point when it has no more space to append x)?

 If the GC is smart enough, then this kind of construct could be used
 instead of copying overlapping ranges.


 The memory blocks don't grow. When an array no longer has enough room
 to increase its size, and you append to it, a new block is allocated,
 and the array is moved to there. Any slices which refer to the
 original block still refer to it. And when a garbage collection cycle
 is run and a memory block has no references to it, it's collected. The
 only "leaking" that occurs is that once no more slices refer to a
 particular portion of a memory block, that portion is no longer
 accessible until the block has been recycled.


 I know that. What I was asking is how the GC handles memory block
 reallocations: does it copy the original block in its entirety, or just
 the part referenced by the slice being appended to.



 If you haven't read this article yet, you really should:

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


 [...]

 After reading this article, I think it's clear that only the portion of
 the block referenced by buf gets copied, correct? And it gets copied to
 the beginning of the new block, so there is no wasted space in the new
 block and the old block will simply be GC'd. Cool.


Yes, most likely.  However, there is one case where it doesn't --  
extending pages.

If an array slice can be extended by consuming the next allocated page  
(this is only for page-sized blocks and above), then instead of copying  
the data, it will just mark the next page as part of the block, and  
continue on.  In this case, the block is not "copied" at all, so it cannot  
deallocate the no-longer referenced data.

This is probably something that can be detected.  For instance, if you are  
appending to a slice of length 5 and its at the end of a 10,000 element  
array, it makes little sense to not copy that data (allowing the original  
block to be freed by the GC).  But the situations are always different.

-Steve
Feb 13 2012
prev sibling parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484

On 02/11/2012 12:09 PM, Ellery Newcomer wrote:

 I'm pretty sure this used to work:

 import std.algorithm;

 int[] ra;
 copy(ra[5 .. 10], ra[4 .. 9]);

 and would correctly shift the range [5 .. 10] down one
 (unlike ra[4 .. 9] = ra[5 .. 10], which is prohibited by spec)

 In dmd 2.057 of course it doesn't work; is this a bug or should I be
 looking elsewhere for this functionality?
Feb 11 2012