[llvm-bugs] [Bug 25413] New: libc++'s string::assign isn't O(1) when assigning the string to itself if the system's memmove() doesn't check for that

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=25413

            Bug ID: 25413
           Summary: libc++'s string::assign isn't O(1) when assigning the
                    string to itself if the system's memmove() doesn't
                    check for that
           Product: libc++
           Version: unspecified
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: nicolasweber at gmx.de
                CC: llvm-bugs at lists.llvm.org, mclow.lists at gmail.com
    Classification: Unclassified

Consider this program:

int main() {
  string s(8 * 1024 * 1024, ' ');

  string d; d.reserve(s.size());

  for (int i = 0; i < s.size(); i += 4096) {
    d.append(&s[i], 4096);
    const char* p = d.data();
    const char* end = p + d.size();
    d.assign(p, end - p);
  }
}


It might look silly, but it's reduced from real-world code that reads chunks of
a pipe, processes completely read packets, and uses assign() to move chunks of
incomplete packets to the front of d. If a packet spans several chunks, that's
the code that effectively runs (from http://crbug.com/547387).

In all standard library implementations that aren't libc++, this runs quickly,
because they all check if p overlaps with the string stored in d and do
something intelligent in that case. libc++'s generic char_traits::move() does
that too from what I can tell, but the char specialization of char_traits just
calls memmove, and then we're at the mercy of the system C library. On most
systems, memmove seems to do something smart, but not on all of them: On OS X
versions 10.8 or older, this program takes a long time to run. With libstdc++
it's fast there too.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20151105/f7035f34/attachment-0001.html>