ICFPC 2009に参加してたので日記。

event icfpc icfpc2009

6/26 27:00 - 6/29 27:00の期間で開催されていたICFPC2009に一人で酒飲みながらちんたら参加していたので感想とか書いておきます。先に結論を書くと結構楽しかったんですけどScoreは0点。

まだバグある提出していないもの一式。


twitterの発言あたり参考に振り返ってみる。

pdfへのリンクがミスってたので勘で修正したら普通にダウンロードに成功。タイムライン眺めてたらダウンロードできてない方々が見受けられたので一瞬だけpdfをミラー。まともに戦えるレベルの人達に感謝されるという偉業を達成したのでicfpc 2009は大満足です。

問題文のpdfはろくに読まないまま理解できる部分だけひろって「なんかまずVM作れとか書いてある」と、仕様を理解していない部分は想像で適当にVMを書き始める。DとかJavaとかは最近あんまし触ってなくて手が忘れてるしrubyとかluaみたいのにに向いた仕事でもないよなあと思ったのでCで。後から考えるまでもなく仕様書をちゃんと読んでからプログラム書き始めた方が良いのはわかりきっていたのだけれども、プログラミングする気分だったので仕様書を読むのを後回しに。結局最後まで仕様は理解しきれなかった。上位とか得点とか狙っていくならまず最初に真面目にちゃんと仕様書を読むのは必須条件だと思います。


「楽しいICFPCをもっと楽しく！」という方針によりこの辺だいたい定期的にアルコールを補給していた。

ログインフォームにはっきりと"Email:"と書いてあるけどfirefoxさんがチーム名を補完するのでずっと不思議に思っていたがついに判明。
みたいな多々ある細かいミスの原因はもしやそれだったのかもしれない。

アドレス偶数番地と奇数番地で値とVM命令の順序が入れ替わるという謎の仕様にまんまとひっかかっていたことに気付く。

VMを何に使うのか、ダウンロードしたバイナリファイルはなんなのか、提出するのは何なのか、何もわからないままVMを書いている人達。国家的ビッグプロジェクトの7次受けとかで自分が何を書いてるのかわからないままプログラミングするのとかに向いてるかもしれません。

  • @mickey24 残念。yet another icpfpc2009勝手開催とか。 12:34 AM Jun 28th

毎年おもしろい問題が発表されてるのにほとんど発表後の72時間しか使われないというのはもったいないので、@mickey24が公開されてる問題を利用して勝手にyet anotherなコンテスト開催してくれると嬉しい。

入力バイナリのメモリと命令のダンプができるようになって喜ぶ。後で気付いたけど同アドレスのメモリと命令は併記すべきだった。

memory[0]: 1.00000
memory[1]: 0.00000
memory[2]: 30.00000
memory[3]: 0.00000
memory[4]: 0.00000
memory[5]: 0.00000
memory[6]: 0.00000
memory[7]: 0.00000
memory[8]: 0.00000
memory[9]: 0.00000
...
insns[0]: OP_NOOP
insns[1]: OP_COPY 1 265
insns[2]: OP_NOOP
insns[3]: OP_NOOP
insns[4]: OP_COPY 4 248
insns[5]: OP_SUB 5 4 3
insns[6]: OP_CMPZ 5 == 0.0
insns[7]: OP_PHI 2 1
insns[8]: OP_SUB 8 7 0
insns[9]: OP_COPY 9 263
...

いいかげん諦めてもうちょっと真面目に仕様書を読み、ようやくInputとOutputがどういう命令なのか、VMはどのようにバイナリを実行するのか、何を提出するのか、その辺りのことをうっすらと認識。

バイナリエディタhexerはたまに暴走してメモリ食いつくしてLinuxカーネルごとおなくなりになることがわかった。x86_64環境なのは関係あるのかなあ。

大学の研究室に置いてある鯖が死んだのでしばらく作業できなかった。あと6/28はFirefoxワークショップに参加していた。これ参加してなかったらビジュアライザー書こうとしたと思う。

Div命令で0除算になるときは0を入れるという仕様に気付きました。この辺からVMが多少は意味ありそうな出力をするようになる。

腐るほどしていた勘違いの一つ。

どうもバグが取れた気がしなかったので気分転換にチューニング。

実行時間の多くが以下のようなVM命令呼び出しのループだったのでその辺を。

    for(;machine->pc < machine->insn_len;++machine->pc) {
        Insn *insn = &machine->insns[machine->pc];
        switch(D_OP(insn)) {
            case OP_S:
                /* S-Type Instruction */
                switch(S_OP(insn)) {
                    case OP_NOOP:
                        break;
                    ...
                }
            ...
        }
    }

まずVMの仕様に無い、呼ぶとVMを終了するEndを追加し、実行前に命令列の最後に追加することにする。これにより命令ループごとのmachine->pc < machine->insn_lenという比較演算を削除できる。

    for(;;++machine->pc) {
        Insn *insn = &machine->insns[machine->pc];

$ sudo opcontrol --reset
$ sudo opcontrol --start && ./vm bin1.obf && sudo opcontrol --stop
$ opannotate --source vm | less

のようにして見た結果

  1279 11.3387 :    for(;;++machine->pc) {
  1685 14.9379 :        Insn *insn = &machine->insns[machine->pc];

というわけでinsnをとってくるのに非常に大きなコストがかかっていることがわかったため、以下のように書き換え。

    Insn *insn = machine->insns;
    for(;;++PC(machine),++insn) {

毎回命令列とプログラムカウンタから現在の命令を持ってくることをしなくて良くなる。プロファイル結果もinsn取ってくる分が丸ごと消せた感じ。

               :    Insn *insn = machine->insns;
   932 10.1415 :    for(;;++machine->pc, ++insn) {

なんかoprofile入ってない環境だったのですが

$ sudo aptitude install oprofile

と叩くだけで準備が完了。気軽に使えて非常に便利な道具だと思います。

実行バイナリのダンプを眺めていてCmpz命令がバグってるのに気付いた。opは23-21bitから取ってくるというのは割と前の段階で把握していたのだけれども実行部分だけ勘違いした時のままのコードだった。

こんなひどいミスがこの時点で残ってるとか。途中で入ったのかもしれないけども。この辺の修正でようやくシナリオのロードができるようになった。


今に至る。そういうわけで得点ゲットには及ばなかったのですが色々と楽しめました。

test