overlapping array copy strikes again!

[Vladimir Panteleev]

Dear Newsgroup and Mr. Bright,

I would like to once again bring to your attention the issue of  
overlapping array copies.

I shall not start it from scratch, since we all know it has been discussed  
before. Thus, I would like to build upon the following post by Mr. Bright:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=12818

To recap:

Currently, overlapping checks are only done in the debug (non-release)  
version: the compiler uses _d_arraycopy from phobos/internal/arraycat.d.  
This function already checks whether the copy would overlap, so in case  
overlapped copy would get implemented, no performance loss would manifest  
in the debug version (in fact it can be optimized, see below).

And what of the release code? In release mode, the compiler inlines a "rep  
movsb" (why not movsd btw? it doesn't add a movsd even if the array  
elements are 4 bytes long) to copy the array. Thus, any overlapping copy  
would silently fail if the source's start address is before the  
destination's.

Now, I would like to quote part of a post by Mr. Bright from 2004, which  
finished off a thread on the same topic:

>> But I don't understand,
>> can't you first check if there is an overlap and then use the optimized
>> code or not depending on that?
>
> Yes, that can work. But since overlapping copies are relatively rare,  
> it's
> fairly expensive.
>
>> From my point of view it seems very simple to do.
>> How many clock cycles takes to check for the overlap?
>
> 4 fetches, 2 adds, 2 compares, and register pressure. A lot of benchmarks
> tend to focus on these kinds of things, and D can't afford to get a
> reputation for being slow.

In reality, you don't need the 2 fetches, 2 adds and 1 compare. All that's  
needed is 2 fetches (array start positions, which will be used for the  
string operation anyway) and 1 compare. All that's needed to do is to  
compare the starting positions, and set the string direction bit  
appropriately (using std/cld). That is, unless there is more than meets  
the eye (or met my eye, to the least).

Personally, I find overlapping copies an immutable part of the language.  
It's not so rare when someone needs to delete a character or two from a  
string (without concatenating slices, which creates redundant copies) - or  
create a rotating queue (for example, event history which holds only the  
last N events). Not being able to use them at all is quite an  
inconvenience - the user has to resort to making extra copies.

Even if this one compare/flag set is unacceptable out of performance  
reasons, would it be acceptable to let the compiler determine at compile  
time when the user is trying to copy a slice of an array to another  
position within the same array? I mean, statements like array[a..b] =  
array[c..d]; - because I believe most situations where overlapping array  
copy is necessary is when a slice of an array is copied over another slice  
of the same array, AND in many cases when a slice of an array is copied  
over another slice of the same array the user is trying to perform an  
overlapping array copy.

Thank you for your attention.

-- 
Best regards,
  Vladimir                          mailto:thecybershadow at gmail.com