第90章 コードをシンプルにする(内部バッファーのアドレスかのチェック)

 スタック領域にメモリーを解放する場合は、ポインターが内部バッファーにあるかのチェックが必要な場合があります。

 例えば以下のようなケースですかね。

 前の項目の例では、力技で乗り切った部分がありましたが、実際

 この基準にあうのであれば、アドレス領域がスタック領域内で定義した内部バッファーにアドレスがあるかチェックするようにしたほうが良いです。

 さらにフォールバックを行うには std::allocator<T> を使えるようにしたいです。

 内部バッファーのアドレスかのチェックは、かなり定型化しているのですが、以下のようになるかと思います。

147   bool internal_buffer(const_pointer p) const
148   {
149     return ((const_pointer)M_begin_ <= p && p <= (const_pointer)M_end_);
150   }

 この internal_buffer() 関数がやってるのはポインター p が M_begin_ と M_end_ の範囲内にあるかというチェックです。

 そして、もしこの internal_buffer() の返す値が偽ならば、 std::allocator<T> へフォールバックするというのが一般的な実装方法かと思いまする。

 ではサンプルコードを見てみましょう。

main.cpp. 

  1 #include <memory>
  2 #include <vector>
  3 #include <iostream>
  4 #include <cassert>
  5 #include <cstddef>
  6 #include <map>
  7
  8 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
  9 class stack_allocator
 10 {
 11 public:
 12   typedef typename std::allocator_traits<Allocator>::value_type value_type;
 13   typedef typename std::allocator_traits<Allocator>::pointer pointer;
 14   typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
 15   typedef typename std::allocator_traits<Allocator>::size_type size_type;
 16   typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
 17   typedef typename std::allocator_traits<Allocator>::void_pointer void_pointer;
 18   typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
 19   typedef typename Allocator::reference reference;
 20   typedef typename Allocator::const_reference const_reference;
 21
 22   typedef std::map<void*,size_t> size_map_t;
 23   typedef std::map<size_t,std::vector<void*>> free_list_t;
 24   typedef std::byte byte;
 25
 26   typedef Allocator allocator_type;
 27
 28   explicit stack_allocator(const allocator_type& alloc = allocator_type())
 29     : M_allocator_(alloc),
 30     M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
 31     M_max_objects_(N),
 32     M_begin_(M_buffer_),
 33     M_end_(M_buffer_+M_block_size_*M_max_objects_),
 34     M_stack_pointer_(M_buffer_)
 35   {}
 36
 37   template<typename U>
 38   stack_allocator(const stack_allocator<U,N,Allocator>& other)
 39     : M_allocator_(other.M_allocator_),
 40     M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
 41     M_max_objects_(N),
 42     M_begin_(other.M_begin_),
 43     M_end_(other.M_end_),
 44     M_stack_pointer_(other.M_stack_pointer_)
 45   {}
 46
 47   template<typename U>
 48   struct rebind
 49   {
 50     typedef stack_allocator<U,N,allocator_type> other;
 51   };
 52
 53   pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
 54   {
 55     auto& free_chunks = M_free_list_[n * M_block_size_];
 56     if(!free_chunks.empty()){
 57       std::cout << "reuse pointer" << '\n';
 58       auto old_block = static_cast<T*>(free_chunks.back());
 59       free_chunks.pop_back();
 60       return old_block;
 61     } else if(M_end_ - M_stack_pointer_ >= n * M_block_size_) {
 62       std::cout << "allocate on the stack" << '\n';
 63       pointer new_block = reinterpret_cast<pointer>(M_stack_pointer_);
 64       M_stack_pointer_ += n * M_block_size_;
 65       M_size_map_[new_block] = n * M_block_size_;
 66       return new_block;
 67     } else {
 68       std::cout << "allocate on the heap" << '\n';
 69       return M_allocator_.allocate(n,hint);
 70     }
 71   }
 72
 73   void deallocate(pointer p, size_type n)
 74   {
 75     auto chunk_size = M_size_map_[(void*)p];
 76     if(internal_buffer(p) || chunk_size != 0)
 77     {
 78       M_free_list_[chunk_size].push_back((void*)p);
 79       std::cout << "deallocate on the stack" << '\n';
 80     } else {
 81       M_allocator_.deallocate(p,n);
 82       std::cout << "deallocate on the heap" << '\n';
 83     }
 84   }
 85
 86   size_type max_size() const noexcept
 87   {
 88     return (size_type)(~0) / sizeof(T);
 89   }
 90
 91   template<typename U, typename... Args>
 92   void construct(U* p, Args&&... args)
 93   {
 94     if(internal_buffer(p)) {
 95       std::cout << "internal buffer construct" << '\n';
 96       ::new ((void*)p) T(args...);
 97     } else {
 98       std::cout << "construct on the heap" << '\n';
 99       M_allocator_.construct(p,std::forward<Args>(args)...);
100     }
101   }
102
103   template<typename U>
104   void destroy(U* p)
105   {
106     if(internal_buffer(p)) {
107       std::cout << "internal buffer destroy" << '\n';
108       p->~T();
109     } else {
110       std::cout << "destroy the heap object" << '\n';
111       M_allocator_.destroy(p);
112     }
113   }
114
115   pointer address(reference x) const noexcept
116   {
117     if(internal_buffer(std::addressof(x)))
118     {
119       return std::addressof(x);
120     }
121
122     return M_allocator_.address(x);
123   }
124
125   const_pointer address(const_reference x) const noexcept
126   {
127     if(internal_buffer(std::addressof(x)))
128     {
129       return addressof(x);
130     }
131
132     return M_allocator_.address(x);
133   }
134
135   pointer buffer() const noexcept
136   {
137     return M_begin_;
138   }
139
140   constexpr static size_type capacity()
141   {
142     return N;
143   }
144
145 private:
146
147   bool internal_buffer(const_pointer p) const
148   {
149     return ((const_pointer)M_begin_ <= p && p <= (const_pointer)M_end_);
150   }
151
152   allocator_type M_allocator_;
153   size_map_t M_size_map_;
154   free_list_t M_free_list_;
155   byte M_buffer_[N*(sizeof(T) < 8 ? sizeof(long long) : sizeof(T))];
156   size_type M_block_size_;
157   size_type M_max_objects_;
158
159   byte* M_begin_;
160   byte* M_end_;
161   byte* M_stack_pointer_;
162 };
163
164 template<typename T1, std::size_t N, typename Allocator, typename T2>
165 bool operator==(const stack_allocator<T1,N,Allocator>& lhs, const stack_allocator<T2,N,Allocator>& rhs) noexcept
166 {
167   return lhs.buffer() == rhs.buffer();
168 }
169
170 template<typename T1, std::size_t N, typename Allocator, typename T2>
171 bool operator!=(const stack_allocator<T1,N,Allocator>& lhs, const stack_allocator<T2,N,Allocator>& rhs) noexcept
172 {
173   return !(lhs == rhs);
174 }
175
176 const std::size_t stack_size = 8;
177
178 int main()
179 {
180   typedef stack_allocator<int,stack_size> allocator_type;
181   allocator_type alloc;
182   int* t = alloc.allocate(1);
183   alloc.construct(t,100);
184   std::cout << *t << '\n';
185   alloc.destroy(t);
186   alloc.deallocate(t,1);
187
188   int* data[15];
189
190   for(int i = 0; i < 5; ++i){
191     data[i] = alloc.allocate(1);
192   }
193   for(int i = 1; i < 5; ++i){
194     alloc.deallocate(data[i],1);
195   }
196
197   for(int i = 5; i < 15; ++i){
198     data[i] = alloc.allocate(1);
199   }
200
201   for(int i = 5; i < 15; ++i){
202     alloc.deallocate(data[i],1);
203   }
204
205   alloc.deallocate(data[0],1);
206
207   return 0;
208 }

ビルドと実行結果. 

$ g++ main.cpp -std=c++17
$ ./a.out
allocate on the stack
internal buffer construct
100
internal buffer destroy
deallocate on the stack
reuse pointer
allocate on the stack
allocate on the stack
allocate on the stack
allocate on the stack
deallocate on the stack
deallocate on the stack
deallocate on the stack
deallocate on the stack
reuse pointer
reuse pointer
reuse pointer
reuse pointer
allocate on the stack
allocate on the stack
allocate on the stack
allocate on the heap
allocate on the heap
allocate on the heap
deallocate on the stack
deallocate on the stack
deallocate on the stack
deallocate on the stack
deallocate on the stack
deallocate on the stack
deallocate on the stack
deallocate on the heap
deallocate on the heap
deallocate on the heap
deallocate on the stack

 まずはクラス内のメンバー型とメンバーオブジェクト・変数から見ていきましょう。

  8 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
  9 class stack_allocator
 10 {
 11 public:
 12   typedef typename std::allocator_traits<Allocator>::value_type value_type;
 13   typedef typename std::allocator_traits<Allocator>::pointer pointer;
 14   typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
 15   typedef typename std::allocator_traits<Allocator>::size_type size_type;
 16   typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
 17   typedef typename std::allocator_traits<Allocator>::void_pointer void_pointer;
 18   typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
 19   typedef typename Allocator::reference reference;
 20   typedef typename Allocator::const_reference const_reference;
 21
 22   typedef std::map<void*,size_t> size_map_t;
 23   typedef std::map<size_t,std::vector<void*>> free_list_t;
 24   typedef std::byte byte;
 25
 26   typedef Allocator allocator_type;

 //   中略

152   allocator_type M_allocator_;
153   size_map_t M_size_map_;
154   free_list_t M_free_list_;
155   byte M_buffer_[N*(sizeof(T) < 8 ? sizeof(long long) : sizeof(T))];
156   size_type M_block_size_;
157   size_type M_max_objects_;
158
159   byte* M_begin_;
160   byte* M_end_;
161   byte* M_stack_pointer_;
162 };

 この中で内部バッファーの範囲を定義するのは M_begin_ と M_end_ です。

 後は M_buffer_ がベースとなるデータを保管してくれるスタック領域のバッファーです。

 28   explicit stack_allocator(const allocator_type& alloc = allocator_type())
 29     : M_allocator_(alloc),
 30     M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
 31     M_max_objects_(N),
 32     M_begin_(M_buffer_),
 33     M_end_(M_buffer_+M_block_size_*M_max_objects_),
 34     M_stack_pointer_(M_buffer_)
 35   {}

 コンストラクターでは M_begin_ を M_buffer_ に設定しています。

 まあ M_buffer_ はスタックバッファーの開始アドレスを指すポインターなので、これが開始点となるのはご依存ないですよね?

 次に M_end_ には 「 M_buffer_+M_block_size_*M_max_objects_ 」が代入されます。

 まあこれも M_buffer_ に M_buffer_ のバイトサイズを加算しているので、終端を指すポインターになるだけです。

 この内部バッファーチェックを使っている箇所が以下の deallocate() 関数です。

 73   void deallocate(pointer p, size_type n)
 74   {
 75     auto chunk_size = M_size_map_[(void*)p];
 76     if(internal_buffer(p) || chunk_size != 0)
 77     {
 78       M_free_list_[chunk_size].push_back((void*)p);
 79       std::cout << "deallocate on the stack" << '\n';
 80     } else {
 81       M_allocator_.deallocate(p,n);
 82       std::cout << "deallocate on the heap" << '\n';
 83     }
 84   }

 p が内部バッファーにないか、フリーチャンクが存在しない場合は標準アロケーターにフォールバックしていますね。

 まあ、こんな感じで内部バッファーのチェックを行うと良いかと思います。

 筆者は時間が無かったのと、説明するときのコードはキレイよりベタな方が良さそうという、その場のノリで、あまりチェックはしていないです。

 まあそれと、書くのも時間かかりますんでご理解賜りたいものです… (´・ω・`)

Copyright 2018-2019, by Masaki Komatsu