FST  openfst-1.7.1
OpenFst Library
memory.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // FST memory utilities.
5 
6 #ifndef FST_MEMORY_H_
7 #define FST_MEMORY_H_
8 
9 #include <list>
10 #include <memory>
11 #include <utility>
12 #include <vector>
13 
14 #include <fst/types.h>
15 #include <fst/log.h>
16 #include <fstream>
17 
18 namespace fst {
19 
20 // Default block allocation size.
21 constexpr int kAllocSize = 64;
22 
23 // Minimum number of allocations per block.
24 constexpr int kAllocFit = 4;
25 
26 // Base class for MemoryArena that allows (e.g.) MemoryArenaCollection to
27 // easily manipulate collections of variously sized arenas.
29  public:
30  virtual ~MemoryArenaBase() {}
31  virtual size_t Size() const = 0;
32 };
33 
34 namespace internal {
35 
36 // Allocates 'size' unintialized memory chunks of size object_size from
37 // underlying blocks of (at least) size 'block_size * object_size'.
38 // All blocks are freed when this class is deleted. Result of allocate() will
39 // be aligned to object_size.
40 template <size_t object_size>
42  public:
43  enum { kObjectSize = object_size };
44 
45  explicit MemoryArenaImpl(size_t block_size = kAllocSize)
46  : block_size_(block_size * kObjectSize), block_pos_(0) {
47  blocks_.emplace_front(new char[block_size_]);
48  }
49 
50  void *Allocate(size_t size) {
51  const auto byte_size = size * kObjectSize;
52  if (byte_size * kAllocFit > block_size_) {
53  // Large block; adds new large block.
54  auto *ptr = new char[byte_size];
55  blocks_.emplace_back(ptr);
56  return ptr;
57  }
58  if (block_pos_ + byte_size > block_size_) {
59  // Doesn't fit; adds new standard block.
60  auto *ptr = new char[block_size_];
61  block_pos_ = 0;
62  blocks_.emplace_front(ptr);
63  }
64  // Fits; uses current block.
65  auto *ptr = blocks_.front().get() + block_pos_;
66  block_pos_ += byte_size;
67  return ptr;
68  }
69 
70  size_t Size() const override { return kObjectSize; }
71 
72  private:
73  const size_t block_size_; // Default block size in bytes.
74  size_t block_pos_; // Current position in block in bytes.
75  std::list<std::unique_ptr<char[]>> blocks_; // List of allocated blocks.
76 };
77 
78 } // namespace internal
79 
80 template <typename T>
82 
83 // Base class for MemoryPool that allows (e.g.) MemoryPoolCollection to easily
84 // manipulate collections of variously sized pools.
86  public:
87  virtual ~MemoryPoolBase() {}
88  virtual size_t Size() const = 0;
89 };
90 
91 namespace internal {
92 
93 // Allocates and frees initially uninitialized memory chunks of size
94 // object_size. Keeps an internal list of freed chunks that are reused (as is)
95 // on the next allocation if available. Chunks are constructed in blocks of size
96 // 'pool_size'.
97 template <size_t object_size>
99  public:
100  enum { kObjectSize = object_size };
101 
102  struct Link {
103  char buf[kObjectSize];
105  };
106 
107  explicit MemoryPoolImpl(size_t pool_size)
108  : mem_arena_(pool_size), free_list_(nullptr) {}
109 
110  void *Allocate() {
111  if (free_list_ == nullptr) {
112  auto *link = static_cast<Link *>(mem_arena_.Allocate(1));
113  link->next = nullptr;
114  return link;
115  } else {
116  auto *link = free_list_;
117  free_list_ = link->next;
118  return link;
119  }
120  }
121 
122  void Free(void *ptr) {
123  if (ptr) {
124  auto *link = static_cast<Link *>(ptr);
125  link->next = free_list_;
126  free_list_ = link;
127  }
128  }
129 
130  size_t Size() const override { return kObjectSize; }
131 
132  private:
133  MemoryArena<Link> mem_arena_;
134  Link *free_list_;
135 
136  MemoryPoolImpl(const MemoryPoolImpl &) = delete;
137  MemoryPoolImpl &operator=(const MemoryPoolImpl &) = delete;
138 };
139 
140 } // namespace internal
141 
142 // Allocates and frees initially uninitialized memory chunks of size sizeof(T).
143 // All memory is freed when the class is deleted. The result of Allocate() will
144 // be suitably memory-aligned. Combined with placement operator new and destroy
145 // functions for the T class, this can be used to improve allocation efficiency.
146 // See nlp/fst/lib/visit.h (global new) and nlp/fst/lib/dfs-visit.h (class new)
147 // for examples.
148 template <typename T>
149 class MemoryPool : public internal::MemoryPoolImpl<sizeof(T)> {
150  public:
151  // 'pool_size' specifies the size of the initial pool and how it is extended.
152  MemoryPool(size_t pool_size = kAllocSize)
153  : internal::MemoryPoolImpl<sizeof(T)>(pool_size) {}
154 };
155 
156 // Stores a collection of memory arenas.
158  public:
159  // 'block_size' specifies the block size of the arenas.
160  explicit MemoryArenaCollection(size_t block_size = kAllocSize)
161  : block_size_(block_size), ref_count_(1) {}
162 
163  template <typename T>
165  if (sizeof(T) >= arenas_.size()) arenas_.resize(sizeof(T) + 1);
166  MemoryArenaBase *arena = arenas_[sizeof(T)].get();
167  if (arena == nullptr) {
168  arena = new MemoryArena<T>(block_size_);
169  arenas_[sizeof(T)].reset(arena);
170  }
171  return static_cast<MemoryArena<T> *>(arena);
172  }
173 
174  size_t BlockSize() const { return block_size_; }
175 
176  size_t RefCount() const { return ref_count_; }
177 
178  size_t IncrRefCount() { return ++ref_count_; }
179 
180  size_t DecrRefCount() { return --ref_count_; }
181 
182  private:
183  size_t block_size_;
184  size_t ref_count_;
185  std::vector<std::unique_ptr<MemoryArenaBase>> arenas_;
186 };
187 
188 // Stores a collection of memory pools
190  public:
191  // 'pool_size' specifies the size of initial pool and how it is extended.
192  explicit MemoryPoolCollection(size_t pool_size = kAllocSize)
193  : pool_size_(pool_size), ref_count_(1) {}
194 
195  template <typename T>
197  if (sizeof(T) >= pools_.size()) pools_.resize(sizeof(T) + 1);
198  MemoryPoolBase *pool = pools_[sizeof(T)].get();
199  if (pool == nullptr) {
200  pool = new MemoryPool<T>(pool_size_);
201  pools_[sizeof(T)].reset(pool);
202  }
203  return static_cast<MemoryPool<T> *>(pool);
204  }
205 
206  size_t PoolSize() const { return pool_size_; }
207 
208  size_t RefCount() const { return ref_count_; }
209 
210  size_t IncrRefCount() { return ++ref_count_; }
211 
212  size_t DecrRefCount() { return --ref_count_; }
213 
214  private:
215  size_t pool_size_;
216  size_t ref_count_;
217  std::vector<std::unique_ptr<MemoryPoolBase>> pools_;
218 };
219 
220 // STL allocator using memory arenas. Memory is allocated from underlying
221 // blocks of size 'block_size * sizeof(T)'. Memory is freed only when all
222 // objects using this allocator are destroyed and there is otherwise no reuse
223 // (unlike PoolAllocator).
224 //
225 // This allocator has object-local state so it should not be used with splicing
226 // or swapping operations between objects created with different allocators nor
227 // should it be used if copies must be thread-safe. The result of allocate()
228 // will be suitably memory-aligned.
229 template <typename T>
231  public:
232  using Allocator = std::allocator<T>;
233  using size_type = typename Allocator::size_type;
234  using difference_type = typename Allocator::difference_type;
235  using pointer = typename Allocator::pointer;
236  using const_pointer = typename Allocator::const_pointer;
237  using reference = typename Allocator::reference;
238  using const_reference = typename Allocator::const_reference;
239  using value_type = typename Allocator::value_type;
240 
241  template <typename U>
242  struct rebind {
244  };
245 
246  explicit BlockAllocator(size_t block_size = kAllocSize)
247  : arenas_(new MemoryArenaCollection(block_size)) {}
248 
249  BlockAllocator(const BlockAllocator<T> &arena_alloc)
250  : arenas_(arena_alloc.Arenas()) {
251  Arenas()->IncrRefCount();
252  }
253 
254  template <typename U>
255  explicit BlockAllocator(const BlockAllocator<U> &arena_alloc)
256  : arenas_(arena_alloc.Arenas()) {
257  Arenas()->IncrRefCount();
258  }
259 
261  if (Arenas()->DecrRefCount() == 0) delete Arenas();
262  }
263 
264  pointer address(reference ref) const { return Allocator().address(ref); }
265 
267  return Allocator().address(ref);
268  }
269 
270  size_type max_size() const { return Allocator().max_size(); }
271 
272  template <class U, class... Args>
273  void construct(U *p, Args &&... args) {
274  Allocator().construct(p, std::forward<Args>(args)...);
275  }
276 
277  void destroy(pointer p) { Allocator().destroy(p); }
278 
279  pointer allocate(size_type n, const void *hint = nullptr) {
280  if (n * kAllocFit <= kAllocSize) {
281  return static_cast<pointer>(Arena()->Allocate(n));
282  } else {
283  return Allocator().allocate(n, hint);
284  }
285  }
286 
288  if (n * kAllocFit > kAllocSize) Allocator().deallocate(p, n);
289  }
290 
291  MemoryArenaCollection *Arenas() const { return arenas_; }
292 
293  private:
294  MemoryArena<T> *Arena() { return arenas_->Arena<T>(); }
295 
296  MemoryArenaCollection *arenas_;
297 
298  BlockAllocator<T> operator=(const BlockAllocator<T> &);
299 };
300 
301 template <typename T, typename U>
302 bool operator==(const BlockAllocator<T> &alloc1,
303  const BlockAllocator<U> &alloc2) {
304  return false;
305 }
306 
307 template <typename T, typename U>
308 bool operator!=(const BlockAllocator<T> &alloc1,
309  const BlockAllocator<U> &alloc2) {
310  return true;
311 }
312 
313 // STL allocator using memory pools. Memory is allocated from underlying
314 // blocks of size 'block_size * sizeof(T)'. Keeps an internal list of freed
315 // chunks thare are reused on the next allocation.
316 //
317 // This allocator has object-local state so it should not be used with splicing
318 // or swapping operations between objects created with different allocators nor
319 // should it be used if copies must be thread-safe. The result of allocate()
320 // will be suitably memory-aligned.
321 template <typename T>
323  public:
324  using Allocator = std::allocator<T>;
325  using size_type = typename Allocator::size_type;
326  using difference_type = typename Allocator::difference_type;
327  using pointer = typename Allocator::pointer;
328  using const_pointer = typename Allocator::const_pointer;
329  using reference = typename Allocator::reference;
330  using const_reference = typename Allocator::const_reference;
331  using value_type = typename Allocator::value_type;
332 
333  template <typename U>
334  struct rebind {
336  };
337 
338  explicit PoolAllocator(size_t pool_size = kAllocSize)
339  : pools_(new MemoryPoolCollection(pool_size)) {}
340 
341  PoolAllocator(const PoolAllocator<T> &pool_alloc)
342  : pools_(pool_alloc.Pools()) {
343  Pools()->IncrRefCount();
344  }
345 
346  template <typename U>
347  explicit PoolAllocator(const PoolAllocator<U> &pool_alloc)
348  : pools_(pool_alloc.Pools()) {
349  Pools()->IncrRefCount();
350  }
351 
353  if (Pools()->DecrRefCount() == 0) delete Pools();
354  }
355 
356  pointer address(reference ref) const { return Allocator().address(ref); }
357 
359  return Allocator().address(ref);
360  }
361 
362  size_type max_size() const { return Allocator().max_size(); }
363 
364  template <class U, class... Args>
365  void construct(U *p, Args &&... args) {
366  Allocator().construct(p, std::forward<Args>(args)...);
367  }
368 
369  void destroy(pointer p) { Allocator().destroy(p); }
370 
371  pointer allocate(size_type n, const void *hint = nullptr) {
372  if (n == 1) {
373  return static_cast<pointer>(Pool<1>()->Allocate());
374  } else if (n == 2) {
375  return static_cast<pointer>(Pool<2>()->Allocate());
376  } else if (n <= 4) {
377  return static_cast<pointer>(Pool<4>()->Allocate());
378  } else if (n <= 8) {
379  return static_cast<pointer>(Pool<8>()->Allocate());
380  } else if (n <= 16) {
381  return static_cast<pointer>(Pool<16>()->Allocate());
382  } else if (n <= 32) {
383  return static_cast<pointer>(Pool<32>()->Allocate());
384  } else if (n <= 64) {
385  return static_cast<pointer>(Pool<64>()->Allocate());
386  } else {
387  return Allocator().allocate(n, hint);
388  }
389  }
390 
392  if (n == 1) {
393  Pool<1>()->Free(p);
394  } else if (n == 2) {
395  Pool<2>()->Free(p);
396  } else if (n <= 4) {
397  Pool<4>()->Free(p);
398  } else if (n <= 8) {
399  Pool<8>()->Free(p);
400  } else if (n <= 16) {
401  Pool<16>()->Free(p);
402  } else if (n <= 32) {
403  Pool<32>()->Free(p);
404  } else if (n <= 64) {
405  Pool<64>()->Free(p);
406  } else {
407  Allocator().deallocate(p, n);
408  }
409  }
410 
411  MemoryPoolCollection *Pools() const { return pools_; }
412 
413  private:
414  template <int n>
415  struct TN {
416  T buf[n];
417  };
418 
419  template <int n>
420  MemoryPool<TN<n>> *Pool() {
421  return pools_->Pool<TN<n>>();
422  }
423 
424  MemoryPoolCollection *pools_;
425 
426  PoolAllocator<T> operator=(const PoolAllocator<T> &);
427 };
428 
429 template <typename T, typename U>
430 bool operator==(const PoolAllocator<T> &alloc1,
431  const PoolAllocator<U> &alloc2) {
432  return false;
433 }
434 
435 template <typename T, typename U>
436 bool operator!=(const PoolAllocator<T> &alloc1,
437  const PoolAllocator<U> &alloc2) {
438  return true;
439 }
440 
441 } // namespace fst
442 
443 #endif // FST_MEMORY_H_
MemoryPool< T > * Pool()
Definition: memory.h:196
BlockAllocator(const BlockAllocator< U > &arena_alloc)
Definition: memory.h:255
typename Allocator::value_type value_type
Definition: memory.h:239
typename Allocator::difference_type difference_type
Definition: memory.h:234
MemoryArenaCollection(size_t block_size=kAllocSize)
Definition: memory.h:160
void deallocate(pointer p, size_type n)
Definition: memory.h:391
size_t PoolSize() const
Definition: memory.h:206
typename Allocator::reference reference
Definition: memory.h:329
std::allocator< T > Allocator
Definition: memory.h:324
virtual size_t Size() const =0
constexpr int kAllocFit
Definition: memory.h:24
void Free(void *ptr)
Definition: memory.h:122
virtual ~MemoryPoolBase()
Definition: memory.h:87
MemoryArenaCollection * Arenas() const
Definition: memory.h:291
constexpr int kAllocSize
Definition: memory.h:21
typename Allocator::const_reference const_reference
Definition: memory.h:238
size_type max_size() const
Definition: memory.h:362
typename Allocator::pointer pointer
Definition: memory.h:327
typename Allocator::const_pointer const_pointer
Definition: memory.h:328
BlockAllocator(const BlockAllocator< T > &arena_alloc)
Definition: memory.h:249
typename Allocator::size_type size_type
Definition: memory.h:325
MemoryArenaImpl(size_t block_size=kAllocSize)
Definition: memory.h:45
size_type max_size() const
Definition: memory.h:270
void deallocate(pointer p, size_type n)
Definition: memory.h:287
pointer address(reference ref) const
Definition: memory.h:264
typename Allocator::difference_type difference_type
Definition: memory.h:326
size_t RefCount() const
Definition: memory.h:208
typename Allocator::value_type value_type
Definition: memory.h:331
bool operator==(const PdtStateTuple< S, K > &x, const PdtStateTuple< S, K > &y)
Definition: pdt.h:133
const_pointer address(const_reference ref) const
Definition: memory.h:266
MemoryPool(size_t pool_size=kAllocSize)
Definition: memory.h:152
void destroy(pointer p)
Definition: memory.h:277
const_pointer address(const_reference ref) const
Definition: memory.h:358
void * Allocate(size_t size)
Definition: memory.h:50
pointer address(reference ref) const
Definition: memory.h:356
void construct(U *p, Args &&...args)
Definition: memory.h:273
size_t RefCount() const
Definition: memory.h:176
constexpr bool operator!=(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2)
Definition: float-weight.h:119
typename Allocator::size_type size_type
Definition: memory.h:233
typename Allocator::const_reference const_reference
Definition: memory.h:330
typename Allocator::reference reference
Definition: memory.h:237
MemoryPoolImpl(size_t pool_size)
Definition: memory.h:107
pointer allocate(size_type n, const void *hint=nullptr)
Definition: memory.h:279
void destroy(pointer p)
Definition: memory.h:369
size_t Size() const override
Definition: memory.h:130
size_t Size() const override
Definition: memory.h:70
size_t BlockSize() const
Definition: memory.h:174
PoolAllocator(size_t pool_size=kAllocSize)
Definition: memory.h:338
PoolAllocator(const PoolAllocator< U > &pool_alloc)
Definition: memory.h:347
pointer allocate(size_type n, const void *hint=nullptr)
Definition: memory.h:371
MemoryPoolCollection * Pools() const
Definition: memory.h:411
void construct(U *p, Args &&...args)
Definition: memory.h:365
PoolAllocator(const PoolAllocator< T > &pool_alloc)
Definition: memory.h:341
virtual ~MemoryArenaBase()
Definition: memory.h:30
MemoryPoolCollection(size_t pool_size=kAllocSize)
Definition: memory.h:192
BlockAllocator(size_t block_size=kAllocSize)
Definition: memory.h:246
MemoryArena< T > * Arena()
Definition: memory.h:164
std::allocator< T > Allocator
Definition: memory.h:232
typename Allocator::pointer pointer
Definition: memory.h:235
typename Allocator::const_pointer const_pointer
Definition: memory.h:236