VMとネイティブでタメを張る

先日のエントリに対して、id:suikanさんから以下の反論を受けました。

suikan 2008/02/19 17:18
信号処理の立場から異議を申し立てます！

ちなみに続報はこちら。

これに対して、思考実験で再反論します。相変わらず再現可能な数値はありません＜理系の風上にもおけんな(^^;)


計算量と、速度最適性の問題に関しては、現時点では以下の仮定が成り立つと思います。

  • 汎用性のあるプロセッサは、汎用性を実現するために計算量を消費するため、コストあたりの使用可能計算量は制限される
  • 汎用性のないプロセッサは、その計算量のほとんどを目的のために使用できる

想定としては、信号処理を行うDSPは汎用CPUよりもコストあたりの計算量は多く、画像処理を行うGPUは汎用CPUよりもコストあたりの計算量が大きい、みたいなのを考えてください。
ここで重要になってくるのは「コストあたりの」というマジックワードで、コストという言葉にはさまざまな意味合いを持たせることが出来ます。
それはたとえば「トランジスタ予算」であったり(価格に影響します)、「熱/消費電力効率」であったり(物理的実装限界に影響します)。
なので、コストにうるさい現代のCPUは、可能な限り汎用性を持たせつつ、どうにもならないところでは専用命令や、専用計算機に対する外部処理でコストあたりの計算量を稼いでいます。


ここで、ある程度現代風のプロセッサがあったとしましょう。このプロセッサは、SIMDの積和算命令を持ち、なおかつデータ自体はある程度型固定で扱うことができるものとします。具体的には、4積算と4加算を1命令で行うような物を想定します。
このとき、

では、もう、圧倒的に前者のほうが計算量は高くなりますが、

では、ほぼ同等とみなすことが出来るはずです。
その上で、さらに現代風のプロセッサがあるとします。このプロセッサはさらに高度なSIMDの積和算命令を持ちます。具体的には4x4積算と4x4加算を1命令で行うような物を想定します。
このとき、

では同等とみなせますが、

では、B''のほうがずっと総計算量は増えるはずです。


ええと、念のため言っておきますが、前提条件をずらしているのでこの話は反論としてはかなーりずるです。
また、インラインアセンブラなどを使って人間が前提条件(この場合、積和算命令や、すごい積和算命令)を直接触っている物に関しては、直接ネイティブになっているほうがずっと計算量は増えます。
でも、

  • A''.ネイティブコンパイラがたまたますごい積和算命令を使うと効率がいい事に気づいたバイナリ
  • B''.すごい積和算命令の実装を知っているVMで、計算内容を解析して、たまたますごい積和算命令を使うと効率がいい事にVMが気づいた時にJITコンパイルをかけたもの

が同等なのであれば、ハードウェアの進歩(この場合、「すごい積和算命令」)や、実際に実行した後で、パフォーマンスのプロファイリングを行ったうえで動的再コンパイルを行うような動作など、つまりは最適化のための手段をまだたくさん持っているBの系列のほうが結果的には「コストあたりの計算量」が増えてしまうのではなかろうかという気すらするのです。
動的再コンパイルによって計算量が増える可能性としては、命令実行スロットの数による並列動作や、パイプラインハザードの発生を遅らせるような分岐命令の配置など、手段はいろいろ考えられます。
もちろん、JITだの、動的再コンパイルだのをやり始めると最低応答時間の保証は非常に難しくなります。このため、適用できる処理は限定されます。実時間に対して何らかの処理を行う系では適用は難しいと思います。
だからといって、

ちなみに、仮想マシンが想定していないアプリの場合、そのアプリを想定しているネイティブ・コンパイラが勝つのは自明だと思って異議を唱えています。たとえば、IntelのV-Tuneコンパイラと行列演算でけんかしてJava VMがタメを張れるとは思っていないのです。

とは、なんとなくいい難いような気がするのです。ネイティブにコンパイルされてしまったものは、コストあたりの総計算量を静的に求めることが出来ますが、Java VMがこの先SIMD命令をサポートしない(あと、処理から無理矢理SIMDを適用できそうな部分を解析するような素敵JITコンパイラがでてこない)とは限らないので。