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

http://www.digitalmars.com/webnews/newsgroups.php?art_group=3Ddigitalmar=
s.D&article_id=3D12818

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  =

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 optimiz=


 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 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