《 scoped_shared_ptrとstatic_allocatorを使用したstatic_map 》
Counter: 9672,
today: 4,
yesterday: 2
この記事は、C++ Advent Calendar 2013 6日目の記事です。
今年も参加させていただきました。昨年の「ゲームプログラミングの都市伝説」は、1日でブログ開設して10年間のアクセス総数を上回るアクセスをいただきました。ありがとうございました。m(_ _)m 今年も都市伝説シリーズをやとうかと考えましたが、少し趣向をかえてちょっぴり真面目な話題にさせていただきました。 今回紹介するプログラムは、私自身がゲームプログラミングをしていて、「あったらいいな」的なものです。
これらの良く使くコンテナとスマートポインタをアロケータ無しで使えるようにしました。アロケータ無しとは、スタック上に確保されるスコープ内のメモリを使うという事です。(boost::container::static_vectorと同じです) 局所的に、ちょこっとmapを使いたいけど、アロケーターが自由に使えない、new/deleteのコストを抑えたいなどの要求に応えるものです。(こんな要求は組み込み系だけですね) 少し長くなってしまいましたが、お楽しみいただければ幸いです。 ———————————————————— 目次 ———————————————————— 更新履歴 †
shared_ptrの落とし穴 †C++11で標準実装された、参照カウンタ方式によるスマートポインタ 'shared_ptr'。 古来のC++でもboostライブラリにより利用できたので、すっかりおなじみのスマートポインターです。 なにせ、newしてもdeleteしなくて良いというお手軽さ。誰からも参照されなくなると勝手にdeleteされるという、慎ましやかな動作で人気を博しています。 しかし、無闇矢鱈と使うと、参照関係が矛盾してしまったり、解放のタイミングが狂って思わぬトラブルに巻き込まれたりすることもあります。 スマートポインタと云えども、正しい設計の下に使うべきでしょう。 ありがちなトラブルの記事は、shared_ptrを要求する邪悪なマネージャーの顛末 を参照してください。 スコープから抜けたときに、参照が残っていたら教えてくれるshared_ptr †すべてのソースコードが正しい設計とプログラミングを行っているとは限りません。そこで、スコープから抜けたときに、参照が残っていたら通知してくれるshared_ptrを作ってみました。 // std::shared_ptrをラップしたscoped_shared_ptr // スコープから出る時に参照が残っていたら、assertする template <typename T> struct scoped_shared_ptr { shared_ptr<T> value_; template <typename ...Param> scoped_shared_ptr(Param&&... params) : value_(new T(params...)) {} ~scoped_shared_ptr() noexcept { assert(value_.use_count() == 1); // 誰かが握っているので解放できない } template<typename TT> operator shared_ptr<TT> () { return value_; } T& get() { return value_.get(); } }; これは、shared_ptrを要求する関数に、ローカルで作成したクラスオブジェクトを使う時に便利です。 スコープから出るときに、誰かが参照を握っていて解放できないと、assertしてくれます。 使用例 // shared_ptrを要求する、ちょっとイケてないapi struct Fuga {}; void foo(shared_ptr<Fuga> ptr); // コンストラクタで頂いたstringを保持するクラス struct Hoge : Fuga { string& msg_; Hoge(string& msg) : msg_(msg) {}; ~Hoge() { cout << msg; }; // 解放時に頂いた文字列を出力。デバッグ用途でありがちです。 }; // Hogeとfooを使う関数。Hogeはこの関数のスコープ内でのみ使用するつもり。 void sometask() { string msg("hello"); // hogeは、msgの参照を含んでいるので、sometask()から出たら使えない。 scoped_shared_ptr<Hoge> hoge(msg); // shared_ptrを要求するAPIを呼ぶ。weak_ptrにしてくれば良いのに。(;_;) foo(hoge); } // もし、fooがhogeの参照を解放していなかったら、assertする // std::shared_ptrを使用した場合、fooがhogeの参照を解除した時に、hogeのデストラクタが呼ばれるので、 // sometask()終了後の場合は、msgに対してアクセス違反が発生する。 これで安心して使えます。わざわざWrapしたクラスを作らなくても、出口で assert(hoge.use_count() == 1); とすれば良いですが、scoped_shared_ptrを使った方が例外で飛んで行った時にも拾えるので、安心度が高いです。 スコープ内でしか使わないのに、newするのは勿体ない †この簡単なshared_ptrのwrapperで、思わぬ参照が残っていてアクセス違反による暗黒面への突入は防げましたが、スコープ内でしか使わないのにアロケーターをnewで呼び出してヒープを喰うのは気持ちよくありません。スタックメモリを使った方が高速ですし、アロケーターを使う事によるメモリフラグメントの弊害からも守れます。(ゲームプログラミングではメモリの断片化に気を使うのです) shared_ptrは、インスタンスを削除するためのデリーターを指定できるので、この機能を使えば簡単にできそうです。 scoped_shared_ptrを make_sharedを使わない(newしない)様に修正してみました。 // std::shared_ptrをラップしたscoped_shared_ptr。 スコープから出る時に参照が残っていたら、assertする。 template <typename T> struct scoped_shared_ptr { using element_type = T; // std::shared_ptrがクラスオブジェクトを破棄するときに呼ばれる。ここでは何もしない。 struct deleter { void operator() (element_type*) {} }; // 共有するインンスタンスの実体。スコープ内で宣言されたときは、スタック上に生成される。 T body_; // std:shared_ptrの実体。newしたクラスオブジェクトでなく、スタック上に作られたクラスオブジェクトのアドレスを入れる。 std::shared_ptr<T> value_; template <typename ...Param> scoped_shared_ptr(Param&&... params) : body_(params...) , value_(&body_, deleter()) {} // デストラクタでshared_ptrのvalue_は解放されるが、インスタンスはdeleterによって破棄されるので、body_には影響を及ぼさない。 ~scoped_shared_ptr() noexcept { assert(value_.use_count() == 1); } // shared_ptrへのアクセス用 template<typename TT> operator shared_ptr<TT> () { return value_; } }; これで、Hogeが巨大なオブジェクトでもnewされることなく、スタックを食い潰して高速に動いてくれそうです。 しかし、よーく考えると、shared_ptrの内部で、参照カウンター用のクラスオブジェクトをnewして作っています。 手元のclang3.4環境で調べてみたところ、48bytesのメモリを標準アロケーターに要求していました。 ゆるせん! ここまできたら、すべてスタック上のメモリで済ませたくなるのが人情です。 乗りかかった船なので、アロケーターを使わないアロケーターを作る事にしました。 アロケートしないアロケーター、static_allocator †考え方は簡単です。サイズを指定して、そのサイズをスコープ内のローカル変数として確保し、そのメモリ空間から必要なメモリをアサインして渡すアロケーターを作れば良いのです。 試行錯誤すること約1年!(嘘)ホントは1日です。 ようやくできました。以下の様な書式で使えます。 // Static Allocator クラス template<size_t BufferSizeByte, typename ElementType> struct static_allocator; // ソースコードは巻末にあります // 使用例 // int型で16byteのインスタンスを生成 static_allocator<16, int> alc; // 内部で、uint8_t[16]がスタック上に確保されます。 // アロケーターオブジェクトの取得 int* i = alc().allocate(1); // int x1つ分のメモリがallocatorから確保される。 double* d = alc.get<double>().allocate(1); // 違う型のアロケーターとしても使えます。 こんな感じです。さっそく、先ほど作成したscoped_shared_ptrを改造して、static_allocatorを利用するよにしてみました。 // newを一切呼ばずにスコープ内で使えるshared_ptr // インスタンスが破棄されるときに、参照が残っていたらエラーにする template <typename T> struct scoped_shared_ptr { using element_type = T; // インスタンスを解放するためのデリーター。何もしない struct deleter { void operator () (element_type*) {} }; element_type body_; // クラスのインスタンス static_allocator<64,element_type> allocator_; // アロケーター(64bytes確保) std::shared_ptr<element_type> value_; // shared_ptrのインスタンス // コンストラクタ template <typename ...Param> scoped_shared_ptr(Param&&... params) : body_(params...) , value_(&body_, deleter(), allocator_()) // shared_ptrの参照カウンタインスタンスは、allocator()によって確保される。 {} // デストラクタでは、shared_ptrの参照カウントが1(自分自身のみ)でないとエラーにする。 ~scoped_shared_ptr() { assert(value_.use_count() == 1); } // shared_ptr<T>に変換するオペレーター // 派生クラスへの変換を可能にするためテンプレート実装にする template <typename TT> operator std::shared_ptr<TT> () { return value_; } }; 参照カウンタのインスタンス確保用に64bytesを固定で確保しているところがイケてないですが、これでメモリアロケーターを使用しないでshared_ptrが使えるようになりました。 ここで、ふと思い出しました。boost::containerには、static_vectorというvector風なコンテナがあります。vectorとの違いは、メモリをアロケートせずに、ローカル宣言で確保して使う事です。 // boost static_vectorの使用例 boost::container::static_vector<int, 2> ivec; // int x 2 でバッファを確保 ivec.push_back(1); ivec.push_back(2); ivec.push_back(3); // エラー! 予約したサイズを超える事は出来ない つまり、今回作成したstatic_allocatorを使えば、普通のvectorをboost::static_vectorと同様に使えるという事です。 static_vectorはboostライブラリにありますが、残念ながらstatic_mapとか、static_unordered_map等は、boost 1.55の時点ではありません。 ならば、作ってしまおう ということで、作りました。 static_vector と static_string †boostにあるのに、なぜ作る? というツッコミはさておき、おそらく最も簡単なのがvectorでしょう。 しかし、実際に作ってみるとけっこう苦戦します。std:vectorと置き換え可能にするために、継承をするか全機能をwrapするかしなければなりません。 今回はコード量を減らすために安易に継承することにしました。ところが、コンストラクタの初期化順番で問題が発生。 コンストラクタは以下のようになります。 template <typename T> struct static_vector : std:vector<T> { allocator alc_; static_vector() : std::vector<T>(alc.get_allocator()) {} // std::vectorにアロケーターを渡すのが、allocatorのコンストラクタより先に実行される ... この時、allocator alc;のコンストラクタよりも、基底クラスのvector<T>()のコンストラクタが先に呼ばれます。つまり、このコードではvector<T>()に、初期化前のallocatorオブジェクトが渡ってしまいます。 allocatorを外部に持てば解決できますが、それだと使い勝手が今ひとつになってしまいます。 そこで、悪魔に魂を売って、多重継承 することにしました。 template <typename T> struct static_vector : private allocator, std:vector<T> { static_vector() : std::vector<T>(allocator::get_allocator()) {} // std::vectorにアロケーターを渡す ... これで、allocatorが初期化されてから、std::vector<T>のコンストラクタが呼ばれます。なんともキタナイ実装になってしまいましたが、綺麗にするには全機能をwrapするしかないので、今回は手抜きです。 できあがったstatic_vectorのコードです。 template<typename T, size_t Elements> struct static_vector_detail { using allocator = static_allocator<sizeof(T)*Elements, T>; using base = std::vector<T, typename allocator::alctype>; struct type : private allocator, base { type() : base(allocator::get_allocator()) { base::reserve(Elements); } type(const std::vector<T>&& other) : base(other, allocator::get_allocator()) { } type(std::initializer_list<T> init) : base(init, allocator::get_allocator()) { } }; }; template<typename T, size_t Elements> using static_vector = typename static_vector_detail<T,Elements>::type; これで、std::vector<Hoge>としていた箇所を、static_vector<Hoge,確保数> に置き換えて使う事ができるようになりました。 static_stringも思わぬ苦戦 †static_vectorができたから、static_stringは簡単だろうと思ったらサニあらず。std::stringは、確保する文字列のサイズよりも多めにメモリを食うようです。 std::vectorはきっちりエレメントサイズ*Nしかメモリを要求しないのにね。 おまけに、basic_stringの内部で、? hogehoge == Allocator() というコードがあって、アローケーターのデフォルトコンストラクタを使ってオブジェクトを比較しています。これはイケてないですねぇ。ステートフルなので、デフォルトコンストラクタは用意していなかったのですが、思わぬ伏兵にヤラレました。(>_<# static_stringは、こんなコードになりました。 template<typename T, size_t Elements> struct static_string_detail { // basic_stringは、文字列のサイズ + ポインタ3個分のメモリを使うようだ using allocator = static_allocator<sizeof(void*) * 3 + sizeof(T) * Elements, T>; using base = std::basic_string<T, std::char_traits<T>, typename allocator::alctype>; struct type : private allocator, base { type() : base(allocator::get_allocator()) {} type(const T* text) : base(text, allocator::get_allocator()) {} type(const base&& other) : base(other, allocator::get_allocator()) {} type(std::initializer_list<T> init) : base(init, allocator::get_allocator()) {} struct hash { std::size_t operator () ( type const & key ) const { return key.length(); } }; }; }; template<size_t Elements> using static_string = typename static_string_detail<char,Elements>::type; template<size_t Elements> using static_wstring = typename static_string_detail<wchar_t,Elements>::type; これで、std::string str("hoge"); を、static_string<5> str("hoge"); に置き換える事ができました。 小さな文字列をローカルで使う場合、std::stringだとアロケーターが使われるので使用を躊躇することがありましたが、これで心置きなくstringクラスが使えます。 hashというサービスクラスがあります。これは、unordered_mapで使うんです。 これで、static_vectorと、static_stringは出来上がりです。 サンプルコードはこんな感じになります。 // static_vector test static_vector<int,2> vec; vec.push_back(1); vec.push_back(2); vec.push_back(3); // これを実行するとout_of_rangeがthrowされる static_vector<char,4>{1,2,3,4}; // 初期化リストもOK! // static_string test static_string<10> str; str = "123456789"; static_string<10> str2("hogehoge"); static_wstring<10> str4{L"hogehoge!"}; cout << str << str2 << str4 << endl; // std::basic_stringを継承しているので、普通のstringとして使えます いい感じでできてきました。次は、mapとunordered_mapです。 こいつらは、ちょいと手ごわいです。 static_mapとstatic_unordered_map †map系が手ごわいのは、内部でアロケートしまくりだからです。しかも、アロケーターはallocator<value_type>を要求しておきながら、内部でrebindして、違うクラスのアロケーターを捏造しています。 もはや、ステートフルなアロケーターでなければ対応不可能ですが、c++11のmapやunordered_mapは嬉しい事にステートフル(アロケーターに状態を持たせられる)なので、なんとかなりそうです。 static_mapの実装はこんな感じになりました。 template <typename Key, typename T, size_t MaxElements, class Cmp = std::less<Key> > struct static_map_detail { using value_type = typename std::map<Key,T>::value_type; using sizetest = std::tuple<Key,T,static_allocator<0>::alctype,void*,void*>; using allocator = static_allocator<MaxElements * sizeof(sizetest), value_type>; using map_type = std::map<Key, T, Cmp, typename allocator::alctype>; struct type : private allocator, map_type { type(const Cmp& comp = Cmp()) : map_type(comp, allocator::get_allocator()) {} type(std::initializer_list<value_type> init , const Cmp& comp = Cmp()) : map_type(init, comp, allocator::get_allocator()) {} }; }; template <typename Key, typename T, size_t BufSz, class Cmp = std::less<Key> > using static_map = typename static_map_detail<Key,T,BufSz,Cmp>::type; 意外とアッサリできたように見えますが、じつはstatic_allocatorを機能させるのにずいぶん苦労しました。 clangとgccでは動作が違うし、allocator_traitsはちゃんと機能してくれないし。。。ブツブツ。。。 いちおう、エレメントの個数をテンプレートパラメーターで渡すようになっています。いちおうといったのは、実際にmapが確保するメモリサイズは実装依存なので、いちおうなんです。サイズの計算は、4行目の、 using sizetest = std::tuple<Key,T,static_allocator<0>::alctype,void*,void*>; で、tupleクラスをsizeof()したサイズで代用しています。とりあえずですが、clang3.4とgcc4.8.1では上手く動いています。 static_unordered_mapは、実装系によってコンストラクタが違う! †なのです! 正確に言うと、gcc4.8.1には規定のコンストラクタが足りないんです。まったく困りました。 文句を言っても仕方ないので、両方のコンパイラで共通のコンストラクタだけ使用して実装しました。 // static_unordered_mapの実装 template <typename Key, typename T, size_t BufferBytes, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>> struct static_unordered_map_detail { using value_type = typename std::unordered_map<Key,T,Hash,KeyEqual>::value_type; using allocator = static_allocator<BufferBytes, value_type>; using map_type = std::unordered_map<Key,T,Hash,KeyEqual,typename allocator::alctype>; struct type : private allocator, map_type { type() : map_type(0, typename map_type::hasher(), typename map_type::key_equal(), allocator::get_allocator()) {} type(std::initializer_list<value_type> init) : map_type(init, 0, typename map_type::hasher(), typename map_type::key_equal(), allocator::get_allocator()) {} }; }; // std::unordered_mapと置き換え可能にするための定義 template <typename Key, typename T, size_t BufferBytes, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>> using static_unordered_map = typename static_unordered_map_detail<Key,T,BufferBytes,Hash,KeyEqual>::type; なんでも、コンストラクタで初期サイズを整数で渡してやる必要があり、ドキュメントによると実装依存の適当な値となっております。 とりあえずゼロを食わせても動いているので、深く考えずにゼロにしました。 std::unordered_mapは、オレオレクラスを渡す場合、std::hash<> の特殊化をするのですが、複雑なクラスでテンプレートで特殊化するとエラーになってしまいます。 // hash<>の特殊化をstatic_string<N>でやりたい template<size_t N> struct hash<static_string<N>>; // エラー! (;_;) ためしに、問題を切り出してサンプルコードを作ってみました。 http://melpon.org/wandbox/permlink/t8roOParscJnb7c3 どうやら、現状のコンパイラでは無理なようです。残念。 拙出のstatic_stringをハッシュするために、static_stringにhashクラスを実装してあります。 std::unordered_mapは、使用するメモリサイズがテンデバラバラなので、要素の最大数を指定することを諦めて、バッファとして使うメモリサイズ(bytes)を指定するようになっています。 サンプルプログラムはこんな感じになります。 //scoped_map_sample static_map<int, int, 3> hoge = { {1,1} }; hoge.insert(make_pair(1,1.0)); hoge[1] = 2; hoge[0] = 1; hoge[2] = 3; // scoped_unordered_map_sample static_unordered_map<int, double, 1000> fuga{ {1,1.1} }; fuga[2] = 2.1; fuga[0] = 1.1; // static_stringをキーとする場合は、hasherとしてstatic_string<>::hashを与える using string10 = static_string<10>; static_unordered_map<string10, int, 1000, string10::hash> strmap = { {"hoge",5}, {"fuga",4}, {"piyo",3}, {"apoon",2} }; cout << "fuga is " << strmap["fuga"] << endl; static_allocatorの正体 †scoped_shared_ptr, static_vector, static_string, static_map, static_unordred_mapと、アロケータを使わずに使えるようになりました。それもこれも、static_allocatorのお陰です。 書式は以下のようになります。
仕組みを簡単に説明しますと、STDアロケータと互換のアロケータ型を内部で生成し、アロケータ型とアロケータオブジェクトを返すメソッドがあります。 アロケートされるバッファは、static_allocatorクラス内部で uint8_t[]型で定義され、宣言したスコープでメモリが確保されます。 以下がソースコード全部です。イケてない部分もありますが、clang3.4とgcc4.8.1で動作するためのworkaroundもアリアリです。 template <size_t BufferByteSize, typename ElementType=void*> struct static_allocator { template <typename T> struct allocator_detail { uint8_t** buffer_ = nullptr; size_t* size_left_ = nullptr; using value_type = T; using element_type = T; // これらの定義は、gcc4.8.1で必要になる。clang3.4では不要 using pointer = T*; using const_pointer = const T*; using reference = T&; using const_reference = const T&; using size_type = size_t; using difference_type = std::ptrdiff_t; // 確保するメモリーのポインタをサイズを受け取る。 // statefulなallocatorで可能になりました。 allocator_detail(uint8_t** buffer, size_t* buffersize) noexcept : buffer_(buffer), size_left_(buffersize) {} // rebindで異なるクラス向けのallocatorを生成するときに呼ばれる // コンストラクタ。インスタンスを引き継ぐための重要な処理です。 template <class U> allocator_detail(const allocator_detail<U>& other) noexcept : buffer_(other.buffer_), size_left_(other.size_left_) {} // gcc4.8.1のbasic_stringでこれがないとエラーになる allocator_detail() {} // メモリをアロケート pointer allocate(std::size_t n) const { size_t required = n * sizeof(value_type); return allocate_buffer(required); } // メモリを解放 void deallocate(pointer p, std::size_t n) const { size_t deallocsize = n * sizeof(value_type); // 解放するポインターが最後にアロケートしたバッファだった場合、再利用可能にする if (reinterpret_cast<uint8_t*>(p) == *buffer_ - deallocsize) { allocate_buffer(-deallocsize); } } // allocatorを異なる型用に再生成するためのクラス template<class Other> struct rebind : allocator_detail<Other> { typedef allocator_detail<Other> other; }; // clangではdestroyとconstructは記述しなくても実行できるが、gcc4.8.1では無いとダメ static void destroy(pointer& p) { p->~T(); } // clangでは、value_type以外の型で呼ばれるためテンプレート化 template<typename U, typename ...Args> static void construct(U* p, Args&&... args) { ::new (static_cast<void*>(p)) U(args...); } bool operator == (const allocator_detail<T>&) const { return true; } bool operator != (const allocator_detail<T>&) const { return false; } private: // メモリ確保の処理 失敗したらout_of_rangeをthrow pointer allocate_buffer(int32_t size) const { if (size > 0 && *size_left_ < size) { std::cerr << "out of memory capacity:" << *size_left_ << " required:" << size << std::endl; throw std::out_of_range("static_allocator out of capacity"); } void* ptr = *buffer_; *buffer_ += size; *size_left_ -= size; return static_cast<pointer>(ptr); } }; // static_allocatorの実装はここから // ElementTypeのallocatorの型をtypeとして定義 template <typename T> using allocator = allocator_detail<T>; using alctype = allocator<ElementType>; // allocator<ElementType>のインスタンスを得る allocator<ElementType> operator () () { return get<ElementType>(); } allocator<ElementType> get_allocator() { return get<ElementType>(); } // allocator<T>のインスタンスを得る template <typename T> allocator<T> get() { return allocator<T>(&buffer_ptr_, &size_left_); } private: // これらのインスタンスは、スコープ内ならスタック領域に、スコープ外ならグローバル領域に生成される。 // 必要なサイズは、バッファサイズ+ sizeof(*) + sizeof(size_t) uint8_t buffer_[BufferByteSize]; // allocateされるバッファ uint8_t* buffer_ptr_ = buffer_; // 現在のバッファ位置 size_t size_left_ = BufferByteSize; // 確保可能な残りのサイズ }; // アロケーターを比較するための演算子の定義が必要らしい template <size_t B, typename V, typename T, typename U> bool operator == (const typename static_allocator<B,V>::template allocator<T>& , const typename static_allocator<B,V>::template allocator<U>&) { return true; } template <size_t B, typename V, typename T, typename U> bool operator != (const typename static_allocator<B,V>::template allocator<T>& , const typename static_allocator<B,V>::template allocator<U>&) { return false; } まとめ †いそいで作成したので手抜きな部分も多々ありますが、仕事でゲームプログラミングをしているので、実際に使って行こうと思います。 vector,string,map,unordered_mapには、アロケータを指定すれば普通に動くので、既存のコンテナと置き換えるのを諦めれば、特別なクラスを作らないで簡単に実現できます。 たとえば、static_vectorの場合、 // static_allocatorで1000バイト(250エレメント)確保 static_allocator<1000, int> alc; std::vector<int, typename alc::alctype> hoge(alc()); これでOKです。 課題 †
あー、課題だらけですね。精進せねば。 長い間、ご拝読ありがとうございました。 この記事は、C++ Advent Calendar 2013 6日目の記事です。 次の記事は、srz_zumixさんによる7日目の記事になります。よろしくお願いします。 ソースコードは、こちらからダウンロードできます。 |