|
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::containerboost::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/ 直下にあるファイルは
(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 の継承元になっています。 ということで C++11なら
// １回 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 に依存しています.
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（実装面倒なのと、ターゲットであまり使わないし... いえ、時間切れ. 後日に何か)
stringstd::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 実装をベースにした特化版。
詳しいことは他のサイトにあたってください。
scoped_allocator_adaptor
C++11 で増えた アロケータです。
scoped_allocator_adaptor を用いれば、例えば map<string,int> のようなコンテナで、ローカルなアロケータをstringとmapで共通で使えるようにできます。 アロケータをコンテナのメンバーにするので、当然メモリー使用量も増えます（とくに内側のコンテナは数が多くなりやすく）。 ので、コンテナのメンバーにするアロケータはポインタだけにし、実装はさらにその先に用意、といった感じにすることになると思います。 詳しいことは こちら のサイトとかみてもらったほうがいいです。 正直なところ一見ではよくわからず、試してみてなんとなく納得の状態です。 以下、試してみたソース.
#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、単に(コピー)コンストラクタの頻度さげるだけじゃなくて、今回のような場合まさに必須の類でした。
おわりに
遅刻したうえに、
グダグダな内容ですみません。 例に挙げたソースのとおり allocator の記述に関してはすごく楽でした。 が、boost::contaneier を std:: にかえて vc12 でコンパイルすると全く×だったので boost::contaneier に結構依存していると思います。 時間の余裕なくなってるので、たぶん後日 補足修正書くことになりそうですが... おつきあいいただきありがとうございました。
追記: コンパイル試したときのソース |