• Vladimir Panteleev (67/78) Jan 07 2007 Dear Newsgroup and Mr. Bright,

"Vladimir Panteleev" <thecybershadow gmail.com> writes:

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=


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

rks
 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