2012-12-14[金] boost::container で俺俺アロケータ

これは C++ Advent Calender 2012 14日目 の記事です。

C++11やboostをまだロクに使っていない人間なので、雰囲気を掴むために boost1.52 の boost/container フォルダを一寸覗いてみました。 new,delete等メモリーアロケート のコストを無視できないターゲットを扱うことも多いので、俺俺アロケータを渡してみたいってのもあり。 C++11仕様でアロケータが今までより楽にかけるようだし、scoped_allocator_adaptor も何か使えそうですし.

※いまだvc9をおもに使ってるので(vc12も使いますが)、C++11の記述はさけてます.

boost::container

boost::container ですが、C++11で仕様拡張された vector,list,map,set,deque 等のコンテナの機能を C++03コンパイラでもなるべく使えるようにした互換コンテナ群+α です。 C++11 で増えたコンテナ(array, unorderd_map 等)については すでにboostに実装があるためか(?) boost::container には含まれていません。詳しいことは こちら とか他のサイトにあたってください。

将来的にどんどん変わっていく部分も多々あるでしょうが、とりあえず boost_1_52_0/boost/container/ フォルダで wc してみると、41ファイル 27613 行(detailフォルダ含)。 実際には container 外のboostヘッダをいろいろinclude しているので実質はもっと大きいです(map,set(tree)等は boost::intrusive のものを使っているようです)。 (ちなみに boost_1_52_0/boost/ では 8779ファイル 約172万行、やっぱりデカいです)

boost/container/ 直下にあるファイルは

allocator_traits.hpp std::allocator_traits 互換
string.hppstd::string 互換
vector.hppstd::vector 互換
deque.hppstd::deque 互換
list.hppstd::list 互換
map.hppstd::map・std::multimap 互換
set.hppstd::set・std::multiset 互換
scoped_allocator.hppstd::scoped_allocator 互換
scoped_allocator_fwd.hpp(scoped_allocator の最小宣言)
slist.hpp古のslist の拡張版
stable_vector.hpp vector<T*>で要素を別途アロケートのvector
flat_map.hppvector< pair<KEY,VALUE> > 風実装で mapインターフェースを持つコンテナ
flat_set.hpp(上記の std::set 風実装)
container_fwd.hppboost::container
detail/ 詳細実装のファイル群

(ptr_container のような)既存のstdコンテナを継承して拡張(メンバー関数追加)とかではないです。 (といっても boost::intrusive 等 boost内の他のライブラリはよく使われています)

次に、いくつかコンテナについて。

vector

ざっくりメンバー変数の部分だけ抜き出してみて、

template <class Allocator>
class vector_alloc_holder {
    struct members_holder : public Allocator {
        pointer     m_start;
        size_type   m_size;
        size_type   m_capacity;
    }
}
template <class T, class Allocator>
class vector : vector_alloc_holder<Allocator>;

(SGI版派生等)他の実装だと全てポインタで管理していることが多いですが、この実装はsize,capacityを個数で持っています(個人的にはデバッグ時にメンバー変数で見れるので好み)。

Allocatorは、(非static)メンバー変数がない場合に実質 0バイトになるよう struct の継承元になっています。
stlの実装では 多少の差違はあれ Allocator は (非static)メンバー変数になっていることが多いですが、 C++03 の場合 static メンバー変数で持つのも有りだったようで、実際そうなっていたコンパイラもありました。
C++11 では scoped_allocator_adaptor のこともあるし Allocator は (非static)メンバー変数必須のようです。

ということで C++11なら

// 1回 N個 アロケートするだけの Allocator
template<typename T, unsigned N>
class SampleAllocator1 {
public:
   typedef T value_type;
   SampleAllocator1() { }
   T* allocate(unsigned n) { assert(n == N); return reinterpret_cast<T*>(buf_); }
   void  deallocate(T*, unsigned) { }
   bool operator == (SampleAllocator1 const & ) const { return false; }
   bool operator != (SampleAllocator1 const & ) const { return true; }
private:
   typedef double buf_t;
   buf_t   buf_[(N*sizeof(T)+sizeof(buf_t)-1) / sizeof(buf_t)];
};
//typedef std::vector<int, SampleAllocator1<int,1024> >  Int1024Vector;
typedef boost::container::vector<int, SampleAllocator1<int,1024> >  Int1024Vector;
Int1024Vector  g_intVec;

みたいな真似をしても大丈夫のはず...と書いたけど上記はたぶん boost::container に依存しています.
(ターゲット環境で mallocの準備前に(固定サイズの)コンテナを使いたい...こともあった)

list

実装は boost::intrusive の定義も多く面倒なので、かなり端折って (boost::container としてでなく) ありそうな list 実装のメンバーの雰囲気として以下 (すみません、後付で boost::container からめたはいいけど対処しきれず...)

class Node_Base {
    Node_Base* next_;
    Node_Base* prev_;
};
template<typename T>
class Node : Node_Base {
    T     value_;
};
template<typename T, class A >
class List : A {
    ListNode_Base root_;
    size_t        size_;
};

かなりいい加減ですが、メモリーの雰囲気がわかれば...

map,multimap, set, multiset

map,set は たいてい赤黒木 実装のようで、boost::container では boost::intrusive を使ってるようです。
で、これも メモリーの雰囲気だけ...

class Node_Base {
    Node_Base* left_;
    Node_Base* right_;
    Node_Base* parent_;
    bool       balance_;
};
template<typename T>
class Node : Node_Base {
    T     value_;
};
template<typename T >
class Tree : A {
    Node_Base root_;
    size_t    size_;
};


List や Map は 渡された アロケータをそのまま使うのではなくて、allocator のメンバーの

template <class U> struct rebind { typedef allocator<U> other; };

を用いて、 T でなく Node<T> の allocator を使っています。 また、allocator への要求は通常 1個単位になると思います。

ということで、list や map の俺俺アロケータとしては、ノードサイズ固定のメモリーをプールしておく、というのが考えられます。

template<unsigned B, unsigned N>
class SampleAlloc2 {
public:
    SampleAlloc2() {
        for (unsigned i = 0; i < N-1; ++i)
            buf_[i].link = &buf_[i+1];
        buf_[N-1].link = NULL;
        root_ = &buf_[0];
    }
    void* allocate(unsigned n) {
        assert(n == 1 && root_);
        Link*   p = root_;
        root_ = p->link;
        return p;
    }
    void  deallocate(void* t, unsigned n) {
        if (t) {
            assert(n == 1);
            Link*   p = reinterpret_cast<Link*>(t);
            p->link   = root_;
            root_     = p;
        }
    }
private:
    union Link {
        Link*   link;
        char    b[B];
    };
private:
    Link*       root_;
    Link        buf_[N];
};
enum { ELM_SIZE = 32 }; // コンテナのノードを含んだ要素のバイト数.
enum { MAX_SIZE = 16 };
template<typename T>
class SampleAllocator2 : public SampleAlloc2<ELM_SIZE,MAX_SIZE> {
    typedef SampleAlloc2<ELM_SIZE,MAX_SIZE> base_type;
public:
    typedef T value_type;
    SampleAllocator2() {BOOST_STATIC_ASSERT(sizeof(T) <= ELM_SIZE);}
    T* allocate(unsigned n) { return reinterpret_cast<T*>(base_type::allocate(n)); }
    void  deallocate(T* t, unsigned n) { base_type::deallocate(t, n); }
    bool operator == (SampleAllocator2 const & ) const { return false; }
    bool operator != (SampleAllocator2 const & ) const { return true; }
};
// list
typedef SampleAllocator2<int>  IntAllocator;
typedef boost::container::list<int, IntAllocator > IntList;
// map
struct cstr_less {
    bool operator()(const char* l, const char* r) const { return strcmp(l,r) < 0; }
};
typedef std::pair<char const* const,int> smpPair_t;
typedef SampleAllocator2<smpPair_t> SmpPairAllocator;
typedef boost::container::map<const char*, int, cstr_less, SmpPairAllocator >	StrIntMap;

※ 要素(ノード)サイズ(ELM_SIZE)が直うちでみっともないですが、とりあえずは。

deque

(実装面倒なのと、ターゲットであまり使わないし... いえ、時間切れ. 後日に何か)

string

std::stringは(C++03では)ライブラリごとに結構実装がばらけています(EffectiveSTL に載ってるのとか)。 c++11 で縛りがきつくなったので多少にかよってくるかもですが、それでもいろいろできそうです。

最小限としては vector と同様の内容になりそうですが... boost::container::string から端折って抜き出してみると

 struct long_t {
    size_type      is_short  : 1;
    size_type      length    : (sizeof(size_type)*CHAR_BIT - 1);
    size_type      storage;
    pointer        start;
 };
 struct short_header {
    unsigned char  is_short  : 1;
    unsigned char  length    : (CHAR_BIT - 1);
 };
 struct short_t {
    short_header   h;
    value_type     data[UnalignedFinalInternalBufferChars]; 
                   // UnalignedFinalInternalBufferChars ≒ (sizeof(long_t)-sizeof(short_header))/sizeof(value_type)
 };
 union repr_t {
    long_raw_t  r;
    short_t     s;
 };

long_t は長い文字列でアロケータを用いる場合で、sizeof(long_t)-α 以内におさまる短い場合は short_t のようにして領域をバッファとして使い動的確保せずにすませる、という工夫がされています。 64bit CPUだと、vector互換でもsizeof(ポインタ)*3=24bytesになりますし、結構ありがたい実装です。 (最近作ってた 俺俺string がまさにこのタイプだった... もうboostのでよく)

※ メモ: ビットフィールドは エンディアン問わず、先に書かれたものが低アドレスに配置される.

stable_vector, flat_map, flat_set

stl コンテナの代用品でなく、vector 実装をベースにした特化版。
stable_vector は、vector<T*> と要素を別途アロケートしたもの。(boost::ptr_vectorの類似品?)
flat_map,flat_set は、vector<T> (mapはT=pair<KEY,VALUE>) にソート状態で登録して、インターフェースがmapやsetになったもの。
各自で俺俺コンテナを作ってそうな類なので(ええ作ってました)、boost にあると楽になりそうです。 (できれば stable_vector を flat_map 化したものもあればうれしいところ)

詳しいことは他のサイトにあたってください。

scoped_allocator_adaptor

C++11 で増えた アロケータです。

scoped_allocator_adaptor を用いれば、例えば map<string,int> のようなコンテナで、ローカルなアロケータをstringとmapで共通で使えるようにできます。
※ 内側のコンテナ(この場合 string)のコンストラクタとして、デフォルトコンストラクタでなくアロケータを引数にとるコンストラクタが使われるようになります。

アロケータをコンテナのメンバーにするので、当然メモリー使用量も増えます(とくに内側のコンテナは数が多くなりやすく)。 ので、コンテナのメンバーにするアロケータはポインタだけにし、実装はさらにその先に用意、といった感じにすることになると思います。

詳しいことは こちら のサイトとかみてもらったほうがいいです。

正直なところ一見ではよくわからず、試してみてなんとなく納得の状態です。

以下、試してみたソース.

#include <stdio.h>
#include <boost/container/map.hpp>
#include <boost/container/string.hpp>
#include <boost/container/scoped_allocator.hpp>
#include <boost/foreach.hpp>

// mapで解放しないこと前提に、スタックで解放無視の簡易アロケータ.
template<unsigned N>
class SampleAlloc3 {
public:
    SampleAlloc3() : size_(0) { }
    void* allocate(unsigned n) {
        assert(size_+n <= N);
        void* p = ptr(size_);
        size_ += n;
        return p;
    }
    void  deallocate(void*, unsigned) { /*dummy*/ }
private:
    typedef double buf_t;
    void*       ptr(unsigned n=0) { return (char*)buf_ + ((n + sizeof(buf_t)-1) & ~(sizeof(buf_t)-1)); }
private:
    unsigned    size_;
    buf_t       buf_[N / sizeof(buf_t)];
};

// map<string,int> のメモリー
template<unsigned SAMPLE_ALLOC3_SIZE>
class Hoge {
public:
    Hoge() : strIntMap_(std::less<String>(), MapAllocator(StrIntPairAlloc(&smpAlc3_))) {}
    void insert(const char* name, int val) {
        //strIntMap_[String(name, &smpAlc3_)] = val;
        strIntMap_.emplace( name, val );
    }
    void printAll() {
        BOOST_FOREACH(StrIntPair p , strIntMap_)
            printf("%s = %d\n", p.first.c_str(), p.second);
    }
private:
    typedef SampleAlloc3<SAMPLE_ALLOC3_SIZE> Alloc;
    template<typename T>
    class SampleAllocator3 {
    public:
        typedef T value_type;
        // SampleAllocator3() : alc_(0) {}  // デフォルトコンストラクタは用意しないほうが安全.
        SampleAllocator3(Alloc* alc) : alc_(alc) { }
        template<typename U> SampleAllocator3(SampleAllocator3<U> const& r) : alc_(r.detail_get_ptr()) { }
        T* allocate(unsigned n) { return reinterpret_cast<T*>(alc_->allocate(n*sizeof(T))); }
        void  deallocate(T* p, unsigned n) { alc_->deallocate(p,n*sizeof(T)); }
        bool operator == (SampleAllocator3 const & ) const { return false; }
        bool operator != (SampleAllocator3 const & ) const { return true; }
        Alloc* detail_get_ptr() const { return alc_; }
    private:
        Alloc*      alc_;
    };
    typedef boost::container::basic_string<char, std::char_traits<char>, SampleAllocator3<char> >   String;
    typedef std::pair<const String, int>    StrIntPair;
    typedef SampleAllocator3<StrIntPair>    StrIntPairAlloc;
    typedef boost::container::scoped_allocator_adaptor< StrIntPairAlloc >           MapAllocator;
    typedef boost::container::map<String, int, std::less<String>, MapAllocator >    StrIntMap;
private:
    SampleAlloc3<SAMPLE_ALLOC3_SIZE>    smpAlc3_;
    StrIntMap                           strIntMap_;
};

void sample3()
{
    Hoge<1024>  hoge;
    hoge.insert("xyz", 1);
    hoge.insert("abcdefghijklmnopqrstuvwxyz", 2);
    hoge.insert("1234567890", 3);
    hoge.printAll();
}

emplace, emplace_back、単に(コピー)コンストラクタの頻度さげるだけじゃなくて、今回のような場合まさに必須の類でした。
共通で使うアロケータ(SampleAllocator3)には デフォルトコンストラクタをつけちゃダメ、というのを実感。
( デフォルトコンストラクタつけてると insertや push_back 使ってもコンパイル通るため... ハマりました)

おわりに

遅刻したうえに、 グダグダな内容ですみません。
(当初の目論見からずれまくり...そもそも deque 調べるため boost::container 見始めたはずが)

例に挙げたソースのとおり allocator の記述に関してはすごく楽でした。 が、boost::contaneier を std:: にかえて vc12 でコンパイルすると全く×だったので boost::contaneier に結構依存していると思います。

時間の余裕なくなってるので、たぶん後日 補足修正書くことになりそうですが...

おつきあいいただきありがとうございました。


15日目は、@yohhoy さんです。


追記: コンパイル試したときのソース
あなたの名前: