第100章 STL コンテナ側のメモリー割り当て要件

戻る		次へ

STL コンテナの要件って言っても、実際は仕様的なものより、コンテナのデータ構造やアルゴリズムを知るだけで十分です。

例えば以下のような点さえ掴んでおけば、アロケーターが使うメモリー消費量を把握しやすくなります。

std::vector はサイズが足りない場合は reserve 関数をコールする
std::vector は reserve() で多めに確保しないと、コンテナサイズの拡張を頻繁に行う
std::list はポインターのサイズが最低でも 2 つ必要となるため、 std::list<int> の各要素のサイズは 24 バイトぐらい
std::map の各要素には std::_Rb_node_tree_base を足したものが各要素のサイズとなる
なお各要素のサイズには切りの良い数にするためのパディングも含む

std::vector のサポートはそれほどは難しくないですが、リサイズを頻繁に行うためデバッグが面倒となりがちです。

std::list は双方向連結リストのポインターのために 16 バイト、データとパディングを合わせると 24 バイトは最低でも無いと割り当てはできないはずです。

さらに std::map は赤黒木というアルゴリズムを使うため、そのためのデータ領域が必要となります。

sizeof(std::_Rb_node_tree_base) にデータ用バイトサイズを加えたサイズを割り当てないと駄目です。

ではとりあえず std::map に適合するヒープアロケーターを作ってみましょう。

main.cpp.

  1 #include <iostream>
  2 #include <new>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <map>
  6 #include <vector>
  7 #include <list>
  8
  9 #define MAX_OBJECTS 64
 10
 11 template<typename T>
 12 struct is_pair : std::false_type {};
 13
 14 template<typename T, typename U>
 15 struct is_pair<std::pair<const T,U>> {
 16   static constexpr bool value = true;
 17 };
 18
 19 template<typename T, typename U>
 20 struct is_pair<std::_Rb_tree_node<std::pair<const T,U>>> {
 21   static constexpr bool value = true;
 22 };
 23
 24 template<typename T>
 25 struct MapAllocator {
 26   using value_type = T;
 27   using pointer = T*;
 28   using const_pointer = const T*;
 29   using reference = T&;
 30   using const_reference = const T&;
 31   using size_type = std::size_t;
 32
 33   using size_addr_t = std::map<void*,size_type>;
 34   using free_mem_t = std::map<size_type,std::vector<void*>>;
 35
 36   static_assert(is_pair<T>::value);
 37
 38   unsigned M_count_;
 39   const unsigned M_block_size_;
 40   size_addr_t M_size_map_;
 41   free_mem_t M_free_map_;
 42   char* Mp_pool_on_heap_;
 43
 44   template<typename U>
 45   struct rebind
 46   {
 47     typedef MapAllocator<U> other;
 48   };
 49
 50   inline MapAllocator() noexcept :
 51     M_count_(0),
 52     M_block_size_(sizeof(T)+sizeof(std::_Rb_tree_node_base))
 53   {
 54     Mp_pool_on_heap_ = static_cast<char*>(std::malloc(MAX_OBJECTS*M_block_size_));
 55     std::cout << "M_block_size_ = " << M_block_size_ << '\n';
 56   }
 57
 58   inline constexpr MapAllocator(const MapAllocator& a) noexcept
 59     : M_count_(a.M_count_),
 60     M_block_size_(a.M_block_size_),
 61     M_size_map_(a.M_size_map_),
 62     M_free_map_(a.M_free_map_)
 63   {
 64     Mp_pool_on_heap_ = static_cast<char*>(std::malloc(MAX_OBJECTS*M_block_size_));
 65     std::memcpy(Mp_pool_on_heap_,a.Mp_pool_on_heap_,MAX_OBJECTS*M_block_size_);
 66   }
 67
 68   template<typename U>
 69   inline constexpr MapAllocator(const MapAllocator<U>& a) noexcept
 70     : M_count_(a.M_count_),
 71     M_block_size_(a.M_block_size_),
 72     M_size_map_(a.M_size_map_),
 73     M_free_map_(a.M_free_map_)
 74   {
 75     Mp_pool_on_heap_ = static_cast<char*>(std::malloc(MAX_OBJECTS*M_block_size_));
 76     std::memcpy(Mp_pool_on_heap_,a.Mp_pool_on_heap_,MAX_OBJECTS*M_block_size_);
 77   }
 78
 79   inline ~MapAllocator(){
 80     std::free(Mp_pool_on_heap_);
 81     Mp_pool_on_heap_ = nullptr;
 82   }
 83
 84   inline pointer allocate(size_type n, typename std::allocator<T>::const_pointer = 0)
 85   {
 86     if(auto& vec = M_free_map_[n]; !vec.empty()){
 87
 88       void* reuse_address = vec.back();
 89       std::cout << "reuse free address: " << reuse_address << '\n';
 90       vec.pop_back();
 91       return reinterpret_cast<pointer>(reuse_address);
 92
 93     } else if(M_count_ + n < MAX_OBJECTS){
 94
 95       void* pblock = static_cast<void*>(Mp_pool_on_heap_ + M_block_size_ * M_count_);
 96       M_size_map_[pblock] = n;
 97       M_count_ += n;
 98       std::cout << "allocate unused address: " << pblock << '\n';
 99       return reinterpret_cast<pointer>(::new (pblock) char[n * M_block_size_]);
100
101     }
102     return nullptr;
103   }
104
105   void deallocate(pointer p,size_type) {
106     size_type size_to_push = M_size_map_[(void*)p];
107     M_free_map_[size_to_push].push_back((void*)p);
108     std::cout << "deallocate: " << p << '\n';
109   }
110
111   template<typename U, typename... Args>
112   void construct(U* p, Args&&... args) {
113     std::cout << "construct: " << p << '\n';
114     ::new ((void*)p) U(std::forward<Args>(args)...);
115   }
116
117   template<typename U>
118   void destroy(U* p) {
119     p->~U();
120   }
121
122 };
123
124 struct Foo {
125   int a,b,c,d,e;
126 };
127
128 int main()
129 {
130   MapAllocator<std::pair<const Foo,int>> map_allocator_foo;
131   MapAllocator<std::pair<const Foo,Foo>> map_allocator_foo_foo;
132   typedef MapAllocator<std::pair<const int,int>> map_allocator;
133   map_allocator alloc;
134
135   std::less<int> comp;
136   std::map<int,int,std::less<int>,map_allocator> m(comp,alloc);
137   m.insert({1,2});
138   m.insert({3,4});
139   m.insert({5,6});
140   m.insert({7,8});
141   auto y = m.find(5);
142   m.erase(y);
143   m.insert({9,10});
144   std::cout << "Map Values: ";
145   for(auto const& x : m)
146     std::cout << x.first << " ";
147   std::cout << '\n';
148
149   return 0;
150 }

ビルドと実行結果.

$ g++ main.cpp -std=c++17 -g
$ ./a.out
M_block_size_ = 56
M_block_size_ = 72
M_block_size_ = 40
allocate unused address: 0x560d49e110d0
construct: 0x560d49e110f0
allocate unused address: 0x560d49e110f8
construct: 0x560d49e11118
allocate unused address: 0x560d49e11120
construct: 0x560d49e11140
allocate unused address: 0x560d49e11148
construct: 0x560d49e11168
deallocate: 0x560d49e11120
reuse free address: 0x560d49e11120
construct: 0x560d49e11140
Map Values: 1 3 7 9
deallocate: 0x560d49e11120
deallocate: 0x560d49e11148
deallocate: 0x560d49e110f8
deallocate: 0x560d49e110d0

まず std::map に限定するためにコンパイル時アサート文を追加しておきます。

 11 template<typename T>
 12 struct is_pair : std::false_type {};
 13
 14 template<typename T, typename U>
 15 struct is_pair<std::pair<const T,U>> {
 16   static constexpr bool value = true;
 17 };
 18
 19 template<typename T, typename U>
 20 struct is_pair<std::_Rb_tree_node<std::pair<const T,U>>> {
 21   static constexpr bool value = true;
 22 };

 //   中略

 36   static_assert(is_pair<T>::value);

これによってテンプレートパラメーター T が std::pair または std::_Rb_tree_node<std::pair<const T,U>> である場合にのみコンパイルするよう制約します。

std::map のデータ構造のベースとなる型が std::pair である事を利用したチェックです。

次にアロケーターのブロックサイズを決定します。

 50   inline MapAllocator() noexcept :
 51     M_count_(0),
 52     M_block_size_(sizeof(T)+sizeof(std::_Rb_tree_node_base))
 53   {
 54     Mp_pool_on_heap_ = static_cast<char*>(std::malloc(MAX_OBJECTS*M_block_size_));
 55     std::cout << "M_block_size_ = " << M_block_size_ << '\n';
 56   }

テンプレートパラメーター T のバイトサイズに加えて赤黒木に必要なデータサイズ sizeof(std::_Rb_tree_node_base) を追加したサイズをブロックサイズとします。

この箇所については以下の行でチェックできます。

130   MapAllocator<std::pair<const Foo,int>> map_allocator_foo;
131   MapAllocator<std::pair<const Foo,Foo>> map_allocator_foo_foo;
132   typedef MapAllocator<std::pair<const int,int>> map_allocator;
133   map_allocator alloc;

インスタンスを作るとコンストラクターがコールされて、コンストラクターからブロックサイズを出力します。

 55     std::cout << "M_block_size_ = " << M_block_size_ << '\n';

出力結果は以下のようになります。

M_block_size_ = 56
M_block_size_ = 72
M_block_size_ = 40

std::pair<const Foo,int> は 56 バイト、 std::pair<const Foo,Foo> は 72 バイト、 std::pair<const int,int> が 40 バイトになります。

std::pair<const int,int> が 40 バイトになるのは int の 4 バイトが 2 個と sizeof(std::_Rb_tree_node_base) のサイズ 32 バイトを足したからです。

STL コンテナはバイトサイズが十分でなければ、正常に動作しないので、この計算が正しければ一応は動いてくれます。

他の箇所は何の変哲もないアロケーターなので説明は割愛しますが、実のところ、この計算も不要ではあります。

前の項目で確認したのを思い出してください。

割り当て型が std::pair<const int,int> の時に allocate() 関数内では sizeof(T) が 40 バイトになりました。

てことは allocate() 関数で動的に割り当てサイズを算出するなら、計算する手間が省けるかもしれません。

次の項目ではこのアイデアを試してみたいと思います。