2016-08-24

Protocol Buffers が本当に遅いのか実際に確かめてみた

C++

Protocol Buffers で検索すると Protocol Buffersは遅いという MessagePack 作者による2008年の記事が未だに上位に来る。一方で、Protocol Buffersは遅いのかという反論記事も見つかる。一体遅いのか速いのかどっちなんだ！！ということで、ベンチマークを取ってみた。

2016年8月現在では、Protocol Buffer の最新バージョンは 3.0.0 であり、MessagePack の C++ バインディングの最新バージョンは 2.0.0 なので、これらのバージョンを使ってベンチマークを取ることにした。

ベンチマーク

元の記事を踏襲して、以下の４つのメッセージを使ってベンチマークを行った。

Test1: 2つの符号無し整数
Test2: 2つの符号付き整数
Test3: 8KBのバイト列
Test4: Test1 + Test2 + Test3

Test1 と Test2 は 2²³ 個、Test3 と Test4 は 2¹⁶ 個のメッセージをシリアライズして所要時間を計測し、再びそれをデシリアライズして所要時間を計測した。外乱の影響を抑えるため、それぞれのワークロードを10回ずつ実行して所要時間の最小値を最終結果とした。

環境:

Linux 4.4.0 on Windows 10 (Hyper-V)
g++ 5.4.0
Intel Core i7-5820K CPU @ 3.30GHz
Memory 4GB

Test1: 2つの符号無し整数

	Serialize	Deserialize	Size
Protobuf	107 msec	145 msec	32 MB
MessagePack	100 msec	1929 msec	24 MB

シリアライズにかかる時間はほとんど同じだったが、MessagePack のデシリアライズが Protobuf の10倍以上遅い。

Test2: 2つの符号付き整数

	Serialize	Deserialize	Size
Protobuf	112 msec	147 msec	32 MB
MessagePack	102 msec	1954 msec	24 MB

Test1 とほぼ同じ結果になった。上で挙げた記事では Protobuf の符号付き整数のシリアライズ後のサイズが非常に大きいと書いてあるが、sint を使えば MessagePack と同じサイズになる。（Protobuf と MessagePack のサイズ差はタグの有無によるもの）

Test3: 8KBのバイト列

	Serialize	Deserialize	Size
Protobuf	162 msec	42 msec	512 MB
MessagePack	121 msec	79 msec	512 MB

バイト列のシリアライズは MessagePack の方が速かった。逆にデシリアライズは Protobuf の方が速い。

Test4: Test1 + Test2 + Test3

	Serialize	Deserialize	Size
Protobuf	165 msec	66 msec	513 MB
MessagePack	123 msec	83 msec	513 MB

Test3 と同じくシリアライズは MessagePack の方が速く、デシリアライズは Protobuf の方が速いという結果になった。

考察

ベンチマークの結果から、バイト列のシリアライズは MessagePack の方が速いが、デシリアライズや整数のシリアライズは Protobuf の方が速いことがわかった。したがって、2016年の現在においては Protobuf は別に遅くないと思ってよさそう。

ベンチマークプログラム

https://gist.github.com/nojima/005cf04bfa35a1fb971adc43b54abbef

2016-08-23

protocol buffer 3 をビルドしてインストール

C++

最近 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 が本当に遅いのか実際に確かめてみた

2016-08-11

ICFPC 2016 に参加しました (チーム: モダン焼きフジ)

C++

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の中で最大の絶望感を味わった。

f:id:nojima718:20160811215546p:plain

とりあえず問題の可視化とスコアリングができないと話にならないので、自分と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さんが手計算で黙々と提出用の問題を作っていた。

f:id:nojima718:20160811221105p:plain

3時ぐらいに寝た。

2日目

起きたら11時だった。 qwertyさんは早起きして問題を作っていた模様。さすがすぎる。

cosさんが任意の直線で紙をfoldする関数を作った。これでようやく我々のチームも長方形以外の形が折れるようになった。

fold関数を使って凸包ソルバを作った。サイズ制限にさえ引っかからなければ、シルエットが凸である形は厳密に折れるようになった。例えば以下の形が折れるようになった。

f:id:nojima718:20160811215749p:plain

その後、Twitter をしているとモダン焼きフジに言及している人を見つけた。

ICFP Programming Contest 参加者、意味もなくモダン焼きの CM 見せられている。
— 宇宙ツイッタラーX (@kenkoooo) 2016年8月7日

seikichiさんがすごい勢いで Jenkins のパイプラインを整備していた。新しい問題が追加されたら自動で既存のソルバ群が実行され最良のスコアが自動で提出される感じのシステムが構築されていた。その裏でqwertyさんが黙々と提出用の問題を作ったり、兜とか風車とかを手で解いたりしてた。

f:id:nojima718:20160811215647p:plain

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三角形など）からちょっとだけ折ったような問題には答えられるようになった。

f:id:nojima718:20160811220444p:plain

また、既存の問題を平行移動したり回転したりしただけの問題が大量に存在しているが、これもそのうちのひとつを解けば、初期値付き全探索ソルバが max_depth=0 で答えを見つけてくれるようになった。

その後は seikichi さんが問題一覧を見れるウェブサービスを作ったり、既に正解した問題を自動計算の対象から外したり、念のため全問題再提出などを行ったりしていた。 qwerty さんと cos さんは黙々と手で問題を解いていた。自分は凸包ソルバや全探索ソルバをちょっと弄って何かできないか試していたが、結局そこから５問しか解けなかった。

まとめ

最終的に 3528 問中 1872 問を解くことができた。 1日目の絶望感からすると結構健闘したような気はする。

2016-06-04

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 にこだわるなら平文じゃないと行けないのかなぁ。

2016-06-03

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 に祈りをささげておかないと。

2014-12-10

unique_ptr で今風な C++ コードを書こう！！

C++ unique_ptr

はじめに

お久しぶりです。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 を利用している箇所に限定でき」

2014-08-03

ICFPC 2014 参戦記

C++

ICFP Programming Contest 2014 に @cos65535 さん, @qwerty__ さん, @seikichi さんとチームを組んで参加した。

レポジトリ: https://bitbucket.org/kmc-ob-icfpc-2014/icfpc2014

25日(金)

21:00　コンテスト開始。問題を読み始める。
- パックマンみたいなゲームの AI を書け、という問題。
- ただしゲームの AI は GCC という謎の LISP マシンの上で動く。（それ専用の機械語が定義されているので、それを使って AI を書かないといけない）
- また、ゴーストの AI も書く必要がある。ゴーストの方は GHC というわりと普通な感じの機械語の上で動くが、メモリが 256 バイトしか使用できず、また、プログラムも 1024 命令しか実行できない。
21:30　夕食を食べに行く。
23:40　seikichi さんが到着。

26日(土)

0:00　方針を決める。
- AI を直接 GCC (与えられた Lisp マシンにおける機械語) で書くのはかなりキツい。高級言語からコンパイルしたい。
- 機械語が Lisp っぽいので Lisp からコンパイルするのが自然なのではないか。Lisp なら構文解析が楽そうだし。ということで、Lisp から GCC へのコンパイラを作ることに。
- また、与えられた機械語で配列（定数時間で任意のインデックスに読み書きもの）が実現できないことが判明する。2分木を使った配列もどきライブラリを作らないといけないという話になる。
- ということで、以下の4つの作業を分担してやることになった。
  - Lisp から GCC へのコンパイラの作成
  - GCC のシミュレータの作成
  - ゲームのシミュレータの作成
  - Lisp 用のライブラリの作成
- 自分はコンパイラを作ることになった。
2:00　GCC の仕様書を読みながら幾つかのプログラムを手コンパイルしてみる。
- DUM と RAP の意味がいまいちわからないが、一応コンパイラはなんとか作れそうな気分になる。
- 実装言語を決める。速度はどうでも良さそうなので Python にした。
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 提出！！

まとめ

最初はどうなることかと思ったが、意外とまともな AI を書けたような気がする。
- やはり高級言語は偉大。
- あと macroexpand 偉い。
プロファイル大事。
コンパイラのエラーチェックを真面目に作っておいたおかげでデバッグコストが結構低かった。
qwerty さんの予約してくれたホテルが快適だった。環境大事。