こんにちは、トイロジックでプログラマーをしているダンシングたんぽぽです。

本記事では、マルチスレッドプログラミングで頻出する排他制御(ロック)と、軽量化を図る時に立ちはだかる難解なロックフリーアルゴリズムについてstd::mutexとstd::atomicを例に軽く解説したいと思います。

マルチスレッドプログラミングとは？

スレッドとはCPUに搭載されているユニットで、1つのスレッドで1つの処理を行うことができます。少し前のCPU業界ではシングルスレッド(1つのスレッド)の性能がどれだけ良いかを追求していましたし、ゲームでは今もシングルスレッドの速度が重要です。

しかし、最近はシングルスレッド性能の進化が鈍化してきています。その結果CPU業界では、スレッド数を増やすなどしてマルチスレッド(複数のスレッド)性能を追求するようになってきました。

コスト重視のコンソール機にも多くのスレッドを搭載したCPUが使われるようになり、それを十二分に活かす大作ゲームも多く出ている現在、マルチスレッドプログラミングの重要性が高まってきています。

誰もが最初に通る道、std::mutex

C++を使ったマルチスレッドプログラミングを学ぶ人が最初に知る処理、それはstd::mutexを使った排他制御ではないでしょうか？

マルチスレッドでは各々の処理が自由に動きまわるため、同じタイミングで複数のスレッドが書き込み/読み込みをすることがあります。読み込みだけなら大丈夫なのですが、書き込みもされる場合は大変です。スレッド1が変数に値を書き込んでいる間にスレッド2がその変数を読み込んだ場合、値が不定となり期待した動作をしてくれない可能性があります。

そこで登場するのが排他制御です。std::mutexではlock関数を実行した後、unlock関数を実行するまでは他のスレッドがlockを実行できません。

//mutexのインクルードが必要
#include <mutex>
//排他制御で使用する
std::mutex gMutex;
//実際に書き込む変数
int gValue = 0;

void MultiThreadFunction()
{
    //排他制御開始
    //他のスレッドではlockを呼び出す際、
    //このスレッドがunlcokを呼び出すまで待機する
    gMutex.lock();

    //排他制御中なので、書き込みをしても安全！
    gValue += 1;

    //排他制御の解除
    gMutex.unlock();
}

つまり、その間だけ排他制御にすることができるのです。これで変数の値が正しいことを保証することができました。複数のスレッドが扱っても問題ないことをスレッドセーフと呼びますが、これは初心者でもわかりやすいですよね。

排他制御は多用できる魔法の言葉ではない

こう書くとこんなことを思った方もいらっしゃるのではないでしょうか。

(なんだ、じゃあこれ使えば解決じゃないか！)

しかしこれがマルチスレッドプログラミングの罠なのです。

確かに、速度を求めない小規模なプログラムなら排他制御で事足りることでしょう。ですが速度を求めつつ、規模も大きくなりがちなゲーム分野においては排他制御を多用すると処理速度が大幅に低下する恐れがあります。

排他制御を行うマルチスレッドプログラムを高速道路として例えてみます。普段は複数車線で快適に走行できますが、眼前に一車線の料金所が見えてきました。混雑しつつも誘導員のおかげで通り抜けます。しかし、眼前にはまた一車線の料金所が…

排他制御は要所要所で使うなら強力な武器になり得ますが、同じ排他制御を使用するスレッド数・1スレッドが行う排他制御の総数が増えれば増えるほど処理待ちの時間が増え、処理速度が低下してしまうのです。

難解なロックフリーアルゴリズムと、入門者向けのstd::atomic

排他制御だけで全てを賄うことはできないことがわかりました。しかし先人は偉大です。ちゃんと沢山の解決策があります。

処理ごとにスレッドを分けて排他制御を減らす、コピーバッファを用意して排他制御を減らす、そもそも変数の用途を読み込みに限定させて排他制御を不要にする、などなどなど…

どれもそれだけで記事が書ける内容ですが、今回は特に難解なロックフリーアルゴリズムとその中で比較的わかりやすいstd::atomicを使った処理を紹介します。

ロックフリーアルゴリズムとは、名の通りmutexのような排他制御を行わずにマルチスレッド間で情報をやり取りする仕組みです。先程の高速道路の例えで言えば、一車線の料金所が複数車線のETCになったようなイメージですね。

もちろんこれも万能ではなくかなり癖がありますし、ロックフリーなリストなどは相当難解…というわけで、表題の通りstd::atomicを見ていきます。

#include <mutex>
//atomicのインクルードが必要
#include <atomic>
//排他制御で使用する
std::mutex gMutex;
//テンプレートクラス, コピー構築&コピー代入が可能な型に限る
std::atomic<int> gAtomicValue = 0;

void MultiThreadFunction()
{
    //ある操作をatomicに行うと不要になる
    //gMutex.lock();

    gAtomicValue.//???

   //gMutex.unlock();
}

std::atomicは排他制御を行わずにスレッドセーフとして扱えるテンプレートクラスで、内部にテンプレート型のインスタンスを保持しています。

このクラスの最大の特徴はCAS(Compare And Swap)が行えること。名前の通り、(現在の値と比較値が等値の場合、指定の値で現在の値を置き換える)ことができます。
std::atomicではcompare_exchange_weak関数がこれにあたり、排他制御を行わずにスレッドセーフな書き換えが可能です。

この機能をループ文と組み合わせて使うことで、同時書き込みを行う場合もスレッドセーフ(値が不定とならない)かつ高速な処理を行うことができます。

//CAS操作はだいたいこんなことをしています
void CopyAndSwapSample(
    int& outNowValue, int oldValue, int newValue)
{
    //値が同じなら入れ替える
    if (outNowValue == oldValue)
    {
        outNowValue = newValue;
    }
}

#include <atomic>

//ループ文を加えることで安全に値を変更できます
std::atomic<int> gAtomicValue = 0;
void MultiThreadFunction()
{
    int oldValue = 0, newValue = 0;

    //値を読み込む
    oldValue = gAtomicValue.load();

    do 
    {
        //+1加算させた値との入れ替えを試みる
        newValue = oldValue + 1;

    //CAS操作を行う。成功するとtrueが返却される
    //失敗した場合oldValueが現在の値(別スレッドで変更された値)が書き込まれるので、再読み込みは不要
    } while (!gAtomicValue.compare_exchange_weak(oldValue, newValue));
}

これだけで複雑なマルチスレッドプログラミングを実現することは難しいですが、他のクラスや機能と使い合わせることで大幅な排他制御待ち時間の削減が行えるはずです。ぜひ使ってみてはいかがでしょうか。

最後に

いかがでしたでしょうか。今回はマルチスレッドプログラミングについて入門者向けの解説をしてみました。

ゲームのマルチスレッドプログラミングは非常に難しい分野で頭の体操をしているような感覚に陥りますが、使いこなせれば大きな処理速度向上を見込める魅力的な分野です。

特にロックフリーアルゴリズムはそれだけで情報工学の論文を書けるような分野で私もまだまだ道半ばといったところですが、基本的なところから少しずつ学んでいけばプログラミングの世界が少し広がって見えるはずです。