memcpyの速度測定

C/C++のmemcpyは十分に最適化されており、forループする大抵のコードよりは速くなるように出来ています。しかし測り方を間違えると十分な効果を期待できません。例えばLinuxで以下のコードでは正しく測定できません。なぜだか分かりますか？

#include <chrono>
#include <iostream>
#include <cstring>

using namespace std;
using namespace std::chrono;

typedef size_t target_t;

int main(int argc, char* argv[]) {
    constexpr size_t N = 1024 * 1024 * 1024; // 1GiB

    auto src = new target_t[N/sizeof(target_t)];
    auto dst = new target_t[N/sizeof(target_t)];

    auto begin = high_resolution_clock::now();
    memcpy(dst, src, N);
    auto end = high_resolution_clock::now();

    cout << N << "bytes copy: " << N / 1024. / 1024. / duration_cast<nanoseconds>(end - begin).count() * 1000000000 << "[MiB/s]" << endl;
    return 0;
}

プログラムは正しく動きます。

$ g++ -g -O0 hoge.cpp -o hoge
$ ./hoge
1073741824bytes copy: 1560.47[MiB/s]
$

何が正しく測定できてないのでしょう？

答え

まずは答えの前に正しい結果です。

$ g++ -g -O0 hoge.cpp -o hoge
$ ./hoge
1073741824bytes copy: 11906.7[MiB/s]
$

およそ7.7倍高速化しています。誤差の範疇にないので、最初のコードでは正しく測定できていませんね。正しい結果のコードは、以下のとおりです。

#include <chrono>
#include <iostream>
#include <cstring>

using namespace std;
using namespace std::chrono;

typedef size_t target_t;

int main(int argc, char* argv[]) {
    constexpr size_t N = 1024 * 1024 * 1024; // 1GiB

    auto src = new target_t[N/sizeof(target_t)];
    memset(src, 0, N); // 追加
    auto dst = new target_t[N/sizeof(target_t)];
    memset(dst, 0, N); // 追加

    auto begin = high_resolution_clock::now();
    memcpy(dst, src, N);
    auto end = high_resolution_clock::now();

    cout << N << "bytes copy: " << N / 1024. / 1024. / duration_cast<nanoseconds>(end - begin).count() * 1000000000 << "[MiB/s]" << endl;
    return 0;
}

最初のコードとの違いは、srcとdstに対してmemsetするコードが追加されているだけです。

初期化コードが足りなかったのでしょうか？以降理由を調査してみます。

初期化コードが足りなかったのか？

仮に何か未初期化時は0以外で、0初期化すると高速化するのであれば、「初期化コードが足りなかったから」で説明が付きます。なので、まずは未初期化時に何が入っているのかを見てみます。

only_alloc.cpp

#include <iostream>

using namespace std;

typedef size_t target_t;

int main() {
    constexpr size_t N = 1024 * 1024 * 1024; // 1GiB

    auto src = new target_t[N/sizeof(target_t)];
    target_t value = 0;
    for (const target_t *p = &src[0], *end = &src[sizeof(src)/sizeof(src[0])]; p != end;) value |= *p++;
    cout << value << endl;

    return 0;
}

Linux(Ubuntu 20.04)で実行すると、出力は0になります。つまり、memsetがなくとも、確保した全ての要素は0で初期化されているということです。これはなぜでしょうか？

C++ではglobalなnew演算子はユーザー定義も出来ますが、なければランタイム側で用意されることになっています。上記Linux環境だとlibstdc++が該当していて、そのオリジナルとなる最新コードが以下になります。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/libsupc%2B%2B/new_opv.cc

2023/11/15現在の当該コード部分を引用すると以下のようになります。

_GLIBCXX_WEAK_DEFINITION void*
operator new[] (std::size_t sz) _GLIBCXX_THROW (std::bad_alloc)
{
  return ::operator new(sz);
}

中で呼ばれている[]が付かないnew演算子の定義は以下になります。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/libsupc%2B%2B/new_op.cc

2023/11/15現在の当該コード部分を引用すると以下のようになります。

_GLIBCXX_WEAK_DEFINITION void *
operator new (std::size_t sz) _GLIBCXX_THROW (std::bad_alloc)
{
  void *p;

  /* malloc (0) is unpredictable; avoid it.  */
  if (__builtin_expect (sz == 0, false))
    sz = 1;

  while ((p = malloc (sz)) == 0)
    {
      new_handler handler = std::get_new_handler ();
      if (! handler)
	_GLIBCXX_THROW_OR_ABORT(bad_alloc());
      handler ();
    }

  return p;
}

つまり、new[]演算子はデフォルトだと単にmallocで必要サイズを確保しているだけということです(正常に確保できた場合)。

ではmallocで0初期化されているのでしょうか？man mallocすると以下のように書いてあります。

The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not initialized. If size is 0, then malloc() returns either
NULL, or a unique pointer value that can later be successfully passed to free().

メモリは初期化されてないようです。だとするとmallocでない誰か、つまりOSレベルでの初期化が行われてる可能性が高いということになります。これを確認するためにstraceを使って使用されているシステムコールを確認してみます。

$ strace ./only_alloc

色々出力されますが、mainの中で実施されてることは以下の3行です(mainの中身を空にして実行し、差分を見ると分かります)。

mmap(NULL, 1073745920, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fbb38477000
fstat(1, {st_mode=S_IFCHR|0600, st_rdev=makedev(0x88, 0x3), ...}) = 0
write(1, "0\n", 2)                      = 2

ここで先頭のmmapがmallocから呼ばれたシステムコールになります。mmapは仮想アドレス空間に新しいページのマッピングを作成します。マッピングできるものはファイルかメモリになります。上のケースではMAP_ANONYMOUSが指定されているのでメモリです。新しく1GiB(1,073,745,920byte)分読み書き可能なメモリ用にアドレスを確保するということです。そして最初に物理メモリを割り当てられたときはメモリ内容が0に初期化されます(man mmapのMAP_ANONYMOUSの項に記載があります)。つまり予想したとおりOSの機能(システムコール)で0初期化されている、ということになります。

まとめると、Linux上でnewで確保された物理メモリは(mmapシステムコールにより、物理メモリを割り当てられたとき)0初期化されるということです。なお、ヒープは再利用される可能性もあり、その場合は物理メモリが既に割り当てられているので初期化されません。

そしてmemsetがなくとも0で初期化されているということは、初期化が重要というわけではない、ということになります。ではなぜmemsetがあったときにmemcpyが速くなっていたのでしょうか？

楽観的メモリ割当て

実はmallocのmanual pageで少し分かりにくい記載があります。

By default, Linux follows an optimistic memory allocation strategy. This means that when malloc() returns non-NULL there is no guarantee that the memory really is available.
In case it turns out that the system is out of memory, one or more processes will be killed by the OOM killer. For more information, see the description of /proc/sys/vm/over‐
commit_memory and /proc/sys/vm/oom_adj in proc(5), and the Linux kernel source file Documentation/vm/overcommit-accounting.rst.

意訳をすると…

デフォルトでLinux は楽観的メモリ割当て戦略に従います。これは、malloc() が NULL 以外を返した場合、メモリが実際に使用可能であるという保証がないことを意味します。 システムのメモリが不足していることが判明した場合、1 つ以上のプロセスが OOM キラーによって強制終了されます。詳細については、proc(5) の/proc/sys/vm/overcommit_memory 、 、/proc/sys/vm/oom_adjの説明、および Linux カーネル ソース ファイル Documentation/vm/overcommit-accounting.rstを参照してください。

となります。楽観的メモリ割当てとは何でしょう？ググったりしてみましたが、実際に使用可能な保証がなく、OOMキラーの餌食になること以外何も見つけられませんでした。明快な答えのためにはCライブラリの奥深くや、カーネルの実装仕様の奥深くに触れることになるため、言及を避けられている印象です。

参考となる文献に以下がありました。Linuxの開発者の1人であるRobert Landley氏のメモみたいなものです。

https://landley.net/writing/memory-faq.txt

How does the page fault handler allocate physical memory?

The Linux kernel uses lazy (on-demand) allocation of physical pages, deferring the allocation until necessary and avoiding allocating physical pages which will never actually be used.

Memory mappings generally start out with no physical pages attached. They define virtual address ranges without any associated physical memory. So malloc() and similar allocate space, but the actual memory is allocated later by the page fault handler.

Virtual pages with no associated physical page will have the read, write, and execute bits disabled in their page table entries. This causes any access to that address to generate a page fault, interrupting the program and calling the page fault handler.

When the page fault handler needs to allocate physical memory to handle a page fault, it zeroes a free physical page (or grabs a page from a pool of prezeroed pages), attaches that page of memory to the Page Table Entry associated with the fault, updates that PTE to allow the appropriate access, and resumes the faulting instruction.

意訳すると…

ページフォールトハンドラーはどうやって物理メモリを割り当てるのか?

Linux カーネルは物理ページの遅延 (オンデマンド) 割り当てを使用し、必要になるまで割り当てを延期し、実際には使用されない物理ページの割り当てを避けています。

メモリ マッピングは、通常物理ページが接続されていない状態で開始されています。関連付けられた物理メモリなしで仮想アドレス範囲を定義しています。なので、malloc() やその類似品はアドレス空間を割り当てますが、実際のメモリは後でページ フォールト ハンドラーによって割り当てることになります。

物理ページが関連付けられていない仮想ページでは、ページ テーブル エントリの読み取り、書き込み、および実行ビットが無効になります。これにより、そのアドレスへのアクセスによってページ フォールトが生成され、プログラムが中断され、ページ フォールト ハンドラーが呼び出されます。

ページ フォールト ハンドラーは、ページ フォールトを処理するために物理メモリを割り当てる必要がある場合、空き物理ページをゼロ化し (または、事前にゼロ化されたページのプールからページを取得し)、そのメモリのページをフォールトに関連付けられたページ テーブル エントリに接続します。適切なアクセスを許可するためにその PTE を更新し、障害のある命令を再開します。

つまり今回のケースでは、malloc()のタイミングではアドレスが割当てられるけど物理メモリがなく、実際に当該アドレスにアクセスした際に物理メモリが割当てられるということです。もちろんmalloc呼出しの全てがそうなるわけではありません。

これで大分カラクリが見えてきました。memsetがない場合、mmapでアドレスだけ確保しただけで物理メモリが確保されず、memcpyのタイミングで物理メモリが確保されることになったため、余計な時間がかかったということです。逆に言うと、memsetがある場合は、そこで物理メモリが確保されているので、余計な時間がかかっています。

検証

Linux環境でnewの前後とmemsetの前後で、仮想メモリと物理メモリの量をpsコマンドで計測してみます。

#include <iostream>
#include <sstream>
#include <cstring>
#include <unistd.h>

using namespace std;

typedef size_t target_t;

int main(int argc, char* argv[]) {
    constexpr size_t N = 1024 * 1024 * 1024; // 1GiB

    auto pid = getpid();    
    stringstream ss;
    ss << "ps -o vsz,rss -p " << pid;
    string cmd = ss.str();
    
    system(cmd.c_str());
    auto src = new target_t[N/sizeof(target_t)];
    system(cmd.c_str());
    memset(src, 0, N);
    system(cmd.c_str());

    return 0;
}

実行すると、以下のように出力されます。

   VSZ   RSS
  5880  3244
   VSZ   RSS
1054460 3248
   VSZ   RSS
1054460 1051824

newでは仮想メモリだけ増え(つまりアドレスの割当てだけ行われている)、memsetでは物理メモリだけ増えている(アクセスされたので物理メモリの割当ても行われた)のが分かります。

結論

楽観的メモリ割当てが行われるLinuxでは、newだけだと物理メモリが割当てられず、いきなりmemcpyを計測しても物理メモリ割当て時間まで含まれてしまう。正しく時間計測をするなら、事前に当該メモリにアクセスし物理メモリを確保してからにしないといけない。

おまけ

Windowsの場合はVS2019で確かめましたが、memsetがなくても、Debugモードだとmallocが0初期化するようになってるので遅くなりません。逆にReleaseモードだとmemsetがないと遅くなります(Linuxの場合-O2にするとmemcpy呼び出し自体が消えてしまう)。なのでLinux同様mallocが楽観的メモリ割当てを行っていて、物理メモリは遅延割当てされると予想しています。

未分類C++,linux

Posted by first_user