www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - overlapping array copy strikes again!

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 discuss=
ed  =

before. Thus, I would like to build upon the following post by Mr. Brigh=


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 manifes=
t  =

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 "r=
ep  =

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  =


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 optimiz=
 code or not depending on that?
Yes, that can work. But since overlapping copies are relatively rare, =
 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 benchma=
 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] =3D = = 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 sli= ce = 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 gmail.com
Jan 07 2007