std::mapへの整列済みデータの挿入がそうでない場合より高速な理由

Question

質問内容

Optimize C++(第3版)10.6.1節に「整列済みデータの挿入はそうでないデータの挿入より高速である(要約)」との記述があり、自分でも実験してみたところ確かに数倍程度高速に動作しているようでした。

ただ書籍ではその理由については触れられていませんでした。自分の考えとしては、整列済みデータの挿入の方が木に偏りが生じやすく、その結果として回転操作の回数が多くなりむしろ遅くなると思っていたのでこの結果は不思議です。どなたか詳しい方がいらっしゃれば、この結果となる理由についてお知恵を拝借できないでしょうか。

該当のソースコード

測定に使用したコードを記載します。
500000要素の重複のないベクトルを生成し、それを前から順番に1つずつmapへinsertします。

#include <algorithm>
#include <chrono>
#include <functional>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <vector>

using namespace std;

void build_rnd_vector(vector<int>& v, unsigned int count)
{
    default_random_engine e;
    uniform_int_distribution<unsigned int> d(count, count * 10 - 1);
    auto randamizer = bind(d, e);
    set<int> unique;
    v.clear();
    while (v.size() < count) {
        unsigned int rv = randamizer();
        if (unique.insert(rv).second) {
            v.push_back(rv);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    chrono::system_clock::time_point start, end;

    int count = 5000000;

    map<int, int> mp;
    vector<int> v;
    build_rnd_vector(v, count);

    // 整列させる
    sort(v.begin(), v.end());

    start = chrono::system_clock::now();
    for (int i = 0; i < v.size(); ++i) {
        mp.insert({ v[i], i });
    }
    end = chrono::system_clock::now();
    double elapsed = chrono::duration_cast<chrono::milliseconds>(end - start).count();

    cout << "Elapsed Sec " << elapsed << " msec\n";

    return 0;
}

非整列データの場合は途中のsort()をコメントアウトして計測しました。
AtCoderのコードテストでC++20(gcc 12.2)で計測してみたところ、Elapsed Secは以下のような結果となりました。

非整列	整列済み
3884	1240

(msec)

Answer 1

実装依存の話で"この実装で"と指定しないと議論になりませんが、ざっと検索すると赤黒木が一般的な実装みたいなのでその前提で考えました。

ソート済みのデータを順に挿入していくと、挿入位置の探索は根から見て常に右側に右側にと進みます。
また回転は確かに高い頻度で起こりますが、根から見て右側に探索する経路のどこかでしか起こらないはずです。（証明できないので断言はできませんが、回転は常に1回で済むはずです。ランダムだとたまに2回の回転が発生します）

それでメモリやCPUキャッシュやCPUの分岐予測が効きやすく、全体は速くなるのではないでしょうか?

---

Claude CodeにPythonで素朴な赤黒木の実装を作らせてみて様子を見たのですが、ソート済みのデータだとデータ数に対してとても線形に近い形で実行時間が伸びていきました。比較してランダムな順のデータだと掛かる時間の伸びが非線形になって、ある程度の個数以下だとランダムの方が速いが、どこかでソート済みの方が速くなる、という感じでした。

ソート済みのデータを渡すとほぼすべてで1回の回転が発生します。
ランダムにシャッフルしたデータを渡すと6割で回転なし、2割で1回の回転、2割で2回の回転、という雰囲気。
リカラーもソート済みのデータを渡した時の方が2倍くらい起きました。
ソード済みのデータを渡した時の方が起きる操作は明らかに多いです。
にも関わらず実行時間はソート済みのデータの方が短い（ある件数より多い場合）という傾向のようです。
"理論値として回転が少ないから速い"みたいなことではなくて、"実際に動かしたら速い"という話だから理由まで言及しなかったのだろうな、と感じました。

Comments

[shukrin]

ご回答ありがとうございます。

> 実装依存の話
実装は一応libstdc++の想定でした。説明不足で申し訳ないです。
おっしゃる通り中身は赤黒木だと思われます。

> ソード済みのデータを渡した時の方が起きる操作は明らかに多いです。
> にも関わらず実行時間はソート済みのデータの方が短い（ある件数より多い場合）という傾向のようです。
実験ありがとうございます。となると操作回数が多ければ遅いはず、というのがそもそも間違った思いこみでボトルネックは別にあったということになりますね。
数割程度なら実際動かしたら速かった、でも納得できるのですが3倍も違うので何かしら明確な理由が欲しいです。ただこれ以上は実際の実装を調べる必要がありそうですかね。

[quickquip]

ここから先はプロファイラでちゃんと調べられる人でないと確たる回答は難しそうです（私はちょっと無理でした）

ただ、「根から見て右に右とたどる一直線しかアクセスしなくていい」というメモリ操作の局所性があるのは分かりましたので、私は割と納得してます。
回転で左側に行ったデータには **一切アクセスしなくていい** ことが効いているのだろうなあ、と思ってます。500万件目のノードを追加するあたりで"参照する必要があるデータ"が数十件程度しかないんですよ（こちら気づいていますか?）

[shukrin]

> 500万件目のノードを追加するあたりで"参照する必要があるデータ"が数十件程度しかないんですよ
確かに...。言われてみると、毎回のinsertでたどる必要のあるノードの数は多くてもその程度、しかも毎回ほとんど同じです。であれば毎回のinsertでたどるノードが全部キャッシュに載っていても不思議ではないですね。

Answer 2

へー、と思ったので、AIに聞いてみました。アルゴリズム系の話はAIが得意だと思ったので。以下、AIの回答です。

---

std::map へのソート済みデータの挿入が高速なのは、主に挿入位置の探索コストが大幅に削減されるためです。

ご指摘の通り、std::map は赤黒木という平衡二分探索木で実装されており、通常、要素の挿入にはキーの比較を繰り返して挿入位置を探すため、O(log n) の計算量がかかります。しかし、ソート済みのデータを順番に挿入する場合には、いくつかの最適化が働くことで、この探索が非常に効率的になります。

---

高速化の主な理由

1. 挿入ヒント（Hint）による最適化 📍

std::map::insert には、挿入位置のヒント（hint）をイテレータで与えることができるオーバーロードバージョンがあります。

iterator insert(const_iterator hint, const value_type& value);

ソート済みのデータを順番に挿入する場合、次に追加する要素は常にコンテナの末尾（最も大きいキーを持つ要素の後）に来ることが分かっています。そのため、map.end() をヒントとして与えることで、std::map は木の根からではなく、ヒント周辺から探索を開始します。

もしヒントが正しければ（つまり、新しい要素がヒントの位置の直前に挿入される場合）、挿入位置の探索は 償却定数時間 O(1) で完了します。多くの標準ライブラリの実装では、ヒントの直後に挿入される場合でも同様に高速化されます。

std::map<int, std::string> my_map;
// ソート済みデータをループで挿入
for (const auto& pair : sorted_data) {
    // ヒントとして my_map.end() を渡すことで高速化が期待できる
    my_map.insert(my_map.end(), pair);
}

C++11以降では emplace_hint もあり、同様の最適化が得られます。

2. メモリの局所性とキャッシュ効率 🧠

ソート済みのデータを連続して挿入すると、新しいノードはメモリ上で物理的に近い位置に配置される可能性が高くなります。これにより、以下のメリットが生まれます。

• キャッシュヒット率の向上: CPUがメモリからデータを読み込む際、関連するデータがキャッシュに乗りやすくなります（空間的局所性）。
• メモリアクセスの高速化: ノード間のポインタをたどる際に、遠くのメモリアドレスにアクセスする必要が減り、メモリアクセスのレイテンシが削減されます。

一方、ランダムなデータを挿入すると、メモリのあちこちにノードが点在することになり、キャッシュミスが頻発してパフォーマンスが低下します。

---

懸念されていた点について

自分の考えとしては、整列済みデータの挿入の方が木に偏りが生じやすく、その結果として回転操作の回数が多くなりむしろ遅くなると思っていたのでこの結果は不思議です。

これは非常に良い着眼点です。確かに、ソート済みのデータを単純な二分探索木に挿入すると、木が線形リストのように偏ってしまい、性能が O(n) に悪化します。

しかし、std::map が使用する赤黒木は自己平衡機能を持っています。挿入によって木の平衡が崩れると、回転（rotation） と色の変更（re-coloring） を行って、木の高さが常に O(log n) に収まるように自動で調整します。

ソート済みデータの挿入では、確かにある程度の回転は発生しますが、そのコストは前述した探索コストの劇的な削減とキャッシュ効率の向上というメリットに比べれば十分に小さく、全体としてはランダムなデータを挿入するよりもはるかに高速になります。

---

まとめ

std::map へのソート済みデータの挿入が高速なのは、単に木が偏るからではなく、C++標準ライブラリに備わっている以下の仕組みによるものです。

1. 挿入ヒントを利用することで、挿入位置の探索が O(log n) から O(1) に削減される。
2. 連続したメモリアロケーションにより、CPUキャッシュの効率が向上する。
3. 赤黒木の自己平衡機能が木の性能劣化を防いでくれる。

これらの要因が組み合わさることで、実験で観測されたような数倍の速度向上が実現されています。

Answer 3

こちらによれば、

内部的には、 map 内の要素は、コンテナの構築時に設定された狭義の弱順序基準に従って小さいものから大きいものへとソートされる。

とあります。

内部的にソートがなされるものであれば、最初からソートしたものを入れたほうが余計なソートの手間が省ける、というのはほぼ明らかだと感じました。

Comments

[fana]

> ほぼ明らか

（頭弱い人の感想なのですが）
内部的にソートされた形でデータを保持する場所に対して，外部からソート済みのデータの塊が「ごっそりと」渡されるのだとしたら「ソートに必要な時間が減りそうかな？」と思えますが，
要素が１個ずつ渡される（且つ，それがソートされている順序で渡されてくるとは知らない）場合に関しては，ちょっと想像つかない感じ(?)です．