C++ Advent Calendar 2013 9日目 「Boost.AsioとBoost.Coroutineで脱コールバック」

本記事は C++ Advent Calendar 2013 9日目として書かれました。

はじめに

お久しぶりです。 @fjnli です。
そういえば、去年はC++関係のAdvent Calendarを書いていませんでした。
最近C++をあまり触っておらず、BoostとかC++14とかのフォローがあまりできていませんし、C++力の劣化が著しいと感じる今日この頃です。
C++書きたいです。

さて、本記事では、Boost.AsioとBoost.Coroutineについて取り上げます。AsioとCoroutineを使うと、非同期処理でコールバックを用いることによるプログラムの見通しの悪さを改善できます。サンプルプログラムをベースに、基本的な使い方を紹介していきたいと思います。なお，Boost.AsioとBoost.Coroutineがそれぞれどういう役割をするライブラリなのかについては，長くなってしまいますので本記事では扱いません．ご了承ください．

ボケた事を書いているかもしれませんので，コメントなどありましたら @fjnli までお願いします．Boost.Asioありきで話が進んでおり，他の選択肢との比較が弱い点は今後の課題です．Boost勉強会などで機会があれば，性能について調査し発表するかもしれません．

Version

Boost.CoroutineはBoost 1.53から、Boost.AsioのspawnはBoost 1.54から導入されています。
本記事の範囲ですと、Boost.Coroutineを直接触らないため影響はありませんが、Boost 1.55からCoroutineのインターフェイスがv2となり、以前のものと互換性がなくなっています。注意してください。
また、サンプルプログラムはC++11で書いていますので、C++11対応環境でしかコンパイルできません。

Callback

Asioで非同期処理を行う場合は、非同期処理を登録する際に、処理が完了した後に読んでほしいコールバックを渡します。プログラムの処理を止めないために非同期処理を行うのですから、コールバックを渡すというインターフェイスは自然で理にかなっていると思います。しかしながら、コールバックを用いると、ソースコード上で処理が分散してしまい、プログラムの見通しが悪くなるという問題点があります。

上記の図のような処理があるとします．この処理を，同期的に書くと次の様になります．

A();
read();
B();
write();
C();

C++では，プログラムはソースコードの上から下に向けて実行されますので，直観的でわかりやすい配置です．次にコールバックを用いて非同期処理風に書いてみます．

void after_read() {
  B();
  async_write(after_write);
}

void after_write() {
  C();
}

A();
read_async(after_read);

このようになりました．A, B, Cと順々に処理がしたいだけにもかかわらず，2つの関数が必要となり，処理が分散してしまい，プログラムの可読性が低下しています．では，C++11で導入されたlambda式を使うとどうなるでしょうか．

A();
read_async([&] {
  B();
  write_async([&] {
    C();
  });
});

コールバックを関数として定義するバージョンと比べれば，処理A, B, Cが順に並んでいるため，わかりやすくなりました．しかしながら，lambda式を用いる方式にも問題点があります．同期版のようなフラットな構造ではなく，入れ子な構造となっていることです．例えば，連鎖させたい処理が増えるとソースコードが右に寄ってしまうという問題があります．また，ソースコード上での順番と，実際の実行順番が異なっているという問題があります．サンプルコードに実行される順番をコメントとして追加します．

// (1)
A();
// (2)
read_async([&] {
  // (4)
  B();
  // (5)
  write_async([&] {
    // (7)
    C();
    // (8)
  });
  // (6)
});
// (3)

3, 6番の位置に注目してください．直観に反する実行順序となっています．3, 6番のところに処理を書かなければいい，という考え方も可能ですが，どうしてもこえられない壁があります．それは変数の寿命です．C++にはGCがありませんので，GCがある言語よりもやっかいです．

int x;
// (1)
A();
// (2)
read_async([&] {
  int y;
  // (4)
  B(x); // ここではもうxは死んでいる
  // (5)
  write_async([&] {
    // (7)
    C(y); // ここではもうyは死んでいる
    // (8)
  });
  // (6)
});
// (3)

サンプルコードに変数xとyを追加しました．変数xは4番の位置から利用できませんし，変数yは7番の位置から利用できません．変数xを4番で利用する時には既に3番が実行された後であり，変数xの寿命が切れています．変数を参照するのではなくコピーしたり，すべてをshared_ptrで包んだり，等の解決方法はありますが，どちらもコストがかかることに変りはありません．

最後にCoroutineを使った例を示します．

A();
read_yield();
B();
write_yield();
C();

read_yieldとwrite_yieldは，スレッドをブロックするかわりに，他のcoroutineに処理を譲る(yield)ような実装になっているものとします．Coroutine版は非常にすっきりとしました．Coroutineが銀の弾丸かといわれると，そうではないと思います．プリエンプション式ではないためyieldをしない限り他のCoroutineに処理が移らないという点に注意しなければなりません．readとwriteがCoroutineに対応していなければなりません．うっかり，普通のreadやwriteを呼んでしまうと，Coroutineのメリットがまったくなくなってしまいます．

Boost.AsioでCoroutineの使い方

Boost.AsioでCoroutineを使うには，boost::asio::spawnを使います．spawnに渡したコールバックがCoroutine上で動きます．引数としてyield_contextが渡されますが，これがAsioでCoroutineを使う鍵となるオブジェクトです．

asio::spawn(io_service, [&] (asio::yield_context yield) {
});

そして，Asioの非同期関数のコールバックのかわりに，yield_contextを渡します．

asio::async_write(socket, buf, yield);

async_writeが開始されるとCoroutineがyieldされます．そして，async_writeが完了すると，あたかも同期処理のようにasync_writeから処理が帰ってきます．

処理の最中でエラーが発生すると，boost::system::system_error例外が発生します．例外ではなく，エラーコードを受け取りたい場合は，yield_context::operator []を使います．

boost::system::error_code ec;
asio::async_write(socket, buf), yield[ec]);

このように書くと，async_writeがエラーになった際に，例外が投げられるかわりに，変数ecにエラーコードが格納されます．

サンプルコード

ソケットを使って通信する簡単なプログラムを作成しました．サーバー側でCoroutineによる非同期処理を使用しています．ソースコード全体は Gist にアップロードしています．

サンプルプログラムは，サーバーがクライアントから送られてきた数字を加算していくという内容です．動作例を見て頂いた方がわかりやすいと思います．「>>」で始まる行が入力，「-->」で始まる行がサーバーからのレスポンスを示します．

サーバー側の処理のメインとなるのは，以下のループです (なお，エラー処理はまったくしていません)．

for (;;) {
    auto const n = asio::async_read_until(s, buf, "\n", yield[ec]);
    if (ec) break;
    
    /* (ç•¥) */
    
    acc += value;

    /* (ç•¥) */
    
    asio::async_write(s, asio::buffer(str), yield[ec]);
    if (ec) break;
}

クライアントからデータを受け取り，変数accに足していきます．そして，変数accの値をクライアントに返します (データは文字列としてやり取りをしているため，変換処理が間に入ります)．yield_contextを用いることで，コールバックがまったくないことに注目してください．サーバー側は1スレッドで実行されていますが，Coroutineの力で非同期に実行されているため，複数のクライアントからの接続を同時に受けて処理できますし，変数accはCoroutine毎に分離しているため，値がまざるようなこともありません．

まとめ

同期版のコードを別スレッドで実行すれば，見通しも良く，処理もブロックしないため，万事解決のように見えますし，多くの場合ではそれで十分であると思います．Boost.Coroutineのメリットは，カーネルの介在がないため，作成や破棄のオーバーヘッドが小さいことと，スレッド切り替えが高速であることです．スレッド数を増やすと違いが表われると考えられます．スレッドの性能差だけではなく，Asioのオーバーヘッドもありますし，Asioはタイマーやシグナルといったものも統一的に扱えます．したがって，性能だけでなく使い勝手も含めて比較をしなければいけないところですが，今のところそれらのデータはありません．今後の課題です．

宣伝

プログラミングの魔導書 Vol.3に、10ページほどの短い記事ですが寄稿しています。Vol.3のテーマは「並行、並列、分散」となっており、並行世界の魔物を倒すためにはどうすればいいかについての記事が掲載されています。僕はOpenACCというフレームワークについて書いています。OpenACCはGPUのようなアクセラレータで汎用計算を行うプログラミングを記述するためのフレームワークです。OpenACCを用いると、メモリ管理やデータ転送といった面倒な部分をコンパイラに任せられ、プログラムの生産性があがることに加えて、OpenACCコンパイラを持つ異なるアクセラレータ間でのプログラムの可搬性 (Performance Portability) が向上します。仕様が策定されてからあまり時間がたっておらず、発展途上な仕様であり、機能面や各種コンパイラの対応が弱いといった問題はありますが、今後の発展が期待されるフレームワークです。

もし、平行世界の魔物に興味があるならば、リンク先を見て頂けると幸いです。なお、書籍版は予約のみの限定販売なようですので、お早めに…!

Ariel AdC 11日目 ぷろぐらみんぐ言語ありえる

はじめに

本記事は Ariel Advent Calendar 2011 : ATND の11日目です。12日にオーバーランしてますが、11日目です。ごめんなさい。

ぷろぐらみんぐ言語ありえる

まずは定番のHello worldをありえるで書いてみましょう。

ありえるありありえるありありえるありありえるありありえるあり
ありえるありありえるありありえるありありえるありえるえるあり
ありありありありえるありありえるありありえるありありえるあり
ありえるありありえるありありえるありありえるありありありあり
ありえるありありえるありありえるありありえるありありえるあり
ありえるありありえるありありえるありありえるありありえるあり
ありえるありありありありありえるありありえるありありえるあり
ありえるありありえるありありありえるありありえるありありえる
ありえるえるえるえるえるありありありえるありありありありあり
ありえるありありえるありえるありありありえるありありえるあり
ありえるありありえるありありえるありありえるありありえるあり
えるありありえるありありありえるありありえるありありえるあり
えるありありありありありありえるえるえるありありありえるえる
ありえるえるありえるえるありえるえるありえるえるありえるえる
ありえるえるありえるえるありえるえるありえるえるありえるえる
ありえるえるえるありありありありえるありえるありありえるあり
ありえるありありえるありありえるありありえるありありえるあり
ありえるありえるありありありえるえるありえるえるありえるえる
ありえるえるありえるえるありえるえるありえるえるありえるえる
えるありありありえるありありえるありありえるありえるありあり
ありえるえるありえるえるありえるえるありえるえるありえるえる
ありえるえるえるありありありえるえるありえるえるありえるえる
ありえるえるありえるえるありえるえるありえるえるありえるえる
えるありありありありありありえるありえるありあり

…、やたら長いですね。

ありえるはBrainfuckの方言の1つです。Brainfuckでは><+_.,[]の8記号で表現する命令列を"あり"と"える"だけで表現している為、すごく長くなります。命令マッピングは以下の通りです。

>	ありありあり
	ありありえる
+	ありえるあり
-	ありえるえる
.	えるありあり
,	えるありえる
[	えるえるあり
]	えるえるえる

ありえるはすごく長い言語なので手で書くのは疲れますね(大体左右交互打鍵なので高速には入力できると思いますが)。なので、書く時はBrainfuckから機械的に変換しましょう。ありえるなので当然Emacsです。選択されたregion内をありえるに変換するEmacs Lispを書いたので、らくちんですね。

↓ソースコード

(require 'cl)
(defun bf-to-ariel (start end)
  (interactive "r")
  (loop with src = (buffer-substring-no-properties start end)
        for (c rep) in '((">" "ありありあり")
                         ("<" "ありありえる")
                         ("+" "ありえるあり")
                         ("-" "ありえるえる")
                         ("." "えるありあり")
                         ("," "えるありえる")
                         ("[" "えるえるあり")
                         ("]" "えるえるえる"))
        for re = (regexp-quote c)
        do (setf src (replace-regexp-in-string re rep src))
        finally (save-excursion
                  (goto-char start)
                  (delete-region start end)
                  (insert src))))

Boost.Container stable_vector

はじめに

本記事は partake.in 7日目です。

stable_vector

Boost 1.48からBoost.ContainerというSTL互換のコンテナライブラリが採用されました。基本的にはboost::container::vectorやboost::container::stringといったSTL互換のクラスが提供されていますが、boost::container::stable_vectorのようにSTLにはない独自のコンテナも提供されています。

(以下、stable_vectorと書いた場合はboost::container::stable_vectorを、vectorと書いた時はstd::vectorを示すものとします)

stable_vectorは名の示す通り(要素が)安定したvectorです。例えばvectorを用いて以下の操作を行うことを考えます。

vector<int> v;

v.push_back(1);
auto const it = v.begin();

for (int i = 2; i < 10; ++i)
  v.push_back(i);

// ↓この *it は大丈夫?
std::cout << *it;

最後の行にある *it をしてiteratorを参照しても大丈夫かどうかという問題です。forループで回されているpush_backによってiteratorが無効化(invalidated)されるかが鍵となります。N3290によると、vectorの末尾に要素を追加する際に v.size() + 1 > v.capacity() ならばiteratorが無効化されるとあります。したがって、上の問題の答えは、v.begin()でiteratorを保存した時のv.capacity()が10以上ならば大丈夫、となります。

insertとeraseの場合、話はもう1段階複雑になります。insertの場合、v.size() + (挿入される要素数) > v.capacity()ならばreallocationが発生し、全てのiteratorが無効化されます。reallocationが発生しないならば、挿入点よりも後の要素を指すiteratorのみ無効化されます。eraseの場合は、reallocationは一切起こらないので、削除点以降の要素を指すiteratorが無効化されます。

以上の例のように、vectorは操作によってiteratorが無効化されてしまうため、頻繁に要素を操作する場合、使いにくいと感じる場面があります。そのような時に使うのがstable_vectorです。

vectorは、格納されている要素の連続性を保証しているため、要素が移動した時にiteratorが無効化されやすいという問題がありますが、stable_vectorは、要素が並んでいる領域を連続確保するのではなく、図1のように要素を指すポインタを連続して確保する仕組みを取っています。リストのようですが、要素を指すポインタは連続して確保されているためランダムアクセスが可能で、また、挿入や削除が発生しても格納されている要素は移動しないためiteratorが無効化されることはありません。また、コンテナ中央に要素を挿入削除した場合、vectorではそれ以降の全要素をmoveする必要があるのに対して、stable_vectorではポインタをcopyするだけで済み、低コストとなる場合があります。

図1: stable_vectorの要素の配置の概念図。

一方で、stable_vectorは要素の安定性を重視しているため、各種性能ではvectorやlistに劣る面もあります。要素のアクセスのために一回余計に間接参照をしなくてはいけないため、vectorよりも遅くなりますし、要素本体が連続している保証がないため、キャッシュ効率も悪くなるでしょう。また、vectorよりも多くのメモリを必要とします。boostのドキュメントによると、(c + 1)p + (n + 1)(e + p) 分のメモリが必要であるとされています。ここで、c=capacity(), p=sizeof(T*), n=size(), e=sizeof(T)です。vectorではc×e分の空間しか必要としないのと比べると多いことがわかります。ただし、一部の場合でstable_vectorの方が省メモリである場合もあります(どのような場合にそうなるかはdocumentを読んでください)。c>>nであることが多いことと、要素を格納するための領域が、vectorはc×e分確保しますが、stable_vectorはn×e分しか確保しないためです。(まめにshrink_to_fitするならば、全く勝目がありませんが…)

まとめ

vectorの直接的な代替というよりは、listの代替の位置付けに近いと思います。要素の安定性や中央への挿入削除速度が必要で、かつ、ランダムアクセスが必要な場合にstable_vectorは威力を発揮します。

8日目は id:tt_clown さんの担当です。よろしくお願いします。

C++11時代のthreading

始めに

本記事は C++11 Advent Calendar 2011 : ATND の6日目です。

std::thread

C++11時代のthreadの基本は std::thread です。おもむろに #include をしましょう。std::threadはコンストラクタで渡された関数オブジェクトを別スレッドで実行します。

#include <iostream>
#include <thread>

void f() {
    std::cout << "f()" << std::endl;
}

int main() {
    std::thread thr(f);

    thr.join();

    return 0;
}

このプログラムを実行すると f() と表示されるはずです。コンパイルして実行してみます。

 $ g++ -o thr thr.cpp -std=c++0x
 $ ./thr
f()
 $

確かに f() と表示されました。でもこれだけだと、本当にメインではないスレッドで実行されているかわかりませんね。そんな時はstd::this_thread::get_id()を使います。

#include <iostream>
#include <thread>

void f() {
    std::cout << '[' << std::this_thread::get_id() << "] f()" << std::endl;
}

int main() {
    std::cout << '[' << std::this_thread::get_id() << "] main()" << std::endl;
    std::thread thr(f);

    thr.join();

    return 0;
}

実行します。

 $ g++ -o thr thr.cpp -std=c++0x
 $ ./thr
[140006855132992] main()
[140006838933248] f()
 $

mainが実行された時と、fが実行された時のthread idが異なっていて、実行スレッドが異なっていることがわかります。

std::threadのコンストラクタは、template thread(F&& f, Args&& args...)の形になっているものがあります。この形のコンストラクタを呼んでthreadを構築すると、別スレッドでf(std::forward(args)...)が実行されます。

#include <iostream>
#include <thread>

void f(int a, int b) {
    std::cout << a << '/' << b << std::endl;
}

int main() {
    std::thread thr(f, 1, 2);
    thr.join();
    return 0;
}

このプログラムを実行すると

 $ ./thr
1/2
 $

と表示されます。

std::threadに渡される関数オブジェクト(例の中ではf)の返り値型はvoidである必要はありません。intとかstd::stringとかでも大丈夫ですが、std::threadは返り値を捨てるだけであり、呼び出し元のスレッドと受け渡しするシステムはありません。もし、そのような機能が必要な場合はstd::futureなどを使用します。グローバル変数でも解決できますが、あまりスマートではないですね。

C++では普段あまり意識する必要があったりなかったりしますが、C++には例外という切っても切り離せない…とは言い切れないシステムがあります。スレッドを扱う場合、そのスレッドで例外が投げられた時にどういう挙動になるかを把握しておくことは重要です。

ということで例外を投げてみましょう。

#include <iostream>
#include <thread>

void f() {
    throw 1;
}

int main() {
    std::thread thr(f);
    thr.join();
    return 0;
}

実行します。

 $ g++ -o thr thr.cpp -std=c++0x
 $ ./thr
terminate called after throwing an instance of 'int'
Aborted
 $

はい。落ちました。例外が投げられて、それが捕獲されなかった場合、std::terminateが呼ばれるのがC++11の仕様です (N3290: 30.3.1.2.4)。結構困りますね。一々try catchを書くのは面倒ですし、親スレッド側で例外を処理したい場合もあります。C++11では例外をスレッド間でやりとりするための機構として、std::exception_ptrが用意されています。が、一々そんなものを使うのはめんどくさいですね。すなわち、std::threadを直接使うのは非常にめんどくさいので、避けましょうということです。かわりにstd::asyncやstd::packaged_taskを使います。

#include <iostream>
#include <thread>
#include <future>

int f(int x, int y) {
    if (x < 0 || y < 0) throw "f";
    return 100;
}

int main() {
    std::future<int> f1 = std::async(std::launch::async, f, 100, 200);
    std::cout << f1.get() << std::endl;

    std::future<int> f2 = std::async(std::launch::async, f, 100, -200);
    try {
        std::cout << f2.get() << std::endl;
    } catch (...) {
        std::cout << "catch!!!" << std::endl;
    }
    return 0;
}

このプログラムを実行すると以下の様になります。

 $ g++ -o thr thr.cpp -std=c++0x
 $ ./thr
100
catch!!!
 $

std::asyncを使うと、ライブラリが勝手にいろいろ面倒を見てくれます。std::asyncの返り値型はstd::futureです。細かい挙動は省略しますが、getすると計算結果が帰ってきます。fの中で例外が飛んだ時は、std::future::getでgetしたスレッド側に例外が移譲されます (main後半のように)。なお、std::asyncの実行ポリシーはimplementation definedなので、スレッドを使って計算したい場合はstd::launch::asyncを明示的に渡します。

まとめ

std::threadは非常にprimitiveなので、可能ならば別の高レベルな仕組みを使った方がいいです。

C++11 advent calendar 7日目はid:kikairoyaさんです。よろしくお願いします。

libclangでMPIの関数を抽出してみた

手作業だとめんどくさいし、間違えそうだということでlibclangを使ってみました。

こんなファイルstub.cを用意して、

#include <mpi.h>

mpi_extractorに食わせると、MPI関数の名前、返り値の型、引数の型がCSVで出力されます。

$ ./mpi_extractor stub.c
MPI_Abort,int,MPI_Comm,int
MPI_Accumulate,int,void *,int,MPI_Datatype,int,MPI_Aint,int,MPI_Datatype,MPI_Op,MPI_Win
MPI_Add_error_class,int,int *
MPI_Add_error_code,int,int,int *
MPI_Add_error_string,int,int,char *
[ç•¥]

Asioでepollを使うのをやめる

Linux環境下でのBoost.Asioは、標準でepoll_reactorを使用します(AsioではIO多重化を行うクラスをreactorと呼んでいます)。しかしながら、epollは登録できるfile descriptorの種類がselectよりも狭いという仕様上の問題があります。例えばファイル(regular file)を指すfile descriptorは登録できません。たぶん、ファイルに対してごにょごにょしたい場合は、カーネルが提供しているaioシステムコールを使えってことなんでしょう。

さて、epollがregular fileを指すfile descriptorを扱えないため、asio::posix::stream_descriptorがregular fileを扱えないという問題が発生します。この問題を簡単に解決する方法は、性能を犠牲にして、epollではなくselectを使うようにすることです。BOOST_ASIO_DISABLE_EPOLL をdefineするとepollの使用を拒否できます。詳しくは boost/asio/detail/config.hpp を読んでください。

windows向けだと、id:faith_and_brave:20110322 にあるようにwindows::stream_handleを使わないといけなかったり、非常にめんどくさいので、asio::file_streamみたいな抽象的な型が欲しいところではあります。

夏休み終ったけどbjam始めてみます 4日目

夏休みはもう終ってしまいましたが、bjamはたまーに使っています。
C++のソースコードをコンパイルするだけなら、bjamは最短なのではないでしょうか。
…と思いましたがmake最短ですね…。

boost使いたいです

3日目に書いた方法でboostを使ってもいいのですが、せっかくのbjamなので、bjamっぽく使いましょう。今回の方法はboostのソースツリーを持って必要に応じてコンパイルする設定のため、ディスク容量的には不利ですが、とを指定すれば、コンパイル済みのライブラリも使えるので、こちらの方がスマートなのではないでしょうか。

まず、boostのソースがある位置をbjamに教えてあげないといけません。方法は2つあります。

1つ目は環境変数BOOST_ROOTを使う方法です。

$ export BOOST_ROOT=${HOME}/boost_1_47_0

もう1つはuser-config.jamに設定を書く方法です。

$ cat ~/user-config.jam
using boost : 1.47 : <root>/home/fujita/boost_1_47_0

そして、プロジェクトのJamrootファイルに以下の文を書きます。

import boost ;
boost.use-project ;

boost.use-projectにはバージョン指定も可能です。

boost.use-project 1.47 ;

これで、/boost//regexや/boost//filesystemといったライブラリが定義されます。ヘッダのみでいい場合は/boost//headersをrequirementsに追加します。例えば、a.cppをfilesystem付きでコンパイルしたい場合は、

exe a : a.cpp /boost/headers /boost//filesystem ;

とします。