digitalmars.D - overlapping array copy strikes again!
- Vladimir Panteleev (67/78) Jan 07 2007 Dear Newsgroup and Mr. Bright,
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:edBut 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.rksFrom 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