タスクの概要：主催者は、特定のプログラムをバイトコードの形式で提供し、それに指定が与えられます。 バイトコードには遷移コードは含まれませんが、2つのセルの条件付き選択のための命令を含む、m1 <-m2 + m3などの形式の命令のみが含まれます。 3つのアドレス可能なメモリタイプがあり、それぞれがダブル配列タイプです。入力パラメータメモリは読み取り専用で、作業メモリは読み取り/書き込み、出力パラメータメモリ-書き込み専用です。 プログラムの1つのパスは、次の時点で天体の座標を提供します。世界の状態が含まれているため、パッセージ間でメモリを保持する必要があります。 この「世界シミュレータ」を使用して、プログラム入力に、この世界を飛び回って何かをしなければならない衛星の制御アクションを適用する必要があります。 内部のすべての座標は、実際の数式に近い、よく知られた数式に従って計算され、すべてが非常に美しくなります。 これらの式はVMでエンコードされます。 このVMを使用する場合、最終的に衛星を最適に制御する必要があり、これらの制御シーケンスは最終的に賞を授与するかどうかになります。
HaskellとJavaを比較する前に、コメントで説明したOCamlとC / C ++プログラムの速度の比較を明確にしたいと思います。 元の記事では、C ++インタープリターがOcaml JITコンパイラーと比較され、そこからOCamlの速度の優位性が比較されました。 このバージョンでは、コンパイラによって生成された同一の最適な仮想マシンを事前に比較します。
速度について何が言えますか？ このタスクのHaskellは、Javaの2倍以上の生産性があります。 よく知られていることです。Cコードを生成すると、パフォーマンスは5〜10に再び高くなります。競合の過程で不完全なコードを試しました。
したがって、タスク：タスク4001全体、つまりすべてのオブジェクト：12個のパッシブ衛星+月+私たちの衛星。 反復カウント/秒
ハードウェア：Intel Q6600オーバークロックなし、Arch Linux 64ビット、GHC 6.10.3、JDK 1.6u14、すべてマルチスレッドなし：Haskell品質をコンパイラーとして測定するため。 Hotspotがウォームアップした後のJavaでの測定。これは最初の数秒で発生し、その後は結果は変わりませんでした）
結果（毎秒の反復、タスク4001..4004で計算された世界全体= 1反復）：
* Javaバージョン（コンテストに送信されたとおり、単純なコンパイル）：22K iter / sec
* Javaバージョン（完全なコンパイル）： 44K iter / src
* Javaバージョン（完全なコンパイル、32ビットJDK）：32K iter / src
* Haskellバージョン（VMStateの遅延データを使用）：1.73K iter / sec、最大8.1K iter / sec ==>カウントしません。
* Haskellバージョン（VMStateの厳密なデータ）： 96K iter / sec。
理想的なJava VMは次のようになります（意味のあるスニペット）。
public class Vm {
double m2039;
{m2039=0.0; }
public void fw(double[] i, double[] o) {
double t60=((6.67428e-11)*(t59+t41))
double t61=(((((t53*t53)*t53) != 0) ? t60/((t53*t53)*t53) : 0));
m2039=(t12+1.0);
o[0]=((((Math.sqrt (((t1989*t1989)+(t1987*t1987))))-6357000.0)<0) ? ...
}
}
ここには何がありますか？ 反復内の一時的なものはすべてローカル変数に取り出され、メンバーの定数は括弧内に示されます（ローカル変数に入った再利用されたものを除く）。 定数は定数によって作成されます。 ポートは配列で作成されるため、個人名を付けることができますが、ポート数は少ないため、パフォーマンスに影響はありません。 関数を1回呼び出すと、オブジェクトが新しい状態に移行します（+1を選択）。 割り当ての優れた機能は、一時変数へのリンクがないことです。
それどころか、不完全にコンパイルされた仮想マシンは次のようになります。一時変数の代わりにメンバーが使用されます。 括弧の代わりに、各ステップで結果をメンバーに保存します。 つまり、タスクに対してPDFで発行された仕様に従って、ほぼ1対1です。
d57 = d2042;
d59 = (d13 == 0.0 ? d56 : d57);
d60 = d34 * d59;
d61 = (d55 != 0.0 ? d60 / d55 : 0.0);
d62 = d45 * d61;
d63 = d62 + d41;
d64 = d63 * d4;
d65 = d2114;
d66 = d9 * d9;
d67 = d11 * d11;
これがHaskellでどのように行われるかを見てみましょう。 ここでオブジェクトを変更することは習慣ではなく、これを行う簡単な方法はありません。 代わりに、オブジェクト（代数データ型）、次に元のインスタンスを作成する関数を記述し、1ティック離れた1つのインスタンスから別のインスタンスを作成する関数を記述します。 コードはJavaに似ていますが、一時変数はなく、代わりにlet-bindingsがあります。 テストでは、45,000回の反復後、画面に状態全体を表示する（すべての遅延チェーンを計算する）必要がありました。
data VMState = VMState { m2039,...,o101::Double } -- " "
initState = VMState {m2039=0.0....} --
nextState x (i16000,i3,i2)= --
let .... --
t18=((if t13==0 then 3.84399e8 else m2051 x)) :: Double
in -- , " x, "
x { m2039= .... , o39=(if (t1699-(t12+t14*2))==0 then 0.0 else 1.0) }
VMStateタイプでは、コンストラクターパラメーター（構造体フィールド）が遅延されます。 VMStateインスタンスがnextStateを介して前のインスタンスから生成された場合、ヒープ上にある遅延スタブ（サンク、言い方がわかりません）が含まれます。 そして、45,000ティックを計算する必要がある場合、45,000コピーを通過する必要があります。各コピーには、公正な（100の）パラメーターがあり、すべてが遅延しています。 要するに、このコードは1秒あたり1.73Kの反復を提供し、ひどいです。 しかし、それらを厳密に置き換えてください。
data VMState = VMState { m2039,...,o101:: !Double } -- . Double
どのようにしてすべてがスマートに実行され始めますか。 （96K iter /秒）。 プロファイラーでは、追加のメモリ割り当ては実質的になく（VMStateインスタンスのみ）、GCの負荷は非常に小さいことがわかります...
原則として、この研究はすでに十分かもしれませんが、おそらく中間オプションは、怠zyが許容可能な速度を提供できるという希望を私たちに与えるでしょうか？
これを行うために、私たちはサブタスクを取ることができます：ほとんどの場合、タスク4001から4004は運動量に応じて独自の空間位置のみを必要とし、衛星の座標は一度だけ計算できます（事前に）。 VMに位置のみを要求し、惑星などの座標を持つ構造全体を要求しないようにしましょう。 私たちの位置は、フィールドo2、o3（仕様の出力ポート0×2、0×3）に対応しています。 Haskellは遅延言語であるため、狭い目的で同じ関数（nextState、遅延バージョン）を使用できます。 この場合、計算速度は4.5K iter / secであり、これは他の値が計算されないため、2倍の速さです！
ここで、これら2つのフィールドを厳密にし、他のすべてのフィールドをレイジーのままにしてみましょう！ 速度は8.1K iter / secです！ これはおそらく、厳密なフィールドを割り当てた後、すべての反復の最後に結果が出力された後だけでなく、遅延計算のチェーンをすぐに解放できるため、ガベージコレクターの作業が少し少なくなるためです。 ビルドがより高速で簡単になります。
Haskellが私たちのタスクでJavaより速いのはなぜですか？ おそらく、それが実行可能ファイルにコンパイルされるのは、その中で生成されたアセンブラコードがC / C ++が生成するものと比較してひどいことを考慮してもです。 そして、おそらく、コンパイラーはここでよりうまく機能します。これにより、式の同じ部分（たとえば、「m12345 x == 0」の条件下）が1回だけ計算するのに十分であることが確実になります。 これは、Javaには余裕のない贅沢です。 Javaの場合、これらのニュアンスを詳述する追加のコードを記述する必要がありますが、Haskellの場合、インテリジェントコンパイラは必要ありません。
コンパイラコードに関するコメント（ここにあります） ：
1.完全な遅延バリアントを生成します（厳密な注釈は、調査目的でコンパイル結果の上に手で追加されました）
2.定数は、ビット単位ではなく、使いやすい形式で挿入されます（ビット単位で必要）
3. Javaを生成するコードの内部にありますが、非アクティブですが、あります。
4.コメントと空行を含むコンパイラコード、およびJava用の分岐-238行。
5.コンパイラはbin4.obf（4タスク）に対して十分に生産的であり、コードは最適化されていません（美しさ）。
コンパイラに対する改善とコメントを歓迎します。 必要に応じて、コンパイラ自体に関する同様の記事、つまり、フラット式から角かっこ付きの式への変換など、これがどれほど簡単かについての記事を書くことができます。
ご清聴ありがとうございました。