Garden

最近の記事

FI_SQRTとライブラリのsqrt関数はどちらが高速か

11 min read

Prompt

WTFで有名なFast Inverse Square Rootアルゴリズムと、言語のライブラリのsqrt関数は、どちらが早くなる？
メジャーな言語毎で比較するとどうなるかな？

面白いところを突いてきたね！👍 Fast Inverse Square Root（FI_SQRT）と、言語の標準ライブラリにあるsqrt関数のどっちが速いかっていうのは、プログラミングの世界でよく議論される、古典的だけど奥深いテーマだよ。

まず、結論から言うと、現代のほとんどのメジャーな言語では、ライブラリのsqrt関数の方が速い場合が多いんだ。

「え、WTFって付くくらいすごいアルゴリズムじゃないの？」って思うよね。その理由を深掘りしてみよう。

Fast Inverse Square Root（FI_SQRT）の正体

FI_SQRTは、Quake III Arenaというゲームのソースコードから見つかった、逆平方根（）を高速に近似計算するアルゴリズムだ。

C

float Q_rsqrt( float number ) {
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit hack
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, optional
    return y;
}

このアルゴリズムは、ビット演算を駆使して初期値をめちゃくちゃ高速に近似し、ニュートン法で精度を上げるという、当時のCPUの特性を最大限に活かした天才的なハックなんだ。

なぜ現代では遅いのか？

では、なぜ現代の環境ではライブラリに勝てないのか？

  1. CPUの進化:

    • 現代のCPUには、SIMD（Single Instruction, Multiple Data）命令という特殊な命令セットがある。SSE, AVX, NEONなどがそうだね。

    • これらの命令は、複数のデータを同時に処理できるため、浮動小数点演算をめちゃくちゃ高速に実行できる。sqrt関数もこれらの命令を使って最適化されている。

    • FI_SQRTは、これらの命令を前提としていない。

  2. コンパイラの最適化:

    • 現代のコンパイラは、もうとんでもなく賢い。例えば、sqrt(x)というコードを見つけると、自動的にSIMD命令に変換してくれるんだ。

    • FI_SQRTのようなビット演算ハックは、コンパイラにとって最適化しにくい。

  3. 精度の問題:

    • FI_SQRTは、あくまでも近似アルゴリズムだ。正確な値が必要な場合は、追加で反復計算を行う必要がある。

    • 一方、ライブラリのsqrtはIEEE 754標準に準拠した、高精度の計算を行う。

言語別の比較

メジャーな言語ごとの比較を見てみよう。

C/C++

  • sqrtf() / std::sqrt()：GCCやClangといったコンパイラは、sqrtf()やstd::sqrt()を**rsqrtpsやsqrtss**といったSIMD命令に最適化する。これはFI_SQRTよりも圧倒的に速い。

  • FI_SQRTをわざわざ使うのは、古い環境や組み込みシステムなど、SIMD命令が使えない特殊なケースに限られる。

Java / C#

  • Math.sqrt()：これらの言語では、ネイティブなC/C++ライブラリを呼び出すことが多い。JIT（Just-In-Time）コンパイラが、ネイティブコードの呼び出しやSIMD命令への最適化をよしなにやってくれる。

  • JavaやC#でFI_SQRTを実装しても、JITコンパイラが最適化しにくいコードになり、ネイティブなsqrtに勝つことはまずない。

JavaScript / Python

  • Math.sqrt()：これらの言語も、内部的にはC/C++で実装された高速なネイティブコードを呼び出している。

  • FI_SQRTをJavaScriptで実装すると、浮動小数点と整数型の変換（evil floating point bit hackの部分）でパフォーマンスのオーバーヘッドが発生し、ネイティブなsqrtに全く歯が立たない。

まとめ

FI_SQRTは、特定の環境下で生まれた歴史的な偉業だ。しかし、CPUとコンパイラが恐ろしいほど進化し、汎用的なsqrt関数が高効率なSIMD命令に最適化されるようになった現代では、その役割は終えている。

まさに「時代遅れ」って感じだね。でも、その発想の奇抜さやコードの衝撃は、今でも多くのプログラマの心を掴んで離さない。君の興味深い質問、最高だったぜ！😉

Prompt

FI_SQRTのintとfloatの激ヤバキャスト操作ができない言語って、結構多いよね？

ほう、いいところに気づいたね！その「激ヤバキャスト操作」…つまり、整数型と浮動小数点数型のメモリ上のビット列をそのまま解釈し直すっていう操作だよね。そうだね、最近の多くの言語では、この操作は明示的に禁止されていたり、非常にやりにくくなっているんだ。

これは、プログラマが意図しないバグや脆弱性を生み出すのを防ぐためなんだ。

なぜ禁止されるのか？

  1. 安全性の問題:

    • このようなキャストは、メモリ上のデータを「強引に解釈する」行為だから、型安全性を完全に無視している。

    • 例えば、もしint型の変数が不正な値を持っていた場合、それをfloatとして解釈すると、予期せぬ挙動やクラッシュにつながる可能性がある。

  2. ポータビリティ（互換性）の問題:

    • 整数や浮動小数点数のビット列の内部表現は、CPUのアーキテクチャやコンパイラによって異なることがある。

    • FI_SQRTは、IEEE 754という特定の浮動小数点数表現に依存している。もしこの表現が違う環境で動かそうとすると、アルゴリズムが破綻してしまうんだ。

    • このビットハックは、移植性が低く、特定の環境に強く依存する。

  3. コンパイラの最適化の妨げ:

    • 現代のコンパイラは、コードの意図を理解して最適化を行う。

    • しかし、ビット列を直接操作するようなコードは、コンパイラにとって何をしているのかが分かりにくく、最適化の妨げになることが多い。

言語ごとの対応

君が知っている言語で見てみよう。

Java / C#

  • JavaやC#では、このような直接的なビットキャストはできない。

  • intとfloatの間でキャストはできるけど、それは型変換であって、ビット列の再解釈ではない。

  • どうしても同じようなことをやりたい場合、Float.floatToIntBits()やFloat.intBitsToFloat()といった専用のメソッドを使う必要がある。これは、言語の設計者が「こういう操作は特別なことだ」と明示的に示している証拠だね。

JavaScript / Python

  • JavaScriptは、そもそも型が動的に決まるから、このようなビット列操作は不可能。

  • Pythonも同様で、データ型が抽象化されているため、メモリ上のビット列を直接いじることはできない。

  • Pythonでビット演算をしたい場合、int型に対してはできるけど、float型をintとして扱うことはできない。

Rust

  • Rustは低レイヤーを扱える言語だけど、この種の操作はtransmuteという**unsafeな関数**を使う必要がある。

  • unsafeキーワードは、「コンパイラの安全保証を無効にする」という意味で、プログラマがその操作の安全性を自分で保証する必要がある。

  • このように、危険な操作には特別なキーワードを付けることで、コードの安全性を守っているんだ。

そうだね、FI_SQRTのビットハックは、言語がどんどん**「安全性」や「抽象化」**を重視する方向に進んでいることの、良い例と言えるかもしれない。

言語がユーザーを「間違った使い方」から守ってくれるようになったことで、バパイオニアたちが生み出したハックの多くは、ライブラリの裏側で密かに使われるか、あるいはレガシーな技術として歴史の中に埋もれていく…そんな時代になったんだ。

グラフビュー

最近の記事

グラフビュー