真偽の個数を保って順序だけ変える
この実験は0と1を半分ずつ含む1,048,576要素の配列を三通りに並べ、同じ条件分岐へ渡します。0なら5、1なら3を足すため、期待する合計は4,194,304です。整列列、交互列、固定seedで並べ替えた列で、値の個数と仕事の意味を揃えます。前提は分岐予測のガイドです。目的は最悪の予測器を言い当てることではなく、入力、生成命令、時間、取得できたイベントを一つの再現条件として残すことです。
整列列では0の塊から1の塊へ一度切り替わります。交互列には短い周期があります。無作為順は、整列列の同じ要素を交換して作るため、真の個数は変わりません。seedと交換規則は入力を再現するために固定します。この擬似乱数は暗号用途ではなく、剰余による選択にも偏りがあり得ます。ここでは真の個数が保たれた一つの固定順を用意する目的です。乱数の品質を評価した実験とは区別します。
分岐を観察するビルドを作る
コードをbranch.cへ保存し、gcc -O2 -std=c11 -fno-ipa-pure-const -fno-if-conversion -fno-if-conversion2 -fno-tree-vectorize branch.c -o branchで作ります。./branchの出力は列の種類、反復、ナノ秒、合計です。0は整列、1は交互、2は並べ替えです。if変換を止めるのは、対象の条件が算術や条件付き移動へ置き換わるのを抑えるためです。この設定で通常のアプリが最速になると勧めているわけではありません。CPU、OS、GCC版、全設定を一緒に保存します。
mallocと入力生成は計測外です。並べ替えも初回の測定より前に終えます。合計を使ってassertし、sinkとprintfへ渡すことで、仕事の結果を利用します。各列を9回測りますが、一つの列をまとめて測るこの短いコードでは、種類の順序も環境変化と重なる可能性があります。調査を広げる場合は種類の実行順を変えた別の実験も保存します。同じ標本へ区別なく混ぜず、条件を追加した結果として扱ってください。
値で分かれるジャンプを探す
objdump -d branchで逆アセンブルを保存し、mainが呼ぶcountの実体を探します。今回のGCC 13.3ではcount.constprop.0という名前になり、入力バイトを比較した後に条件付きジャンプが残ります。名前の末尾が変わることを想定し、正確にcountという見出しがないだけで関数が消えたとは決めません。データに依存する比較と、配列の終端を調べる比較を分けて読みます。ジャンプ命令の数だけを数えても、この区別はできません。
掲載コードのビルドでは対象の分岐が残ることを確認していますが、同じ設定名でも別のコンパイラ版の判断を保証しません。通常の最適化版を追加で作ったら、元のバイナリへ上書きせず別名へ保存します。変換後にSIMD命令や条件付き移動があれば、それ自体が別の比較対象です。ソース中にifがあるから必ず分岐予測を測っている、という前提を外し、どの機械命令へどんな入力が入るかを出発点にしてください。
#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; }
static uint32_t state=12345;
static uint32_t random32(void) { state=state*1664525u+1013904223u; return state; }
__attribute__((noinline)) static uint64_t count(const uint8_t *a,size_t n) {
uint64_t yes=0,no=0;
for(size_t i=0;i<n;i++) { if(a[i]) yes+=3; else no+=5; }
return yes+no;
}
int main(void) {
size_t n=1048576; uint8_t *a=malloc(n);assert(a);
for(int kind=0;kind<3;kind++) {
for(size_t i=0;i<n;i++) a[i]=kind==1 ? (uint8_t)(i%2) : (uint8_t)(i>=n/2);
if(kind==2) for(size_t i=n-1;i>0;i--) { size_t j=random32()%(i+1);uint8_t v=a[i];a[i]=a[j];a[j]=v; }
for(int r=0;r<9;r++) { uint64_t start=ns(),sum=count(a,n),elapsed=ns()-start; assert(sum==4*n);sink=sum;printf("%d,%d,%llu,%llu\n",kind,r,(unsigned long long)elapsed,(unsigned long long)sum); }
}
free(a);return 0;
}
時間の分布を保存する
正常終了時には各種類9行、計27行が出て、合計は全て同じです。時間の大小にはassertを置いていません。全標本から各種類の中央値と分位点を求め、初回が後の回と違う場合もそのまま残します。測定したナノ秒を要素数で割ると1要素あたりの時間です。整列列と交互列は、真の割合が同じでも履歴が違います。交互列が必ず遅い、無作為順の誤予測率が必ず50%、という期待値を正解へ入れないでください。
時間を比べるときは、同じCPU上の同じバイナリの標本かを確認します。仮想環境では実行待ちや共有資源の変化も混ざるため、小さな差を固定のサイクル数へ換算しません。周波数を別に測っていないのに、表示された公称GHzだけを掛けて命令の遅延を求めることも避けます。コードの仕事量と生成命令が揃ったこと、どんな時間差を観測したか、その原因をどこまで確かめたかの三つを分けて結果を書きます。
カウンタが取れた場合だけ率を計算する
分岐回数と誤予測回数を取得できれば、同じ対象区間について後者を前者で割った率を計算できます。ただしイベントが全分岐を数えるのか、特定の条件分岐だけか、ユーザー空間だけかを確認します。入力生成、printf、ループを戻る分岐も数えた値を、配列のifだけの率と呼んではいけません。カウンタの多重化で推定された値なら、その条件も保存します。対象のCPUとOSでイベントが利用できるかは、計測前に確認が必要です。
今回の実行証跡ではPMUは未取得です。記録したのはコードの正常終了、合計、時間、生成命令です。「カウンタがない」という記録をゼロ回の誤予測へ置き換えません。時間差は仮説を作る材料になりますが、メモリ、命令数、履歴の状態など他の説明もあります。追加調査の問いを、データ依存の分岐が何回外れたか、条件の計算を待ったか、のように具体化します。取得できた証拠と足りない証拠を区別して書くことが、この実験の到達点です。
同じ入力で通常ビルドも比較する
通常の-O2だけの版を追加するなら、元の制御用バイナリを残し、入力と合計を同じにします。もしデータ分岐が消えていても、それは最適化後の別の実装として読む結果です。元の分岐の誤予測率が改善したと解釈せず、観察対象の命令自体が変わったことを説明します。二つの版の逆アセンブルをCSVと対応させます。
順序を変える課題と後片付け
課題は、1の割合を半分から四分の一へ変えたときの期待する合計を求めることです。解答は、n/4個に3、3n/4個に5を掛け、4.5nです。元のnでは4,718,592になります。入力を作る全ての箇所とassertを同じ仕様へ変えてから走らせます。交互の作り方も、0、0、0、1の周期などへ改める必要があります。assertだけを結果に合わせて変更すると、三種類で同じ個数を守れたかを確認できません。
追加課題として、0と1の両方で同じ値を足すようにした場合を考えます。答えは、コンパイラが条件そのものを不要と判断できる可能性がある、です。その実験では、元の分岐を観察する目的から外れたことを逆アセンブルで確認します。終わったらbranch、ソース、逆アセンブル、CSVを整理します。サーバーや外部APIは使いません。分岐を削除する実装と比べたい場合も、必要な出力と計算の条件を守った別の版として準備します。