protocol buffer 3 をビルドしてインストール
最近 version 3 が出た protobuf を試しに動かしてみたメモ。
導入手順
Releases から C++ のアーカイブをダウンロードしてきて展開する。(protobuf-cpp-3.0.0.tar.gz というやつ)
展開後のディレクトリに cd して、以下の手順でビルドする。
./configure make -j $(nproc)
後は、sudo make install && sudo ldconfig すればインストールできるが、個人的に野良インストールはしたくないので、deb パッケージを作ることにする。別に deb を作りたくない人はこの手順は無視してOK。
# ./deb に make install する mkdir deb make install DESTDIR=$(pwd)/deb mkdir ./deb/DEBIAN # control ファイルを書く cat > ./deb/DEBIAN/control <<EOF Package: nojima-protobuf Version: 3.0.0-1 Maintainer: Nobody <nobody@example.com> Architecture: amd64 Description: protocol buffer EOF # postinst スクリプトを書く (ldconfig するだけ) cat > ./deb/DEBIAN/postinst <<EOF #!/bin/sh -e ldconfig EOF chmod +x ./deb/DEBIAN/postinst # deb パッケージ化する fakeroot dpkg-deb --build -Z gzip ./deb ./ # できた deb パッケージをインストールする sudo dpkg -i ./nojima-protobuf_3.0.0-1_amd64.deb
試しに動かしてみる
以下の内容を person.proto という名前で保存する。
syntax = "proto3";
message Person {
string name = 1;
int32 id = 2;
string email = 3;
}
protoc でコンパイルして C++ のソースコードを生成する。
protoc --cpp_out=./ person.proto
すると person.pb.h と person.pb.cc というファイルができる。
これを使って person を encode するコードを書いてみる。
以下の内容を encode_person.cc という名前で保存する。
#include <cstdlib>
#include <fstream>
#include <iostream>
#include "person.pb.h"
int main(int argc, char** argv) {
// Verify that the version of the library that we linked against is
// compatible with the version of the headers we compiled against.
GOOGLE_PROTOBUF_VERIFY_VERSION;
if (argc != 2) {
std::cerr << "Usage: encode_person FILE\n";
std::exit(1);
}
Person person;
person.set_name("Yusuke Nojima");
person.set_id(42);
person.set_email("nojima@example.com");
std::fstream output(argv[1], std::ios::out|std::ios::trunc|std::ios::binary);
if (!output) {
std::cerr << "ERROR: failed to open file: " << argv[1] << "\n";
std::exit(1);
}
if (!person.SerializeToOstream(&output)) {
std::cerr << "ERROR: failed to serialize person.\n";
std::exit(1);
}
return 0;
}
そしてコンパイルして実行。
g++ -Wall -o encode_person encode_person.cc person.pb.cc -l protobuf ./encode_person person01
すると person01 というファイルにそれっぽい何かが出力される。
$ xxd person01 00000000: 0a0d 5975 7375 6b65 204e 6f6a 696d 6110 ..Yusuke Nojima. 00000010: 2a1a 126e 6f6a 696d 6140 6578 616d 706c *..nojima@exampl 00000020: 652e 636f 6d e.com
次に、シリアライズされた person を decode するものを書いてみる。
以下の内容を decode_person.cc という名前で保存する。
#include <cstdlib>
#include <fstream>
#include <iostream>
#include "person.pb.h"
int main(int argc, char** argv) {
// Verify that the version of the library that we linked against is
// compatible with the version of the headers we compiled against.
GOOGLE_PROTOBUF_VERIFY_VERSION;
if (argc != 2) {
std::cerr << "Usage: decode_person FILE\n";
std::exit(1);
}
std::fstream input(argv[1], std::ios::in|std::ios::binary);
if (!input) {
std::cerr << "ERROR: failed to open file: " << argv[1] << "\n";
std::exit(1);
}
Person person;
if (!person.ParseFromIstream(&input)) {
std::cerr << "ERROR: failed to parse person.\n";
std::exit(1);
}
std::cout << "name = " << person.name() << "\n";
std::cout << "id = " << person.id() << "\n";
std::cout << "email = " << person.email() << "\n";
return 0;
}
そしてコンパイルして実行。
$ g++ -Wall -o decode_person decode_person.cc person.pb.cc -l protobuf $ ./decode_person person01 name = Yusuke Nojima id = 42 email = nojima@example.com
読めた！！
TODO
ベンチマーク取りたい。
[追記] ベンチマーク取った → Protocol Buffers が本当に遅いのか実際に確かめてみた
ICFPC 2016 に参加しました (チーム: モダン焼き フジ)
ICFP Programming Contest にcosさん、qwertyさん、seikichiさんとチーム名「モダン焼き フジ」で参加しました。 チーム名は大学生のころによく行ったモダン焼き屋さんの名前から取りました。
最終結果はまだ公開されていないけど、Leaderboard が凍結された時点では13位でした。
レポジトリ: https://github.com/seikichi/icfpc2016
0日目
去年のICFPCでは、メンバーの環境が Ubuntu, Mac, Cygwin とバラバラだったため、環境ごとに微妙に使えるコンパイラオプションとかライブラリとかが異なって非常に面倒だったので、今回は環境をそろえようということになった。 ということで Ubuntu 16.04 をまずセットアップ。
また、去年は CI 環境をコンテストが始まってから用意していたけど、時間の無駄なので今年は事前に用意することにした。 ということで seikichiさんが Jenkins をセットアップしてくれた。 CI サーバは Google Compute Engine の 1CPU インスタンスを利用した。
Makefile もある程度作りこんだものをこの時点で書いておいた。
1日目
全員で問題文を読む。 大雑把に言うと、折り紙のシルエットとスケルトンが与えられるので、どのように折ったらその形になるのかを答えよという問題だった。 個人的に苦手意識の強い平面幾何の問題であり、さらにどうやって探索したらいいのか全く見当がつかない。 これまで参加したICFPCの中で最大の絶望感を味わった。
とりあえず問題の可視化とスコアリングができないと話にならないので、自分とseikichiさんがビジュアライザを、cosさんとqwertyさんがスコア計算プログラムを作ることになった。
ビジュアライザだけであれば Python とか Ruby とかで書くのが楽そうだが、どうせソルバを作るときに C++ 用の入力関数が必要になるので、コードの再利用性を考えてビジュアライザも C++ で書くことにした。 ビジュアライザを作る過程で、問題のspecにアホみたいに大きい座標が含まれていることがわかった。 したがって多倍長有理数を扱う必要があるので、GMP を使うことにした。 C++用のクラスも用意されていて意外と便利だった。
スコア計算は結構面倒そうだから実装には結構時間がかかりそうだなと思っていたら、cosさんがモンテカルロ法による実装をさっくり作ってしまって凄い(小並感
昼食後、弱くてもいいから何かソルバを作ろうということで、seikichiさんが初期状態から並行移動して重心の位置を合わせるだけのソルバを作った。 一瞬だけランキングで２位になった。
その後、x軸、y軸に並行に何回か折るだけのソルバを作った。 これで単に長方形になるように折っただけの問題は解けるようになった。 また、予め与えておいた角度を全探索することで、既知の角度で回転している長方形は解けるようになった。 問題の制約として、全ての座標が有理数でないといけないという制約があるため、みんな似通った角度で回転させるので、この(頭の悪い)方法でもそこそこ正解したりもした。 また、長方形を適当にスケーリングしてみて resemblance を稼ぐみたいなこともやった。 （この時点では、このコンテストにおいては厳密解のみが正義で近似解に人権はないことに気付いていなかった）
ソルバを動かすのに時間がかかるようになってきたので、GCEで16コアのVMを借りた。
自分が長方形ソルバを作っている間にcosさんがスコア計算を高速化したりライブラリを整備したりしていた。 また、seikichiさんがソルバの性能（解けた問題の数、平均resemblanceなど）を Jenkins でグラフ化してくれるやつを作ったり、問題が増えた時に自動で fetch してきて git レポジトリに push してくれるやつを作ったりしていた。 その裏でqwertyさんが手計算で黙々と提出用の問題を作っていた。
3時ぐらいに寝た。
2日目
起きたら11時だった。 qwertyさんは早起きして問題を作っていた模様。さすがすぎる。
cosさんが任意の直線で紙をfoldする関数を作った。 これでようやく我々のチームも長方形以外の形が折れるようになった。
fold関数を使って凸包ソルバを作った。 サイズ制限にさえ引っかからなければ、シルエットが凸である形は厳密に折れるようになった。 例えば以下の形が折れるようになった。
その後、Twitter をしているとモダン焼き フジに言及している人を見つけた。
ICFP Programming Contest 参加者、意味もなくモダン焼きの CM 見せられている。
— 宇宙ツイッタラーX (@kenkoooo) 2016年8月7日
seikichiさんがすごい勢いで Jenkins のパイプラインを整備していた。 新しい問題が追加されたら自動で既存のソルバ群が実行され最良のスコアが自動で提出される感じのシステムが構築されていた。 その裏でqwertyさんが黙々と提出用の問題を作ったり、兜とか風車とかを手で解いたりしてた。
12時過ぎぐらいに寝た。
3日目
起きたら11時だった。 qwertyさんは早起きして問題を作っていた模様。さすがすぎる。
そろそろ探索を書かないとまずいということで、全探索ソルバを書いた。 最終形から unfold していく方針は unfold 時にどの面とどの面に別れるかがわからないため難しいと判断して、初期状態から直線を適当に選んで fold していく方針にした。
このとき、スケルトンに現れている直線の集合をそのまま探索の候補として使うことはできない。 なぜなら、ある直線にそって紙を折ると、それまでの折り目がその直線によって反射されてしまうので、最終的なスケルトンに現れない場合があるので。 そこで、深さ0ではスケルトンに現れる直線の集合を候補として使い、深さnでは深さn-1の候補集合に加えて最後に選んだ直線で候補集合を反射したものを候補とするようにした。
この全探索はその見た目どおり計算量が凄まじく、実行してすぐに答えが返ってくるのは max_depth=2 までで、max_depth=3 だと10秒以上待たされるし、max_depth=4 だと返ってこない。
また、前から fold していく方針なので、初期状態で紙がどれぐらい回転及び平行移動しているかを求めないといけない。 とりあえず多くの場合で使えそうなヒューリスティックとして、スケルトンに含まれる直線から「同じ点をどちらかの端点に持ち」「互いに直交しており」「直線が水平になるように回転したときに、あらゆる有理数座標が有理数座標に移る」ような２直線を選んできて、その２直線と初期状態の紙の角を合わせるという方針を取った。
全探索ソルバによって、3手以内で折れる問題は解けるようになったが、実際の問題はもうちょっと手数のかかる問題が多い。 例えば、紙を水平方向に3回折って 1/8 の幅の長方形を作った後に1～2回適当に折るみたいな問題がいっぱいある。 ということで、全探索ソルバに初期値を与えることができるようにした。 これで下図のような既知の初期状態（1/8長方形、1/16長方形、1/2三角形など）からちょっとだけ折ったような問題には答えられるようになった。
また、既存の問題を平行移動したり回転したりしただけの問題が大量に存在しているが、これもそのうちのひとつを解けば、初期値付き全探索ソルバが max_depth=0 で答えを見つけてくれるようになった。
その後は seikichi さんが問題一覧を見れるウェブサービスを作ったり、既に正解した問題を自動計算の対象から外したり、念のため全問題再提出などを行ったりしていた。 qwerty さんと cos さんは黙々と手で問題を解いていた。 自分は凸包ソルバや全探索ソルバをちょっと弄って何かできないか試していたが、結局そこから５問しか解けなかった。
まとめ
最終的に 3528 問中 1872 問を解くことができた。 1日目の絶望感からすると結構健闘したような気はする。
Kafka の勉強 (2日目)
昨日の記事に引き続き、Kafka の設計についてドキュメント を読んでいく。
4.3 Efficiency
4.2 節ではディスクの効率について議論した。 ディスクの効率以外で、この種のシステムでよくある非効率性は、次の２つだ。
- 小さな多数の I/O オペレーション
- 過剰なバイトコピー
小さな I/O オペレーションはサーバ側、クライアント側の両方で発生しうる。
この問題を避けるために、Kafka のプロトコルは「メッセージセット」というメッセージをグループ化するための概念を持つ。 これにより、ネットワークのラウンドトリップに伴うオーバーヘッドを償却できる。 また、サーバは複数のメッセージを一度にログファイルに追記でき、consumer は連続する多数のメッセージを一度に取得できる。 このシンプルな最適化により、速度が10倍になる。
もう一つの非効率性はバイトコピーである。バイトコピーはメッセージの量が少ないうちは問題にならないが、負荷が高まってくると非効率性が顕在化する。これを解消するために、Kafka は producer, broker, consumer で共通のバイナリメッセージフォーマットを使用する。 したがって、この三者の間ではデータチャンクを修正なしで転送できる。
broker が保持するメッセージログはそれ自体単なるファイルのディレクトリで、各ファイルはメッセージセットの列を追記していったものである。 メッセージセットのフォーマットは producer や consumer が使うものと同じフォーマットを利用する。 共通のフォーマットをディスク上のフォーマットとしても使うことで、ログチャンクのネットワーク転送を最適化することができる。 最近の Unix にはページキャッシュからソケットへの極めて高度に最適化された転送の仕組みが用意されている。 Linux では sendfile(2) システムコールがそれである。
sendfile について理解するために、データをファイルからソケットに転送する一般的な方法について考える。
- OS がディスクからデータを読んでカーネル空間のページキャッシュに入れる
- アプリケーションはカーネル空間からデータを読んでユーザ空間のバッファに入れる。
- アプリケーションはカーネル空間に存在するソケットバッファにそのデータを書く。
- OS はソケットバッファのデータを NIC のバッファに書く。
これは明らかに非効率で、４回のコピーが行われている。 sendfile を利用すれば、ユーザ空間へのコピーをすることなしにページキャッシュから直接ネットワークにデータを送ることができる。
所感
sendfile 便利（小並感
ゼロコピーを達成するために producer, broker, consumer の間でバイナリフォーマットを揃えるのは力強い感じで好感がもてる。 Kafka のレイヤーで一切メッセージをいじれなくなるので、相当強い意思がないとできない最適化だと思った。
Kafka の通信を TLS 化する仕組みとかあるけど、sendfile にこだわるなら平文じゃないと行けないのかなぁ。
Kafka の勉強 (1日目)
Kafka のドキュメント を読みながらわかったことをメモしていく。
設計に興味があるので 4. Design から読む。
4.1 Motivation
以下のような性質を持つデータハンドリングプラットフォームが欲しい。
- 高いスループット
- 低いレイテンシ
- partitioned, distributed, real-time processing
- fault-tolerance
4.2 Persistence
Don't fear the filesystem
Kafka はメッセージを保存するためにファイルシステムをヘビィに使っている。 多くの人が「ディスクは遅い」と思っているが、適切にディスク上の構造を設計すればネットワークと同じぐらい速くできる。 実際、6台の 7200rpm SATA からなる RAID-5 アレイに対するシーケンシャル書き込み速度は 600MB/sec ぐらいになる。
また、最近の OS はメインメモリをディスクキャッシュに積極的に利用するようになってきている。 モダンな OS であれば、空きメモリ全てをディスクキャッシュとして利用できる。 アプリケーションがもし独自にキャッシュ機構を持つならば、(Direct I/O などでファイルキャッシュを迂回しない限り) ２重にキャッシュを保持することになってしまう。
さらに、Java アプリケーションの場合、
- Java のオブジェクトのメモリオーバーヘッドはとても大きく、データサイズは２倍以上になる。
- Java のガーベジコレクションはヒープ内のデータが増えるにつれて遅くなっていく。
という問題もある。
ゆえに、ファイルシステムとページキャッシュを利用する戦略は、インメモリキャッシュを利用する戦略に対して優っている。
さらに、以下のような利点もある。
- ページキャッシュはサービスが再起動しても消えない。一方、インメモリキャッシュは消えるので、ファイルから再構築するか、完全に空の状態からスタートする必要がある。
- キャッシュとファイルシステムの間の一貫性をより簡単に担保できる。
したがって、「データをメモリにできるだけためて、空きメモリがなくなったらディスクにフラッシュする」のではなく、「全てのデータを受け取ったら直ちに fsync なしでファイルシステムに書き込む」という設計にした。fsync をしない書き込みは、実質的にはカーネルのページキャッシュへの転送を意味する。
所感
最初 Kafka がインメモリキャッシュを使わずにファイルキャッシュを利用する設計になっているということを聞いたときは、そのほうが実装が楽なのかなぁという程度に思っていたけど、実はインメモリキャッシュよりもファイルキャッシュのほうが優れているという考察の下でこの設計を行ったと知って驚いた。 確かに、ネットワークと同程度のスループットが出ればボトルネックにはならないわけだから、RAID で束ねれば 10Gbps ぐらいのネットワークならば戦えると。ただし、シーケンシャルアクセスが前提となっているので、topic 数とか partition 数が増えてくると（ランダムアクセスに近づくので）辛そう。
あと、fsync しない設計なので、突然の電源断とかがあると直近のメッセージは失われることになる。これは分散しているから別のノードから取ってくればリカバーできるよということだろうか。落雷でデータセンターごと停電とかしたら嫌だな…。UPS に祈りをささげておかないと。
unique_ptr で今風な C++ コードを書こう！！
はじめに
お久しぶりです。KMC OB の id:nojima です。
この記事は KMC Advent Calendar 2014 の10日目の記事です。 昨日は id:murata さんの「受験生応援！Javascriptでひねくれ数列」 でした。
今日は C++ の unique_ptr の話です。
（最初は rvalue について書こうと思っていたのですが、書いてみると unique_ptr だらけになったのでタイトルを変えました。なので、KMC Advent Calendar 2014 に書いてあるタイトルとは食い違っています。すみません）
個人的には C++03 ではなく C++11 を使う最大の理由は unique_ptr の存在だと思っています。
- 例外発生時にももれなく delete してくれる。
- 生ポインタとパフォーマンスが同じ。(最適化されている場合)
- 所有権を型として表明できる。
など、様々なメリットがあり、ソースコードに unique_ptr という文字列が存在するだけで何となく今風な雰囲気が漂ってくる優れものです。
ということで、今回は unique_ptr にまつわる tips 集です。
生ポインタではなく unique_ptr を返す関数を書こう
ゲームを制作している状況を考えます。
ステージのレベルに合わせて Enemy を作成して返す関数 CreateEnemy は以下のように書くことができます。
unique_ptr<Enemy> CreateEnemy(int level) { if (level <= 5) return unique_ptr<Enemy>(new WeakEnemy()); // 低い階層では弱い敵を返す else return unique_ptr<Enemy>(new StrongEnemy()); // 高い階層では強い敵を返す } ... unique_ptr<Enemy> enemy = CreateEnemy(10);
CreateEnemy をこのように unique_ptr を使って書くメリットは２つあります。
Enemy*が登場しないので、メモリリークを心配する必要はありません。unique_ptrを使っている限り、適切なタイミングでメモリが解放されることが保証されます。 もちろん、CreateEnemyの利用者側でunique_ptrのget関数を呼び出して生のポインタを得た場合はこの限りではありませんが、その場合でも use-after-free の可能性をgetを利用している箇所に限定でき、デバッグが容易になります。- 戻り値の型から
EnemyをCreateEnemyの利用者側がdeleteすべきであることが簡単にわかります。Enemy*を返す関数の場合、その関数の利用者がEnemy*を削除していいのかわかりません。 もしかすると、static な領域にEnemyを確保しており、それへのポインタを返している可能性もありますし、複数回の関数コールでメモリ領域を共有しているため、簡単には delete できないかもしれません。unique_ptrを返している場合は、型から利用者に delete の責任があることがわかるので、こういった心配をする必要はありません。
また、unique_ptr を返す関数を shared_ptr で受けることもできます。このため、複数の場所で Enemy を共有したい場合でも CreateEnemy の戻り値の型を shared_ptr に変更する必要はありません。
shared_ptr<Enemy> enemy = CreateEnemy(10);
unique_ptr&& を受け取って別の関数に渡すときは move しよう
unique_ptr を受け取って、それをそのまま別の関数に渡したい場合があります。
特に、クラスのコンストラクタで unique_ptr<T>&& を受け取って unique_ptr<T> 型のメンバ変数を初期化するようなことは頻繁に発生します。
ところが、普通に以下のように書くことはできません。
// 背景 class Background { public: // 受け取った bitmap を利用してメンバ変数を初期化する。 // unique_ptr はコピーできないので move したい。 Background(unique_ptr<Bitmap>&& bitmap) : bitmap_(bitmap) {} private: unique_ptr<Bitmap> bitmap_; };
clang に書けると以下のようなエラーになります。
t.cpp:63:11: error: call to deleted constructor of 'unique_ptr<Bitmap>'
: bitmap_(bitmap) {}
^ ~~~~~~
/usr/include/c++/4.8/bits/unique_ptr.h:273:7: note: 'unique_ptr' has been
explicitly marked deleted here
unique_ptr(const unique_ptr&) = delete;
^
1 error generated.
エラーメッセージにあるとおり、unique_ptr(unique_ptr&&) を呼びたかったのに、unique_ptr(const unique_ptr&) を呼んでしまっています。
しかし、bitmap の型は unique_ptr<Bitmap>&& のはずなのに、なぜ unique_ptr(unique_ptr&&) ではなくて unique_ptr(const unique_ptr&) が呼ばれてしまうのでしょうか？
その理由は、unique_ptr(unique_ptr&&) の方を呼ぶためには引数の型が rvalue reference であるだけでは不十分で、引数の式の value category が rvalue であることも要求されるからです。この場合は、引数の式の value category が lvalue なので、unique_ptr(const unique_ptr&) の方を呼びだそうとしてしまいます。
（lvalue は、bitmap や bitmap.width などの「名前のついたオブジェクト」を表す式です。rvalue は lvalue の逆で foo() や x + 1 といった「名前のないオブジェクト」を表す式です。）
これを解決するためには以下のように std::move 関数を使って引数の式を rvalue にすればよいです。
// 背景 class Background { public: // 受け取った bitmap を利用してメンバ変数を初期化する。 Background(unique_ptr<Bitmap>&& bitmap) : bitmap_(move(bitmap)) {} // move すれば OK private: unique_ptr<Bitmap> bitmap_; };
vector<unique_ptr<...>> を使うときは make_move_iterator を活用しよう
unique_ptr の vector などを作っていると、各要素を move するような iterator が欲しいことがあります。
std::make_move_iterator 関数を使うと、まさにそのような iterator を作ってくれます。
またゲームの例ですが、2つの vector があって、片方の vector からもう片方の vector に要素を移動させたい場合を考えます。
// 全 Enemy を格納する vector vector<unique_ptr<Enemy>> all_enemies; // 現在のフレームで生成された Enemy を格納する vector // (現在のフレームが終わるまでは all_enemies には登録されない) vector<unique_ptr<Enemy>> new_enemies; ... // new_enemies に入っている Enemy を全て all_enemies に移動させる。 all_enemies.insert(all_enemies.end(), make_move_iterator(new_enemies.begin()), make_move_iterator(new_enemies.end())); new_enemies.clear();
こんな感じに、make_move_iterator と vector::insert で簡単に要素を移動させることができます。
また、<algorithm> の関数とも組み合わせることもできて便利なので、覚えておくといろんな所で役に立つと思います。
終わりに
ということで、unique_ptr を積極的に活用して delete をソースコードから駆逐しましょう！！
明日は id:nonylene さんの「電電宮にお参りした話」です。お楽しみに！！
追記 (12/10)
id:cos65535 さんの指摘により訂正
「メモリリークの可能性を get を利用している箇所に限定でき」
↓
「use-after-free の可能性を get を利用している箇所に限定でき」
ICFPC 2014 参戦記
ICFP Programming Contest 2014 に @cos65535 さん, @qwerty__ さん, @seikichi さんとチームを組んで参加した。
25日(金)
- 21:00 コンテスト開始。問題を読み始める。
- 21:30 夕食を食べに行く。
- 23:40 seikichi さんが到着。
26日(土)
- 0:00 方針を決める。
- 2:00 GCC の仕様書を読みながら幾つかのプログラムを手コンパイルしてみる。
- 5:00 構文解析まで実装終了。寝る。
- 11:00 起きる。
- 13:00
(+ 1 1)がコンパイルできるようになる。 - 15:00
defineの実装でつまる。- 以下のコードをどうやってコンパイルしたらいいかわからない。
;; カリー化された add (define add (lambda (x) (lambda (y) (+ x y)))) ; 部分適用 (define inc (add 1)) ;; 42 が返る。 (inc 41)
- 以下のコードをどうやってコンパイルしたらいいかわからない。
- 16:00 DUM で予め領域を確保しておき、後から ST でクロージャを入れていけば
defineが実装できることに気付く。- lambda の中で define してもちゃんとレキシカルスコープ的に正しく動作する。
- 17:00
lambdaの実装が完了。 - 17:20
ifの実装が完了。 - 17:30 ラベルをアドレスに変換する部分を実装し、Lisp コンパイラが完成。
- 20:30 seikichi さんが Lisp でそれっぽい AI を実装し、ライトニングラウンドにサブミット。
27日(日)
土曜日の反動でだらだらしてしまった日。
- 0:00 seikichi 先生が Gauche の macroexpand を使ってマクロを展開してからコンパイラに投げるプログラムを書く。
- これにより、
define-macroで簡単に構文を拡張できるようになる。 let,and,begin,condなどのおなじみのマクロが自由に使えるようになる。- さすが Lisp …。
- これにより、
- 1:30 末尾関数呼び出しの最適化を実装。
- 2:00 寝る。
- 10:00 起きる。
- 14:00 コンパイラのデバッグ +
(define (foo x y) ...)のような構文の実装。- かなり普通の Scheme っぽく書けるようになってきた。ぱっと見では見分けがつかない。
- 15:00 コンパイラでやることがなくなってきたので、GCC のシミュレータのデバッグを手伝う。
- 18:00 GCC のシミュレータが動くようになる。
- cos さんが作ったゲームのシミュレータと合わせると、Lambda Man の AI を動作させる環境が完全に揃ったことになる。
- 20:00 再びやることがなくなってたので AI の作成を始める。
- 21:30 BFS をする AI を書いた。が、バグっていて動かない。
- 22:30 Scheme の関数の引数の数を間違っているところがあったのを修正。
- 22:30 ゴーストが弱い場合はマップをクリアできるようになった。
- AI は動くようになったがやけに重い。最初はシミュレータのパフォーマンスが悪いのかと疑ったが、実はそうではなく、BFS の実行に時間がかかりすぎているようだった。
- 32x32 程度のマップを BFS するのに 170 万命令かかっていた。AI の 1 ステップの命令数の上限が 300 万命令程度なので、これはかなり危ない (というか 256x256 のマップが来たら即死する）状況だということを認識する。
- とりあえず、適当に最適化をしてみたが、ほとんど改善しなかったので、qwerty さんにプロファイラの実装をお願いする。
28日(月)
- 2:00 プロファイラのおかげで組み込み関数の呼び出しに時間がかかっていることが判明したので、コンパイラを改造して最適化。
- この改修で 170 万命令 → 140 万命令。
- 次のボトルネックは
vector-refだが、作者が寝てしまっていたので、放置して寝ることにした。
- 8:30 起きる。
- 10:30 seikichi 先生がひたすら関数をマクロでインライン展開する。
- 140 万命令 → 40 万命令。
- 11:00 移動
- 13:30 BFS AI のループ回数に上限をつけた。これで 256x256 のマップでも一応動作するようになった。
- 14:00 近くにゴーストがいるときはゴーストからに逃げるようにした。
- これで結構 AI っぽくなった。
- 14:30 ゴーストを殺せるときは殺しに行くようにした。
- 18:40 方向にスコア付けして一番高いスコアの方向に行くようにした。
- 複数のゴーストに同時に襲われたときに逃げられる確率が上がった。たぶん。
- Lambda-Man Hall of Fame の ghostbusters でランクインした。
- 19:00 cos さんがいつの間にか DFS をするゴーストの AI を書いていた。
- 19:45 フルーツを食べに行くようにした。(by seikichi 先生)
- 20:30 パラメータの調整など
- 20:50 AI 提出！！
まとめ
VirtualBoxにArch Linuxをインストールしたときのメモ
VirtualBoxにInstall media 2012.08.04 を使用してArch Linuxをインストールしたときのメモ．VMのディスクサイズは40GB，メモリは4GB．メモリサイズが1GB以上あるときはswap作らないほうがパフォーマンスがでるらしいのでswapなし．
いつの間にかインストーラが削除されていてArch Linuxのインストールが面倒になってました．
# loadkeys jp106 # parted (parted) unit MiB (parted) mklabel msdos (parted) mkpart primary 1 10241 (parted) mkpart primary 10241 20481 (parted) mkpart primary 20481 20581 (parted) mkpart extended 20581 40959 (parted) mkpart logical 20582 40959 (parted) quit # mkfs -t ext4 /dev/sda1 # mkfs -t reiserfs /dev/sda2 # mkfs -t ext2 /dev/sda3 # mkfs -t ext4 /dev/sda5 # mount -t ext4 /dev/sda1 /mnt # mkdir /mnt/{var,boot,home} # mount -t reiserfs /dev/sda2 /mnt/var # mount -t ext2 /dev/sda3 /mnt/boot # mount -t ext4 /dev/sda5 /mnt/home # vi /etc/pacman.d/mirrorlist 日本のサーバをリストの一番上に持ってくる # pacstrap /mnt base base-devel # pacstrap /mnt grub-bios # genfstab -p /mnt >> /mnt/etc/fstab # arch-chroot /mnt # vi /etc/hostname arch-vm # ln -s /usr/share/zoneinfo/Asia/Tokyo /etc/localtime # vi /etc/locale.conf LANG="en_US.UTF-8" LC_COLLATE="C" LC_TIME="en_DK.UTF-8" # vi /etc/locale.gen 以下の3行のコメントアウトを解除 en_DK.UTF-8 UTF-8 en_US.UTF-8 UTF-8 ja_JP.UTF-8 UTF-8 # locale-gen # mkinitcpio -p linux # mv /boot/grub /boot/grub-legacy # mkdir /backup # dd if=/dev/sda of=/backup/mbr-backup bs=512 count=1 # modprobe dm-mod # grub-install --target=i386-pc --recheck --debug /dev/sda # mkdir -p /boot/grub/locale # cp /usr/share/locale/en\@quot/LC_MESSAGES/grub.mo /boot/grub/locale/en.mo # grub-mkconfig -o /boot/grub/grub.cfg # vi /etc/rc.conf 次の行を追加 KEYMAP=jp106 # passwd rootパスワードを設定 # exit # umount /mnt/{var,boot,home,} # reboot
# pacman -S zsh vim tmux git openssh sudo # pacman -S virtualbox-archlinux-additions # modprobe -a vboxguest vboxsf vboxvideo # vim /etc/modules-load.d/vbox.conf vboxguest vboxsf vboxvideo # pacman -S dbus # vim /etc/rc.conf DAEMONSにdbusを加える # rc.d start dbus # pacman -S xorg # pacman -S gnome # pacman -S gdm # pacman -S xorg-xinit xterm # vim /etc/inittab id3:initdefault: をコメントアウトして id5:initdefault: のコメントアウトを解除 x:5:respawn:/usr/bin/xdm -nodaemon をコメントアウトして x:5:respawn:/usr/bin/gdm -nodaemon のコメントアウトを解除 # vim /etc/skel/.xinitrc VBoxClient-all & exec ck-launch-session gnome-session # adduser 普段使い用ユーザを追加 # visudo 今追加したユーザをsudoerにする
