yarv-dev:346

　ささだです。

　どうにもわからない現象が起こってしましました。お知恵を拝借できれば幸
いです。


　オペランドを統合して１命令にする実験をしていました。たとえば、スタッ
ク上に true を push する命令は、通常は

	putobject true

になりますが、これを統合して

	putobject_true

という1命令にすれば、オペランドのフェッチのコストが下がります。

　これを簡単に行うため、これを自動的に行えるようにしました。具体的には
「ある命令」について「どのオペランドを統合するか」を指定することで、
「その統合した命令の C の記述」と「コンパイル時自動的にその命令に変換
するためのオプティマイザ」を生成するように
しました。

input:
* 統合する命令
* 統合するオペランド

output:
* その命令を利用するコードに変換するコンパイラ（オプティマイザ）
* その命令の C での記述



　まぁこれは実際簡単に作れるんですが、こういうものを作っておけば、手軽
に試せるかなぁと思ったわけです。


　で、これを実際に試してみたところ、不思議な現象が起こりました。

　意に反して、命令統合を行った場合のほうが速度が遅くなってしまったので
す。（なぜ語り口調）

　結構期待していたんですが、がっかりです。（まだ語り口調）

　理由を推測しました。

* 命令数が多くなったため、I-Cache から追い出された
* 複数のVM命令がひとつのコードを共有していたとき、そのジャンプが
  相対ジャンプの量を超えた（IA32 って、遠くへ飛ぼうとすると、実行
  コストが増えますよね）


　そこで、自暴自棄になった私は、無駄な命令をどんどん突っ込んでみること
にしました。つまり、ある命令 A があったとき、A_1 、A_2、...のように、
違う名前で同じ命令をどんどん突っ込んでみたのです（具体的には、ひとつの
命令につき、10 の無駄な命令を作りました）。ただし、無駄な命令は、何も
動作しない命令にしてみました（本当は、複製を複数作ろうとしたのだけれ
ど、プログラムをミスって（ボディ部を複製するのを忘れていて）エントリポ
イントだけになりました。replication も試してみたかったんですが）。する
とどうしたことでしょう。gcc でコンパイルした結果が、非常に高速になった
ではありませんか。（しつこいか）

　これは、gcc の場合だけだったのですが（VCではならず）、非常に不思議で
す。命令統合については、残念ながら、あんまり芳しい結果にはならなかった
のですが（でも、この命令を増やした後では少し速くなる（1.27 -> 1.17
(sec)））、命令を凄く増加させることで、かなりの高速化が果たせました
（1.53->1.27(sec)）。

　かなり不思議です。

　現象をまとめます。

・環境：Celeron1.4Ghz, 256MB memory, Win2000, cygwin/gcc 3.3.3
・命令を１０倍ほどに多くするとけっこう性能が良くなった
・命令を１０倍ほどに多くすると命令統合の効果が出た
・命令の中身は空（エントリポイントのみで、PCを進めるだけ）


　いくつか原因を考えてみました。


* I-Cache のラインがうまい具合に乗るようになった（可能性低）
* GCC のスレッデッドコードが、なぜかよりよいものになった
* ラベルが多すぎるので、GCC がコードを共有するのを諦めたらよりよい
  コードを生成した

　どうにもわかりません。

　アセンブラを眺めればわかったりするんでしょうか。しかし、１関数がでか
い（2000行くらいの C のコード）ので、あんまり見たくないなあ。

* この理由
* この理由を調査する方法
* アセンブラを見る方法、とくに C のある部分と照らし合わせながら

　を知っていれば・思いついたら教えてください。


　ちなみに、きちんとボディ部も複製すると、1.5 sec。遅くはなってない
が、速くもなってない。

-- 
// SASADA Koichi at atdot dot net
//

もうちょっと参考：

so_ackermann:
#!/usr/bin/ruby
# -*- mode: ruby -*-
# $Id: ackermann-ruby.code,v 1.4 2004/11/13 07:40:41 bfulgham Exp $
# http://www.bagley.org/~doug/shootout/

def ack(m, n)
    if m == 0 then
        n + 1
    elsif n == 0 then
        ack(m - 1, 1)
    else
        ack(m - 1, ack(m, n - 1))
    end
end

NUM = 7
ack(3, NUM)



--
      user     system      total        real
ruby  3.969000   0.078000   4.047000 (  4.082000)
yarv  0.328000   0.000000   0.328000 (  0.331000)  # 何もしない
yarv  0.265000   0.000000   0.265000 (  0.273000)  # 命令増加＋統合



--
ML: yarv-dev quickml.atdot.net
使い方: http://www.atdot.net/~ko1/quickml