実験・実装 · 基礎から応用へ

Atomicカウンタの順序指定を比べる

複数スレッドの加算をrelaxedとseq_cstで実行し、最終値と測定時間を比べます。カウンターの正しさと、他のデータの公開順序を区別します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 同じ加算を、二つの順序指定で実行する
  2. 終了をjoinで待ってから、最終値を読む
  3. relaxedの成功を、公開の保証へ広げない
  4. 時間の差が小さくても、不思議ではない
  5. 結果には、値と環境条件を一緒に残す
  6. この記事をロゲイアに質問する理解を確かめる

同じ加算を、二つの順序指定で実行する

この実験ではGCCの__atomic組み込み関数を使い、4スレッドが同じカウンターへ3万回ずつ1を加えます。relaxedとseq_cstの二通りを実行し、どちらでも最終値が12万になることを確認します。非アトミックな加算を別スレッドから競合させるコードは含めません。C言語でそのようなデータ競合を起こして得た数値を、安全な比較対象にしてはいけないためです。Linux、GCC互換の組み込み関数、pthread、単調増加時計を使える環境を想定します。コードをcounter.cへ保存し、cc -std=c11 -O2 -Wall -Wextra -Werror -pthreadでコンパイルします。

終了をjoinで待ってから、最終値を読む

各スレッドはatomicなread-modify-writeで更新するため、同じ値を読んで加算を取りこぼす問題を防げます。relaxedもこの更新自体の不可分性を持ちます。主スレッドはすべてをjoinしてから最終値を読みます。まだ計算中の値を最終値と呼ばない点が大切です。コードはスレッドの作成やjoinの戻り値も確認し、失敗したのに予定の全加算が終わったものとして扱いません。二通りの実行の間では、前のスレッドが全員終了した後にカウンターを0へ戻します。同じ変数へ、実行中の無保護な初期化を混ぜない構成です。

c
#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <time.h>
static unsigned long counter;
struct job { int order; };
static void *work(void *arg) {
    const struct job *job = arg;
    if (job->order == __ATOMIC_RELAXED) {
        for (unsigned i = 0; i < 30000; ++i)
            __atomic_fetch_add(&counter, 1UL, __ATOMIC_RELAXED);
    } else {
        for (unsigned i = 0; i < 30000; ++i)
            __atomic_fetch_add(&counter, 1UL, __ATOMIC_SEQ_CST);
    }
    return NULL;
}
static void run(int order, const char *name) {
    pthread_t threads[4]; struct job job = {order};
    struct timespec a, b;
    __atomic_store_n(&counter, 0UL, __ATOMIC_RELAXED);
    assert(clock_gettime(CLOCK_MONOTONIC, &a) == 0);
    for (unsigned i = 0; i < 4; ++i)
        assert(pthread_create(&threads[i], NULL, work, &job) == 0);
    for (unsigned i = 0; i < 4; ++i)
        assert(pthread_join(threads[i], NULL) == 0);
    assert(clock_gettime(CLOCK_MONOTONIC, &b) == 0);
    unsigned long count = __atomic_load_n(&counter, __ATOMIC_RELAXED);
    assert(count == 120000UL);
    double seconds = (b.tv_sec - a.tv_sec) + (b.tv_nsec - a.tv_nsec) / 1e9;
    printf("%s count=%lu seconds=%.6f\n", name, count, seconds);
}
int main(void) {
    run(__ATOMIC_RELAXED, "relaxed");
    run(__ATOMIC_SEQ_CST, "seq_cst");
    return 0;
}

relaxedの成功を、公開の保証へ広げない

この実験の共有データはカウンターだけです。別の配列へ値を書いてからカウンターを増やし、別スレッドがその増加を見て配列を読むという公開プロトコルは試していません。relaxedで最終値が正しくなったことから、他の非アトミックなデータの可視性まで保証されたとはいえません。公開には、対応するreleaseとacquireなどの同期、参照先の寿命、変更の規則も必要です。一方、seq_cstを選ぶだけで、無関係なデータ競合や解放済みメモリの利用がすべて直るわけでもありません。何の順序が必要かを、共有する状態ごとに検討します。

時間の差が小さくても、不思議ではない

同じアドレスへ全スレッドが加算するため、キャッシュラインの所有をめぐる競合が大きな要因になります。機械によっては、二つの順序指定が同じ種類の命令へ変換される場合もあります。relaxedにしたら必ず何倍も速くなる、とは期待しません。コードの時間にはスレッドの生成と回収も含まれます。より細かな比較では反復回数、CPU配置、負荷、命令列などを調べますが、まず測定範囲をそろえます。順序を弱めることが仕様上許されるかを確認する前に、短い一回の時間だけで本番の指定を変えないでください。

結果には、値と環境条件を一緒に残す

記録するのは各指定の最終値、経過秒数、コンパイラーと最適化設定、スレッド数、反復回数です。複数回行うなら実行順も変え、最小値だけを選ばないようにします。このプログラムは、使用する整数型のatomic操作が常にロックフリーだとは主張しません。実装が補助処理を使う場合もあり、必要なら対応する確認APIや生成コードで調べます。正しい値になった事実、今回観測した時間、別の公開プロトコルに必要な保証を、別々の結論としてまとめます。未知の環境について性能や待ち時間を保証する実験ではありません。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

学習コースから次を選ぶ