missed loop-idiom when a vector is copied into another

[hiraditya]

There are two missed optimization opportunities:

• the copy of elements can be a memmove/memcpy but compiler is unable to recognize the loop-idiom
• the new copy is dead so it can be removed.

#include<vector>
#include<string>
using namespace std;

using T = int;
T vat1(std::vector<T> v1) {
    auto v = v1;
    return 10;
}

$ clang++ -std=c++17 -O3 -fno-exceptions

vat1(std::__1::vector<int, std::__1::allocator<int> >): # @vat1(std::__1::vector<int, std::__1::allocator<int> >)
        push    r15
        push    r14
        push    rbx
        sub     rsp, 32
        xorps   xmm0, xmm0
        movaps  xmmword ptr [rsp], xmm0
        mov     qword ptr [rsp + 16], 0
        mov     r15, qword ptr [rdi]
        mov     r14, qword ptr [rdi + 8]
        mov     rbx, r14
        sub     rbx, r15
        je      .LBB0_10
        js      .LBB0_11
        mov     rdi, rbx
        call    operator new(unsigned long)@PLT
        add     rbx, -4
        cmp     rbx, 28
        jb      .LBB0_3
        mov     rcx, rax
        sub     rcx, r15
        cmp     rcx, 32
        jb      .LBB0_3
        shr     rbx, 2
        inc     rbx
        mov     rsi, rbx
        and     rsi, -8
        lea     rcx, [r15 + 4*rsi]
        lea     rdx, [rax + 4*rsi]
        xor     edi, edi
.LBB0_6:                                # =>This Inner Loop Header: Depth=1
        movups  xmm0, xmmword ptr [r15 + 4*rdi]
        movups  xmm1, xmmword ptr [r15 + 4*rdi + 16]
        movups  xmmword ptr [rax + 4*rdi], xmm0
        movups  xmmword ptr [rax + 4*rdi + 16], xmm1
        add     rdi, 8
        cmp     rsi, rdi
        jne     .LBB0_6
        cmp     rbx, rsi
        jne     .LBB0_8
        jmp     .LBB0_9
.LBB0_3:
        mov     rcx, r15
        mov     rdx, rax
.LBB0_8:                                # =>This Inner Loop Header: Depth=1
        mov     esi, dword ptr [rcx]
        mov     dword ptr [rdx], esi
        add     rcx, 4
        add     rdx, 4
        cmp     rcx, r14
        jne     .LBB0_8
.LBB0_9:
        mov     rdi, rax
        call    operator delete(void*)@PLT
.LBB0_10:
        mov     eax, 10
        add     rsp, 32
        pop     rbx
        pop     r14
        pop     r15
        ret
.LBB0_11:
        mov     rdi, rsp
        call    std::__1::vector<int, std::__1::allocator<int> >::__throw_length_error[abi:v170000]() const

[philnik777]

More specifically, __uninitialized_allocator_copy doesn't unwrap the iterator before trying to forward to memmove.

[hiraditya]

More specifically, __uninitialized_allocator_copy doesn't unwrap the iterator before trying to forward to memmove.

like this?

diff --git a/libcxx/include/vector b/libcxx/include/vector
index 2361ba8e215f..672c917a1ccd 100644
--- a/libcxx/include/vector
+++ b/libcxx/include/vector
@@ -1029,7 +1029,7 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
 {
   _ConstructTransaction __tx(*this, __n);
-  __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), __first, __last, __tx.__pos_);
+  __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), std::__unwrap_iter(std::move(__first)), std::__unwrap_iter(std::move(__last)), __tx.__pos_);
 }
 
 //  Default constructs __n objects starting at __end_

[philnik777]

More specifically, __uninitialized_allocator_copy doesn't unwrap the iterator before trying to forward to memmove.

like this?

diff --git a/libcxx/include/vector b/libcxx/include/vector
index 2361ba8e215f..672c917a1ccd 100644
--- a/libcxx/include/vector
+++ b/libcxx/include/vector
@@ -1029,7 +1029,7 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
 {
   _ConstructTransaction __tx(*this, __n);
-  __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), __first, __last, __tx.__pos_);
+  __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), std::__unwrap_iter(std::move(__first)), std::__unwrap_iter(std::move(__last)), __tx.__pos_);
 }
 
 //  Default constructs __n objects starting at __end_

In essence yes, but it should be unwrapped in __uninitialized_alloctor_copy and then a helper should be called, so that all call sites benefit from it (and we don't have to remember to unwrap it every time).

[hiraditya]

but it should be unwrapped in __uninitialized_alloctor_copy

sg.

diff --git a/libcxx/include/__memory/uninitialized_algorithms.h b/libcxx/include/__memory/uninitialized_algorithms.h
index d860cee50977..37e3b44204e6 100644
--- a/libcxx/include/__memory/uninitialized_algorithms.h
+++ b/libcxx/include/__memory/uninitialized_algorithms.h
@@ -12,6 +12,7 @@
 
 #include <__algorithm/copy.h>
 #include <__algorithm/move.h>
+#include <__algorithm/unwrap_iter.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
@@ -582,7 +583,7 @@ __uninitialized_allocator_copy(_Alloc&, const _Type* __first1, const _Type* __la
     }
     return __first2;
   } else {
-    return std::copy(__first1, __last1, const_cast<_RawType*>(__first2));
+    return std::copy(std::__unwrap_iter(std::move(__first1)), std::__unwrap_iter(std::move(__last1)), const_cast<_RawType*>(__first2));
   }
 }

then a helper should be called,

Not sure what you meant by a helper.

[philnik777]

The problem is that __uninitialized_allocator_copy only specializes for raw pointers, but vector iterators are __wrap_iter<T>s. The result is that the optimized overload isn't called. Essentially, you have to rename the current __uninitialized_allocator_copy to something like __uninitialized_allocator_copy_impl and make a new __uninitialized_allocator_copy that just does return std::__uninitialized_allocator_copy_impl(__alloc, std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2)).

[hiraditya]

posted the patch: https://reviews.llvm.org/D147741

[hiraditya]

Test cases for benchmarking the performance of vector copy has been added in: https://reviews.llvm.org/D148850

[hiraditya]

Fixed.