VCRuntime: `memmove()` is surprisingly slow for more than 8 KB on certain CPUs

[StephanTLavavej]

Extracted from #5502 by Alex Guteniev (@AlexGuteniev):

🐛 memmove performance bug

After the initial implementation I observed that some of the benchmark exhibited unexpected slowdown. The issue was in surprisingly slow memmove. I've created benchmark repro of this problem.

Benchmark

#include <benchmark/benchmark.h>
#include <cstring>

using namespace std;

alignas(4096) unsigned char v[1024 * 1024];

void bm_memmove(benchmark::State& state) {
    const auto size = static_cast<size_t>(state.range(0));
    const auto n    = static_cast<ptrdiff_t>(state.range(1));

    const size_t n1 = n < 0 ? 0 : n;
    const size_t n0 = n < 0 ? -n : 0;

    benchmark::DoNotOptimize(v);

    for (auto _ : state) {
        memmove(v + n0, v + n1, size);
        benchmark::DoNotOptimize(v);
    }
}

BENCHMARK(bm_memmove)->ArgsProduct({{8191, 8193}, {-5, +5}});

BENCHMARK_MAIN();

Results on i5-1235U (Alder Lake)

-------------------------------------------------------------
Benchmark                   Time             CPU   Iterations
-------------------------------------------------------------
bm_memmove/8191/-5       71.4 ns         71.5 ns      8960000
bm_memmove/8193/-5       71.1 ns         71.5 ns      8960000
bm_memmove/8191/5        62.6 ns         61.0 ns      8960000
bm_memmove/8193/5        1903 ns         1925 ns       373333

Results on i7-8750H (Coffee Lake)

-------------------------------------------------------------
Benchmark                   Time             CPU   Iterations
-------------------------------------------------------------
bm_memmove/8191/-5        143 ns          141 ns      4977778
bm_memmove/8193/-5        145 ns          146 ns      4480000
bm_memmove/8191/5        77.2 ns         76.7 ns      8960000
bm_memmove/8193/5        80.9 ns         80.2 ns      8960000

Analysis

All I know or suspect so far:

• The problem exists on Alder Lake (Intel Core 12th gen) but does not exist on Coffee Lake (Intel Core 8th gen) or Skylake (Intel Core 6th gen)
• The problematic instruction is rep movsb, which is used in memmove
• The problematic behavior is recreated for me when the size is greater than 8192 and the pointer difference is smaller than 64
• Clang on Linux is also affected, proved by recreating the issue here: https://quick-bench.com/q/HgY3kPAaUIqkfmzwz_NFeoTcj3U

I appreciate any help in investigating the issue further.

Ideally we'd need to report this issue to VCRuntime maintainers.
But I feel like we need to try to gather more information to report it better.

[AlexGuteniev]

My progress on understanding the problem made since I made that PR:

1. In hardware, the problematic instruction is forward rep movsb, and the problematic case is pointers difference is less than 64 bytes.
2. For my Alder Lake it only affects P-cores
3. Other refinements, specifically, only greater than 8192 elements, and only when destination address is smaller are coming from the C runtime library -- it does not use rep movsb for other cases, at least for my setups.

The modified benchmark to investigate CPU behavior without library specific:

#include <benchmark/benchmark.h>
#include <intrin.h>

using namespace std;

alignas(4096) unsigned char v[1024 * 1024];

void bm_memmove(benchmark::State& state) {
    const auto size = static_cast<size_t>(state.range(0));
    const auto n    = static_cast<ptrdiff_t>(state.range(1));

    benchmark::DoNotOptimize(v);

    for (auto _ : state) {
        __movsb(v , v + n, size);
        benchmark::DoNotOptimize(v);
    }
}

BENCHMARK(bm_memmove)->ArgsProduct({{8191, 8193}, 
  {+63, +64, +65, +255, +256}});

BENCHMARK_MAIN();

My results:

---------------------------------------------------------------
Benchmark                     Time             CPU   Iterations
---------------------------------------------------------------
bm_memmove/8191/63         1910 ns         1925 ns       373333
bm_memmove/8193/63         1885 ns         1800 ns       373333
bm_memmove/8191/64         36.4 ns         36.8 ns     20363636
bm_memmove/8193/64         36.4 ns         36.1 ns     19478261
bm_memmove/8191/65         55.1 ns         56.2 ns     10000000
bm_memmove/8193/65         55.6 ns         54.4 ns     11200000
bm_memmove/8191/255        54.8 ns         54.7 ns     10000000
bm_memmove/8193/255        55.9 ns         55.8 ns     11200000
bm_memmove/8191/256        36.2 ns         35.3 ns     19478261
bm_memmove/8193/256        36.0 ns         36.1 ns     19478261

[AlexGuteniev]

statementreply come up with a case in STL where the affected memmove impacts vector:

void rem(benchmark::State& state) {
    vector<char, highly_aligned_allocator<char>> v(static_cast<size_t>(state.range(0)));
    for (auto _ : state) {
        v.erase(v.begin());
        v.push_back(0);
        benchmark::DoNotOptimize(v);
    }
}

BENCHMARK(rem)->Arg(8191);
BENCHMARK(rem)->Arg(8194);

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
rem/8191         60.9 ns         60.0 ns     11200000
rem/8194         1876 ns         1883 ns       373333

[AlexGuteniev]

Confirmed on more CPUs:

• i5-11400H (Tiger Lake),
• Xeon Platinum 8362 (Ice Lake)

Created DevCom-10906320

[StephanTLavavej]

Fix shipped in MSVC Compiler 19.50 Preview 1, thanks again.