Auto-vectorize arrays swap (#4991)

AlexGuteniev · StephanTLavavej · web-flow · commit 7b199b235a12 · 2024-10-24T08:44:18.000-07:00
Co-authored-by: Stephan T. Lavavej &lt;stl@nuwen.net&gt;
diff --git a/benchmarks/src/swap_ranges.cpp b/benchmarks/src/swap_ranges.cpp
@@ -9,8 +9,22 @@
 
 using namespace std;
 
+template <size_t N, class T>
+void std_swap(benchmark::State& state) {
+    T a[N];
+    memset(a, 'a', sizeof(a));
+    T b[N];
+    memset(b, 'b', sizeof(b));
+
+    for (auto _ : state) {
+        swap(a, b);
+        benchmark::DoNotOptimize(a);
+        benchmark::DoNotOptimize(b);
+    }
+}
+
 template <class T>
-void bm(benchmark::State& state) {
+void std_swap_ranges(benchmark::State& state) {
     vector<T> a(static_cast<size_t>(state.range(0)), T{'a'});
     vector<T> b(static_cast<size_t>(state.range(0)), T{'b'});
 
@@ -21,6 +35,27 @@ void bm(benchmark::State& state) {
     }
 }
 
-BENCHMARK(bm<uint8_t>)->Arg(1)->Arg(5)->Arg(15)->Arg(26)->Arg(38)->Arg(60)->Arg(125)->Arg(800)->Arg(3000)->Arg(9000);
+BENCHMARK(std_swap<1, uint8_t>);
+BENCHMARK(std_swap<5, uint8_t>);
+BENCHMARK(std_swap<15, uint8_t>);
+BENCHMARK(std_swap<26, uint8_t>);
+BENCHMARK(std_swap<38, uint8_t>);
+BENCHMARK(std_swap<60, uint8_t>);
+BENCHMARK(std_swap<125, uint8_t>);
+BENCHMARK(std_swap<800, uint8_t>);
+BENCHMARK(std_swap<3000, uint8_t>);
+BENCHMARK(std_swap<9000, uint8_t>);
+
+BENCHMARK(std_swap_ranges<uint8_t>)
+    ->Arg(1)
+    ->Arg(5)
+    ->Arg(15)
+    ->Arg(26)
+    ->Arg(38)
+    ->Arg(60)
+    ->Arg(125)
+    ->Arg(800)
+    ->Arg(3000)
+    ->Arg(9000);
 
 BENCHMARK_MAIN();
diff --git a/stl/inc/concepts b/stl/inc/concepts
@@ -138,6 +138,13 @@ namespace ranges {
                 noexcept(noexcept(operator()(__t[0], __u[0])))
                 requires requires(_Cpo __fn) { __fn(__t[0], __u[0]); }
             {
+                if constexpr (is_same_v<_Ty1, _Ty2> && _Is_trivially_swappable_v<_Ty1>) {
+                    if (!_STD is_constant_evaluated()) {
+                        _STD _Swap_trivial_arrays(__t, __u);
+                        return;
+                    }
+                }
+
                 for (size_t __i = 0; __i < _Size; ++__i) {
                     operator()(__t[__i], __u[__i]);
                 }
diff --git a/stl/inc/type_traits b/stl/inc/type_traits
@@ -9,6 +9,7 @@
 #if _STL_COMPILER_PREPROCESSOR
 #include <cstddef>
 #include <cstdint>
+#include <cstring>
 #include <xtr1common>
 
 #pragma pack(push, _CRT_PACKING)
@@ -2516,6 +2517,43 @@ _NODISCARD constexpr bool _Is_finite(const _Ty _Xx) noexcept { // constexpr isfi
 template <bool _IsConst, class _Ty>
 using _Maybe_const = conditional_t<_IsConst, const _Ty, _Ty>;
 
+template <class _Ty, size_t _Size>
+void _Swap_trivial_arrays(_Ty (&_Left)[_Size], _Ty (&_Right)[_Size]) noexcept {
+    // Swap arrays using temporary buffers of 64 bytes, followed by the tail.
+    // In optimized builds, the stack usage optimizes away, and vector registers are used.
+    // The 64-byte size has desirable properties:
+    // * Big enough to engage AVX-512.
+    // * Small enough to be handled by SSE2 (using eight registers).
+    // * Avoids excessive stack consumption for non-optimized builds.
+    auto _Left_ptr  = reinterpret_cast<unsigned char*>(&_Left);
+    auto _Right_ptr = reinterpret_cast<unsigned char*>(&_Right);
+
+    constexpr size_t _Part_size_bytes = 64;
+    constexpr size_t _Size_bytes      = _Size * sizeof(_Ty);
+    constexpr size_t _Size_tail       = _Size_bytes % _Part_size_bytes;
+    constexpr size_t _Size_parts      = _Size_bytes - _Size_tail;
+
+    if constexpr (_Size_parts != 0) {
+        const auto _Stop = _Left_ptr + _Size_parts;
+        do {
+            unsigned char _Buf[_Part_size_bytes];
+            _CSTD memcpy(_Buf, _Left_ptr, _Part_size_bytes);
+            _CSTD memcpy(_Left_ptr, _Right_ptr, _Part_size_bytes);
+            _CSTD memcpy(_Right_ptr, _Buf, _Part_size_bytes);
+            _Left_ptr += _Part_size_bytes;
+            _Right_ptr += _Part_size_bytes;
+
+        } while (_Left_ptr != _Stop);
+    }
+
+    if constexpr (_Size_tail != 0) {
+        unsigned char _Buf[_Size_tail];
+        _CSTD memcpy(_Buf, _Left_ptr, _Size_tail);
+        _CSTD memcpy(_Left_ptr, _Right_ptr, _Size_tail);
+        _CSTD memcpy(_Right_ptr, _Buf, _Size_tail);
+    }
+}
+
 #if _HAS_TR1_NAMESPACE
 _STL_DISABLE_DEPRECATED_WARNING
 namespace _DEPRECATE_TR1_NAMESPACE tr1 {
diff --git a/stl/inc/utility b/stl/inc/utility
@@ -110,14 +110,23 @@ _NODISCARD constexpr _Ty(min)(initializer_list<_Ty>); // implemented in <algorit
 
 _EXPORT_STD template <class _Ty, size_t _Size, enable_if_t<_Is_swappable<_Ty>::value, int> /* = 0 */>
 _CONSTEXPR20 void swap(_Ty (&_Left)[_Size], _Ty (&_Right)[_Size]) noexcept(_Is_nothrow_swappable<_Ty>::value) {
-    if (&_Left != &_Right) {
-        _Ty* _First1 = _Left;
-        _Ty* _Last1  = _First1 + _Size;
-        _Ty* _First2 = _Right;
-        for (; _First1 != _Last1; ++_First1, ++_First2) {
-            swap(*_First1, *_First2); // intentional ADL
+    if (&_Left == &_Right) {
+        return; // Handle self-swap as a no-op; see LWG-4165
+    }
+
+    if constexpr (_Is_trivially_swappable_v<_Ty>) {
+        if (!_STD _Is_constant_evaluated()) {
+            _STD _Swap_trivial_arrays(_Left, _Right);
+            return;
         }
     }
+
+    _Ty* _First1 = _Left;
+    _Ty* _Last1  = _First1 + _Size;
+    _Ty* _First2 = _Right;
+    for (; _First1 != _Last1; ++_First1, ++_First2) {
+        swap(*_First1, *_First2); // intentional ADL
+    }
 }
 
 #if _HAS_CXX17
diff --git a/tests/std/tests/VSO_0000000_vector_algorithms/test.cpp b/tests/std/tests/VSO_0000000_vector_algorithms/test.cpp
@@ -869,6 +869,31 @@ void test_swap_ranges(mt19937_64& gen) {
     }
 }
 
+// GH-2683 "std::swap of arrays, why is there no specialization for trivial types"
+template <class T, size_t N>
+void test_swap_arrays(mt19937_64& gen) {
+    const auto fn = [&]() { return static_cast<T>(gen()); };
+    T left[N];
+    T right[N];
+    generate(begin(left), end(left), fn);
+    generate(begin(right), end(right), fn);
+
+    const vector<T> origLeft(begin(left), end(left));
+    const vector<T> origRight(begin(right), end(right));
+
+    swap(left, right);
+
+    assert(equal(begin(left), end(left), origRight.begin(), origRight.end()));
+    assert(equal(begin(right), end(right), origLeft.begin(), origLeft.end()));
+
+#if _HAS_CXX20
+    ranges::swap(left, right);
+
+    assert(equal(begin(left), end(left), origLeft.begin(), origLeft.end()));
+    assert(equal(begin(right), end(right), origRight.begin(), origRight.end()));
+#endif // _HAS_CXX20
+}
+
 void test_vector_algorithms(mt19937_64& gen) {
     test_count<char>(gen);
     test_count<signed char>(gen);
@@ -1027,6 +1052,21 @@ void test_vector_algorithms(mt19937_64& gen) {
     test_swap_ranges<int>(gen);
     test_swap_ranges<unsigned int>(gen);
     test_swap_ranges<unsigned long long>(gen);
+
+    test_swap_arrays<uint8_t, 1>(gen);
+    test_swap_arrays<uint16_t, 1>(gen);
+    test_swap_arrays<uint32_t, 1>(gen);
+    test_swap_arrays<uint64_t, 1>(gen);
+
+    test_swap_arrays<uint8_t, 47>(gen);
+    test_swap_arrays<uint16_t, 47>(gen);
+    test_swap_arrays<uint32_t, 47>(gen);
+    test_swap_arrays<uint64_t, 47>(gen);
+
+    test_swap_arrays<uint8_t, 512>(gen);
+    test_swap_arrays<uint16_t, 512>(gen);
+    test_swap_arrays<uint32_t, 512>(gen);
+    test_swap_arrays<uint64_t, 512>(gen);
 }
 
 template <typename Container1, typename Container2>

Original file line number	Diff line number	Diff line change
`@@ -138,6 +138,13 @@ namespace ranges {`
`138`	`138`	`noexcept(noexcept(operator()(__t[0], __u[0])))`
`139`	`139`	`requires requires(_Cpo __fn) { __fn(__t[0], __u[0]); }`
`140`	`140`	`{`
	`141`	`+ if constexpr (is_same_v<_Ty1, _Ty2> && _Is_trivially_swappable_v<_Ty1>) {`
	`142`	`+ if (!_STD is_constant_evaluated()) {`
	`143`	`+ _STD _Swap_trivial_arrays(__t, __u);`
	`144`	`+ return;`
	`145`	`+ }`
	`146`	`+ }`
	`147`	`+`
`141`	`148`	`for (size_t __i = 0; __i < _Size; ++__i) {`
`142`	`149`	`operator()(__t[__i], __u[__i]);`
`143`	`150`	`}`