Automatic Differentiation
 
Loading...
Searching...
No Matches
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
14namespace stan {
15namespace math {
16
28template <typename T>
29STAN_STRONG_INLINE bool is_aligned(T* ptr, unsigned int bytes_aligned) {
30 return (reinterpret_cast<uintptr_t>(ptr) % bytes_aligned) == 0U;
31}
32
33namespace internal {
34const size_t DEFAULT_INITIAL_NBYTES = 1 << 16; // 64KB
35
36// FIXME: enforce alignment
37// big fun to inline, but only called twice
39 char* ptr = static_cast<char*>(malloc(size));
40 if (unlikely(!ptr)) {
41 return ptr; // malloc failed to alloc
42 } else if (unlikely(!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 } else {
48 return ptr;
49 }
50}
51
59STAN_STRONG_INLINE char* align_up(char* ptr, size_t alignment) {
60 const uintptr_t address = reinterpret_cast<uintptr_t>(ptr);
61 const uintptr_t aligned
62 = (address + alignment - 1) & ~static_cast<uintptr_t>(alignment - 1);
63 return ptr + (aligned - address);
64}
65} // namespace internal
66
85 private:
86 std::vector<char*> blocks_; // storage for blocks,
87 // may be bigger than cur_block_
88 std::vector<size_t> sizes_; // could store initial & shift for others
89 size_t cur_block_; // index into blocks_ for next alloc
90 char* cur_block_end_; // ptr to cur_block_ptr_ + sizes_[cur_block_]
91 char* next_loc_; // ptr to next available spot in cur
92 // block
93 // next three for keeping track of nested allocations on top of stack:
94 std::vector<size_t> nested_cur_blocks_;
95 std::vector<char*> nested_next_locs_;
96 std::vector<char*> nested_cur_block_ends_;
97
107 STAN_STRONG_INLINE char* move_to_next_block(size_t len, size_t alignment) {
108 // Blocks are 8 byte aligned, so leave room to align the start.
109 const size_t needed = alignment > 8 ? len + alignment - 8 : len;
110 ++cur_block_;
111 // Find the next block (if any) containing at least needed bytes.
112 while ((cur_block_ < blocks_.size()) && (sizes_[cur_block_] < needed)) {
113 ++cur_block_;
114 }
115 // Allocate a new block if necessary.
116 if (unlikely(cur_block_ >= blocks_.size())) {
117 // New block should be max(2*size of last block, needed) bytes.
118 size_t newsize = sizes_.back() * 2;
119 if (newsize < needed) {
120 newsize = needed;
121 }
123 if (!blocks_.back()) {
124 throw std::bad_alloc();
125 }
126 sizes_.push_back(newsize);
127 }
128 char* result = internal::align_up(blocks_[cur_block_], alignment);
129 // Get the object's state back in order.
130 next_loc_ = result + len;
132 return result;
133 }
134
135 public:
145 explicit stack_alloc(size_t initial_nbytes = internal::DEFAULT_INITIAL_NBYTES)
146 : blocks_(1, internal::eight_byte_aligned_malloc(initial_nbytes)),
147 sizes_(1, initial_nbytes),
148 cur_block_(0),
149 cur_block_end_(blocks_[0] + initial_nbytes),
150 next_loc_(blocks_[0]) {
151 if (!blocks_[0]) {
152 throw std::bad_alloc(); // no msg allowed in bad_alloc ctor
153 }
154 }
155
163 // free ALL blocks
164 for (auto& block : blocks_) {
165 if (block) {
166 free(block);
167 }
168 }
169 }
170
186 STAN_STRONG_INLINE void* alloc(size_t len, size_t alignment = 8) {
187 size_t pad = len % 8 == 0 ? 0 : 8 - len % 8;
188
189 // Typically, just return and increment the next location.
190 char* result
191 = alignment <= 8 ? next_loc_ : internal::align_up(next_loc_, alignment);
192 next_loc_ = result + len + pad;
193 // Occasionally, we have to switch blocks.
195 result = move_to_next_block(len + pad, alignment);
196 }
197 return reinterpret_cast<void*>(result);
198 }
199
208 template <typename T>
210 return static_cast<T*>(alloc(n * sizeof(T)));
211 }
212
219 inline void recover_all() {
220 cur_block_ = 0;
221 next_loc_ = blocks_[0];
223 }
224
229 inline void start_nested() {
231 nested_next_locs_.push_back(next_loc_);
233 }
234
238 inline void recover_nested() {
239 if (unlikely(nested_cur_blocks_.empty())) {
240 recover_all();
241 }
242
244 nested_cur_blocks_.pop_back();
245
247 nested_next_locs_.pop_back();
248
250 nested_cur_block_ends_.pop_back();
251 }
252
258 inline void free_all() {
259 // frees all BUT the first (index 0) block
260 for (size_t i = 1; i < blocks_.size(); ++i) {
261 if (blocks_[i]) {
262 free(blocks_[i]);
263 }
264 }
265 sizes_.resize(1);
266 blocks_.resize(1);
267 recover_all();
268 }
269
280 inline size_t bytes_allocated() const {
281 size_t sum = 0;
282 for (size_t i = 0; i <= cur_block_; ++i) {
283 sum += sizes_[i];
284 }
285 return sum;
286 }
287
296 inline size_t approx_bytes_used() const {
297 size_t sum = 0;
298 for (size_t i = 0; i < cur_block_; ++i) {
299 sum += sizes_[i];
300 }
301 return sum + static_cast<size_t>(next_loc_ - blocks_[cur_block_]);
302 }
303
312 inline bool in_stack(const void* ptr) const {
313 for (size_t i = 0; i < cur_block_; ++i) {
314 if (ptr >= blocks_[i] && ptr < blocks_[i] + sizes_[i]) {
315 return true;
316 }
317 }
318 if (ptr >= blocks_[cur_block_] && ptr < next_loc_) {
319 return true;
320 }
321 return false;
322 }
323};
324
325} // namespace math
326} // namespace stan
327#endif
void * alloc(size_t len, size_t alignment=8)
Return a newly allocated block of memory of the appropriate size managed by the stack allocator.
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...
std::vector< char * > blocks_
char * move_to_next_block(size_t len, size_t alignment)
Moves us to the next block of memory, allocating that block if necessary, and allocates len bytes of ...
stack_alloc(size_t initial_nbytes=internal::DEFAULT_INITIAL_NBYTES)
Construct a resizable stack allocator initially holding the specified number of bytes.
std::vector< size_t > sizes_
~stack_alloc()
Destroy this memory allocator.
std::vector< char * > nested_cur_block_ends_
void recover_nested()
recover memory back to the last start_nested call.
std::vector< size_t > nested_cur_blocks_
void start_nested()
Store current positions before doing nested operation so can recover back to start.
size_t bytes_allocated() const
Return number of bytes allocated to this instance by the heap.
std::vector< char * > nested_next_locs_
void recover_all()
Recover all the memory used by the stack allocator.
void free_all()
Free all memory used by the stack allocator other than the initial block allocation back to the syste...
size_t approx_bytes_used() const
Return the approximate number of bytes handed out through calls to alloc().
An instance of this class provides a memory pool through which blocks of raw memory may be allocated ...
#define STAN_STRONG_INLINE
#define unlikely(x)
int64_t size(const T &m)
Returns the size (number of the elements) of a matrix_cl or var_value<matrix_cl<T>>.
Definition size.hpp:19
const size_t DEFAULT_INITIAL_NBYTES
char * eight_byte_aligned_malloc(size_t size)
char * align_up(char *ptr, size_t alignment)
Return the first address at or after ptr that is aligned to alignment bytes.
auto block(T_x &&x, 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:24
bool is_aligned(T *ptr, unsigned int bytes_aligned)
Return true if the specified pointer is aligned on the number of bytes.
auto sum(const std::vector< T > &m)
Return the sum of the entries of the specified standard vector.
Definition sum.hpp:23
The lgamma implementation in stan-math is based on either the reentrant safe lgamma_r implementation ...