或曰

日曜日, 8月 19, 2007

週末の過ごし方

土曜日はダートトラックを走りに行く予定だったが、天候が怪しかったのでキャンセル。疲れもあり一日インドアで過ごす。

日曜は「うみねこのなく頃に」と amazon で注文していたマンガが何冊か届いたので、そちらを消化して終わりそう。

ラベル:

issei さんの投稿 4:44 午後 に投稿 | 0 件のコメント この投稿へのリンク

CScript コンパイルが遅い原因

boost::lambda::bind を boost::bind にしたら、parser.y のコンパイル時間 25% 減。

issei さんの投稿 1:54 午前 に投稿 | 0 件のコメント この投稿へのリンク

CScript 定数畳み込み

定数畳み込み (constant folding) 最適化の実装。

スクリプトソースコード中でコンパイル時に計算できる式を先に計算して、コンパイル済バイナリには結果を書く。例えば 1 + 2 というコードに対して push 1, push 2, iadd の 3 命令を出力にする代わりに push 3 としたい。

理屈は簡単で、元々は文法に付随するアクションで直接 VM のコードを出力しているが、これを構文解析した結果を後で参照できる形で保持しておき必要な情報が揃ったところで VM のコードを出力するように変更すれば OK。ただし、実装するに当たっては決めるべき詳細がいくつか出てくる。

  • 中間解析結果として保持する内容。
  • 中間解析結果を保持するデータ構造。
  • コード生成を行うタイミング。完全にプログラム全体の解析完了後にコードを出力させるのか、それとも途
    中で出力させてしまうか。

本気でフロー解析や最適化を行なおうと思ったら、ソースコードをそのまま木構造に変換した構文木 (parse tree) tree もしくは以降の処理に必要なトークンのみに絞りこんだ抽象構文木 (AST: abstract syntax tree) を作り、次にその構文木を基本ブロックに分割し最適化を行ない、最後にコードを生成する。

ただ、そこまでやると、ちょっと文法に手を入れるだけでも

  1. 文法の修正
  2. 文法に付随する AST ノード作成ルーチンの修正
  3. AST を辿って最適化を行なうルーチンの修正
  4. AST を辿ってコード生成を行なうルーチンの修正

と変更箇所が分散して面倒なことになりがちな上、現状のコード生成ルーチンを破棄して作り直す必要がある。漸進的に開発を進めるため、次の方針でいくことに。

  • 式の段階ではコードを生成せず必要な情報を保持するに留め、文が出てきたタイミングでコード生成を行う。
  • 構文解析の結果として保持する情報は次の 4 つ。

    • 型
    • 定数かどうか
    • (定数であれば) 値
    • コード生成ルーチン


コード生成は元々 Comp クラスのメンバ関数を呼び出すことで行なっているので、その場でメンバ関数を呼び出す代わりにメンバ関数ポインタを std::vector に入れておき、後でまとめて呼び出せるようにする。型チェックやエラー処理などを除いた骨格部分は、こんな感じになる。

/*
 * 変更前
 */
node_primary_expression:
 TOK_INT {
  vm_int_t val = boost::any_cast<vm_int_t>($1);
  p_comp-<genCodePUSH_I(val);
  $$ = Cast::INT;
 }

node_assignment_expression:
 node_primary_expression
 | node_assignment_expression '+' node_assignment_expression:          {
  p_comp->genOprADD_I();
  $$ = $1;
 }

/*
 * 変更後
 */
node_primary_expression:
 TOK_INT {
  vm_int_t val = boost::any_cast<vm_int_t>($1);
  ExpressionInfoP expr(new ExpressionInfo(val));
  expr->addGenCode(boost::lambda::bind(&Comp::genCodePUSH_I, boost::lambda::_1, val));
  $$ = expr;
 }

node_assignment_expression:
 node_primary_expression
 | node_assignment_expression '+' node_assignment_expression
 {
  // 定数同士の加算の場合は、この場で計算して結果に置き換え
  ExpressionInfoP expr1 = boost::any_cast<ExpressionInfoP>($1);
  ExpressionInfoP expr2 = boost::any_cast<ExpressionInfoP>($3);
  if (expr1->isConst() && expr2->isConst()) {
   vm_int_t val = expr1->getVal<vm_int_t>() + expr2->getVal<vm_int_t>()
   ExpressionInfoP expr(new ExpressionInfo(val));
   expr->addGenCode(boost::lambda::bind(&Comp::genCodePUSH_I, boost::lambda::_1, val));
   $$ = expr;
  }
  // 定数たたみこみできない場合は、それぞれの命令出力後に add 命令を出力するように
  else {
   ExpressionInfoP expr(new ExpressionInfo());
   expr->setCast(Cast::INT);
   expr->addGenCode(*expr1);
   expr->addGenCode(*expr2);
   expr->addGenCode(boost::lambda::bind(&Comp::genOprADD_I, boost::lambda::_1));
   $$ = expr;
  }
 }


コード生成ルーチンに関しては、構文解析直後では確定できない情報 (コードが配置されるアドレスなど) の解決を遅延させる必要がある。boost::lambda::bind をネストして合成関数にしてしまうか、それだと書けない場合にはファンクタを用意して使う。

// 三項演算子
typedef boost::function<void (Comp* comp)> GenCode;
typedef std::vector<GenCode> GenCodeList;

struct GenCode3Op
{
 GenCode3Op(ExpressionInfoP expr_cond, ExpressionInfoP expr_true, ExpressionInfoP expr_false)
 {
  expr_cond->gt;swapGenCode(m_gen_cond);
  expr_true->gt;swapGenCode(m_gen_true);
  expr_false->gt;swapGenCode(m_gen_false);
 }
 /*
   [expr_cond]
   jump_if0 L_false
   [expr_true]
   jump L_exit
 L_false:
   [expr_false]
 L_exit:
 */
 void operator()(Comp* comp) const
 {
  _genCode(comp, m_gen_cond);
  vm_taddr_t taddr1 = comp->gt;genCodeJUMP_IF0();
  _genCode(comp, m_gen_true);
  vm_taddr_t taddr2 = comp->gt;genCodeJUMP();
  comp->gt;backpatchJUMP_IF0(taddr1, comp->gt;getCodeSize());
  // L_false
  _genCode(comp, m_gen_false);
  // L_exit
  comp->gt;backpatchJUMP(taddr2, comp->gt;getCodeSize());
 }

private:
 GenCodeList m_gen_cond;
 GenCodeList m_gen_true;
 GenCodeList m_gen_false;
};


ファンクタだろうがメンバ関数ポインタだろうが気にせず扱える boost::function と、既存のメンバ関数を簡単にカリー化できる boost::lambda::bind 万歳。

parser.y のコンパイルで実メモリが不足してスワップ領域使いだしたので、とりあえずデバッグビルドではコンパイル時に最適化しないように変更。調べたら 500MB ぐらいメモリ消費してるけど、何が原因なのやら。

/usr/bin/time -l の結果

  • 最適化なし
           25.06 real        11.60 user         2.51 sys
        275828  maximum resident set size
          4008  average shared memory size
         20237  average unshared data size
           203  average unshared stack size
         81429  page reclaims
             0  page faults
             0  swaps
             0  block input operations
            74  block output operations
             0  messages sent
             0  messages received
             0  signals received
          1121  voluntary context switches
           418  involuntary context switches

  • 最適化 -O
           27.06 real        23.48 user         4.56 sys
        493700  maximum resident set size
          4221  average shared memory size
         87521  average unshared data size
           220  average unshared stack size
        151172  page reclaims
             0  page faults
             0  swaps
             0  block input operations
            42  block output operations
             0  messages sent
             0  messages received
             0  signals received
           826  voluntary context switches
           670  involuntary context switches

  • 最適化 -Os
           24.05 real        21.79 user         3.14 sys
        493684  maximum resident set size
          4226  average shared memory size
         91473  average unshared data size
           225  average unshared stack size
        151171  page reclaims
             0  page faults
             0  swaps
             0  block input operations
            69  block output operations
             0  messages sent
             0  messages received
             0  signals received
           832  voluntary context switches
           581  involuntary context switches

  • 最適化 -O2
           31.42 real        23.95 user         8.32 sys
        493700  maximum resident set size
          4268  average shared memory size
        109638  average unshared data size
           230  average unshared stack size
        151169  page reclaims
             0  page faults
             0  swaps
             0  block input operations
            67  block output operations
             0  messages sent
             0  messages received
             0  signals received
           831  voluntary context switches
           602  involuntary context switches


関連 commit

ラベル:

issei さんの投稿 12:58 午前 に投稿 | 0 件のコメント この投稿へのリンク

日曜日, 8月 12, 2007

もてぎロードフルコース　スポーツ走行

週末は土日とツインリンクもてぎでロードコース走行。

前々から、3速でアクセル開けると断続的にトルクがかかったり抜けたりする症状が出ていたけど、悪化して3速で加速するとまともに走れない状態に。

仕方ないので2速→4速とシフトアップして走行。ベストラップは 2'30.134 ということで一応自己ベスト更新。バイクは、そのままバイク屋さんに直行して入院。ギアが逝ったか？

私はサーキットだと腰をイン側に落とした姿勢で走るけど、それほど極端には腰を入れないし膝もあまり開かない。が、さすがにバンク角が深くなってきてキツい状態に。写真の場所でももっと腰をイン側に向けたいけど、もう膝が地面に付いてしまってるので無理。社外パーツのバックステップを入れる時期か。

次回の課題は、アクセルを開けるポイントを早めること。早い人の走りを見てると、コーナー進入でフルバンク、早い時期からアクセルを開けてクリッピングポイントではバイク立てつつ全開に近い状態で立ち上がってる。いつまでも膝すって旋回してるとタイムが伸びない。

ラベル:

issei さんの投稿 9:21 午後 に投稿 | 0 件のコメント この投稿へのリンク

金曜日, 8月 10, 2007

Transactional Memory: Architectural Support for Lock-Free Data Structures (1993)

マルチプロセッサシステム上で並列プログラミングを行う場合、複数の実行単位で競合する処理を調停する必要がある。現在はロックベースの排他制御を行うのが一般的だが、それに変わるものとして提案されている方式の一つである Transactional Memory に関するおそらく最初の paper。1993年。

Transactional Memory については既に多方面で研究が進んでいて、実装手段としてソフトウェアベース/ハードウェアベース/混在とあり、また transaction の意味にも広がりがある。体系的に整理して理解しておきたいので、まずこれから読んでみる。
  • Architectual Support for Software Transactional Memory
  • An Integrated Hardware-Software Approach to Flexible Transactional Memory
その後は、新しめの paper で MICRO06, ISCA'07あたりから上記を見つけてきたけど、先に reference 調べてから手を付けた方が良いかな。次の一手は、とりあえず今のが終わってから見直し。

ラベル:

issei さんの投稿 1:00 午後 に投稿 | 0 件のコメント この投稿へのリンク

水曜日, 8月 08, 2007

M'soft: Parallel programming model 10 years off

Microsoft の研究者による並列プログラミング今後の展望。

キーワードとして共有メモリ・プロセッサ間通信に加えて、関数型言語が出てきてるのが興味深い。理論的背景はしっかりしており研究も盛んだが、なかなかメインストリームに躍り出ることがなかった関数型言語が一気に普及する契機になるんだろうか。

C#の関数型言語的な拡張の詳細調べるのと、F#使ってみる方向で。

ラベル:

issei さんの投稿 6:45 午後 に投稿 | 0 件のコメント この投稿へのリンク

月曜日, 8月 06, 2007

HOT CHIPS 19: A Symposium on High Performance Chips

プログラム公開。参加はできないが、あとで archive に文書が公開されたら目を通すものメモ。Networking とか Wireless もチェックしときたいが、時間無いかな。
  • Session One
    IBM Power6
  • Session Two
    Multi-Core and Parallelism I
  • Session Three
    Multi-Core and Parallelism II
  • Keynote II
    Multicore and Beyond: Evolving the x86 Architecture
  • Session Eight
    Mobile PC Processors and Chipsets
  • Session Nine
    Big Iron
    Special Presentation

ラベル:

issei さんの投稿 6:03 午後 に投稿 | 0 件のコメント この投稿へのリンク

Microsoft Financial Analyst Meeting 2007, Craig Mundie

Microsoft 研究部門トップ Craig Mundie によるアナリスト向けミーティング発表内容。

単一プロセッサの性能向上が限界に来ており、今後も継続的に性能向上を行うためには、は異種混合プロセッサ環境を前提にプログラミング言語・環境を整えていく必要があるという話をしてる。

アナリスト向けミーティングで、ここまで焦点を絞って話しているということ自体が、一つのメッセージですね。

ラベル:

issei さんの投稿 2:49 午後 に投稿 | 2 件のコメント この投稿へのリンク

Researchers set to spark up new more secure network, routers, switches

スタンフォード大学で研究が進められている、中央集権型のネットワークアクセスポリシー Ethane の話。今はネットワークポリシーを設計後、実現するには個々のルーター・スイッチなどに個別設定を行う必要があるが、それを一箇所で設定するだけで OK になる。

ラベル:

issei さんの投稿 10:31 午前 に投稿 | 0 件のコメント この投稿へのリンク

日曜日, 8月 05, 2007

週末の過ごし方

土曜日は LL魂 に参加、日曜日は交通教育センターレインボー埼玉で HMS 中級 (CBR600RR)。

この炎天下にライディングスクールで走ってるだけでもバカだが、そこでフルカウルで風が来ない上、積極的に身体を使って操作する必要があるスーパースポーツ車を選択するのは大バカとしか……。疲労困憊、帰宅してシャワー浴びたらベッド直行。

issei さんの投稿 9:06 午後 に投稿 | 0 件のコメント この投稿へのリンク

木曜日, 8月 02, 2007

Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation

ACM SIGPLAN (プログラミング言語に関する研究部会) による「プログラミング言語の設計と実装」に関するカンファレンスの proceeding。

全部読む時間はないから、abstract だけ目を通して最新動向把握するのと、面白そうなものだけいくつかピックアップして読むか。身近にこの手の paper 読める人がいると、手分けして作業できて効率良いんだけどねぇ。

ラベル:

issei さんの投稿 11:20 午前 に投稿 | 0 件のコメント この投稿へのリンク