Stan Math Library  2.20.0
reverse mode automatic differentiation
stack_alloc.hpp
Go to the documentation of this file.
1 #ifndef STAN_MATH_MEMORY_STACK_ALLOC_HPP
2 #define STAN_MATH_MEMORY_STACK_ALLOC_HPP
3 
4 // TODO(Bob): <cstddef> replaces this ifdef in C++11, until then this
5 // is best we can do to get safe pointer casts to uints.
6 #include <stdint.h>
8 #include <cstdlib>
9 #include <cstddef>
10 #include <sstream>
11 #include <stdexcept>
12 #include <vector>
13 
14 namespace stan {
15 namespace math {
16 
28 template <typename T>
29 bool is_aligned(T* ptr, unsigned int bytes_aligned) {
30  return (reinterpret_cast<uintptr_t>(ptr) % bytes_aligned) == 0U;
31 }
32 
33 namespace internal {
34 const size_t DEFAULT_INITIAL_NBYTES = 1 << 16; // 64KB
35 
36 // FIXME: enforce alignment
37 // big fun to inline, but only called twice
38 inline char* eight_byte_aligned_malloc(size_t size) {
39  char* ptr = static_cast<char*>(malloc(size));
40  if (!ptr)
41  return ptr; // malloc failed to alloc
42  if (!is_aligned(ptr, 8U)) {
43  std::stringstream s;
44  s << "invalid alignment to 8 bytes, ptr="
45  << reinterpret_cast<uintptr_t>(ptr) << std::endl;
46  throw std::runtime_error(s.str());
47  }
48  return ptr;
49 }
50 } // namespace internal
51 
71 class stack_alloc {
72  private:
73  std::vector<char*> blocks_; // storage for blocks,
74  // may be bigger than cur_block_
75  std::vector<size_t> sizes_; // could store initial & shift for others
76  size_t cur_block_; // index into blocks_ for next alloc
77  char* cur_block_end_; // ptr to cur_block_ptr_ + sizes_[cur_block_]
78  char* next_loc_; // ptr to next available spot in cur
79  // block
80  // next three for keeping track of nested allocations on top of stack:
81  std::vector<size_t> nested_cur_blocks_;
82  std::vector<char*> nested_next_locs_;
83  std::vector<char*> nested_cur_block_ends_;
84 
93  char* move_to_next_block(size_t len) {
94  char* result;
95  ++cur_block_;
96  // Find the next block (if any) containing at least len bytes.
97  while ((cur_block_ < blocks_.size()) && (sizes_[cur_block_] < len))
98  ++cur_block_;
99  // Allocate a new block if necessary.
100  if (unlikely(cur_block_ >= blocks_.size())) {
101  // New block should be max(2*size of last block, len) bytes.
102  size_t newsize = sizes_.back() * 2;
103  if (newsize < len)
104  newsize = len;
105  blocks_.push_back(internal::eight_byte_aligned_malloc(newsize));
106  if (!blocks_.back())
107  throw std::bad_alloc();
108  sizes_.push_back(newsize);
109  }
110  result = blocks_[cur_block_];
111  // Get the object's state back in order.
112  next_loc_ = result + len;
113  cur_block_end_ = result + sizes_[cur_block_];
114  return result;
115  }
116 
117  public:
127  explicit stack_alloc(size_t initial_nbytes = internal::DEFAULT_INITIAL_NBYTES)
128  : blocks_(1, internal::eight_byte_aligned_malloc(initial_nbytes)),
129  sizes_(1, initial_nbytes),
130  cur_block_(0),
131  cur_block_end_(blocks_[0] + initial_nbytes),
132  next_loc_(blocks_[0]) {
133  if (!blocks_[0])
134  throw std::bad_alloc(); // no msg allowed in bad_alloc ctor
135  }
136 
144  // free ALL blocks
145  for (auto& block : blocks_)
146  if (block)
147  free(block);
148  }
149 
162  inline void* alloc(size_t len) {
163  // Typically, just return and increment the next location.
164  char* result = next_loc_;
165  next_loc_ += len;
166  // Occasionally, we have to switch blocks.
167  if (unlikely(next_loc_ >= cur_block_end_))
168  result = move_to_next_block(len);
169  return reinterpret_cast<void*>(result);
170  }
171 
180  template <typename T>
181  inline T* alloc_array(size_t n) {
182  return static_cast<T*>(alloc(n * sizeof(T)));
183  }
184 
191  inline void recover_all() {
192  cur_block_ = 0;
193  next_loc_ = blocks_[0];
194  cur_block_end_ = next_loc_ + sizes_[0];
195  }
196 
201  inline void start_nested() {
202  nested_cur_blocks_.push_back(cur_block_);
203  nested_next_locs_.push_back(next_loc_);
204  nested_cur_block_ends_.push_back(cur_block_end_);
205  }
206 
210  inline void recover_nested() {
211  if (unlikely(nested_cur_blocks_.empty()))
212  recover_all();
213 
214  cur_block_ = nested_cur_blocks_.back();
215  nested_cur_blocks_.pop_back();
216 
217  next_loc_ = nested_next_locs_.back();
218  nested_next_locs_.pop_back();
219 
220  cur_block_end_ = nested_cur_block_ends_.back();
221  nested_cur_block_ends_.pop_back();
222  }
223 
229  inline void free_all() {
230  // frees all BUT the first (index 0) block
231  for (size_t i = 1; i < blocks_.size(); ++i)
232  if (blocks_[i])
233  free(blocks_[i]);
234  sizes_.resize(1);
235  blocks_.resize(1);
236  recover_all();
237  }
238 
249  inline size_t bytes_allocated() const {
250  size_t sum = 0;
251  for (size_t i = 0; i <= cur_block_; ++i) {
252  sum += sizes_[i];
253  }
254  return sum;
255  }
256 
265  inline bool in_stack(const void* ptr) const {
266  for (size_t i = 0; i < cur_block_; ++i)
267  if (ptr >= blocks_[i] && ptr < blocks_[i] + sizes_[i])
268  return true;
269  if (ptr >= blocks_[cur_block_] && ptr < next_loc_)
270  return true;
271  return false;
272  }
273 };
274 
275 } // namespace math
276 } // namespace stan
277 #endif
fvar< T > sum(const std::vector< fvar< T > > &m)
Return the sum of the entries of the specified standard vector.
Definition: sum.hpp:20
size_t bytes_allocated() const
Return number of bytes allocated to this instance by the heap.
~stack_alloc()
Destroy this memory allocator.
void recover_nested()
recover memory back to the last start_nested call.
char * eight_byte_aligned_malloc(size_t size)
Definition: stack_alloc.hpp:38
void free_all()
Free all memory used by the stack allocator other than the initial block allocation back to the syste...
void recover_all()
Recover all the memory used by the stack allocator.
#define unlikely(x)
Definition: likely.hpp:9
bool in_stack(const void *ptr) const
Indicates whether the memory in the pointer is in the stack.
T * alloc_array(size_t n)
Allocate an array on the arena of the specified size to hold values of the specified template paramet...
stack_alloc(size_t initial_nbytes=internal::DEFAULT_INITIAL_NBYTES)
Construct a resizable stack allocator initially holding the specified number of bytes.
int size(const std::vector< T > &x)
Return the size of the specified standard vector.
Definition: size.hpp:17
void start_nested()
Store current positions before doing nested operation so can recover back to start.
bool is_aligned(T *ptr, unsigned int bytes_aligned)
Return true if the specified pointer is aligned on the number of bytes.
Definition: stack_alloc.hpp:29
Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > block(const Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > &m, size_t i, size_t j, size_t nrows, size_t ncols)
Return a nrows x ncols submatrix starting at (i-1, j-1).
Definition: block.hpp:22
const size_t DEFAULT_INITIAL_NBYTES
Definition: stack_alloc.hpp:34
An instance of this class provides a memory pool through which blocks of raw memory may be allocated ...
Definition: stack_alloc.hpp:71
void * alloc(size_t len)
Return a newly allocated block of memory of the appropriate size managed by the stack allocator...

     [ Stan Home Page ] © 2011–2018, Stan Development Team.