FPUエミュレータの超最適化

FPUエミュレータの超最適化

2026年10月16日 Hacker News Lobsters

超最適化とは、コンパイラがループを含まない命令シーケンスに対して、自動的に最適なシーケンスを見つけるプロセスである。

– Wikipedia

コンパイラは、コードを高速化するための機械的な変換を得意とします。しかし、ほとんどのコンパイラは非自明な推論が得意ではないため、問題解決のための全く新しいアプローチを発明することはできません。

浮動小数点計算ライブラリを設計する際、float型の f を受け取り、f の最下位ビットに対応するfloat型を返す関数を実装する必要がありました。例えば、f がバイナリで 1.01101⋅2^10 の場合、0.00001⋅2^10 = 2^5 を返します。

これはビット操作で実装できますが、単純なアルゴリズムでは2のべき乗の場合に破綻するため、if 文を挿入する必要がありました。

if f32::from_bits(x.to_bits() & !f32::MANTISSA_MASK) == x { // xは2のべき乗か？
    return x; // x自体が最下位ビット
} else {
    return x - f32::from_bits(x.to_bits() & (x.to_bits() - 1)); // xから、xの最下位ビットを除いたものを引く
}

この if 文は私を大いに悩ませました。一般的なケースで実行速度が低下し、分岐は誤予測される可能性があります。2のべき乗も自動的に処理できるような、明らかに最適な数式を見つけたいと思っていましたが、いくら試しても納得のいくものは見つかりませんでした。

そこで、私は型破りな手段に出ました。

総当たり（ブルートフォース）

もし、そのような数式を自動的に見つける方法があったらどうでしょうか？ LLMの群れを起動するのではなく、考えられる全ての数式を総当たりで探索するのです。LLMは何かを見落としたり、一般的なパターンに過度に依存したりすることがありますが、総当たりはそうではありません。

しかし、数式が正しいかどうかをどうやって確認するのでしょうか？ 定理証明器は遅すぎますが、いくつかの代表的なテストケースを設計し、見つかった数式が正しいことを願うことができます。もし反例が見つかったら、それをテストケースリストに追加して繰り返せばよいのです。

これはそれほど狂った考えではありません。この時点で既に6オペレーションのアルゴリズムを実装していたので、5オペレーション以下の数式を反復処理するだけでよかったのです。以下のオペレーションが有用である可能性がありました。

• ビット操作のための整数加算/減算およびビットごとのAND/OR/XOR。
• 最後のオペレーションとしての浮動小数点減算。
• 比較演算子？

5つのオペレーションを選択する方法は 6^5 = 7776 通りあり、それぞれに6つのバリエーションがあり、カタラン数 C5=42 通りの括弧の配置があります。これはそれほど多くありません！

しかし、各オペレーションの入力も選択する必要があります。入力は、入力値 x または何らかの定数になります。私は、float のバイナリ表現の様々なフィールドをカバーする定数のみが必要で、完全にランダムな定数は必要ないだろうと推測しました。これによりリストは64種類の定数に絞られました。これは656の組み合わせとなり、多く聞こえるかもしれませんが、実際にはその多くを枝刈りできます。

探索

探索を効率的に実装するために、数式セットを帰納的に構築しました。

0オペレーションの数式は x と定数のみです。nオペレーションの数式は、kオペレーションとn-1-kオペレーションを持つ全ての数式のペアを組み合わせることで見つけることができます。

for n_ops in 1..N_OPS {
    let mut new_exprs = FxHashSet::default();
    for a_ops in 0..n_ops {
        let b_ops = n_ops - 1 - a_ops;
        let a_exprs = &exprs_per_op_count[a_ops];
        let b_exprs = &exprs_per_op_count[b_ops];
        for a_expr in a_exprs {
            for b_expr in b_exprs {
                for op in OPS {
                    // 新しい数式: `a_expr op b_expr`
                    new_exprs.insert(Expr {
                        values: core::array::from_fn(|i| {
                            op(a_expr.values[i], b_expr.values[i])
                        }),
                    });
                }
            }
        }
    }
}

帰納法により重複を枝刈りできます。例えば、(x+1)+2 と (x+2)+1 は異なる数式ですが、同じ値を返します。出力値のセットごとに1つの数式のみを保持することで、さらなるイテレーションをより速く完了させることができます。これが、総当たりがわずか4分で完了した理由です！（最適化すればさらに速くできると思いますが、一度きりのスクリプトの最適化よりもYouTubeを見ることを優先しました。）

時間とメモリを節約するため、最後のイテレーションでの重複排除は避け、一致する候補をすべて出力しました。メモリ使用量が重要です。この時点でテストケースが20個あり、数式あたり80バイトを保存する必要がありましたが、数式は非常に多くありました。

結果

では、この網羅的な探索は何か興味深いものを見つけたのでしょうか？ はい！5オペレーションの数式がいくつかありました。例えば、以下のものです。

return x - f32::from_bits(x.to_bits() & (
    (f32::EXPONENT_MASK - (x | f32::EXPONENT_MASK)) ^ !f32::EXPONENT_MASK
));

4オペレーションの数式は見つかりませんでしたが、このアプローチには限界があります。それは、計算の再利用を考慮していないことです。例えば、x & 1 が2箇所で使用されている場合、それは1つのオペレーションではなく2つのオペレーションとしてカウントされます。5オペレーションの数式のいずれかが、再利用によって実際には4オペレーションで表現できることを期待していました。全ての数式を手動で確認した後、最後の数式がこのプロパティを持っていることが判明しました！それがこちらです。

let a = x.to_bits() & !f32::MANTISSA_MASK; // マントッサビットのないx
return f32::from_bits(x.to_bits() & (a - x.to_bits())) - f32::from_bits(a);

2のべき乗の場合、わずかに異なる動作をします。符号ビットが反転しますが、これは気になりません。そして、そのロジックは一見すると意味不明ですが、機能します。

a を再利用できる数式がこれだけである理由は、サブエクスプレッション a - x.to_bits() にあります。これは -(x & f32::MANTISSA_MASK) に相当し、他の数式ではこのように参照されています。全ての数式は x & !f32::MANTISSA_MASK と x & f32::MANTISSA_MASK を計算しますが、この数式は後者を x - (x & f32::MANTISSA_MASK) として書き換え、それを否定とマージしてオペレーションを1つ節約しています！

それがこのような巧妙な書き換えを見つけたことに気づいたとき、私は唖然としました。コンピュータが発明できるものに驚くのにLLMは必要ありません！そして、それは産業を破壊しません。

とにかく、このコードは現在、私の作業中のFPUエミュレータに収められており、私はそれを誇りに思っています。