スタックアロケーターでアラインメントを厳格に適用するのは、あまり実用的だと筆者は考えないのですが、実験的に作ってみたくなることもあります。
まあカスタムアロケーターなみに memory_resource インターフェースの実装に色々と手を加えると、必ずしも良い実装でなくとも、抽象クラスのインターフェースを覚えるには結構役に立つもんです。
では前の項目の aligned_heap_allocator をスタックにも拡張するとしたら、どんな変更が必要でしょうかね？
真っ先に思いつくのが std::align ですが void ポインターを用意する必要があるし、かったるそうです。
glibc のアラインメント実装をそのまま持ってくる方法です…
つまりスタックポインターに対して以下のビット処理をします。
(ptr + alignment - 1) & (alignment - 1)
これは単にアラインメント値分だけ加算して繰り上げ後に、下のビットを 0 にするという方法です。
では実装したソースコードを見てみましょう。
main.cpp.
1 #include <experimental/memory_resource>
2 #include <experimental/vector>
3 #include <iostream>
4 #include <vector>
5 #include <cstdlib>
6 #include <cstdio>
7 #include <map>
8
9 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
10 class stack_allocator : public std::experimental::pmr::memory_resource
11 {
12 public:
13 typedef std::size_t size_type;
14 typedef T value_type;
15 typedef value_type* pointer;
16 typedef const value_type* const_pointer;
17 typedef value_type& reference;
18 typedef const value_type const_reference;
19
20 typedef Allocator allocator_t;
21 typedef std::map<void*,size_t> size_map_t;
22 typedef std::map<size_t,std::vector<void*>> free_list_t;
23
24 public:
25
26 explicit stack_allocator() :
27 M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
28 M_max_objects_(sizeof(std::byte[N])),
29 M_begin_(M_buffer_),
30 M_end_(M_buffer_ + M_max_objects_ * M_block_size_),
31 M_stack_pointer_(M_buffer_)
32 {}
33
34 explicit stack_allocator(const stack_allocator& alloc) :
35 M_block_size_(alloc.M_block_size_),
36 M_max_objects_(alloc.M_max_objects_),
37 M_begin_(alloc.M_begin_),
38 M_end_(alloc.M_end_),
39 M_stack_pointer_(alloc.M_stack_pointer_)
40 {}
41
42 template<typename U>
43 explicit stack_allocator(const stack_allocator<U,N>& other) :
44 M_allocator_(other.M_allocator_),
45 M_block_size_(other.M_block_size_),
46 M_max_objects_(other.M_max_objects_),
47 M_begin_(other.M_begin_),
48 M_end_(other.M_end_),
49 M_stack_pointer_(other.M_stack_pointer_)
50 {}
51
52 protected:
53 void *do_allocate(std::size_t n, std::size_t alignment = alignof(std::max_align_t)) override
54 {
55 auto& free_chunks = M_free_list_[n * M_block_size_];
56 if(!free_chunks.empty()){
57 auto old_block = static_cast<void*>(free_chunks.back());
58 free_chunks.pop_back();
59 std::printf("reuse pointer: %p\n",old_block);
60 return old_block;
61 } else if(M_end_ - M_stack_pointer_ >= n * M_block_size_ + alignment){ //alignment によるオーバーフロー防止
62 M_stack_pointer_ = reinterpret_cast<std::byte*>(((unsigned long)M_stack_pointer_ + alignment - 1) & ~(alignment - 1)); //アライン処理
63 auto new_block = static_cast<void*>(M_stack_pointer_);
64 M_stack_pointer_ += n * M_block_size_;
65 M_size_map_[new_block] = n * M_block_size_;
66 std::printf("allocate on stack: %p\n",new_block);
67 return new_block;
68 } else {
69 std::printf("allocate on heap\n");
70 return static_cast<pointer>(std::aligned_alloc(alignment,n * M_block_size_));
71 }
72 }
73
74 void do_deallocate(void *p, size_t n, std::size_t alignment = alignof(std::max_align_t)) override
75 {
76 auto chunk_size = M_size_map_[(void*)p];
77 if(internal_buffer(p) || chunk_size != 0){
78 M_free_list_[chunk_size].push_back((void*)p);
79 } else {
80 std::free(p);
81 }
82 }
83
84 bool do_is_equal(std::experimental::pmr::memory_resource const & other) const noexcept override
85 {
86 return this == &other;
87 }
88
89 private:
90 bool internal_buffer(void* p) const {
91 return (M_begin_ <= p && p <= M_end_);
92 }
93
94 allocator_t M_allocator_;
95 free_list_t M_free_list_;
96 size_map_t M_size_map_;
97
98 std::byte M_buffer_[N * (sizeof(T) < 8 ? sizeof(long long) : sizeof(T))];
99 const size_type M_block_size_;
100 const size_type M_max_objects_;
101 size_type M_remaining_;
102
103 std::byte* M_begin_;
104 std::byte* M_end_;
105 std::byte* M_stack_pointer_;
106 };
107
108 int main()
109 {
110 std::printf("alignment default: %lu\n",alignof(std::max_align_t));
111
112 stack_allocator<int,128> alloc;
113 void* ptr[5];
114
115 for(int i = 0; i < 5; ++i){
116 ptr[i] = alloc.allocate(1,256);
117 }
118 for(int i = 0; i < 5; ++i){
119 alloc.deallocate(ptr[i],1);
120 }
121 for(int i = 0; i < 5; ++i){
122 ptr[i] = alloc.allocate(1,256);
123 }
124
125 std::cout << "===== vector =====" << '\n';
126
127 std::experimental::pmr::vector<int> vec({1},&alloc);
128 vec.push_back(10);
129 vec.push_back(20);
130 vec.pop_back();
131 vec.push_back(30);
132
133 std::cout << &vec.back() << '\n';
134
135 return 0;
136 }
ビルドと実行結果.
$ g++ main.cpp -std=c++17 $ ./a.out alignment default: 16 allocate on stack: 0x7ffca65c8500 allocate on stack: 0x7ffca65c8600 allocate on stack: 0x7ffca65c8700 allocate on stack: 0x7ffca65c8800 allocate on heap reuse pointer: 0x7ffca65c8800 reuse pointer: 0x7ffca65c8700 reuse pointer: 0x7ffca65c8600 reuse pointer: 0x7ffca65c8500 allocate on heap ===== vector ===== allocate on stack: 0x7ffca65c8808 allocate on stack: 0x7ffca65c8828 allocate on heap 0x55c3b7459868
この実装では memory_resource の継承の問題も浮き彫りにしています。
例えば allocate() 関数が do_allocate() 関数をコールしてメモリー領域を確保しているわけですが、返ってくるのは void ポインターになります。
まあ大した問題じゃないですけど、そうすると割り当て型の指定は何だったのか… てな疑問はわいてきます。
53 void *do_allocate(std::size_t n, std::size_t alignment = alignof(std::max_align_t)) override
54 {
55 auto& free_chunks = M_free_list_[n * M_block_size_];
56 if(!free_chunks.empty()){
57 auto old_block = static_cast<void*>(free_chunks.back());
58 free_chunks.pop_back();
59 std::printf("reuse pointer: %p\n",old_block);
60 return old_block;
61 } else if(M_end_ - M_stack_pointer_ >= n * M_block_size_ + alignment){ //alignment によるオーバーフロー防止
62 M_stack_pointer_ = reinterpret_cast<std::byte*>(((unsigned long)M_stack_pointer_ + alignment - 1) & ~(alignment - 1)); //アライン処理
63 auto new_block = static_cast<void*>(M_stack_pointer_);
64 M_stack_pointer_ += n * M_block_size_;
65 M_size_map_[new_block] = n * M_block_size_;
66 std::printf("allocate on stack: %p\n",new_block);
67 return new_block;
68 } else {
69 std::printf("allocate on heap\n");
70 return static_cast<pointer>(std::aligned_alloc(alignment,n * M_block_size_));
71 }
72 }スタックアロケーターにちょっと変更を加えた程度の実装なので、この本をここまで写経してきた人なら慣れ親しんだ内容かもしれないです。
アラインメントのためにスタックアロケーターで使っていたコードに加えた変更は以下の 2 行です。
61 } else if(M_end_ - M_stack_pointer_ >= n * M_block_size_ + alignment){ //alignment によるオーバーフロー防止
62 M_stack_pointer_ = reinterpret_cast<std::byte*>(((unsigned long)M_stack_pointer_ + alignment - 1) & ~(alignment - 1)); //アライン処理if 文内の条件式は単に alignment 値をリクエストされたブロックサイズに加算することで、オーバーフローがおきないようにガードしています。
後は M_stack_pointer_ 変数はアラインの計算と reinterpret_cast をしています。
まあ特筆すべき点はこんだけです。
後は memory_resource のインターフェースに合わせるために do_allocate() 関数をオーバーライドしているくらいですかね。
Copyright 2018-2019, by Masaki Komatsu