2026年7月12日

先日、ドメイン特化の圧縮ツールを最適化していました。

重要な問題のひとつは、入力文字列をチャンク分けし、各チャンクに最適な符号化方式を選ぶことでした（符号化方式によって特定の文字の圧縮効率が異なるため、どこで分割するかは自明ではありません）。前回の記事でアルゴリズムの詳細を説明していますが、要するにグリッド上の最短経路を見つける問題になります。各セルに対して、続いてくる最良のセルを計算します。先頭セルから末尾セルへの参照をたどることで、最適な符号化順序が得られます。

uint8_t next_j[n_symbols][8]; // references to the next cell

// The core of the algorithm populating `next_j`.
// Don't worry too much about understanding it, it's just here for completeness.
__m128i best_path_length = _mm_setzero_epi16();
for (int i = n_symbols - 1; i >= 0; i--) {
    __m128i tmp = _mm_add_epi16(cost[i], best_path_length);
    __m128i minpos = _mm_minpos_epu16(tmp);
    __m128i cost_without_switching = _mm_sub_epi16(tmp, _mm_broadcastw_epi16(minpos));
    __m128i cost_with_switching = _mm_set1_epi16(switch_cost);
    best_path_length = _mm_min_epu16(cost_without_switching, cost_with_switching);
    __m128i choice = _mm_blendv_epi8(
        _mm_set1_epi16(_mm_extract_epi16(minpos, 1)),
        _mm_set_epi16(7, 6, 5, 4, 3, 2, 1, 0),
        _mm_cmpeq_epi16(best_path_length, cost_without_switching)
    );
    _mm_storeu_si64(&next_j[i], _mm_packs_epi16(choice, choice));
}

// Find the optimal encoding for each symbol.
// Chunk boundaries are located where encodings change.
uint8_t encoding[n_symbols];
uint8_t j = 0; // always start with encoding 0 for simplicity
for (int i = 0; i  n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}

この長いループは今回の話題ではありません。十分に最適化されています。ここで取り上げるのは2番目のループで、初見でははるかに単純に見えます。

Latency

書き込みを除くと、ループ本体の処理は j = next_j[i][j] だけで、1つの mov 命令にコンパイルされます。これ以上最適化の余地はないように思えます。

1984年のプログラミングであればそれで十分でしたが、現代のプロセッサには 命令レベル並列性 があります。つまり、複数の命令を並列に実行できます。これはループの反復をまたいでも機能し、通常 i n_symbols や i++ のような命令をループ性能評価で無視する理由のひとつになっています。これらの命令は、CPUがさらに多くの処理を行うことを妨げないためです。

しかし重要な点として、2つの依存関係のある命令を同時に実行することはできません。今回のケースでは、各ループ反復は前の反復が終了するまで開始できず、j がループを通じて受け渡されるため、メモリアクセスのレイテンシに制限されます。これはキャッシュを使用してもかなり顕著です。

これを修正できるでしょうか？この特定のケースでは可能です！チャンク数がそれほど多くないと予想されるため、next_j[i][j] は j そのものと等しくなる可能性が高いです。CPUに「j は変わらない」と予測させることができれば、ループはレイテンシ境界ではなくスループット境界になります。

アドレス予測を直接制御することはできませんが、分岐予測でこれをシミュレートできます：

for (int i = 0; i  n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}

CPUが if 本体を「起こりにくい」と予測すれば、それを無視して反復間の依存関係を見えなくします。条件が最終的に true になったとき、分岐予測ミスの解決処理が働き、誤った投機的書き込みを取り消して正しい j で再開します。これがまさに望んでいる動作です！

コンパイラへの嘘

唯一の問題は、コンパイラから見るとこの if は完全に無意味だということです。j がメモリ上にあれば、読み取り専用メモリへの書き込みを避けられるかもしれませんが、j はレジスタ上にあります。他のほとんどのケースでコンパイラヒントを使うのとは逆に、ここでは分岐なしのコードを分岐ありに変換したいのですが、どのコンパイラもそれをサポートしていません。特に CSE パス なら、ためらいなく削除してしまいます。愚かなコンパイラは、整数にハードウェア由来があることを理解していません。

私が知る限り、これを実装する唯一の方法は volatile へのキャストを使って、条件と代入が独立しているように見せることです：

for (int i = 0; i  n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}

合成ベンチマークでは、この変更によりループが320μsから80μsに高速化しました（大した数字に見えないかもしれませんが、圧縮中に何度も実行されるため、累積します）。

より現実的な実験では、LLVMのコード生成が最適でなかったため2倍程度の改善にとどまりました。それでも十分に価値があります！

補足

興味深いことに、このアルゴリズムでは各 next_j[i][j] は2つの値のいずれかしか取りません。すなわち、ほとんどの場合 j か、あるいは i のみに依存し j には依存しない値です。そのため、各8要素配列 next_j[i] をその値とビットマスクのペアに置き換えれば、if が意味的に重要になり、volatile のトリックが不要になります。ただし、変数のビットをテストするのは比較よりも遅い（少なくともx86では）ため、コードが遅くなる可能性が高いです。