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

開始位置の整列を安全に比べる

型の整列を守った二つの開始位置で同じ長さを走査し、ラインをまたぐ範囲と個々のアクセスを区別します。

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

更新日

この記事の目次
  1. 型の整列とラインの整列を分ける
  2. 余分な領域を含めて確保する
  3. 二つの開始位置と範囲をコードで追う
  4. 速さの差が小さくても結果を残す
  5. 偽共有と同じ実験にしない
  6. 整列を要求する命令と型を区別する
  7. 不正なずらし方を見抜く課題
  8. この記事をロゲイアに質問する理解を確かめる

型の整列とラインの整列を分ける

この実験では64バイト境界へ確保した配列の先頭と、そこから16バイト進めた位置を使い、同じ個数のuint32_tを合計します。どちらもCの型が要求する整列を守ります。目的は、ラインの開始位置と型の有効なアドレスを区別し、範囲外や未定義動作で見かけの速度差を作らないことです。キャッシュ配置のガイドを先に読みます。開始位置が違うとき、どのラインを使うかを予測してから、同じ結果を確認するCコードを実行します。

uint32_tのポインタを1バイトだけずらすと、型の整列条件を破る場合があります。CPUがそのアクセスを実行できたとしても、Cとして許された実験とは限りません。ここではuint32_tの要素単位で4個進め、16バイトの差を作ります。コードでもアドレスを_Alignof(uint32_t)で割った余りが0であることを確認します。64で割った余りが0か16かは、型の有効性とは別の欄で表示します。二つの整列を同じ「ずれ」と呼ばずに区別してください。

余分な領域を含めて確保する

コードをalign.cへ保存し、gcc -O2 -std=c11 -fno-ipa-pure-const align.c -o alignで作って./alignを実行します。LinuxのPOSIX APIを使い、posix_memalignで64バイトの整列を要求します。成功時の戻り値を確認してからポインタを使います。元のn=1,048,576要素に16要素分を加えて確保するので、開始位置を4要素進めてもn要素全てを有効範囲内で読めます。最後に解放するのは進めたポインタではなく、元のbaseです。

全ての要素を1へ初期化するため、どちらの範囲も合計はnです。同じ値というだけで同じアドレス列ではありませんが、ここで変えたいのはその開始位置です。異なる区間を読むことを隠さず記録します。割当てと初期化は区間外で、walk一回の時間を測ります。出力は開始位置のバイト差、64で割ったアドレスの余り、反復、ナノ秒です。実際のポインタ値全体は、差を理解するために必須ではなく、この実験では余りを保存します。

二つの開始位置と範囲をコードで追う

offsetは要素数で0か4です。p=a+offsetなので、CSVではoffset×4の0か16が表示されます。各範囲はn個の4バイト値を読みます。64バイトラインの模型では、整列した範囲は65,536本に収まり、16バイトずれた同じ長さの範囲は両端を含め65,537本にまたがります。これはラインをまたぐ範囲の数で、実際のミス数ではありません。また一つの4バイト値が64バイト境界をまたぐことも、この配置ではありません。範囲全体と個々のロードを分けましょう。

反復ごとに先に測る位置を入れ替え、両方を9回ずつ測ります。同じ割当ての重なった範囲なので、一方が他方の状態を温める影響もあります。独立した空のキャッシュで比較したとは扱いません。結果のassertとsinkへの利用を保ち、逆アセンブルでは実際のロードとループを確認します。コンパイラが複数要素へまとめた場合は、それも実装の条件に含めます。ソースの型だけで、全ての機械ロードが4バイトだったと推測しないでください。

c
#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static volatile uint64_t sink;
static uint64_t ns(void) { struct timespec t; assert(!clock_gettime(CLOCK_MONOTONIC,&t)); return (uint64_t)t.tv_sec*1000000000u+t.tv_nsec; }
__attribute__((noinline)) static uint64_t walk(const uint32_t *a,size_t n) {uint64_t sum=0;for(size_t i=0;i<n;i++)sum+=a[i];return sum;}
int main(void) {
 size_t n=1048576,bytes=(n+16)*sizeof(uint32_t);void *base=NULL;assert(!posix_memalign(&base,64,bytes));uint32_t *a=base;
 for(size_t i=0;i<n+16;i++)a[i]=1;
 for(int r=0;r<9;r++)for(int k=0;k<2;k++){size_t offset=((r+k)%2)*4;uint32_t *p=a+offset;assert((uintptr_t)p%_Alignof(uint32_t)==0);
  uint64_t start=ns(),sum=walk(p,n),elapsed=ns()-start;assert(sum==n);sink=sum;printf("%zu,%zu,%d,%llu\n",offset*4,(size_t)((uintptr_t)p%64),r,(unsigned long long)elapsed);
 }
 free(base);return 0;
}

速さの差が小さくても結果を残す

全行の余りが0または16で、合計のassertを通ることが構造上の期待値です。どちらが速いかは期待値へ入れません。現代CPUのロード、コンパイラの選択、キャッシュに残る量によって差は変わります。全標本から中央値と分位点を出し、出た差が標本の揺れより小さい場合も、そのまま記録してください。差がないように見えることは、全ての境界ずれが無料という証明でも、このコードが失敗した証拠でもありません。

掲載コードはGCC 13.3と仮想CPUで正常終了し、有効な二つの範囲と合計を検証しています。PMUは取得していません。開始位置の違いを、キャッシュミスや分割ロードの実測値へ置き換えないでください。別の型やSIMD幅を試す場合は、必要な整列、命令、割当て末尾を改めて調べます。明示的な整列ロード命令を追加するなら、その命令の要求を全ての呼出しで満たす必要があります。希望する性能から逆に安全性の条件を省かないことが先です。

偽共有と同じ実験にしない

このコードは一つのスレッドが読取りだけを行います。二つのコアが同じラインの別の変数を書き換える偽共有を発生させていません。キャッシュラインへ整列したらマルチスレッドの更新が必ず速くなる、とこの結果から言うことはできません。偽共有の実験では書込み位置、スレッド、コア、共有されるラインを別に用意し、正しい同期と結果も確認します。関係する教材へ進むときは、共通する言葉より、コード中の操作が何かを見直してください。

型の整列、ベクトル命令が要求する整列、キャッシュラインへの対応、ページ境界はそれぞれ異なる条件です。メモリを64バイトへ揃えても、複数ページの配置やNUMAの近さまで保証されません。必要な制約だけを採用し、余分なパディングが容量を増やす費用も考えます。配列を使う頻度が低い場合や、同時に持つ配列が多い場合には、わずかなループの差より確保量の増加が問題になることもあります。単独の測定を全体の設計判断へつなげる際の境界です。

整列を要求する命令と型を区別する

型の整列を守ることと、特定のベクトル命令が要求する整列を守ることは別です。16バイトずれたpがuint32_tとして有効でも、より強い整列を要求する命令へ無条件に渡せるとは限りません。コンパイラの生成命令を確認し、明示的なintrinsicを使う変更ではその命令の契約を新しい前提として記録します。

不正なずらし方を見抜く課題

課題は、baseをchar*へ変換して1バイト足し、uint32_t*へ戻して読む変更を採用できるかです。解答は、この実験の代替としては採用できません。Cの型の整列を満たさない場合があり、CPUが動かしても未定義動作を含み得るためです。バイト列を扱いたいなら、対応する型やmemcpyなど、正しく定めた読取り方法へ設計を変えます。型の違反を起こさずラインの開始位置を変えるという元の目的には、4要素の差を使えば十分です。

追加課題はoffsetを16要素へ変える場合です。バイト差は64で余りは0へ戻ります。ただしn要素を読むために追加領域が足りるかも確認してください。現在のn+16ならちょうど収まります。解放は元のbaseのままです。元と新しい配置は同じライン整列ですが、開始アドレス自体は違うので、実時間が常に同一という解答にはしません。終わったら出力とバイナリを整理します。常駐プロセスやDBはなく、実験で確保した領域は終了前に解放されます。

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

コースの順番に沿って学ぶ

CS基礎を固める · STEP 8

AI基盤へ進む · STEP 5

学習コースから次を選ぶ