この項目では固定長のスタックアロケーターを紹介します。
スタックアロケーターは割り当てたいメモリーのサイズが可変長の場合だと、いくつか念頭にしておくべき点が出てきます。
実装の観点から感がえると、割り当てるサイズが固定長のサイズであり、解放は最後に割り当てたメモリー領域からする前提が一番シンプルです。
この条件が満たされるなら、以下のような関数の実装で割り当て、解放ができます。
allocate（リクエスト個数）{
スタックポインター += (リクエスト個数 * ブロックサイズ);
return スタックポインター;
}
deallocate (リクエスト個数) {
スタックポインター -= (リクエスト個数 * ブロックサイズ);
}スタックポインターは割り当てるポインターとなり、リクエスト個数はアロケーター要件に準拠した allocate() や deallocate() の引数の一つです。
ブロックサイズは 1 回のメモリー割り当てに使える最低サイズ、つまり割り当ての最少単位です。
リクエスト個数とかブロックサイズが理解しにくければ「（割り当ての）リクエストサイズ ＝ リクエスト個数 * ブロックサイズ」と考えると分かりやすいかもしれないですね。
allocate() と deallocate() は割り当てをすればスタックポインターの位置は上がり、解放すれば位置は下がるという具合になります。
ですがこのようなアロケーター実装は現実には全く使えません。
なぜならアロケーターは以下の 2 点を満たさないのなら、スタックのエミュレーターと何ら変わりがないからです。
この条件を満たすには、以下の 2 つを作り込む必要があります。
どちらも難しいですが実装してみましょう。
main.cpp.
1 #include <cstddef>
2 #include <memory>
3 #include <cassert>
4 #include <new>
5 #include <cstdlib>
6 #include <iostream>
7 #include <cstring>
8 #include <map>
9 #include <vector>
10
11 #define MAX_OBJECTS 32
12
13 template<typename T,size_t N>
14 class allocator
15 {
16 struct block_not_in_use;
17 typedef std::map<void*,size_t> size_map_t;
18 typedef std::map<size_t,block_not_in_use*> free_list_t;
19 static_assert(sizeof(std::byte[N]) >= sizeof(T));
20 public:
21
22 allocator()
23 :
24 M_max_objects_(MAX_OBJECTS),
25 M_pool_index_(0),
26 M_block_size_(sizeof(std::byte[N]) < 8 ? sizeof(long long) : sizeof(std::byte[N]))
27 {
28 Mp_pool_ = ::new (&Mp_Mem_) std::byte[M_block_size_*MAX_OBJECTS];
29 }
30
31 ~allocator(){}
32
33 inline void* allocate(size_t n){
34 auto cache_head = M_free_list_[n*M_block_size_];
35 void* pblock = pop_from_pool(cache_head,n);
36 if(!pblock)
37 {
38 if(M_pool_index_ <= M_max_objects_)
39 {
40 std::cout << "NEW! M_pool_index : M_block_in_use_ = " << M_pool_index_
41 << " : " << M_block_in_use_ << '\n';
42 pblock = static_cast<void*>(Mp_pool_ + (M_pool_index_ * M_block_size_));
43 M_pool_index_ += n;
44 } else {
45 std::cout << "M_pool_index = " << M_pool_index_ << '\n';
46 assert(false);
47 }
48 M_block_in_use_ += n;
49 M_size_map_[pblock] = n*M_block_size_;
50 } else {
51 std::printf("reuse pointer %p for size %lu\n",pblock,n*M_block_size_);
52 }
53 return pblock;
54 }
55
56 inline void deallocate(void* memory, size_t )
57 {
58 auto chunk_size = M_size_map_[memory];
59 if(chunk_size != 0){
60 rewind(memory,chunk_size);
61 }
62 }
63
64 private:
65 // 開放(deallocate)時に使用可能チャンクを更新
66 void rewind(void* memory,size_t size){
67 auto head = M_free_list_[size];
68 block_not_in_use* pblock = static_cast<block_not_in_use*>(memory);
69 pblock->next = head; //先頭ポインタを次にすすめる
70 head = pblock;
71 M_free_list_[size] = head;
72 std::printf("rewind cache head %p for size %lu\n",head,size);
73 }
74 // 割当(allocate)時に開放された使用可能領域から使う
75 void* pop_from_pool(block_not_in_use* head,size_t n){
76 block_not_in_use* pblock = nullptr;
77 if(head)
78 {
79 pblock = head;
80 head = head->next;
81 }
82 M_free_list_[n*M_block_size_] = head;
83 return static_cast<void*>(pblock);
84 }
85 // 使用可能なメモリータグ（一度割当、後に開放された領域）
86 struct block_not_in_use {
87 block_not_in_use *next;
88 };
89 size_map_t M_size_map_;
90 free_list_t M_free_list_;
91
92 const size_t M_block_size_;
93 const size_t M_max_objects_;
94
95 std::byte* Mp_pool_;
96 unsigned M_pool_index_; //新規割当時にインクリメント、下がることはない
97 unsigned M_block_in_use_;
98 std::byte Mp_Mem_[sizeof(std::byte[N])*MAX_OBJECTS];
99 };
100
101 /* スタックメモリーのブロックを割り当てるクラステンプレート */
102
103 template<typename T,size_t N>
104 class block_allocator
105 {
106 public:
107 typedef T* pointer;
108 typedef const T* const_pointer;
109 typedef T value_type;
110
111 template<typename U>
112 struct rebind
113 {
114 typedef block_allocator<U,N> other;
115 };
116
117 explicit block_allocator() noexcept {
118 }
119 ~block_allocator() {
120 }
121
122 template<typename U>
123 block_allocator(const block_allocator<U,N>&){}
124
125 template<typename U>
126 block_allocator(const std::allocator<U>&){}
127
128 T* allocate(std::size_t n)
129 {
130 return reinterpret_cast<T*>(S_alloc_.allocate(n));
131 }
132
133 void deallocate(T* p,size_t n)
134 {
135 S_alloc_.deallocate(static_cast<void*>(p),n);
136 }
137
138 private:
139 static allocator<T,N> S_alloc_;
140 };
141
142 template<typename T,size_t N>
143 allocator<T,N> block_allocator<T,N>::S_alloc_;
144
145 /* voidパラメーターのエラーチェックのためにvoid型のクラステンプレートを用意 */
146
147 template <size_t N>
148 class block_allocator<void,N>
149 {
150 public:
151 typedef void* pointer;
152 typedef const void* const_pointer;
153 typedef void value_type;
154
155 template<typename U>
156 struct rebind
157 {
158 typedef block_allocator<U,N> other;
159 };
160
161 explicit block_allocator() noexcept {
162 }
163
164 template<typename U>
165 block_allocator(const block_allocator<U,N>&){}
166
167 template<typename U>
168 block_allocator(std::allocator<U>&){}
169
170 };
171
172 struct A{
173 A(int x, int y, int z, int a) :
174 x_(x),
175 y_(y),
176 z_(z),
177 a_(a)
178 {}
179 int x_,y_,z_,a_;
180 };
181
182 int main()
183 {
184 int *ptr[10];
185
186 block_allocator<int,16> ba;
187
188 std::cout << "size == 1" << '\n';
189 for(int i = 0; i < 5; ++i){
190 ptr[i] = ba.allocate(1);
191 }
192 for(int i = 1; i < 5; ++i){
193 ba.deallocate(ptr[i],1);
194 }
195 for(int i = 5; i < 10; ++i){
196 ptr[i] = ba.allocate(1);
197 }
198 std::cout << "size == 2" << '\n';
199 for(int i = 1; i < 5; ++i){
200 ptr[i] = ba.allocate(2);
201 }
202 for(int i = 1; i < 5; ++i){
203 ba.deallocate(ptr[i],2);
204 }
205 for(int i = 1; i < 5; ++i){
206 ptr[i] = ba.allocate(2);
207 }
208 }
ビルドと実行結果.
$ g++ main.cpp -std=c++17 $ ./a.out size == 1 NEW! M_pool_index : M_block_in_use_ = 0 : 0 NEW! M_pool_index : M_block_in_use_ = 1 : 1 NEW! M_pool_index : M_block_in_use_ = 2 : 2 NEW! M_pool_index : M_block_in_use_ = 3 : 3 NEW! M_pool_index : M_block_in_use_ = 4 : 4 rewind cache head 0x56354f80a1d0 for size 8 rewind cache head 0x56354f80a1d8 for size 8 rewind cache head 0x56354f80a1e0 for size 8 rewind cache head 0x56354f80a1e8 for size 8 reuse pointer 0x56354f80a1e8 for size 8 reuse pointer 0x56354f80a1e0 for size 8 reuse pointer 0x56354f80a1d8 for size 8 reuse pointer 0x56354f80a1d0 for size 8 NEW! M_pool_index : M_block_in_use_ = 5 : 5 size == 2 NEW! M_pool_index : M_block_in_use_ = 6 : 6 NEW! M_pool_index : M_block_in_use_ = 8 : 8 NEW! M_pool_index : M_block_in_use_ = 10 : 10 NEW! M_pool_index : M_block_in_use_ = 12 : 12 rewind cache head 0x56354f80a1f8 for size 16 rewind cache head 0x56354f80a208 for size 16 rewind cache head 0x56354f80a218 for size 16 rewind cache head 0x56354f80a228 for size 16 reuse pointer 0x56354f80a228 for size 16 reuse pointer 0x56354f80a218 for size 16 reuse pointer 0x56354f80a208 for size 16 reuse pointer 0x56354f80a1f8 for size 16
このアロケーターは allocator クラステンプレートに実装していますね。
11 #define MAX_OBJECTS 32
12
13 template<typename T,size_t N>
14 class allocator
15 {
16 struct block_not_in_use;
17 typedef std::map<void*,size_t> size_map_t;
18 typedef std::map<size_t,block_not_in_use*> free_list_t;
19 static_assert(sizeof(std::byte[N]) >= sizeof(T));
20 public:
21
22 allocator()
23 :
24 M_max_objects_(MAX_OBJECTS),
25 M_pool_index_(0),
26 M_block_size_(sizeof(std::byte[N]) < 8 ? sizeof(long long) : sizeof(std::byte[N]))
27 {
28 Mp_pool_ = ::new (&Mp_Mem_) std::byte[M_block_size_*MAX_OBJECTS];
29 }
30
31 ~allocator(){}
32
// 中略
85 // 使用可能なメモリータグ（一度割当、後に開放された領域）
86 struct block_not_in_use {
87 block_not_in_use *next;
88 };
89 size_map_t M_size_map_;
90 free_list_t M_free_list_;
91
92 const size_t M_block_size_;
93 const size_t M_max_objects_;
94
95 std::byte* Mp_pool_;
96 unsigned M_pool_index_; //新規割当時にインクリメント、下がることはない
97 unsigned M_block_in_use_;
98 std::byte Mp_Mem_[sizeof(std::byte[N])*MAX_OBJECTS];
99 };最初に見ておきたいのが以下の 5 つの変数・ポインターです。
これらのオブジェクト・変数はコンストラクターで初期化されています。
22 allocator()
23 :
24 M_max_objects_(MAX_OBJECTS),
25 M_pool_index_(0),
26 M_block_size_(sizeof(std::byte[N]) < 8 ? sizeof(long long) : sizeof(std::byte[N]))
27 {
28 Mp_pool_ = ::new (&Mp_Mem_) std::byte[M_block_size_*MAX_OBJECTS];
29 }Mp_pool_ は Mp_mem_ のアドレスにある std::byte[] 配列を指すポインターとなり、これをメモリープールと呼びます。
メモリープール Mp_pool_ は単に割り当て可能なメモリー領域となります。
そして MAX_OBJECTS は任意の値ですが 32 個になってますね。
11 #define MAX_OBJECTS 32
これは最大オブジェクト数を意味します。
24 M_max_objects_(MAX_OBJECTS),
したがって M_max_objects が最大オブジェクト「数」ってことです。
M_block_size_ はブロックのバイトサイズなので個数じゃないので混同しないでくださいね。
ブロックサイズはオブジェクトのサイズである「sizeof(T)」以上に念の為にとっておきます。
19 static_assert(sizeof(std::byte[N]) >= sizeof(T));
さらにポインター型をサポートしたいのでブロックサイズは 8 バイト以上に強制的に設定しておきます。
26 M_block_size_(sizeof(std::byte[N]) < 8 ? sizeof(long long) : sizeof(std::byte[N]))
もっと小さい値を使う場合にしても、後で STL コンテナと使う場合には reserve() 関数を使う std::vector 等では コンテナが勝手に使い方を決めてしまうので、かなり無駄になるかも知りませんね…
(´・ω・｀)
後はメモリープールはこの 2 つを使って定義します。
28 Mp_pool_ = ::new (&Mp_Mem_) std::byte[M_block_size_*MAX_OBJECTS];
voidポインターでなく、std::byte ポインターをベースに使うのはポインター算術が使えるからです。
まあ char ポインターでも良いんですけどね…
ちなみにスタックアロケーターはヒープアロケーターと比べ大容量に弱いので MAX_OBJECTS または M_max_objects はあまり巨大な数値にするのはやめときましょう。
後はメモリーを解放後に管理するためのキャッシュ記憶域ですが、これは単に単方向の連結リストを使います。
85 // 使用可能なメモリータグ（一度割当、後に開放された領域）
86 struct block_not_in_use {
87 block_not_in_use *next;
88 };struct block_not_in_use は一つのポインターを持つだけの連結リストとして、フリーチャンクを保持します。
具体には deallocate() をコールするたびに以下のように先頭ポインターを先に進めることで使います。
先頭を更新していきます。
65 // 開放(deallocate)時に使用可能チャンクを更新
66 void rewind(void* memory,size_t size){
67 auto head = M_free_list_[size];
68 block_not_in_use* pblock = static_cast<block_not_in_use*>(memory);
69 pblock->next = head; //先頭ポインタを次にすすめる
70 head = pblock;
71 M_free_list_[size] = head;
72 std::printf("rewind cache head %p for size %lu\n",head,size);
73 }この関数によって用済みになったメモリーをリワインド（巻き戻す）していきます。
正確には最後にキャッシュ( struct block_not_in_use* )にいれたチャンクが先頭( head ) になるので、巻き戻すというより押し込むの方が正しそうですね…
(´・ω・｀)
まあ慣れちゃって癖なので気にしないヨ…
次にフリーチャンクを再割り当て、再利用に使うための関数です。
74 // 割当(allocate)時に開放された使用可能領域から使う
75 void* pop_from_pool(block_not_in_use* head,size_t n){
76 block_not_in_use* pblock = nullptr;
77 if(head)
78 {
79 pblock = head;
80 head = head->next;
81 }
82 M_free_list_[n*M_block_size_] = head;
83 return static_cast<void*>(pblock);
84 }これは allocate() 関数からコールする関数ですが head （先頭）にフリーチャンクが存在するなら、それを pblock に代入して head を連結リストから取り出し、直前の head を現在の head に更新します。
77 if(head)
78 {
79 pblock = head;
80 head = head->next;
81 }後は更新されたであろう head をフリーリストにいれておきます。
82 M_free_list_[n*M_block_size_] = head;
M_free_list_ の型は free_list_t となり以下のように定義されています。
18 typedef std::map<size_t,block_not_in_use*> free_list_t;
まあつまり、重複なしのマップデータ構造となりますが、すでに存在したら何もしないですし、存在するアドレスならデータ構造に挿入されます。
まあいきなりなので補足しますね。
89 size_map_t M_size_map_; 90 free_list_t M_free_list_;
この 2 つは以下のような定義になっています。
17 typedef std::map<void*,size_t> size_map_t; 18 typedef std::map<size_t,block_not_in_use*> free_list_t;
free_list_t は各リクエストサイズごとにフリーチャンクのリスト（ block_no_in_use* ）をキープします。
size_map_t は各フリーチャンクのリクエストサイズをキープします。
この 2 つのオブジェクトは一見不要に見えますが、必須です。
これは allocate() 関数の宣言を見れば分かります。
33 inline void* allocate(size_t n){allocate() 関数はリクエスト個数（ n ） * ブロックサイズ( M_block_size_ )をリクエストサイズとするので、毎回リクエストサイズが同じとは限らないです。
ということは解放したチャンクサイズはブロックサイズ 1 個分、ブロックサイズ 2 個分、ブロックサイズ 3 個分というように異なるサイズとなるために、フリーチャンクのサイズは一定せず変動します。
33 inline void* allocate(size_t n){
34 auto cache_head = M_free_list_[n*M_block_size_];
35 void* pblock = pop_from_pool(cache_head,n);
36 if(!pblock)
37 {
38 if(M_pool_index_ <= M_max_objects_)
39 {
40 std::cout << "NEW! M_pool_index : M_block_in_use_ = " << M_pool_index_
41 << " : " << M_block_in_use_ << '\n';
42 pblock = static_cast<void*>(Mp_pool_ + (M_pool_index_ * M_block_size_));
43 M_pool_index_ += n;
44 } else {
45 std::cout << "M_pool_index = " << M_pool_index_ << '\n';
46 assert(false);
47 }
48 M_block_in_use_ += n;
49 M_size_map_[pblock] = n*M_block_size_;
50 } else {
51 std::printf("reuse pointer %p for size %lu\n",pblock,n*M_block_size_);
52 }
53 return pblock;
54 }allocate() 関数は必要以上に長いように見えますが、スタックの再利用を実装するならば、これぐらいの行数は普通に使います。
まずはキャッシュの先頭を取得して、そのキャッシュヘッドから使えるフリーチャンクを取り出します。
34 auto cache_head = M_free_list_[n*M_block_size_]; 35 void* pblock = pop_from_pool(cache_head,n);
この際に pop_from_pool() にはリクエスト個数 n を指定していますね。
これはキャッシュから「リクエスト個数（ n ） × ブロックサイズ( M_block_size_ )」のリクエストサイズに一致するフリーチャンクをポップするために必要な引数です。
pblock が NULL 値でないのなら allocate() 関数は pblock をそのまま返します。
それで pblock が NULL の場合の allocate() 関数の続きです。
38 if(M_pool_index_ <= M_max_objects_)
39 {
40 std::cout << "NEW! M_pool_index : M_block_in_use_ = " << M_pool_index_
41 << " : " << M_block_in_use_ << '\n';
42 pblock = static_cast<void*>(Mp_pool_ + (M_pool_index_ * M_block_size_));
43 M_pool_index_ += n;
44 } else {
45 std::cout << "M_pool_index = " << M_pool_index_ << '\n';
46 assert(false);
47 }
48 M_block_in_use_ += n;
49 M_size_map_[pblock] = n*M_block_size_;pblock はメモリープールこと Mp_pool_ を起点にして「プールインデックス × ブロックサイズ」を加算した void ポインターアドレスを代入します。
42 pblock = static_cast<void*>(Mp_pool_ + (M_pool_index_ * M_block_size_));
M_pool_index_ は「次に使用するブロック数」を意味します。
M_pool_index_ は pblock に割り当てた時点で「使用中のブロック数」に意味を転じます。
つまり使用中のブロック数とブロックサイズを乗じることで、次に割り当てたいブロックのアドレスを算出します。
割り当てアドレスを算出後には以下のようにアップデートします。
43 M_pool_index_ += n;
最後に割り当てたブロック情報のブックキーピングをしておきます。
48 M_block_in_use_ += n; 49 M_size_map_[pblock] = n*M_block_size_;
M_block_in_use_ は使用中のブロック数で M_pool_index_ と同じ値となりますが、名前が紛らわしいので、もう一つ変数を保持することにしただけです。
M_size_map_ の行は pblock のアドレスとリクエストサイズを紐付けるマップデータを設定していますね。
最後に割り当て済みチャンクを解放する deallocate() 関数です。
56 inline void deallocate(void* memory, size_t )
57 {
58 auto chunk_size = M_size_map_[memory];
59 if(chunk_size != 0){
60 rewind(memory,chunk_size);
61 }
62 }最初にやるのは M_size_map_ から memory に一対のチャンクサイズを取得します。
58 auto chunk_size = M_size_map_[memory];
次に該当するメモリーアドレスとチャンクサイズが存在するのであれば rewind() 関数をコールします。
59 if(chunk_size != 0){
60 rewind(memory,chunk_size);
61 }これによってチャンクをフリーリストに登録して、メモリーを再利用のキャッシュとして使えるようにします。
最後にテストコードもチェックしてみましょうかね。
182 int main()
183 {
184 int *ptr[10];
185
186 block_allocator<int,16> ba;
187
188 std::cout << "size == 1" << '\n';
189 for(int i = 0; i < 5; ++i){
190 ptr[i] = ba.allocate(1);
191 }
192 for(int i = 1; i < 5; ++i){
193 ba.deallocate(ptr[i],1);
194 }
195 for(int i = 5; i < 10; ++i){
196 ptr[i] = ba.allocate(1);
197 }
198 std::cout << "size == 2" << '\n';
199 for(int i = 1; i < 5; ++i){
200 ptr[i] = ba.allocate(2);
201 }
202 for(int i = 1; i < 5; ++i){
203 ba.deallocate(ptr[i],2);
204 }
205 for(int i = 1; i < 5; ++i){
206 ptr[i] = ba.allocate(2);
207 }
208 }リクエストするオブジェクト数を 1 個と 2 個のケースでテストしていますね。
オブジェクト数 1 個のケースでは 5 回割り当てた後に 4 回解放します。
さらにその後に追加で 5 回割り当てをします。
189 for(int i = 0; i < 5; ++i){
190 ptr[i] = ba.allocate(1);
191 }
192 for(int i = 1; i < 5; ++i){
193 ba.deallocate(ptr[i],1);
194 }
195 for(int i = 5; i < 10; ++i){
196 ptr[i] = ba.allocate(1);
197 }4 個分のフリーチャンクができるので、新規割り当て回数はこの場合は 6 回となりますね。
これは出力を見ると分かるかと思います。
size == 1 NEW! M_pool_index : M_block_in_use_ = 0 : 0 NEW! M_pool_index : M_block_in_use_ = 1 : 1 NEW! M_pool_index : M_block_in_use_ = 2 : 2 NEW! M_pool_index : M_block_in_use_ = 3 : 3 NEW! M_pool_index : M_block_in_use_ = 4 : 4 rewind cache head 0x56354f80a1d0 for size 8 rewind cache head 0x56354f80a1d8 for size 8 rewind cache head 0x56354f80a1e0 for size 8 rewind cache head 0x56354f80a1e8 for size 8 reuse pointer 0x56354f80a1e8 for size 8 reuse pointer 0x56354f80a1e0 for size 8 reuse pointer 0x56354f80a1d8 for size 8 reuse pointer 0x56354f80a1d0 for size 8 NEW! M_pool_index : M_block_in_use_ = 5 : 5
オブジェクト数 2 個のケースでは 4 回割り当てた後に 4 回解放し、さらにもう一回割り当てします。
199 for(int i = 1; i < 5; ++i){
200 ptr[i] = ba.allocate(2);
201 }
202 for(int i = 1; i < 5; ++i){
203 ba.deallocate(ptr[i],2);
204 }
205 for(int i = 1; i < 5; ++i){
206 ptr[i] = ba.allocate(2);
207 }これも出力で正しく実装されていることが確認できます。
size == 2 NEW! M_pool_index : M_block_in_use_ = 6 : 6 NEW! M_pool_index : M_block_in_use_ = 8 : 8 NEW! M_pool_index : M_block_in_use_ = 10 : 10 NEW! M_pool_index : M_block_in_use_ = 12 : 12 rewind cache head 0x56354f80a1f8 for size 16 rewind cache head 0x56354f80a208 for size 16 rewind cache head 0x56354f80a218 for size 16 rewind cache head 0x56354f80a228 for size 16 reuse pointer 0x56354f80a228 for size 16 reuse pointer 0x56354f80a218 for size 16 reuse pointer 0x56354f80a208 for size 16 reuse pointer 0x56354f80a1f8 for size 16
リクエストサイズは「ブロックサイズ × 2 = 16 バイト」になってますね。
ただこのケースでは一定サイズを超えるとエラーを投げるようにしています。
38 if(M_pool_index_ <= M_max_objects_)
39 {
// 中略
44 } else {
45 std::cout << "M_pool_index = " << M_pool_index_ << '\n';
46 assert(false);
47 }これを解決する方法は次に項目で解説したいと思います。
Copyright 2018-2019, by Masaki Komatsu