Hatena::ブログ(Diary)

hogeなlog

プロフィール

hogelog

hogelog

小室 直(こむろ すなお)。電気通信大学2003年入学。2010年修士卒業。プログラミングとかしてます。

カレンダー
1984 | 01 |
2006 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2010 | 01 | 06 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 05 | 08 | 09 | 10 | 12 |
2012 | 01 | 04 | 06 |

July 17(Fri), 2009

[][] Lua処理系コード読み(1) lua_State

せっかくLua処理系いじったりしてるんだから適当にアウトプットしていこうかなと思った。ストーリーだてた解説ではなく、思いついたときに目についた構造体や関数、マクロの適当な解説を日記にのっける感じで。いつまで続けるか未定。



lua_Stateは「Lua処理系」というものの実体と考えても良い。(メインスレッド含む)スレッドごとに一つ持つ。全てのスレッドはメインスレッドから辿ることができる。

  • lua_State mainthread
    • lua_State thread (1)
    • lua_State thread (2)
    • ...
    • lua_State thread (n)

スレッドに限らず「Lua VMスタックの底」や「現在実行しているクロージャ情報」、「GC管理オブジェクト」などの全ての状態はここから辿ることができる。

ほとんどのLua APIはこのlua_Stateを第一引数とする。lua_Stateを引数としないAPIとしてはlua_Stateを作成するlua_State *luaL_newstate(void) (= lua_open)など。

# 最初にlua_Stateを作る関数がlua_Stateが必要だと困りますし当然ですが。

typedef struct lua_State lua_State;

/*
** `per thread' state
*/
struct lua_State {
  CommonHeader;
  lu_byte status;
  StkId top;  /* first free slot in the stack */
  StkId base;  /* base of current function */
  global_State *l_G;
  CallInfo *ci;  /* call info for current function */
  const Instruction *savedpc;  /* `savedpc' of current function */
  StkId stack_last;  /* last free slot in the stack */
  StkId stack;  /* stack base */
  CallInfo *end_ci;  /* points after end of ci array*/
  CallInfo *base_ci;  /* array of CallInfo's */
  int stacksize;
  int size_ci;  /* size of array `base_ci' */
  unsigned short nCcalls;  /* number of nested C calls */
  unsigned short baseCcalls;  /* nested C calls when resuming coroutine */
  lu_byte hookmask;
  lu_byte allowhook;
  int basehookcount;
  int hookcount;
  lua_Hook hook;
  TValue l_gt;  /* table of globals */
  TValue env;  /* temporary place for environments */
  GCObject *openupval;  /* list of open upvalues in this stack */
  GCObject *gclist;
  struct lua_longjmp *errorJmp;  /* current error recover point */
  ptrdiff_t errfunc;  /* current error handling function (stack index) */
};

[][] Lua処理系コード読み(2) Value, TValue

Lua処理系内部における「値」は共用体Valueにint型のタグを付与した構造体TValueで表現される。int ttは各種ビット(例えばTValueが示すのがgc, p, n, bいずれの型の値であるかなどの情報)を保持する。

/*
** Union of all Lua values
*/
typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;


/*
** Tagged Values
*/

#define TValuefields	Value value; int tt

typedef struct lua_TValue {
  TValuefields;
} TValue;
トラックバック - http://d.hatena.ne.jp/hogelog/20090717

July 15(Wed), 2009

[] 2009/7/19(日)電気通信大学オープンキャンパスのお知らせ

http://www.uec.ac.jp/admission/dept/open.html

7/19(日)に高校生など電気通信大学の学部入学を考えている人向けのオープンキャンパスが開催されます。

プログラムとしては

  • 大学紹介 【講堂】
  • キャンパスツアー
  • 研究室公開
  • 個別相談 【大学会館4階】

などがあります。

受け付けの類は講堂の大学紹介以外は特に無いのでフラっと来て適当に見てまわると良いと思います。


私がやっているのは研究室公開です。西9号館の6階で高校生を捕まえて話をするだけの簡単なお仕事に勤しむ予定です。研究室公開と言っても研究以外のことでも、答えられることは何でも答えます。

  • 大学って何それおいしいの?
  • 留年するとどうなるの?
  • オレオレ言語ってどうやって作るの?
  • なんでCRubyは保守的GCなの?

のような質問も歓迎です。研究室公開を見てまわる予定のある方で、プログラミングプログラミングしたコンパイラやらインタプリタやらICPCプログラミングコンテストやら、そういうのが好きな方は是非西9号館まで来ると良いと思います。現情報工学科、来年からは情報・通信工学科の研究室が集まってます。西9まで来たら6階にも顔を出していただければ幸いです。

トラックバック - http://d.hatena.ne.jp/hogelog/20090715

July 12(Sun), 2009

[] 2009/7/9(土)に参加したイベント

SmileyHackathon#5 直前秋葉原オフ - は、だいたい12時前後に秋葉原つく感じでいいのかなと、あまり時計とか気にしないでなんとなく行ったんですけどどうも遅刻してたようですね。すいません。

リナックスカフェについてからは自分のコードとかよりむしろid:pi8027さんのコードとか見てあれこれ横からやいのやいの言ってました。ちょっとトイレに行って戻るとやたら賑やかな集団が。天下一ストリートコンピューティング大会の面々でした。ストリートコンピューティングは人の心を和ませる何かがあるのかもしれない。参加者の方々は皆ひどく楽しそうな笑顔を浮かべていました。

SmileyHackathonの開始時刻とかドワンゴの最寄り駅とか調べていかなかったのでpi8027さんに促されるままにリナカフェを出て、なんとか駅のなんとか線に乗ってなんとか駅で降りてドワンゴに。そういえば秋葉原のでかい信号渡ってるところでid:inajobさんとすれ違うなんてイベントがあり、ああ秋葉原だなあと。


SmileyHackathon#5 - Smiley Hackathon(仮)

そんなわけでドワンゴに着いてid:acotieさんも来てSmileyHachathon#5開始。そういえば私はacotieさんという人を最初に認識したのがこの一連の発言事件の時だったので、どうもその印象が残っていたので、acotieさんが普通の方で少しびっくりしました。

HachathonそのものとしてはLuaの処理系をvim+global、emacs+gdbあたり使いながら呼んでました。まあ結構読み解けましたし有意義でした。最後に発表の時間があったのですが「Luaの関数はコンパイル時に静的に生成した命令列などのプロトタイプと呼ぶ部分に、CLOSURE命令実行時に動的にローカル変数と環境を結びつけたもので云々」とかちょっと地味かなと思ったので、Hachathonとは無関係のお蔵入りしていた「プログラミング環境Vimperator」的なスライドを適当に発表。


眠いのでどんどん描写が減っていくというかもう眠いのでここまででもうポストします。とっぺんぱらりのぷう。

July 09(Thu), 2009

[] 2009/7/9(土)に参加するイベント

SmileyHackathon#5 直前秋葉原オフ -

SmileyHackathon#5 - Smiley Hackathon(仮)

SmileyHackathonがドワンゴで開催されるのですけどドワンゴの場所わからないのでid:pi8027に連れってってもらおうと思います! SmileyHackathonの方は募集終えてる感じですね。直前オフはたぶんその時間にその辺に行ったらいるのだと思います。

トラックバック - http://d.hatena.ne.jp/hogelog/20090709

July 01(Wed), 2009

[][][] ICFPC 2009感想エントリとかリンク集

たぶんここだよね的なチーム名も併記します。間違ってたらすいません。指摘していただければ書き換えます。

チーム名
リンク
shinh
2009-06-30 - 兼雑記:

一般的に、信用のおけるパーツを一つずつきちんと組んでくのは大事だなぁ

shinhさんと俺じゃレベルは全く違うわけですがこれは本当に大事だなあと、今回のicfpcでしみじみ思った。

pepsiso
ICFPCまとめ - d.y.d

ビジュアライザーの動画楽しそう。やっぱビジュアライザー大事だなあ。

pepsiso
ICFPC 2009 - なんとなくな日々のコメント
kuma-
ICFP Programming Contest 2009 終了 - まめめも
yowa
xe-kdoo(2009-06-30)
Ikoma
紫ログ:ICFP 2009 Programming Contest(1日目), 紫ログ:ICFP 2009 Programming Contest(2日目), 紫ログ:ICFP 2009 Programming Contest(3日目)
Intercaml
揺動散逸日記 ICFP PC 2009
Intercaml
週記: ICFP-PC2009参加記録
Intercaml
Operation Clear Sky - にゃあさんの戯言日記
Intercaml
ICFPC - 雑記
Sim
ICFPプログラミングコンテスト2009 - Sim’s blog
mokehehe
ICFPC2009 - IMHO
kt3k
kt3k ニート日記 ICFP Contest 2009 (1), kt3k ニート日記 ICFP Contest 2009 (2), kt3k ニート日記 ICFP Contest 2009 (3)

.osf ファイルヘッダーの、0xCAFEBABE をリトルエンディアンにしていないことに気づけなくて、

そのまま大会終了するところだった。

勘違いしてそのまま大会終了しました。少し悲しい。

msiro
Coding Memorandum ICFP Contest 2009 メモ
tomerun
ICFP2009 Programming Contest - 総合的な学習のお時間
rayerd.wiz
ICFPC 2009 の情報集めを開始 ...ing logging 3.0
irori
ICFP Programming Contest 2009 - iroriの日記
HITO(ry
ICFP ’09 Programming Contest - てきとーな日記
HITO(ry
6月にあったプログラミングコンテスト - (iwi)の日記
eldesh
ICFP2009参加 - ::Eldesh a b = LEFT a | RIGHT b
Purely Functional Infrastructure
ICFPCに参加中@記念撮影 - nobu-qの日記
ayatuki
反省会 - ayatukiの雑記

反省点2: 問題文はちゃんと読もう

まあこれも基本ですが… なんか一時期 900 step で目標軌道までつかなきゃいけないと思い込んだりしてたので(^^;

これは多くの人が勘違いしていたようですね。

safii
blog/2009-06-30 - Flightless wing
Team Sampou
haskell-ja > Archives > 2009/06/26, 2009/06/27, 2009/06/28, 2009/06/29

チーム名とかがわからない方


ICFPC2009の日本語解説的なページ


参加してたぽい人達のtwitterアカウントとか

網羅はしていないと思いますが見掛けた範囲で。

pepsiso
@kinaba, @tsukuno
shinh
@shinh
Purely Functional Infrastructure
@tanakh, @nobu_k
Intercaml
@nya3jp, @chunjp, @phoenixstarhiro, @gusmachine
mokehehe
@mokehehe
tomerun
@tomerun
rayerd.wiz
@Rayerd
HITO(ry
@wata_orz, @iwiwi
eldesh
@eldesh
Team Sampou
@1to100pen, @ikegami__, @nobsun, @masahiro_sakai, @cutsea
hogelog
@hogelog 点数取ってないのでスコアボードに乗ってませんが。

チーム名とかがわからない方

情報提供ありがとうございます

id:shinichiro_h, id:haru-s の情報によりIntercamlのphoenix_hiroさん、iroriのiroriさんのエントリ、id:haru-sこと@Rayerdさんのチーム名追記

追加

Team Sampouのitto100penさんの情報提供によりTeam Sampouの情報追記。

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

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から取ってくるというのは割と前の段階で把握していたのだけれども実行部分だけ勘違いした時のままのコードだった。


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


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

shinichiro_hshinichiro_h 2009/07/01 12:32 まとめありがとうございます。とてもありがたいです。他にもあるかもですが、僕がさっくり気付けた見落としです。

Intercaml: http://d.hatena.ne.jp/phoenix_hiro/20090630/1246382348
irori: http://d.hatena.ne.jp/Irori/20090630/1246382472
pepsiso: http://d.hatena.ne.jp/tsukuno/20090630#1246301431

id:haru-sid:haru-s 2009/07/01 12:52 お疲れ様です.
「ICFPC 2009 の情報集めを開始 ...ing logging 3.0」のid:haru-s == @Rayerd です.
チーム名はrayerd.wizでした.

itto100penitto100pen 2009/07/03 22:22 Team Sampou の奮闘ぶり(混乱ぶり(笑))は
Haskellに関するチャット部屋
http://practical-scheme.net/chaton/haskell-ja/
の「Read Archive」で 2009/6/26 辺りからを選んでもらえると見ることができます。

最近のコメント
Connection: close