2011-12-11
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))))
Permalink | コメント(0) | トラックバック(0) | 11:41 
2011-12-07
Boost.Container stable_vector
はじめに
本記事は Boost Advent Calendar 2011 - [PARTAKE] 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 さんの担当です。よろしくお願いします。
Permalink | コメント(0) | トラックバック(0) | 23:45
2011-12-06
C++11時代のthreading
始めに
本記事は C++11 Advent Calendar 2011 : ATND の6日目です。
std::thread
C++11時代のthreadの基本は std::thread です。おもむろに #include <thread> をしましょう。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 <class F, class... Args> thread(F&& f, Args&& args...)の形になっているものがあります。この形のコンストラクタを呼んでthreadを構築すると、別スレッドでf(std::forward<Arg>(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さんです。よろしくお願いします。
Permalink | コメント(0) | トラックバック(1) | 17:22
2011-10-19
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 * [略]
Permalink | コメント(0) | トラックバック(0) | 19:46
2011-10-05
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みたいな抽象的な型が欲しいところではあります。
Permalink | コメント(1) | トラックバック(0) | 17:21
