[Bug libstdc++/110945] New: std::basic_string::assign dramatically slower than other means of copying memory

[Bug libstdc++/110945] New: std::basic_string::assign dramatically slower than other means of copying memory

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

            Bug ID: 110945
           Summary: std::basic_string::assign dramatically slower than
                    other means of copying memory
           Product: gcc
           Version: 12.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: janschultke at googlemail dot com
  Target Milestone: ---

See https://quick-bench.com/q/bqGjfyd180oOlJhiY_XnURMNKG8

Using the copy constructor performs best, and ends up using std::memcpy
internally. Even using .resize() and std::copy is much faster than .assign(),
because it is subject to more partial loop unrolling.

basic_string::assign:
https://github.com/gcc-mirror/gcc/blob/25c4b1620ebc10fceabd86a34fdbbaf8037e7e82/libstdc%2B%2B-v3/include/bits/basic_string.h#L1713C28-L1713C28

this calls the four-iterator form of .replace():
https://github.com/gcc-mirror/gcc/blob/25c4b1620ebc10fceabd86a34fdbbaf8037e7e82/libstdc%2B%2B-v3/include/bits/basic_string.h#L2378

this calls this form of _M_replace_dispatch(): (I think)
https://github.com/gcc-mirror/gcc/blob/25c4b1620ebc10fceabd86a34fdbbaf8037e7e82/libstdc%2B%2B-v3/include/bits/basic_string.tcc#L430

this calls _M_replace():
https://github.com/gcc-mirror/gcc/blob/25c4b1620ebc10fceabd86a34fdbbaf8037e7e82/libstdc%2B%2B-v3/include/bits/basic_string.tcc#L507

in this case, it should call _S_move():
https://github.com/gcc-mirror/gcc/blob/25c4b1620ebc10fceabd86a34fdbbaf8037e7e82/libstdc%2B%2B-v3/include/bits/basic_string.h#L431

this calls char_traits::move():
https://github.com/gcc-mirror/gcc/blob/25c4b1620ebc10fceabd86a34fdbbaf8037e7e82/libstdc%2B%2B-v3/include/bits/char_traits.h#L223

and that calls __builtin_memcpy()

However, I must have followed this chain of calls incorrectly, because I do not
see a call to memmove in the output assembly, and most of the time is spent
here:

>        nopl   (%rax)
>        movdqa 0x42d8a0(%rdx),%xmm0
> 63.27% movups %xmm0,(%rax,%rdx,1)
> 36.69% add    $0x10,%rdx
> 0.03%  cmp    $0x100000,%rdx

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

Jan Schultke <janschultke at googlemail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization

--- Comment #1 from Jan Schultke <janschultke at googlemail dot com> ---
Oops, I meant that it calls __builtin_memmove(). Well, neither memmove nor
memcpy are visible in the output.

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #2 from Jan Schultke <janschultke at googlemail dot com> ---
Also it looks like GCC doesn't emit memcpy or memmove in either of the first
benchmarks. Those statements refer to the corresponding clang output, actually.
What's consistent for both compilers is that .assign() is dramatically slower
than any other method.

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #3 from Jan Schultke <janschultke at googlemail dot com> ---
When increasing the input size to 8 MiB, the results become more similar to
what clang delivers for 1 MiB too:
https://quick-bench.com/q/DFHYW6eZq-FAif8xuLkBOPwzYWA

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Please provide the testcase in a usable form, not just a link to an external
site (which uses its own custom benchmark macros). This is requested at
https://gcc.gnu.org/

The relevant code is:

#include <string>
#include <array>

auto make_bytes() {
  std::array<unsigned char, 1024 * 1024> result;
  for (int i = 0; i < result.size(); i++) {
    result[i] = i % 256;
  }
  return result;
}

auto raw_data = make_bytes();

static void BenchmarkAssign() {
  std::string target_data;
  target_data.assign(raw_data.begin(), raw_data.end());
}

This is not equivalent to the other forms of copying in the benchmark, because
string::assign has to handle possible aliasing. It's valid to do things like
str.assign(str.data()+1, str.data()+2).

The copy constructor doesn't have to deal with that case (the input can't
possibly alias the object under construction). The assignment operator form
also just uses the copy constructor followed by a cheap move. For the
resize+std::copy form there's a precondition on std::copy that the start of the
output range is not in the input range, which rules out the problematic forms
of aliasing.

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #4)
> Please provide the testcase in a usable form, not just a link to an external
> site (which uses its own custom benchmark macros). This is requested at
> https://gcc.gnu.org/

Oops, I meant https://gcc.gnu.org/bugs.html

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-08-08
             Status|UNCONFIRMED                 |NEW

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #4)
> because string::assign has to handle possible aliasing. It's valid to do
> things like str.assign(str.data()+1, str.data()+2).

Even more problematic is something like:

str.assign(make_move_iterator(str.begin()), make_move_iterator(str.begin()+n));

or something similar with a counted_iterator wrapped in a common_iterator.

We can't rely on the iterators not being (convertible to) const char* to decide
that they don't alias the existing content, because arbitrary iterator types
could still alias the characters in the string.

It might be better to not use replace(begin(), end(), first, last) for
assign(first, last) though, because when we're replacing the entire string we
don't need the code that decides if we need to shuffle the existing content
around.

And _M_replace_dispatch creates a new copy anyway:

      _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
                          _InputIterator __k1, _InputIterator __k2,
                          std::__false_type)
      {
        // _GLIBCXX_RESOLVE_LIB_DEFECTS
        // 2788. unintentionally require a default constructible allocator
        const basic_string __s(__k1, __k2, this->get_allocator());
        const size_type __n1 = __i2 - __i1;
        return _M_replace(__i1 - begin(), __n1, __s._M_data(),
                          __s.size());
      }

So maybe assign(InputIterator, InputIterator) could just do:

        basic_string&
        assign(_InputIterator __first, _InputIterator __last)
        { return assign(basic_string(__first, __last)); }

We know _M_replace_dispatch will make a copy anyway.

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(except with correct allocator propagation)

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[janschultke at googlemail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #8 from Jan Schultke <janschultke at googlemail dot com> ---
(In reply to Jonathan Wakely from comment #4)
> Please provide the testcase in a usable form, not just a link to an external
> site (which uses its own custom benchmark macros). This is requested at
> https://gcc.gnu.org/

Thanks, I will remember to do that in the future.

> This is not equivalent to the other forms of copying in the benchmark,
> because string::assign has to handle possible aliasing. It's valid to do
> things like str.assign(str.data()+1, str.data()+2).

From what I could read in the `char_traits::move` code that presumably gets
called, this function explicitly tests for overlap between the memory regions,
and dispatches to cheap functions if possible. The input size was 8 MiB, so it
is unlikely that the overhead from this overlap detection is contributing in
any relevant capacity.

Basically, due to this overlap testing, `assign` SHOULD be just as fast as
other methods if there is no overlap (and in this case, there clearly is none).
However, it is 14x slower, so something is off.

Either I haven't followed the logic correctly, or there is a mistake in this
dispatching logic which leads to much worse performance for .assign().

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
That improves things:

----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
BenchmarkInit              38136 ns        38069 ns        18243
BenchmarkAssignmentOp      45476 ns        45382 ns        15038
BenchmarkAssign            45767 ns        45653 ns        15457
BenchmarkCopy              56617 ns        56515 ns        11721

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jan Schultke from comment #8)
> From what I could read in the `char_traits::move` code that presumably gets
> called, this function explicitly tests for overlap between the memory
> regions, and dispatches to cheap functions if possible. The input size was 8
> MiB, so it is unlikely that the overhead from this overlap detection is
> contributing in any relevant capacity.

I think you're reading it wrong. The overlap detection in char_traits::move is
only for constant evaluation, because we can't use memmove.

The overlap detection that matters here is in _M_replace, long before we use
char_traits::move.

> Basically, due to this overlap testing, `assign` SHOULD be just as fast as
> other methods if there is no overlap (and in this case, there clearly is
> none). However, it is 14x slower, so something is off.
> 
> Either I haven't followed the logic correctly, or there is a mistake in this
> dispatching logic which leads to much worse performance for .assign().

Or the optimizers don't optimize away all the checks in _M_replace and so we
don't unroll everything to a simple memmove, but do all the runtime checks
every time. Which is what I think is happening.

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #6)
> And _M_replace_dispatch creates a new copy anyway:
> 
>       _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
> 			  _InputIterator __k1, _InputIterator __k2,
> 			  std::__false_type)
>       {
> 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
> 	// 2788. unintentionally require a default constructible allocator
> 	const basic_string __s(__k1, __k2, this->get_allocator());
> 	const size_type __n1 = __i2 - __i1;
> 	return _M_replace(__i1 - begin(), __n1, __s._M_data(),
> 			  __s.size());
>       }

When distance(k1, k2) > this->capacity() this function will make two copies of
[k1,k2) and allocate twice. So even with the checks for disjunct strings, we do
a lot more work than the copy construction benchmarks.

With this change we make a single allocation+copy and then do a cheap move
assignment:

--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -1711,4 +1711,4 @@
         basic_string&
         assign(_InputIterator __first, _InputIterator __last)
-        { return this->replace(begin(), end(), __first, __last); }
+        { return *this = basic_string(__first, __last, get_allocator()); }

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> ---
That would also benefit this overload:

      basic_string&
      assign(initializer_list<_CharT> __l)
      { return this->assign(__l.begin(), __l.size()); }

That currently goes via replace(begin(), end(), l.begin(), l.end()) but we know
that an initializer_list cannot possibly alias the string's contents.

But we can do even better and avoid any copy if __l.size() <= capacity():

      basic_string&
      assign(initializer_list<_CharT> __l)
      {
        const size_type __n = __l.size();
        if (__n > capacity())
          *this = basic_string(__l.begin(), __l.end(), get_allocator());
        else
          {
            if (__n)
              _S_copy(_M_data(), __l.begin(), __n);
            _M_set_length(__n);
          }
        return *this;
      }

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #11)
> With this change we make a single allocation+copy and then do a cheap move
> assignment:
> 
> --- a/libstdc++-v3/include/bits/basic_string.h
> +++ b/libstdc++-v3/include/bits/basic_string.h
> @@ -1711,4 +1711,4 @@
>          basic_string&
>          assign(_InputIterator __first, _InputIterator __last)
> -        { return this->replace(begin(), end(), __first, __last); }
> +        { return *this = basic_string(__first, __last, get_allocator()); }

Except it's not cheap for C++98 because it's a copy, so we're back to
allocating and copying everything twice. That's solvable though.

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Ah, and the patch will pessimize cases like str.assign(str2.begin(),
str2.end()) where
str.capacity() >= str2.capacity().

The current implementation in terms of replace(begin(), end(), first, last)
handles that, because replace is overloaded for string iterators and pointers.

Also solvable, but it's getting more complicated.

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #15 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:cc3d7baf2741777e99567d4301802c99f5775619

commit r14-3306-gcc3d7baf2741777e99567d4301802c99f5775619
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Aug 8 16:31:42 2023 +0100

    libstdc++: Optimize std::string::assign(Iter, Iter) [PR110945]

    Calling string::assign(Iter, Iter) with "foreign" iterators (not the
    string's own iterator or pointer types) currently constructs a temporary
    string and then calls replace to copy the characters from it. That means
    we copy from the iterators twice, and if the replace operation has to
    grow the string then we also allocate twice.

    By using *this = basic_string(first, last, get_allocator()) we only
    perform a single allocation+copy and then do a cheap move assignment
    instead of a second copy (and possible allocation). But that alternative
    has to be done conditionally, so that we don't pessimize the native
    iterator case (the string's own iterator and pointer types) which
    currently select efficient overloads of replace which will not allocate
    at all if the string already has sufficient capacity. For C++20 we can
    extend that efficient case to work for any contiguous iterator with the
    right value type, not just for the string's native iterators.

    So the change is to inline the code that decides whether to work in
    place or to allocate+copy (instead of deciding that via overload
    resolution for replace), and for the allocate+copy case do a move
    assignment instead of another call to replace.

    For C++98 there is no change, as we can't do an efficient move
    assignment anyway, so keep the current code.

    We can also simplify assign(initializer_list<CharT>) because the backing
    array for an initializer_list is always disjunct with *this, so most of
    the code in _M_replace is not needed.

    libstdc++-v3/ChangeLog:

            PR libstdc++/110945
            * include/bits/basic_string.h (basic_string::assign(Iter, Iter)):
            Dispatch to _M_replace or move assignment from a temporary,
            based on the iterator type.

[Bug libstdc++/110945] std::basic_string::assign dramatically slower than other means of copying memory

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110945

--- Comment #16 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk. This seems worth considering for backports later though.