malloc() を使って大きめの記憶域を先に割り当てるアロケーターは、前の項目で可能な事が判明したので、早速アロケーターを設計してみましょうかね。
まず割り当てには malloc() や new を使わない点においてスタックアロケーターとは何も変わらないです。
さらに言えばスタックアロケーターと allocate() 関数の実装については特に変更は必要ないです。
では実装してみましょう。
main.cpp.
1 #include <iostream>
2 #include <cassert>
3 #include <cstddef>
4 #include <cstdint>
5 #include <new>
6 #include <map>
7 #include <vector>
8
9 #define MAX_OBJECTS 256
10
11 struct Foo {
12 int x_,y_,z_;
13 Foo(int x, int y, int z) :
14 x_(x),y_(y),z_(z){}
15 };
16
17 template<typename T>
18 struct A {
19 typedef T* pointer;
20 typedef std::size_t size_type;
21
22 const size_t M_object_size_;
23 unsigned M_count_;
24 char* M_heap_;
25
26 using size_map = std::map<void*,size_type>;
27 using free_map = std::map<size_type,std::vector<void*>>;
28
29 A() : M_count_(0), M_object_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T))
30 {
31 M_heap_ = (char*)std::malloc(MAX_OBJECTS*M_object_size_);
32 }
33
34 ~A(){
35 std::free(M_heap_);
36 M_heap_ = nullptr;
37 }
38
39 pointer allocate(size_type n = 1) {
40 assert(M_count_ <= MAX_OBJECTS);
41 auto& free_chunks = free_map_[n*M_object_size_];
42 if(!free_chunks.empty()){
43 T* available_block = static_cast<T*>(free_chunks.back());
44 free_chunks.pop_back();
45 std::cout << "reuse pointer: " << available_block << " M_count_: " << M_count_ << '\n';
46 return available_block;
47 }
48 M_count_ += n;
49 void* pblock = static_cast<void*>(M_heap_ + (M_object_size_ * M_count_));
50 size_map_[pblock] = n * M_object_size_;
51 std::cout << "new pointer: " << pblock << " M_count_: " << M_count_ << '\n';
52 return reinterpret_cast<T*>(::new (pblock) char(n*M_object_size_));
53 }
54
55 void deallocate(pointer p) {
56 auto no_longer_in_use_chunks = size_map_[(void*)p];
57 free_map_[no_longer_in_use_chunks].push_back((void*)p);
58 std::printf("deallocate %p with size %lu\n",p,no_longer_in_use_chunks);
59 }
60
61 template<typename U, typename... Args>
62 void construct(U* p, Args&& ...args) {
63 ::new ((void*)p) U(std::forward<Args>(args)...);
64 }
65
66 template<typename U>
67 void destroy(U* p) {
68 p->~U();
69 }
70 private:
71 size_map size_map_;
72 free_map free_map_;
73 };
74
75 int main()
76 {
77 A<int> a;
78 int* d[10];
79 A<Foo> f;
80 Foo* foo[10];
81 for(int i = 0; i < 5; ++i) {
82 auto size = i % 2 + 1;
83 d[i] = a.allocate(size);
84 foo[i] = f.allocate(size);
85 a.construct(d[i],i);
86 f.construct(foo[i],i,i,i);
87 }
88 for(int i = 2; i < 5; ++i){
89 a.deallocate(d[i]);
90 f.deallocate(foo[i]);
91 }
92 for(int i = 5; i < 10; ++i){
93 d[i] = a.allocate(2);
94 foo[i] = f.allocate(2);
95 }
96 return 0;
97 }
ビルドと実行結果.
$ g++ main.cpp $ ./a.out new pointer: 0x56342fb05e78 M_count_: 1 new pointer: 0x56342fb0668c M_count_: 1 new pointer: 0x56342fb05e88 M_count_: 3 new pointer: 0x56342fb066a4 M_count_: 3 new pointer: 0x56342fb05e90 M_count_: 4 new pointer: 0x56342fb066b0 M_count_: 4 new pointer: 0x56342fb05ea0 M_count_: 6 new pointer: 0x56342fb066c8 M_count_: 6 new pointer: 0x56342fb05ea8 M_count_: 7 new pointer: 0x56342fb066d4 M_count_: 7 deallocate 0x56342fb05e90 with size 8 deallocate 0x56342fb066b0 with size 12 deallocate 0x56342fb05ea0 with size 16 deallocate 0x56342fb066c8 with size 24 deallocate 0x56342fb05ea8 with size 8 deallocate 0x56342fb066d4 with size 12 reuse pointer: 0x56342fb05ea0 M_count_: 7 reuse pointer: 0x56342fb066c8 M_count_: 7 new pointer: 0x56342fb05eb8 M_count_: 9 new pointer: 0x56342fb066ec M_count_: 9 new pointer: 0x56342fb05ec8 M_count_: 11 new pointer: 0x56342fb06704 M_count_: 11 new pointer: 0x56342fb05ed8 M_count_: 13 new pointer: 0x56342fb0671c M_count_: 13 new pointer: 0x56342fb05ee8 M_count_: 15 new pointer: 0x56342fb06734 M_count_: 15
アロケーターの状態には、オブジェクト数をキープする M_count_ 変数と、オブジェクトサイズを保持する M_object_size_ があります。
17 template<typename T>
18 struct A {
19 typedef T* pointer;
20 typedef std::size_t size_type;
21
22 const size_t M_object_size_;
23 unsigned M_count_;
24 char* M_heap_;
25
26 using size_map = std::map<void*,size_type>;
27 using free_map = std::map<size_type,std::vector<void*>>;
//中略
70 private:
71 size_map size_map_;
72 free_map free_map_;
73 };M_heap_ はヒープで割り当てる記憶域ですが、ヒープはコンストラクターを呼び出す一回に限り malloc() で割り当てます。
29 A() : M_count_(0), M_object_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T))
30 {
31 M_heap_ = (char*)std::malloc(MAX_OBJECTS*M_object_size_);
32 }
33
34 ~A(){
35 std::free(M_heap_);
36 M_heap_ = nullptr;
37 }オブジェクトサイズについては、テンプレートパラメーター T のバイトサイズが 8 を下回る場合は強制的に 8 に設定します。
long long は 8 バイトになるはずなので、そのバイトサイズを設定するか、T のバイトサイズをオブジェクトサイズとします。
後はコンストラクター時に M_heap_ に割り当てたヒープ領域のメモリーはデストラクタ―で解放します。
allocate() については M_heap_ のアドレスを起点として新たなアドレスを割り当てたり、解放していきます。
39 pointer allocate(size_type n = 1) {
40 assert(M_count_ <= MAX_OBJECTS);
41 auto& free_chunks = free_map_[n*M_object_size_];
42 if(!free_chunks.empty()){
43 T* available_block = static_cast<T*>(free_chunks.back());
44 free_chunks.pop_back();
45 std::cout << "reuse pointer: " << available_block << " M_count_: " << M_count_ << '\n';
46 return available_block;
47 }
48 M_count_ += n;
49 void* pblock = static_cast<void*>(M_heap_ + (M_object_size_ * M_count_));
50 size_map_[pblock] = n * M_object_size_;
51 std::cout << "new pointer: " << pblock << " M_count_: " << M_count_ << '\n';
52 return reinterpret_cast<T*>(::new (pblock) char(n*M_object_size_));
53 }まず最初にフリーリスト内にチャンクがないかチェックします。
41 auto& free_chunks = free_map_[n*M_object_size_];
42 if(!free_chunks.empty()){allocate() の引数である n は要求されている要素数なので、アロケーターへのリクエストサイズは n*M_object_size_ となりますね。
もしチャンクが空であれば、そのまま新たなアドレスを割り振ります。
48 M_count_ += n; 49 void* pblock = static_cast<void*>(M_heap_ + (M_object_size_ * M_count_)); 50 size_map_[pblock] = n * M_object_size_; 51 std::cout << "new pointer: " << pblock << " M_count_: " << M_count_ << '\n'; 52 return reinterpret_cast<T*>(::new (pblock) char(n*M_object_size_)); 53 }
M_count_ はアロケーターの新規割り当てに使ったブロックの合計なので、それにブロックサイズである M_object_size_ をかけたものを M_heap_ に加算すれば、新規割り当てに使えるアドレスを算出できます。
仮にフリーリスト（フリーチャンクのリスト）が空でない場合は、リクエストサイズと同じサイズのリストを検索します。
42 if(!free_chunks.empty()){
43 T* available_block = static_cast<T*>(free_chunks.back());
44 free_chunks.pop_back();
45 std::cout << "reuse pointer: " << available_block << " M_count_: " << M_count_ << '\n';
46 return available_block;
47 }検索にマッチするサイズのフリーチャンクがあれば、それを再利用して返します。
後は deallocate() も軽く説明しておきますね。
55 void deallocate(pointer p) {
56 auto no_longer_in_use_chunks = size_map_[(void*)p];
57 free_map_[no_longer_in_use_chunks].push_back((void*)p);
58 std::printf("deallocate %p with size %lu\n",p,no_longer_in_use_chunks);
59 }不要になり解放したいポインター p については size_map_ を使って、割り当て時にリクエストされたサイズを照合します。
照合されたサイズをキーにして、フリーリスト（フリーチャンクのリスト）にポインターを追加します。
それとアロケーターのテストについては int 型と Foo 型の 2 パターンを用意しました。
int 型は 4 バイトで Foo 型は 12 バイトのオブジェクトとしてヒープに割り当てをしますが、リクエストサイズは 8 バイトか 16 バイト、12 バイトか 24 バイトのいずれかのパターンとします。
77 A<int> a; 78 int* d[10]; 79 A<Foo> f; 80 Foo* foo[10];
後は for ループを回してるだけですが、5 回割り当てをし、3 回解放、5 回割り当てというパターンを試すことで、適切な解放領域が再利用されるかチェックしてみます。
81 for(int i = 0; i < 5; ++i) {
82 auto size = i % 2 + 1;
83 d[i] = a.allocate(size);
84 foo[i] = f.allocate(size);
85 a.construct(d[i],i);
86 f.construct(foo[i],i,i,i);
87 }
88 for(int i = 2; i < 5; ++i){
89 a.deallocate(d[i]);
90 f.deallocate(foo[i]);
91 }
92 for(int i = 5; i < 10; ++i){
93 d[i] = a.allocate(2);
94 foo[i] = f.allocate(2);
95 }出力結果については以下の部分で再利用が確認されています。
deallocate 0x56342fb05e90 with size 8 deallocate 0x56342fb066b0 with size 12 deallocate 0x56342fb05ea0 with size 16 deallocate 0x56342fb066c8 with size 24 deallocate 0x56342fb05ea8 with size 8 deallocate 0x56342fb066d4 with size 12 reuse pointer: 0x56342fb05ea0 M_count_: 7 reuse pointer: 0x56342fb066c8 M_count_: 7
つまり解放は各アロケーターに大して 3 回づつ行われてますが、実際に再利用されたのは 16 バイト（ 0x56342fb05ea0 ） と 24 バイト（ 0x56342fb066c8 ）のチャンクだけです。
93 d[i] = a.allocate(2); 94 foo[i] = f.allocate(2);
各 allocate() がリクエストするサイズが 16 バイトと 24 バイトだからです。
Copyright 2018-2019, by Masaki Komatsu