C++ のコンテナ・スレッド・-O2 を実測で比べる

シリーズ：C++講座 6/6（上級）。 テンプレートが書けて STL も使える人（第5回）で、これから C++ のコードを速くしたり、複数コアで動かしたりする人向けです。読み終えると、計算量だけでなく実測でコンテナを選び、reserve と小さな文字列の最適化（SSO）で見えない確保を避け、ThreadSanitizer でデータ競合を捕まえ、ミューテックス・アトミック・「共有しない」を使い分け、デバッグビルドが 30 倍遅くなる理由を説明できるようになります。

基本情報技術者試験やデータ構造の講義では「連結リストは挿入が O(1) で速い」と習います。間違いではありませんが、今の CPU で測ると話がだいぶ変わります。「アトミックはロックフリーだから速い」「テストは -O0 で十分」も同じです。この回では、そうした定説を1つずつ今のマシンで確かめます。以下はすべて Apple Silicon Mac（M1 Pro、ハードウェアスレッド 8）、macOS 26、Apple clang 21.0.0 + libc++ で、特に断りがなければ clang++ -std=c++23 -Wall -Wextra -pedantic -O2、シード固定・中央値で実行しました。GCC・MSVC・Linux・Valgrind は動かしていません。別の CPU では比率は変わりますが、理由は変わりません。

5つのコンテナ、4つの作業

標準のシーケンスコンテナと連想コンテナを int で測りました。キーは 0..N-1 を std::mt19937（シード 42）でシャッフルしたもの、検索キーは同じ生成器の続きから取ったランダム値で、時間はすべて 5 回の中央値です。

template <class F> double med_ms(F f) {
    std::vector<double> t;
    for (int r = 0; r < 5; ++r) {
        auto a = clk::now(); f(); auto b = clk::now();
        t.push_back(std::chrono::duration<double, std::milli>(b - a).count());
    }
    std::sort(t.begin(), t.end());
    return t[2];
}
// e.g. med_ms([&] { sink = std::accumulate(l.begin(), l.end(), 0LL); });

数字が言っていること：

• list はほぼ全敗。 push_back のたびにノードを確保します（25 ms 対 0.7 ms）。合計は、ノードが確保順に並んでいる間は vector の 23 倍「程度」でしたが、l.sort() でつなぎ替えた後は同じ合計が 61 ms（別の回では 52.7 ms）になりました。1歩ごとに予測できないアドレスへ飛び、キャッシュを外すからです。連結リストの記事の利点と欠点を数字にするとこうなります。
• 途中への挿入は vector が 77 倍速い。 list::insert は O(1) でも、位置を探すのはどちらも O(n) で、1万個のノードをたどるのは 40 KB の連続した int を memmove するよりはるかに遅いのです。
• 先頭への挿入だけは deque の出番：0.04 ms 対 vector の 11 ms。vector は毎回全要素をずらします。
• 検索は unordered_map が map の 35 倍速い。 map は赤黒木で、1回の検索で 20 段ほどポインタをたどります。ソート済み vector の二分探索はその中間で、構築時間とメモリでは勝ちます。

Java の ArrayList と LinkedList でも同じ話になります。Java コレクションの実測も参照してください。

reserve と見えない確保

libc++ の vector は、空から push_back すると容量を倍々に増やします。int を 100 万回 push_back する間の operator new の呼び出し回数を数えました。

vector<int> 1M push_back, reserve=0: allocations=21 final capacity=1048576
vector<int> 1M push_back, reserve=1: allocations=1 final capacity=1000000

確保 21 回と、伸びていくバッファのコピー 20 回、対して1回。1,000 万回の push_back では 5.0〜5.9 ms が 3.1〜3.3 ms になりました（7 回の中央値、2回実行）。倍々の伸長がもともと安いので、ここでの reserve の効果は 10 倍ではなく 1.6 倍です。効くのは要素のムーブが高いときや、使わない 48,576 個分の領域を無駄にしたくないときです。

小さな文字列の最適化：23 文字目のコスト

std::string は短い文字列をオブジェクトの中に直接持ち、長いときだけヒープを確保します。これが SSO（small-string optimization） です。「短い」とは何文字までか、確保回数で調べました。

std::printf("sizeof(std::string)=%zu  capacity of empty string=%zu\n",
            sizeof(std::string), std::string().capacity());
for (int len : {0, 15, 22, 23, 24, 100}) {
    n_alloc = 0;
    std::string s(len, 'x');
    std::printf("len %3d: allocations=%ld capacity=%zu\n", len, n_alloc, s.capacity());
}

sizeof(std::string)=24  capacity of empty string=22
len   0: allocations=0 capacity=22
len  15: allocations=0 capacity=22
len  22: allocations=0 capacity=22
len  23: allocations=1 capacity=24
len  24: allocations=1 capacity=31
len 100: allocations=1 capacity=103

libc++ の文字列は 24 バイトで、22 文字まではヒープに触れません。reserve 済みの vector に文字列を 100 万個作ると、22 文字で 5.9 ms、23 文字で 17.7 ms（ウォームアップ1回の後の 5 回の中央値。22 文字で 8.2 ms の回もありました）。1文字でコストが3倍です。第4回のコピー計測で 32 文字の文字列が1つずつ確保していた理由もこれです。libstdc++（GCC）は 32 バイトで 15 文字まで内蔵です（ここでは動かしていません）。

スレッド、std::async、TSan で捕まえるデータ競合

std::thread は関数を新しい OS スレッドで動かし、破棄する前に join() が必要です。C++20 の std::jthread はデストラクタで自動的に join します（この libc++ で動きました）。std::async はタスクを動かして std::future を返し、get() は結果を待ち、タスク内の例外を投げ直します。

auto f = std::async(std::launch::async, [&] { return sum_range(v, 0, h); });
long long right = sum_range(v, h, v.size());
long long total = f.get() + right;

async task on another thread: 1
total=32000004000000 expected=32000004000000 hw threads=8
deferred task on main thread: 1

std::launch::async は明示しましょう。std::launch::deferred ではタスクが get() の時点で呼び出し元のスレッドで動き、「async なのに並列にならない」という定番のバグになります。

そして並行処理の講義が必ず最初に扱うバグです。2つのスレッドが普通の int を加算します。

#include <thread>
#include <cstdio>
int counter = 0;
void work(){ for(int i=0;i<100000;i++) counter++; }
int main(){
  std::thread a(work), b(work);
  a.join(); b.join();
  std::printf("counter=%d (expected 200000)\n", counter);
}

$ clang++ -std=c++23 -O0 race.cpp -o race0 && ./race0      (5 runs)
counter=102379 (expected 200000)
counter=102276 (expected 200000)
counter=118794 (expected 200000)
counter=102211 (expected 200000)
counter=101185 (expected 200000)
$ clang++ -std=c++23 -O2 race.cpp -o race2 && ./race2      (3 runs)
counter=200000 (expected 200000)

-O0 では加算の半分が消えました。counter++ は読み込み・加算・書き込みの3つで、スレッド同士が上書きし合います。-O2 では毎回正しい値でした。コンパイラがループを counter += 100000 1回に変え、競合の窓がごく小さくなったからです。バグは残っています。 データ競合は未定義動作で、オプティマイザはそう変えてよいのです（-O で変わる未定義動作は C言語講座 第5回にもっとあります）。ThreadSanitizer はどちらでも見つけます。

$ clang++ -std=c++23 -g -O1 -fsanitize=thread race.cpp -o race_tsan && ./race_tsan
==================
WARNING: ThreadSanitizer: data race (pid=42472)
  Write of size 4 at 0x000104434000 by thread T2:
    #0 work() race.cpp:4 (race_tsan:arm64+0x10000072c)
  Previous write of size 4 at 0x000104434000 by thread T1:
    #0 work() race.cpp:4 (race_tsan:arm64+0x10000072c)
  Location is global 'counter' at 0x000104434000 (race_tsan+0x100008000)
  Thread T2 (tid=26070715, running) created by main thread at:
    #4 main race.cpp:6 (race_tsan:arm64+0x100000778)
SUMMARY: ThreadSanitizer: data race race.cpp:4 in work()
==================
counter=200000 (expected 200000)
ThreadSanitizer: reported 1 warnings

Apple Silicon の macOS でも Apple clang の TSan は動きます。TSan ビルドでも合計は正しく出ていて、本当のことを言ったのはレポートだけでした。この Mac では TSan のバイナリはその後終了コード 134 で終わったので、CI のスクリプトは失敗として扱えます。TSan と ASan は1つのビルドに同居できません（clang++: error: invalid argument '-fsanitize=address' not allowed with '-fsanitize=thread'）。ビルドを2つ作ります。

アトミック・ミューテックス・共有しない、を実測

競合を直す方法を比べます。4 スレッドがそれぞれ共有カウンタに 1 を 1,000 万回足し（合計 4,000 万）、5 回の中央値。スレッドは std::jthread です。

// mutex
run_threads([&](int) { for (int i = 0; i < PER; ++i) { std::lock_guard<std::mutex> g(m); ++n; } });
// atomic
run_threads([&](int) { for (int i = 0; i < PER; ++i) n.fetch_add(1); });
run_threads([&](int) { for (int i = 0; i < PER; ++i) n.fetch_add(1, std::memory_order_relaxed); });
// count locally, publish once
run_threads([&](int) {
    long long local = 0;
    for (int i = 0; i < PER; ++i) { ++local; asm volatile("" : "+r"(local)); }  // barrier: keep the loop
    n += local; });

5つとも結果はちょうど 40,000,000 でした。大事な点：

• 激しく競合すると、ミューテックスが既定のアトミックに勝った。 1スレッドならアトミックのほうが速い（274 ms 対 353 ms）のに、4スレッドが1つのキャッシュラインを叩くと、fetch_add のたびにそのラインがコア間を行き来します。ミューテックスでは1つのスレッドが何回か続けて加算できました。「アトミックは常に速い」は誤りです。
• 本当のコストは共有そのもの。 共有カウンタを使う4スレッドは、共有しない1スレッドの 52〜126 倍遅くなりました。ローカルに数えて最後に1回足す方式は1スレッドより 3.6 倍速く、コアを本当に使えたのはこれだけでした。
• memory_order_relaxed は、ほかのデータの同期に使わない純粋なカウンタなら正しい選択です。「カウントを見た後で」ほかのデータを読むスレッドがあるなら既定の順序が必要です。

原則：スレッド間で共有するものをできるだけ減らし、残ったものはミューテックスで守り、アトミックは単一のフラグやカウンタに使います。

-O0 対 -O2：デバッグビルドは速さについて嘘をつく

同じファイルを2回ビルドし、int 1,000 万個（rng() % 1000、シード 42）、5 回の中央値です。

教訓は3つです。1つ目、STL のコードはインライン化が前提です。 -O0 では operator[] もイテレータの ++ もラムダも本物の関数呼び出しになり、std::accumulate は -O2 の 60 倍遅くなりました。C++ の速さをデバッグビルドで判断してはいけません。2つ目、既定の比較の std::sort はほとんど変わりませんでした。libc++ が最適化済みのものをライブラリに同梱しているからです（第5回）。ラムダの比較はあなたのフラグでコンパイルされます。3つ目、ranges は自動的にタダではありません。 -O2 で filter | transform は 33.6 ms、同じ条件の素のループは 1.2 ms で、後者はコンパイラが分岐のないベクトル命令に変えていました。ホットパスでビューを使う前に測りましょう。キャッシュの効果や lldb での調査は C言語講座 第6回にあります。

よくある間違い → 実際に起きたこと → 直し方

正直な限界・バージョンの注意

• 実行環境は Apple clang 21.0.0 と libc++（_LIBCPP_VERSION 220106）、M1 Pro 1台、macOS 26 だけです。GCC/libstdc++、MSVC、Linux、Valgrind（helgrind）は動かしていません。比率は CPU のキャッシュとコア数で変わり、10% 程度までの差は実行ごとのばらつきの範囲です。
• この Mac の steady_clock は約 42 ns 刻みなので、1マイクロ秒未満の時間は載せていません。
• バージョン：std::thread・std::async・std::mutex・std::atomic は C++11、std::jthread は C++20（ここでは __cpp_lib_jthread 201911）。std::hardware_destructive_interference_size（C++17）は定義されていました。std::execution::par の並列アルゴリズムはこの libc++ にはなく、import std; は unknown type name 'import' で失敗しました（このツールチェーンには標準ライブラリのモジュールが付いていません）。
• SSO の上限 22 文字、伸長率 2 倍、コンパイル済みの std::sort は libc++ の実装の話です。
• TSan の終了コード 134 はここで観測した値です。ドキュメント上は、競合を報告すると 0 以外で終わるのが既定です。

練習問題

1. race.cpp を、どの最適化レベルでも 200000 を出し、TSan が何も報告しないように直してください。変更は最小で。

2. 実行せずに、libc++ で各ループのヒープ確保回数を予想し、回数を数える operator new で確かめてください。

for (int len : {10, 30}) {
    std::vector<std::string> v;
    v.reserve(1000);
    for (int i = 0; i < 1000; ++i) v.push_back(std::string(len, 'x'));
}

解答

1. カウンタをアトミックにします。

#include <atomic>
std::atomic<int> counter{0};
void work(){ for(int i=0;i<100000;i++) counter++; }
// print with counter.load()

-fsanitize=thread 付きで counter=200000 (expected 200000)、警告なし、終了コード 0 でした。std::atomic<int> の counter++ はアトミックな fetch_add です。速さを求めるなら、実測の節のローカル集計版がさらに上です。

2. 10 文字は 1 回（reserve したバッファだけ。10 文字は SSO のバッファに収まる）。30 文字は 1001 回（バッファ＋文字列ごとに1回）。push した一時オブジェクトは vector にムーブされ、ヒープ上の文字列のムーブはポインタを渡すだけです。reserve なしだと 30 文字で 1011 回、バッファが 1, 2, 4, …, 1024 と伸びる分の 11 回が増えます。

シリーズのまとめ

C++講座はここまでです。第1回から読んできたなら、サニタイザ付きでビルドとデバッグができ、RAII とスマートポインタで資源を持ち、テンプレートのエラーを読み、性能の判断を実測で裏付けられるようになっているはずです。新しく学ぶ人に勧めるなら第1回からどうぞ。

• 前回：C++講座 第5回：テンプレート・STL アルゴリズム・ranges
• それ以前：第2回、第3回、第4回
• 関連：C言語の性能：キャッシュ・make・lldb、Swift のメモリと -O 性能、プログラミング学習ロードマップ