www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 7484] New: std.algorithm.copy overlapping array copy

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484

           Summary: std.algorithm.copy overlapping array copy
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: ellery-newcomer utulsa.edu



11:52:25 PST ---
Way back in 2.054 you could use std.algorithm.copy in an overlapping copy,
e.g.,

copy(a[5 .. 10], a[4 .. 9]);

Fast forward a couple releases, and copy seems to be delegating to

a[4 .. 9] = a[5 .. 10];

in the interest of speed, but here overlapping copy is prohibited by spec and
implementation.

I maintain that std.algorithm.copy should permit overlapping copy in the case
of arrays because

1: it is consistent with STL copy's semantics (see Note 2)

2: copy can still do an overlapping copy on non-array range types*, and failing
to do so on arrays is an inconsistency

If this behavior is desired, the docs should at least make mention of it. Also
note that if copy's behavior is reverted, it could be the solution for issue
1317.

*proof:

auto a = make!(SList!int) ([1,2,3,4,5,6,7,8,9,10]);
auto r1 = a[];
auto r2 = a[];
r2.popFront();
copy(r2,r1);
writeln(a[]); // prints [2, 3, 4, 5, 6, 7, 8, 9, 10, 10]

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 11 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484


David Simcha <dsimcha yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dsimcha yahoo.com



Agreed.  I implemented the special-casing a few releases back because the
performance difference was huge, and the overlapping copy thing was an
oversight, not a conscious decision.  I'll put in an extra test for overlap and
fallback to naive copying if the arrays do overlap.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 11 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc





 I'll put in an extra test for overlap and
 fallback to naive copying if the arrays do overlap.


Is using memmove() good there is overlap?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 11 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484








 I'll put in an extra test for overlap and
 fallback to naive copying if the arrays do overlap.


 
 Is using memmove() good there is overlap?


I don't think it would have the same semantics in all cases.  memmove()
requires semantics identical to if an intermediate buffer were used.  Imagine
copying a[4..9] to a[5..10].

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 11 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484




Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/3f510e39f1bfddb16701834590ef3a8ba9e50578
Bug 7484:  Overlapping array copy.

https://github.com/D-Programming-Language/phobos/commit/cbe1d8e13d6e1b7506fd104beb039d670efc4bfc


Bug 7484:  Overlapping array copy.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 11 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484


Jonathan M Davis <jmdavisProg gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |jmdavisProg gmx.com
         Resolution|                            |FIXED
           Severity|normal                      |regression


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 11 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484




Commit pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/0179562172613ca272017dc8d776da51bc75597f
Added bug 7484 to changelog.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 11 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7484




08:10:17 PST ---
Awesome. May I additionally request that overlapping copy be mentioned in the
documentation

1: in std.algorithm.copy

something like

copy(a[5 .. 10], a[4 .. 9]); //valid
copy(a[4 .. 9], a[5 .. 10]); //invalid
copy(retro(a[5 .. 10]), retro(a[4 .. 9])); // invalid
copy(retro(a[4 .. 9]), retro(a[5 .. 10])); // valid

2: in Language / Arrays / Array Copying

just point the reader to std.algorithm.copy for overlapping copy

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 12 2012