memcpyをまた擦る
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の"読込み処理"の転送レートは、ＳIMD化し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