Hatena::ブログ(Diary)

fjnlの生存記録のような何か このページをアンテナに追加 RSSフィード

2011-12-07

Boost.Container stable_vector

はじめに

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

stable_vector

Boost 1.48からBoost.ContainerというSTL互換のコンテナライブラリが採用されました。基本的にはboost::container::vectorboost::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するだけで済み、低コストとなる場合があります。

f:id:fjnl:20111207232436p:image

図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 さんの担当です。よろしくお願いします。

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みたいな抽象的な型が欲しいところではあります。

2011-09-29

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

夏休みはもう終ってしまいましたが、bjamはたまーに使っています。

C++のソースコードをコンパイルするだけなら、bjamは最短なのではないでしょうか。

…と思いましたがmake最短ですね…。

boost使いたいです

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

まず、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 ;

とします。

2011-07-31

夏休みなのでbjam始めてみます 3日目

0xの使い方やライブラリ回りは、プロのbjammerことid:Flast先生に教えてもらいました。

複数のソースから1つの実行ファイルを作りたい

単に依存関係を並べればいいようです。

Jamroot:

exe a : a.cpp b.cpp ;
$ $BOOST_ROOT/bjam release
...found 13 targets...
...updating 6 targets...
common.mkdir bin
common.mkdir bin/darwin-4.6
common.mkdir bin/darwin-4.6/release
darwin.compile.c++ bin/darwin-4.6/release/a.o
darwin.compile.c++ bin/darwin-4.6/release/b.o
darwin.link bin/darwin-4.6/release/a
...updated 6 targets...

システムに入ってるライブラリを使いたい

requirementsの所に<name>で名前を教えてあげればいいようです。ただし、先頭のlibはいりません(libz→z、libpng→png)。システム標準でない場所にライブラリが入っている場合は<search>で場所を教えてあげます。

Jamroot:

lib z : : <name>z <search>/opt/local/lib : : <include>/opt/local/include ;
exe a : a.cpp z ;

a.cpp

#include <iostream>
#include <zlib.h>

int main() { std::cout << zlibVersion() << '\n'; return 0; }
$ $BOOST_ROOT/bjam release
...found 11 targets...
...updating 5 targets...
common.mkdir bin
common.mkdir bin/darwin-4.6
common.mkdir bin/darwin-4.6/release
darwin.compile.c++ bin/darwin-4.6/release/a.o
darwin.link bin/darwin-4.6/release/a
...updated 5 targets...
$ ./bin/darwin-4.6/release/a
1.2.5

C++0xを使いたい

projectのrequirementsでオプションを追加してあげればいいようです。

Jamroot:

project : requirements <cxxflags>-std=c++0x ;
exe a : a.cpp ;

2011-07-30

夏休みなのでbjam始めてみます 2日目

1日目と同日公開ですが、2日目です。はい。デフォルトのvariantがdebugなので、ぼーっとしてると遅いバイナリを作ってしまいそうで怖いですね。3日目に続くかは謎です。

variantオプション

bjamはデフォルトでdebugモードでビルドされます。ビルドモードを変更するにはbjamの引数にvariantオプションを渡すか、単にdebugやreleaseと引数に加えます。なお、コンパイルオプションその他を一杯表示させるには、 -d+2 オプションを渡します。逆に、出力を最小限にしたい場合は-d0を渡します。

Debug:

$ $BOOST_ROOT/bjam -d+2 debug
[]
"g++-mp-4.6"  -ftemplate-depth-128 -O0 -fno-inline -Wall -g -dynamic -gdwarf-2 -fexceptions -fPIC     -c -o "bin/darwin-4.6/debug/a.o" "a.cpp"
[]

Release:

$ $BOOST_ROOT/bjam -d+2 variant=release
[]
"g++-mp-4.6"  -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -dynamic -gdwarf-2 -fexceptions -fPIC  -DNDEBUG   -c -o "bin/darwin-4.6/release/a.o" "a.cpp"
[]

なお、variantは複数指定できるので、releaseとdebugを同時にビルドできます。

Debug+Release:

$ $BOOST_ROOT/bjam -d+2 debug release
[]
"g++-mp-4.6"  -ftemplate-depth-128 -O0 -fno-inline -Wall -g -dynamic -gdwarf-2 -fexceptions -fPIC     -c -o "bin/darwin-4.6/debug/a.o" "a.cpp"
[]
"g++-mp-4.6"  -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -dynamic -gdwarf-2 -fexceptions -fPIC  -DNDEBUG   -c -o "bin/darwin-4.6/release/a.o" "a.cpp"
[]

-j オプション

GNU Makeと同様に-jオプションを指定すると、平行ビルドで実行されます。多数のコアがあるマシンで実行する場合は、ビルド時間が短縮される可能性があります。

boost本体レベルの規模となると物理8コアのマシンで、ビルド時間が-jなしで604秒、-j8付きで93.8秒となり、8倍とはいきませんが、6倍程度高速化されています。

夏休みなのでbjam始めてみます 1日目

bjamが欲しいので、まずはboostをダウンロードして展開し、bjamをビルドします。そして、boostを展開したディレクトリをBOOST_ROOT環境変数に定義しておきます。BOOT_ROOTはbjamの動作上も必要です。

$ export BOOST_ROOT=/path/to/boost
$ cd $BOOST_ROOT
$ ./bootstrap

boost 1.47.0からbootstrapで作成されるbjamの実行ファイル名が、"bjam"と"b2"の2つになっています。1.47の段階ではこれらのファイルの内容は同一で単なるコピーのようですが、以降はbjamで統一します。

Mac環境で、Appleによって提供されていないgccを使う場合は、以下の修正を行う必要があります。(例えばMacports) -no-cpp-precompというオプションはAppleのgccにしか存在しないためです。(本当にこの修正で大丈夫なのか、よくわかんないですけど)

--- $BOOST_ROOT/tools/build/v2/tools/darwin.jam.org	2011-07-30 19:12:42.000000000 +0900
+++ $BOOST_ROOT/tools/build/v2/tools/darwin.jam	2011-07-30 19:12:49.000000000 +0900
@@ -498,7 +498,7 @@
 flags darwin.compile OPTIONS <link>shared : -dynamic ;
 
 # Misc options.
-flags darwin.compile OPTIONS : -no-cpp-precomp -gdwarf-2 -fexceptions ;
+flags darwin.compile OPTIONS : -gdwarf-2 -fexceptions ;
 #~ flags darwin.link OPTIONS : -fexceptions ;
 
 # Add the framework names to use.

さて、a.cppとJamrootファイルを用意して適当にコンパイルしてみます。

a.cpp:

#include <iostream>
int main() { std::cout << "Hello bjam\n"; return 0; }

Jamroot:

exe a : a.cpp ;
$ ls
Jamroot a.cpp
$ $BOOST_ROOT/bjam
...found 9 targets...
...updating 4 targets...
common.mkdir bin/darwin-4.6
common.mkdir bin/darwin-4.6/debug
darwin.compile.c++ bin/darwin-4.6/debug/a.o
darwin.link bin/darwin-4.6/debug/a
...updated 4 targets...
$ ./bin/darwin-4.6/debug/a
Hello bjam

あ、2日目に続くかは謎です。