www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Arrays, overlapping, etc

reply Regan Heath <regan netmail.co.nz> writes:
I did a lot of coding over the weekend.  (I wrote a lexer for C and the 
preprocessor - don't ask ;)) and had a number of issues which I wanted 
to bring up.

The first of which is the "overlapping array copy" exception.  It has no 
file:line numbers and this can make it a real pain to track down where 
it has occurred.

The next point is that surely an overlapping copy can be 
implemented/handled?  I had a quick look in Bugzilla and found a couple 
of of items the topic and related topics.  One even suggests documenting 
the various methods you can use to get around the deficiency.

A related post talks about adding a remove() method for normal arrays to 
efficiently remove an item from the array.  Adding overlapping array 
copies will make this a relatively trivial operation, eg.

To remove item at index 'n' from 'array':
   array[n..$-1] = array[n+1..$];

So, some questions about overlapping copies;

1. Why is it illegal (mentioned in the docs)?

2. Is it because Walter wants to keep the language simple to implement?

(surely not)

3. Is it because W hasn't gotten round to implementing an overlapping copy?

(perhaps)

4. Is there some reason I am not seeing?

(more than likely)

It seems an overlapping copy could be handled by the internal array copy 
function using a combination of memmove and memcpy.

Take a memory block X:
X:  [abcde0123456789]

With overlapping slices S and D:
S:       [0123456789]
D:  [abcde01234]

Perform a move on the overlapping part:
m:     <-[01234]
=:  [01234xxxxx]

Then a copy on the rest:
c:        |---[56789]
=:  [0123456789]

Resulting memory block:
X:  [012345678956789]

memmove and memcpy don't care if the blocks in question below to one 
array, or 2, 3, or more.  Nor does it matter (so far as I can see) 
provided the resulting block in memory looks like S copied to the 
location of D.

Thoughts?

Regan
Jul 09 2007
next sibling parent reply "Vladimir Panteleev" <thecybershadow gmail.com> writes:
On Mon, 09 Jul 2007 11:31:25 +0300, Regan Heath <regan netmail.co.nz> wrote:


 The next point is that surely an overlapping copy can be implemented/handled? 
I had a quick look in Bugzilla and found a couple of of items the topic and
related topics.  One even suggests documenting the various methods you can use
to get around the deficiency.


The main reason for overlapping copy being forbidden is because forbidding it
makes normal array operations much faster - the compiler doesn't have to check
for overlaps each time an array (slice) is copied. I made a suggestion some
time ago to make the compiler allow overlapping copy when it's obvious that
you're doing it (copying a slice of one array onto itself). No one has yet
discussed implementing it as a separate language feature, though.

-- 
Best regards,
  Vladimir                          mailto:thecybershadow gmail.com
Jul 09 2007
next sibling parent Xinok <xnknet gmail.com> writes:
I think a new method should be added to arrays for overlapped copies. 
Sometimes, an overlapped copy is required, and it would be nice if the 
language handled that for me.
The only deficiency is the check. Otherwise, it's just a matter of 
iterating the array forwards or backwards.

int[] a;
a[1..10].ocopy(a[0..9]);

Vladimir Panteleev wrote:

 On Mon, 09 Jul 2007 11:31:25 +0300, Regan Heath <regan netmail.co.nz> wrote:
 

 The next point is that surely an overlapping copy can be implemented/handled? 
I had a quick look in Bugzilla and found a couple of of items the topic and
related topics.  One even suggests documenting the various methods you can use
to get around the deficiency.


 
 The main reason for overlapping copy being forbidden is because forbidding it
makes normal array operations much faster - the compiler doesn't have to check
for overlaps each time an array (slice) is copied. I made a suggestion some
time ago to make the compiler allow overlapping copy when it's obvious that
you're doing it (copying a slice of one array onto itself). No one has yet
discussed implementing it as a separate language feature, though.
Jul 09 2007
prev sibling parent reply Regan Heath <regan netmail.co.nz> writes:
Vladimir Panteleev wrote:

 On Mon, 09 Jul 2007 11:31:25 +0300, Regan Heath <regan netmail.co.nz>
 wrote:
 

 The next point is that surely an overlapping copy can be
 implemented/handled?  I had a quick look in Bugzilla and found a
 couple of of items the topic and related topics.  One even suggests
 documenting the various methods you can use to get around the
 deficiency.


 
 The main reason for overlapping copy being forbidden is because
 forbidding it makes normal array operations much faster - the
 compiler doesn't have to check for overlaps each time an array
 (slice) is copied. 


Isn't it already checking?  I mean, it has to be in order to give the 
exception "overlapping array copy", right?


 I made a suggestion some time ago to make the
 compiler allow overlapping copy when it's obvious that you're doing
 it (copying a slice of one array onto itself). No one has yet
 discussed implementing it as a separate language feature, though.


I dont want a seperate language feature.  I just want it to work.

Regan
Jul 09 2007
parent reply "Vladimir Panteleev" <thecybershadow gmail.com> writes:
On Mon, 09 Jul 2007 20:15:19 +0300, Regan Heath <regan netmail.co.nz> wrote:


 Vladimir Panteleev wrote:

 The main reason for overlapping copy being forbidden is because
 forbidding it makes normal array operations much faster - the
 compiler doesn't have to check for overlaps each time an array
 (slice) is copied.


 Isn't it already checking?  I mean, it has to be in order to give the
 exception "overlapping array copy", right?


It only does that in debug versions. If you compile a release build, stuff will
just break.


 I made a suggestion some time ago to make the
 compiler allow overlapping copy when it's obvious that you're doing
 it (copying a slice of one array onto itself). No one has yet
 discussed implementing it as a separate language feature, though.


 I dont want a seperate language feature.  I just want it to work.


Don't think it's possible to do without the abovementioned performance penalty
with all array slice copies.

-- 
Best regards,
  Vladimir                          mailto:thecybershadow gmail.com
Jul 09 2007
parent reply Regan Heath <regan netmail.co.nz> writes:
Vladimir Panteleev wrote:

 On Mon, 09 Jul 2007 20:15:19 +0300, Regan Heath <regan netmail.co.nz> wrote:
 

 Vladimir Panteleev wrote:

 The main reason for overlapping copy being forbidden is because
 forbidding it makes normal array operations much faster - the
 compiler doesn't have to check for overlaps each time an array
 (slice) is copied.


 Isn't it already checking?  I mean, it has to be in order to give the
 exception "overlapping array copy", right?


 
 It only does that in debug versions. If you compile a release build, stuff
will just break.


Ahh, of course.  Thanks for clarification.


 I made a suggestion some time ago to make the
 compiler allow overlapping copy when it's obvious that you're doing
 it (copying a slice of one array onto itself). No one has yet
 discussed implementing it as a separate language feature, though.


 I dont want a seperate language feature.  I just want it to work.


 
 Don't think it's possible to do without the abovementioned performance penalty
with all array slice copies.


Yes, I see what you mean now.

How much of a penalty is it really.  The code reads:

     else if (cast(byte *)to + to.length * size <= cast(byte *)from ||
	cast(byte *)from + from.length * size <= cast(byte *)to)
     {
	memcpy(cast(byte *)to, cast(byte *)from, to.length * size);
     }
     else
     {
	throw new Error("overlapping array copy");
     }

Assuming the debug code is in phobos\internal\arraycat.d.  (I didn't 
release this was debug only code... where is the release version of the 
code?)

Regan
Jul 10 2007
parent "Vladimir Panteleev" <thecybershadow gmail.com> writes:
On Tue, 10 Jul 2007 11:05:58 +0300, Regan Heath <regan netmail.co.nz> wrote:


 Assuming the debug code is in phobos\internal\arraycat.d.  (I didn't
 release this was debug only code... where is the release version of the
 code?)


In release mode, the compiler generates the code directly - so, it gets
assembled as a "rep movsd" instruction (which moves ecx dwords from esi to edi,
and is the fastest way to transfer memory).

-- 
Best regards,
  Vladimir                          mailto:thecybershadow gmail.com
Jul 10 2007
prev sibling parent BCS <BCS pathlink.com> writes:
Regan Heath wrote:

 
 So, some questions about overlapping copies;
 
 1. Why is it illegal (mentioned in the docs)?
 


IIRC the actual copy is done as one op (with a repeat prefix) on x86 so 
there might be some major advantage to being able to assume non 
overlapping data.
Jul 09 2007