[Bug libstdc++/90409] New: std::move[_backward] could be more optimized for deque iterators

[morwenn29 at hotmail dot fr]

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

            Bug ID: 90409
           Summary: std::move[_backward] could be more optimized for deque
                    iterators
           Product: gcc
           Version: 9.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: morwenn29 at hotmail dot fr
  Target Milestone: ---

The standard library currently contains optimized versions of std::move and
std::move_backward for std::deque iterators, which move everything block per
block. However those overloads only work when both the input and output
iterators are std::deque iterators, and not when the types of iterators differ.

I noticed that lately when checking the performance of merge algorithms on
std::deque algorithms: I expected memmove to be called when calling std::move
to move the contents of a std::deque to a temporary buffer (represented by a
simple pointer) and when moving the elements back from the buffer to the
std::deque, but while memmove was called as expected when using libc++, it
wasn't when using libstdc++. I looked at the standard library code and that's
when I realized that the libstdc++ overloads for deque iterators didn't accept
mixed iterators.

Would it be possible to add std::[_backward] overloads to take this case into
account? If I'm not mistaken it should improve std::inplace_merge and
std::stable_sort out of the box for std::deque<T> iterators when T is trivially
copyable.