共有していない変数でも、同じラインを使う
二つのスレッドが別々の変数を更新していても、それらが同じキャッシュコヒーレンスの単位へ入ると、互いの更新がラインの所有や無効化へ影響することがあります。これが偽共有です。実験では近接した二つのカウンターと、間隔を空けた二つを用意し、同じ回数だけ加算します。更新自体はatomicにして、データ競合による未定義の動作を比較へ混ぜません。LinuxとGCC互換のコンパイラー、pthreadを想定し、C11でコンパイルします。この配置変更は試験プログラムの内部だけで、ホストのキャッシュ設定やCPU設定は変えません。
間隔と、二つの最終値を表示する
近接配置は128バイトに整列させた配列の先頭二要素です。間隔を空けた配置は、それぞれ128バイトの整列を要求する構造体へ入れます。128はこの実験で選ぶ間隔であり、あらゆる機械のキャッシュラインサイズを意味しません。コードは実際のアドレス差を表示して、指定した配置がどう表れたかを確認します。各スレッドが10万回ずつ更新し、両方の値が10万であることも検査します。時間だけを比べて、片方の処理が抜けた結果を高速化と呼ばないためです。コンパイルにはcc -std=c11 -O2 -Wall -Wextra -Werror -pthreadを使います。
#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <pthread.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>
struct adjacent { _Alignas(128) unsigned long value[2]; };
struct slot { _Alignas(128) unsigned long value; };
struct job { unsigned long *value; };
static void *work(void *arg) {
struct job *j = arg;
for (unsigned i = 0; i < 100000; ++i)
__atomic_fetch_add(j->value, 1UL, __ATOMIC_RELAXED);
return NULL;
}
static void run(const char *name, unsigned long *a, unsigned long *b) {
pthread_t threads[2]; struct job jobs[2] = {{a}, {b}};
struct timespec begin, end;
assert(clock_gettime(CLOCK_MONOTONIC, &begin) == 0);
for (unsigned i = 0; i < 2; ++i)
assert(pthread_create(&threads[i], NULL, work, &jobs[i]) == 0);
for (unsigned i = 0; i < 2; ++i)
assert(pthread_join(threads[i], NULL) == 0);
assert(clock_gettime(CLOCK_MONOTONIC, &end) == 0);
assert(*a == 100000UL && *b == 100000UL);
double seconds = (end.tv_sec - begin.tv_sec) + (end.tv_nsec - begin.tv_nsec) / 1e9;
printf("%s spacing=%lu count=%lu/%lu seconds=%.6f\n", name,
(unsigned long)((uintptr_t)b - (uintptr_t)a), *a, *b, seconds);
}
int main(void) {
struct adjacent close = {{0, 0}};
struct slot spaced[2] = {{0}, {0}};
run("adjacent", &close.value[0], &close.value[1]);
run("spaced", &spaced[0].value, &spaced[1].value);
return 0;
}速さの順番を、成功条件にしない
二つのスレッドが別コアで同時に動かなければ、期待するラインの競合が目立たない場合があります。起動費用、CPUの共有、周波数、スケジューラー、実際のラインサイズなども時間へ影響します。したがって、間隔を空けた方が必ず速いというassertは入れません。複数回、実行順を入れ替えて結果を残し、必要なら専用の検証環境でCPU配置や性能カウンターを調べます。今回のプログラムはスレッド作成からjoinまでを含めて測るため、加算命令だけの費用ではありません。測定の範囲を変えるなら、両方の条件へ同じ変更を適用してください。
パディングにも、保存領域の代償がある
小さなカウンターを一つずつ離すと、同じ個数の値を置くために多くの領域を使います。要素数が大きければ、キャッシュ容量やTLBへの負荷が増えることもあります。同じスレッドが関連する値をまとめて読む場面では、近い配置の方が局所性へ有利な場合もあります。偽共有を避けたい書き込みと、一緒に読みたいデータを区別して配置を選びましょう。structを大きくしたという事実だけで、実アプリの問題が解決したとはいえません。どのスレッドがどの値をいつ触るか、共有単位に対してどこへ置かれるかを、観測に基づいて確認します。
観測結果から、次の仮説を選ぶ
記録には二つのカウンター値、アドレス差、経過秒数、コンパイラー、実行条件を含めます。差が大きければ偽共有を仮説の一つにできますが、時間だけでは原因を確定できません。差が小さくても、一般に偽共有が存在しないという意味ではありません。実際のコア配置や命令列、他の共有データが比較へ入っていないかを確かめます。コードでは性能の再現を狙って巨大な反復回数やホスト全体の設定変更を行わず、小さな負荷で終わります。実サービスへ適用するときは、部分的な差と全体の応答時間の改善を分けて測り、保存領域の増加も併せて評価してください。