🐸

memcpyをまた擦る

2022/08/19に公開

0. はじめに

C++のmemcpyの処理性能の話です。

memcpyの処理性能(最適化)は先駆者に散々擦られたネタですが、ある先駆者はmemcpyはSIMD化するとXX倍速になったと言い、またある先駆者はmemcpyは十分高速だと言い、良く分からなくなりました。

本記事は、私の環境では十分速いよということを確認する話です。

わりと新しめのIntel CPUでWindowsのVisual C++を使ってる方は、似たような結論が導けて参考になるのではと思い、共有します。

1. 前提条件

今回の前提条件は、memcpyするサイズがL3キャッシュに乗らないほど十分大きい場合で考えます。処理性能が気になるのは、コピーするサイズが大きいときだという仮定です。

また計測環境は以下で、以降の内容はこの条件を前提に話を進めます。コンシューマ向けのCPUなので似たような条件の人は多いと思います。

  • CPU : Core-i7 7800X
  • RAM : DDR4-2400@4ch
  • OS : Windows 10 Pro 21H2
  • コンパイラ: Visual Studio Community 2019 16.11.11

2. 事前検討

memcpyが十分速いかどうかの基準は、理論的な最大転送レートに対して、実測の転送レートがどれくらいなのか?を考えればわかりやすいです。

memcpyの処理性能はコピーするサイズがキャッシュの影響を無視できるほど十分大きい場合、DDRの転送レートが性能上限となります。ここで、DDRの最大転送レートは下記の式で算出でき、例えば、DDR4-2400 4chでは76800[MB/sec](= 2400[MHz] * 8[Byte] * 4[ch])となります。

転送レート[Byte/sec] = 動作周波数[Hz] * 8[Byte] * チャンネル数

memcpyはDDRに対する"読込み処理"と"書込み処理"を行いますが、それぞれ単独の処理性能は、読込み処理より書込み処理の方が速く、書込み処理は4スレッドあれば理論的な最大転送レートが出ることがわかっています。

また、DDRの"読込み処理"の転送レートは、SIMD化し4スレッド使った場合に最大転送レートの約68%で、ピュアなC++実装の場合は最大転送レートの約60%になることもわかってます。

従って、memcpyの処理速度は"読込み処理"に律速することが想定され、速いかどうかの基準は以下のように導けると思います。

memcpyが十分に最適化されている場合
→ 最大転送レートの100% > memcpyの転送レート >= 最大転送レートの68%
memcpyがある程度最適化されている場合
→ 最大転送レートの68% > memcpyの転送レート > 最大転送レートの60%
memcpyが最適化されてない場合
→ memcpyの転送レート <= 最大転送レートの60%

3. 計測

念のため自作したSIMD版のmemcpyも合わせて計測し、標準ライブラリのmemcpyの処理性能と比較してみます。

自作したSIMD版のmemcpyは以下で、サイズやアラインメントの制約がある簡易的なものです。計測プログラム全体は、付録を参照ください。

void *memcpy_avx(void *dst, const void *src, size_t len)
{
  const __m256i *s = reinterpret_cast<const __m256i *>(src);
  __m256i *d = reinterpret_cast<__m256i*>(dst);
  __m256i ymm0, ymm1, ymm2, ymm3;

  while (len)
  {
    ymm0 = _mm256_loadu_si256(s + 0);
    ymm1 = _mm256_loadu_si256(s + 1);
    ymm2 = _mm256_loadu_si256(s + 2);
    ymm3 = _mm256_loadu_si256(s + 3);
    _mm256_stream_si256(d + 0, ymm0);
    _mm256_stream_si256(d + 1, ymm1);
    _mm256_stream_si256(d + 2, ymm2);
    _mm256_stream_si256(d + 3, ymm3);
    d += 4;
    s += 4;
    len -= 128;
  }
  return dst;
}

集計結果
コピーするサイズは16MB ~ 2GBを計測し、最大転送レートに対する実測転送レートの割合(=100 * 実測転送レート ÷ 最大転送レート)を、%で表しています。

thread	size[MB]	memcpy[%]	memcpy_avx[%]
4	16	        51.06	        53.79
4	32	        62.96	        64.82
4	64	        71.84	        74.00
4	128	        74.95	        74.45
4	256	        78.34	        80.77
4	512	        78.80	        81.19
4	1024	        79.12	        80.73
4	2048	        78.13	        77.36

標準ライブラリのmemcpyの転送レートは64MB以上コピーするとき最大レートの70%以上でます。また、自作したSIMD版のmemcpy関数(memcpy_avx)と比べても同等の性能です。

なお、コピーするサイズが小さいほど転送レートが下がるのは、スレッド生成や同期処理によるオーバーヘッドの影響が大きくなる為です(計測プログラムの実装の問題です。ごめんなさい)。

転送レートを生値でみると以下です。

thread size[MB]       memcpy[MB/s]   memcpy_avx[MB/s]
     4       16           39217.87           41308.66
     4       32           48353.73           49784.35
     4       64           55171.99           56829.24
     4      128           57559.82           57176.48
     4      256           60165.60           62034.73
     4      512           60517.26           62354.13
     4     1024           60762.15           62002.93
     4     2048           60000.96           59409.62

4. 標準ライブラリのmemcpyのasm

せっかくなので、デバッガで逆アセンブルした標準ライブラリのmemcpyの処理を読むと、以下になってました。

       align   16
YmmLoopNT:
        vmovdqu  ymm1, YMMWORD PTR (__AVX_STEP_LEN*0)[rdx]
        vmovdqu  ymm2, YMMWORD PTR (__AVX_STEP_LEN*1)[rdx]
        vmovdqu  ymm3, YMMWORD PTR (__AVX_STEP_LEN*2)[rdx
        vmovdqu  ymm4, YMMWORD PTR (__AVX_STEP_LEN*3)[rdx]
        vmovntdq YMMWORD PTR (__AVX_STEP_LEN*0)[rcx], ymm1 
        vmovntdq YMMWORD PTR (__AVX_STEP_LEN*1)[rcx], ymm2
        vmovntdq YMMWORD PTR (__AVX_STEP_LEN*2)[rcx], ymm3
        vmovntdq YMMWORD PTR (__AVX_STEP_LEN*3)[rcx], ymm4
        vmovdqu  ymm1, YMMWORD PTR (__AVX_STEP_LEN*4)[rdx]
        vmovdqu  ymm2, YMMWORD PTR (__AVX_STEP_LEN*5)[rdx]
        vmovdqu  ymm3, YMMWORD PTR (__AVX_STEP_LEN*6)[rdx]
        vmovdqu  ymm4, YMMWORD PTR (__AVX_STEP_LEN*7)[rdx]
        vmovntdq YMMWORD PTR (__AVX_STEP_LEN*4)[rcx], ymm1
        vmovntdq YMMWORD PTR (__AVX_STEP_LEN*5)[rcx], ymm2
        vmovntdq YMMWORD PTR (__AVX_STEP_LEN*6)[rcx], ymm3
        vmovntdq YMMWORD PTR (__AVX_STEP_LEN*7)[rcx], ymm4
        add      rcx, __AVX_LOOP_LEN                             
        add      rdx, __AVX_LOOP_LEN                             
        sub      r8, __AVX_LOOP_LEN                              
        cmp      r8, __AVX_LOOP_LEN                              
        jae      YmmLoopNT                                       

vmovdquは_mm256_loadu_si256のことで、vmovntdqは_mm256_stream_si256なので、(ループの単位は違いますが)自作した関数とほぼ同じことをやってるようです。

5. まとめ

  • コピーサイズが大きなとき、Visual Studioの標準ライブラリのmemcpyはSIMD化されてる
  • 単純にSIMD化したレベルの自作memcpyでは、大きな性能差はなさそう
  • 標準ライブラリのmemcpyは既にDDRの最大転送レートの70%以上出てるので、さらに2倍,3倍..速くすることは、そもそもできない

サイズ別に細かく調べるとまだ最適化できる余地はあるかもしれませんが、十分早いのではと思います

6. 付録:計測プログラム全体

#include <cstdio>
#include <cstdint>
#include <cstring>
#include <numeric>
#include <vector>
#include <thread>
#include <intrin.h>

using namespace std;

void *memcpy_avx(void *dst, const void *src, size_t len)
{
  const __m256i *s = reinterpret_cast<const __m256i *>(src);
  __m256i *d = reinterpret_cast<__m256i*>(dst);

  __m256i ymm0, ymm1, ymm2, ymm3;

  while (len)
  {
    ymm0 = _mm256_loadu_si256(s + 0);
    ymm1 = _mm256_loadu_si256(s + 1);
    ymm2 = _mm256_loadu_si256(s + 2);
    ymm3 = _mm256_loadu_si256(s + 3);
    _mm256_stream_si256(d + 0, ymm0);
    _mm256_stream_si256(d + 1, ymm1);
    _mm256_stream_si256(d + 2, ymm2);
    _mm256_stream_si256(d + 3, ymm3);
    d += 4;
    s += 4;
    len -= 128;
  }

  return dst;
}

int main(void)
{
  using MemCopy = void* (*)(void*, const void*, size_t);
  constexpr MemCopy MEM_COPY[] =
  {
    memcpy,
    memcpy_avx,
  };
  constexpr size_t READ_WRITE_SIZE[] =
  {
       16ULL * 1024 * 1024,  //   16MB
       32ULL * 1024 * 1024,  //   32MB
       64ULL * 1024 * 1024,  //   64MB
      128ULL * 1024 * 1024,  //  128MB
      256ULL * 1024 * 1024,  //  256MB
      512ULL * 1024 * 1024,  //  512MB
     1024ULL * 1024 * 1024,  // 1024MB
     2048ULL * 1024 * 1024,  // 2048MB
  };
  constexpr int NUM_THREAD[] =
  {
    1, // 1 thread
    2, // 2 thread
    4, // 4 thread
  };
  constexpr int PTN_FUNC = sizeof(MEM_COPY) / sizeof(MemCopy);
  constexpr int PTN_RW_SIZE = sizeof(READ_WRITE_SIZE) / sizeof(size_t);
  constexpr int PTN_THREAD_NUM = sizeof(NUM_THREAD) / sizeof(int);
  constexpr int NUM_ITR = 3;
  constexpr int MEMSET_VAL = 255;
  constexpr int ALIGNMENT = 64;
  constexpr double CPU_FREQ = 3.5 * 1024 * 1024 * 1024; // i7-7800X 3.5GHz

  double aveTrRate[PTN_FUNC][PTN_THREAD_NUM][PTN_RW_SIZE] = {};

  for (int f = 0; f < PTN_FUNC; ++f)
  {
    for (int t = 0; t < PTN_THREAD_NUM; ++t)
    {
      for (int s = 0; s < PTN_RW_SIZE; ++s)
      {
        char *src = nullptr;
        char *dst = nullptr;
        const auto rwSize = READ_WRITE_SIZE[s];
        const auto numThread = NUM_THREAD[t];
        vector<double> rwRate(NUM_ITR);
        vector<size_t> rwSizePerThread(numThread);
        vector<size_t> rwOfstPerThread(numThread, 0);

        // スレッド毎の読書きサイズ計算
        for (int i = 0; i < numThread; ++i)
        {
          rwSizePerThread[i] = rwSize / numThread;
          if (i == numThread - 1)
            rwSizePerThread[i] += rwSize % numThread; // 端数処理
          if (i > 0)
            rwOfstPerThread[i] = rwOfstPerThread[i - 1] + rwSizePerThread[i];
        }

        // ヒープメモリ確保
        src = (reinterpret_cast<char *>(_aligned_malloc(rwSize, ALIGNMENT)));
        dst = (reinterpret_cast<char *>(_aligned_malloc(rwSize, ALIGNMENT)));
        if (!src)
        {
          printf("***src memory allocation err\n");
          exit(1);
        }
        if (!dst)
        {
          printf("***dst memory allocation err\n");
          exit(1);
        }

        // 初期化
        memset(src, MEMSET_VAL, rwSize);
        memset(dst, ~MEMSET_VAL, rwSize);

        for (int i = 0; i < NUM_ITR; ++i)
        {
          uint64_t beg, end;
          uint32_t tmp;
          bool isErr = false;
          double rate = 0.0;
          vector<thread> trThread;
          trThread.reserve(numThread);

          // キャッシュメモリをフラッシュ
          for (auto j = 0; j < rwSize >> 6; ++j)
          {
            _mm_clflush(src + 64 * j);
            _mm_clflush(dst + 64 * j);
          }

          // 転送時間を計測
          beg = __rdtscp(&tmp);

          for (int j = 0; j < numThread; ++j)
          {
            trThread.emplace_back(thread(MEM_COPY[f],
                                         dst + rwOfstPerThread[j],
                                         src + rwOfstPerThread[j],
                                         rwSizePerThread[j]));
          }
          for (int j = 0; j < numThread; ++j)
            trThread[j].join();
          end = __rdtscp(&tmp);

          // 結果のテスト
          for (size_t j = 0; j < rwSize; ++j)
          {
            if (dst[j] != static_cast<char>(MEMSET_VAL))
              isErr = true;
          }
          if (isErr)
          {
            printf("***verify err\n");
            exit(1);
          }

          // 転送レート(MB per second)を記録
          rate = (2 * rwSize / (1024 * 1024)) / ((end - beg) / CPU_FREQ);
          rwRate.push_back(rate);
        }

        // ヒープメモリ解放
        _aligned_free(src);
        _aligned_free(dst);

        aveTrRate[f][t][s] =
          accumulate(rwRate.begin(), rwRate.end(), 0.0) / NUM_ITR;
      }
    }
  }

  printf("%6s %8s %18s %18s\n"
         , "thread"
         , "size[MB]"
         , "memcpy[MB/s]"
         , "memcpy_avx[MB/s]");
  for (int t = 0; t < PTN_THREAD_NUM; ++t)
  {
    for (int s = 0; s < PTN_RW_SIZE; ++s)
    {
      printf("%6d %8llu"
           , NUM_THREAD[t]
           , READ_WRITE_SIZE[s] / (1024 * 1024));
      for (int f = 0; f < PTN_FUNC; ++f)
        printf(" %18.2f", aveTrRate[f][t][s]);
      printf("\n");
    }
  }
}

Discussion