. /include/boost/capy /ex /recycling_memory_resource.hpp
94.92% Lines (56/59) 100.00% Functions (9/9)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
1   // 1   //
2   // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com) 2   // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3   // Copyright (c) 2026 Michael Vandeberg 3   // Copyright (c) 2026 Michael Vandeberg
4   // 4   //
5   // Distributed under the Boost Software License, Version 1.0. (See accompanying 5   // Distributed under the Boost Software License, Version 1.0. (See accompanying
6   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7   // 7   //
8   // Official repository: https://github.com/cppalliance/capy 8   // Official repository: https://github.com/cppalliance/capy
9   // 9   //
10   10  
11   #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP 11   #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
12   #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP 12   #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
13   13  
14   #include <boost/capy/detail/config.hpp> 14   #include <boost/capy/detail/config.hpp>
15   15  
16   #include <bit> 16   #include <bit>
17   #include <cstddef> 17   #include <cstddef>
18   #include <memory_resource> 18   #include <memory_resource>
19   #include <mutex> 19   #include <mutex>
  20 + #include <new>
20   21  
21   namespace boost { 22   namespace boost {
22   namespace capy { 23   namespace capy {
23   24  
24   /** Recycles freed blocks through per-thread pools, with a shared pool for cross-thread reuse. 25   /** Recycles freed blocks through per-thread pools, with a shared pool for cross-thread reuse.
25   26  
26   This memory resource recycles memory blocks using power-of-two 27   This memory resource recycles memory blocks using power-of-two
27   size classes for O(1) allocation lookup. It maintains a thread-local 28   size classes for O(1) allocation lookup. It maintains a thread-local
28   pool for fast lock-free access and a global pool for cross-thread 29   pool for fast lock-free access and a global pool for cross-thread
29   block sharing. 30   block sharing.
30   31  
31   Size classes: 64, 128, 256, 512, 1024, 2048 bytes. 32   Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
32   Allocations larger than 2048 bytes bypass the pools entirely. 33   Allocations larger than 2048 bytes bypass the pools entirely.
33   34  
  35 + Each pool caches at most 256 KiB of blocks per size class:
  36 + 4096 blocks of the smallest class, 128 of the largest. A freed
  37 + block that fits in neither the thread's pool nor the global pool
  38 + goes back to `::operator delete`.
  39 +
  40 + Blocks a thread caches but stops using drain back to the global
  41 + pool. The drain runs as the thread goes on freeing blocks or
  42 + refilling from the global pool. Other threads can then reuse what a
  43 + burst leaves behind. Blocks the global pool has no room for go back
  44 + to `::operator delete`.
  45 +
34   This is the default allocator used by run_async when no allocator 46   This is the default allocator used by run_async when no allocator
35   is specified. 47   is specified.
36   48  
37   @par Thread Safety 49   @par Thread Safety
38   Thread-safe. The thread-local pool requires no synchronization. 50   Thread-safe. The thread-local pool requires no synchronization.
39   The global pool uses a mutex for cross-thread access. 51   The global pool uses a mutex for cross-thread access.
40   52  
41   @par Example 53   @par Example
42   @par !example example 54   @par !example example
43   55  
44   56  
45   @see @ref get_recycling_memory_resource 57   @see @ref get_recycling_memory_resource
46   @see @ref run_async 58   @see @ref run_async
47   */ 59   */
48   BOOST_CAPY_MSVC_WARNING_PUSH 60   BOOST_CAPY_MSVC_WARNING_PUSH
49   BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class 61   BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
50   class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource 62   class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
51   { 63   {
52   static constexpr std::size_t num_classes = 6; 64   static constexpr std::size_t num_classes = 6;
53   static constexpr std::size_t min_class_size = 64; // 2^6 65   static constexpr std::size_t min_class_size = 64; // 2^6
54   static constexpr std::size_t max_class_size = 2048; // 2^11 66   static constexpr std::size_t max_class_size = 2048; // 2^11
55 - static constexpr std::size_t bucket_capacity = 16; 67 + static constexpr int min_class_shift = std::countr_zero(min_class_size);
  68 + static constexpr std::size_t max_cached_bytes = 256 * 1024;
  69 +
  70 + // Frees on one thread, plus blocks it refills from the global pool,
  71 + // between decay passes. Allocations served from the thread's pool
  72 + // aren't counted, which keeps the counter off that path.
  73 + static constexpr std::size_t decay_period = 4096;
56   74  
57   static std::size_t 75   static std::size_t
HITCBC 58   433122 round_up_pow2(std::size_t n) noexcept 76   2287936 round_up_pow2(std::size_t n) noexcept
59   { 77   {
HITCBC 60   433122 return n <= min_class_size ? min_class_size : std::bit_ceil(n); 78   2287936 return n <= min_class_size ? min_class_size : std::bit_ceil(n);
61   } 79   }
62   80  
63   static std::size_t 81   static std::size_t
HITCBC 64   433122 get_class_index(std::size_t rounded) noexcept 82   2287936 get_class_index(std::size_t rounded) noexcept
65   { 83   {
ECB 66 - 433122 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6 84 + auto const idx = static_cast<std::size_t>(
HITGNC   85 + 2287936 std::countr_zero(rounded) - min_class_shift);
HITCBC 67   433122 return idx < num_classes ? idx : num_classes; 86   2287936 return idx < num_classes ? idx : num_classes;
68   } 87   }
69   88  
  89 + static constexpr std::size_t
HITGNC   90 + 1410470 bucket_capacity(std::size_t idx) noexcept
  91 + {
HITGNC   92 + 1410470 return max_cached_bytes >> (idx + min_class_shift);
  93 + }
  94 +
  95 + // Cached blocks are linked through their own storage, so a bucket
  96 + // holds any number of them without a side array.
  97 + struct node
  98 + {
  99 + node* next;
  100 + };
  101 +
70   struct bucket 102   struct bucket
71   { 103   {
  104 + node* head = nullptr;
72   std::size_t count = 0; 105   std::size_t count = 0;
73 - void* ptrs[bucket_capacity] = {}; 106 +
  107 + // Fewest blocks cached since the last decay pass: that many sat
  108 + // unused through the whole period.
  109 + std::size_t low = 0;
74   110  
HITCBC 75   221201 void* pop() noexcept 111   1199427 void* pop() noexcept
76   { 112   {
HITCBC 77 - 221201 if(count == 0) 113 + 1199427 node* n = head;
HITGNC   114 + 1199427 if(n == nullptr)
HITCBC 78   210523 return nullptr; 115   302445 return nullptr;
HITCBC 79 - 10678 return ptrs[--count]; 116 + 896982 head = n->next;
HITGNC   117 + 896982 --count;
HITGNC   118 + 896982 if(count < low)
HITGNC   119 + 53349 low = count;
HITGNC   120 + 896982 return n;
80   } 121   }
81   122  
82   // Peter Dimov's idea 123   // Peter Dimov's idea
  124 + // `b` must be empty: its chain is overwritten.
HITCBC 83   210522 void* pop(bucket& b) noexcept 125   302443 void* pop(bucket& b) noexcept
84   { 126   {
HITCBC 85 - 210522 if(count == 0) 127 + 302443 if(head == nullptr)
HITCBC 86   209932 return nullptr; 128   302414 return nullptr;
HITCBC 87 - 4782 for(std::size_t i = 0; i < count; ++i) 129 + 29 b.head = head;
HITCBC 88 - 4192 b.ptrs[i] = ptrs[i]; 130 + 29 b.count = count;
HITCBC 89 - 590 b.count = count - 1; 131 + 29 head = nullptr;
HITCBC 90   590 count = 0; 132   29 count = 0;
HITCBC 91 - 590 return b.ptrs[b.count]; 133 + 29 low = 0;
HITGNC   134 + 29 return b.pop();
92   } 135   }
93   136  
HITCBC 94 - 426166 bool push(void* p) noexcept 137 + 1410348 bool push(void* p, std::size_t capacity) noexcept
95   { 138   {
HITCBC 96 - 426166 if(count >= bucket_capacity) 139 + 1410348 if(count >= capacity)
HITCBC 97   414898 return false; 140   473705 return false;
HITCBC 98 - 11268 ptrs[count++] = p; 141 + 936643 head = ::new(p) node{head};
HITGNC   142 + 936643 ++count;
HITCBC 99   11268 return true; 143   936643 return true;
100   } 144   }
101   }; 145   };
102   146  
103   struct pool 147   struct pool
104   { 148   {
105   bucket buckets[num_classes]; 149   bucket buckets[num_classes];
  150 + std::size_t arrivals = 0;
106   151  
107   // No destructor: a non-trivial dtor forces a guard variable on the 152   // No destructor: a non-trivial dtor forces a guard variable on the
108   // thread_local in local(), checked on every alloc/free. Constant 153   // thread_local in local(), checked on every alloc/free. Constant
109   // initialization plus a trivial dtor makes that access a bare TLS 154   // initialization plus a trivial dtor makes that access a bare TLS
110   // load. Cached blocks are instead reclaimed explicitly: per-thread 155   // load. Cached blocks are instead reclaimed explicitly: per-thread
111   // by arm_thread_cleanup() at thread exit, and the global pool by 156   // by arm_thread_cleanup() at thread exit, and the global pool by
112   // global()'s holder destructor at process exit. 157   // global()'s holder destructor at process exit.
113   }; 158   };
114   159  
115   #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \ 160   #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \
116   !defined(BOOST_CAPY_STATIC_LINK) 161   !defined(BOOST_CAPY_STATIC_LINK)
117   // A shared build defines this thread's pool, and the flag below, in 162   // A shared build defines this thread's pool, and the flag below, in
118   // the library: inline, each module would cache in a pool of its own, 163   // the library: inline, each module would cache in a pool of its own,
119   // which the library's thread-exit cleanup never drains. 164   // which the library's thread-exit cleanup never drains.
120   static pool& local() noexcept; 165   static pool& local() noexcept;
121   #else 166   #else
122   static pool& local() noexcept 167   static pool& local() noexcept
123   { 168   {
124   static thread_local pool p; 169   static thread_local pool p;
125   return p; 170   return p;
126   } 171   }
127   #endif 172   #endif
128   173  
129   static pool& global() noexcept; 174   static pool& global() noexcept;
130   static std::mutex& global_mutex() noexcept; 175   static std::mutex& global_mutex() noexcept;
131   176  
132   void* allocate_slow(std::size_t rounded, std::size_t idx); 177   void* allocate_slow(std::size_t rounded, std::size_t idx);
133   void deallocate_slow(void* p, std::size_t idx); 178   void deallocate_slow(void* p, std::size_t idx);
134   179  
  180 + // Move half of each bucket's idle blocks to the global pool, or
  181 + // release them when it has no room. Halving, rather than emptying,
  182 + // leaves a burst that skips one period half its blocks.
  183 + static void decay(pool& lp) noexcept;
  184 +
135   // Register a thread-exit callback that drains this thread's local 185   // Register a thread-exit callback that drains this thread's local
136   // pool back to the OS. Called only off the hot path: unconditionally 186   // pool back to the OS. Called only off the hot path: unconditionally
137   // from the slow paths, and from deallocate_fast while the flag below 187   // from the slow paths, and from deallocate_fast while the flag below
138   // is clear. Returns false once that callback has run: nothing drains 188   // is clear. Returns false once that callback has run: nothing drains
139   // the local pool after it, so frees must bypass it. 189   // the local pool after it, so frees must bypass it.
140   static bool arm_thread_cleanup() noexcept; 190   static bool arm_thread_cleanup() noexcept;
141   191  
142   // Guard-free flag (constinit bool, trivial dtor): set once cleanup is 192   // Guard-free flag (constinit bool, trivial dtor): set once cleanup is
143   // armed, and cleared again when the cleanup has run. 193   // armed, and cleared again when the cleanup has run.
144   #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \ 194   #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \
145   !defined(BOOST_CAPY_STATIC_LINK) 195   !defined(BOOST_CAPY_STATIC_LINK)
146   static bool& thread_armed() noexcept; 196   static bool& thread_armed() noexcept;
147   #else 197   #else
148   static bool& thread_armed() noexcept 198   static bool& thread_armed() noexcept
149   { 199   {
150   static thread_local bool armed = false; 200   static thread_local bool armed = false;
151   return armed; 201   return armed;
152   } 202   }
153   #endif 203   #endif
154   204  
155   public: 205   public:
156   /** Destroy the resource. 206   /** Destroy the resource.
157   207  
158   No cached block is released here. Every pool is static, so an 208   No cached block is released here. Every pool is static, so an
159   instance holds no state of its own. The thread-local pool is 209   instance holds no state of its own. The thread-local pool is
160   drained at thread exit, and the global pool at process exit. 210   drained at thread exit, and the global pool at process exit.
161   */ 211   */
162   ~recycling_memory_resource(); 212   ~recycling_memory_resource();
163   213  
164   /** Allocate without virtual dispatch. 214   /** Allocate without virtual dispatch.
165   215  
166   Handles the fast path inline (thread-local bucket pop) 216   Handles the fast path inline (thread-local bucket pop)
167   and falls through to the slow path for global pool or 217   and falls through to the slow path for global pool or
168   heap allocation. 218   heap allocation.
169   219  
170   A request larger than the largest size class (2048 bytes) 220   A request larger than the largest size class (2048 bytes)
171   bypasses the pools and goes straight to `::operator new`. 221   bypasses the pools and goes straight to `::operator new`.
172   222  
173   The second parameter is the requested alignment, and it is ignored. 223   The second parameter is the requested alignment, and it is ignored.
174   Every block comes from `::operator new`, so blocks carry the 224   Every block comes from `::operator new`, so blocks carry the
175   implementation's default new alignment and no more. 225   implementation's default new alignment and no more.
176   226  
  227 + @par Complexity
  228 + Amortized constant. Now and then a call also hands this thread's
  229 + idle cached blocks to the global pool, or releases them when it
  230 + has no room.
  231 +
177   @param bytes The number of bytes to allocate. 232   @param bytes The number of bytes to allocate.
178   233  
179   @return A pointer to a block of at least `bytes` bytes. A pooled 234   @return A pointer to a block of at least `bytes` bytes. A pooled
180   block is rounded up to its size class, so it may be larger than 235   block is rounded up to its size class, so it may be larger than
181   requested. 236   requested.
182   237  
183   @throws std::bad_alloc If the underlying `::operator new` fails. 238   @throws std::bad_alloc If the underlying `::operator new` fails.
184   */ 239   */
185   void* 240   void*
HITCBC 186   216561 allocate_fast(std::size_t bytes, std::size_t) 241   1143968 allocate_fast(std::size_t bytes, std::size_t)
187   { 242   {
HITCBC 188   216561 std::size_t rounded = round_up_pow2(bytes); 243   1143968 std::size_t rounded = round_up_pow2(bytes);
HITCBC 189   216561 std::size_t idx = get_class_index(rounded); 244   1143968 std::size_t idx = get_class_index(rounded);
HITCBC 190   216561 if(idx >= num_classes) 245   1143968 if(idx >= num_classes)
MISUBC 191   ✗ return ::operator new(bytes); 246   ✗ return ::operator new(bytes);
HITCBC 192 - 216561 auto& lp = local(); 247 + 1143968 if(auto* p = local().buckets[idx].pop())
DCB 193 - 216561 if(auto* p = lp.buckets[idx].pop())  
HITCBC 194   6038 return p; 248   841524 return p;
HITCBC 195   210523 return allocate_slow(rounded, idx); 249   302444 return allocate_slow(rounded, idx);
196   } 250   }
197   251  
198   /** Deallocate without virtual dispatch. 252   /** Deallocate without virtual dispatch.
199   253  
200   Handles the fast path inline (thread-local bucket push) 254   Handles the fast path inline (thread-local bucket push)
201   and falls through to the slow path for global pool or 255   and falls through to the slow path for global pool or
202   heap deallocation. 256   heap deallocation.
203   257  
204   The block is cached in the pool of the thread that frees it, not 258   The block is cached in the pool of the thread that frees it, not
205   the thread that allocated it. 259   the thread that allocated it.
206   260  
207   The third parameter is the alignment the block was allocated with, 261   The third parameter is the alignment the block was allocated with,
208   and it is ignored, as it is on allocation. 262   and it is ignored, as it is on allocation.
209   263  
  264 + @par Complexity
  265 + Amortized constant. Now and then a call also hands this thread's
  266 + idle cached blocks to the global pool, or releases them when it
  267 + has no room.
  268 +
210   @param p The block to return. It must have come from 269   @param p The block to return. It must have come from
211   @ref allocate_fast or @ref do_allocate on this resource. 270   @ref allocate_fast or @ref do_allocate on this resource.
212   271  
213   @param bytes The size the block was allocated with. The size class 272   @param bytes The size the block was allocated with. The size class
214   is recomputed from it, so passing a different value puts the block 273   is recomputed from it, so passing a different value puts the block
215   in the wrong bucket. 274   in the wrong bucket.
216   */ 275   */
217   void 276   void
HITCBC 218   216561 deallocate_fast(void* p, std::size_t bytes, std::size_t) 277   1143968 deallocate_fast(void* p, std::size_t bytes, std::size_t)
219   { 278   {
HITCBC 220   216561 std::size_t rounded = round_up_pow2(bytes); 279   1143968 std::size_t rounded = round_up_pow2(bytes);
HITCBC 221   216561 std::size_t idx = get_class_index(rounded); 280   1143968 std::size_t idx = get_class_index(rounded);
HITCBC 222   216561 if(idx >= num_classes) 281   1143968 if(idx >= num_classes)
223   { 282   {
MISUBC 224   ✗ ::operator delete(p); 283   ✗ ::operator delete(p);
MISUBC 225   ✗ return; 284   ✗ return;
226   } 285   }
227   // Arms thread-exit cleanup for any thread that caches via 286   // Arms thread-exit cleanup for any thread that caches via
228   // deallocate, including consumer threads that never hit a slow 287   // deallocate, including consumer threads that never hit a slow
229   // path; after that cleanup, the block bypasses the local pool. 288   // path; after that cleanup, the block bypasses the local pool.
HITCBC 230   216561 auto& armed = thread_armed(); 289   1143968 auto& armed = thread_armed();
HITCBC 231   216561 if(!armed) 290   1143968 if(!armed)
232   { 291   {
HITCBC 233   355 if(!arm_thread_cleanup()) 292   375 if(!arm_thread_cleanup())
234   { 293   {
HITCBC 235   4 deallocate_slow(p, idx); 294   4 deallocate_slow(p, idx);
HITCBC 236   4 return; 295   4 return;
237   } 296   }
HITCBC 238   351 armed = true; 297   371 armed = true;
239   } 298   }
HITCBC 240   216557 auto& lp = local(); 299   1143964 auto& lp = local();
HITCBC 241 - 216557 if(lp.buckets[idx].push(p)) 300 + 1143964 if(++lp.arrivals == decay_period)
HITGNC   301 + 272 decay(lp);
HITGNC   302 + 1143964 if(lp.buckets[idx].push(p, bucket_capacity(idx)))
HITCBC 242   6952 return; 303   877584 return;
HITCBC 243   209605 deallocate_slow(p, idx); 304   266380 deallocate_slow(p, idx);
244   } 305   }
245   306  
246   protected: 307   protected:
247   /** Allocate through the `std::pmr::memory_resource` interface. 308   /** Allocate through the `std::pmr::memory_resource` interface.
248   309  
249   Forwards to @ref allocate_fast, so it has that function's contract. 310   Forwards to @ref allocate_fast, so it has that function's contract.
250   Call `allocate_fast` directly to skip the virtual dispatch. 311   Call `allocate_fast` directly to skip the virtual dispatch.
251   312  
252   @param bytes The number of bytes to allocate. 313   @param bytes The number of bytes to allocate.
253   314  
254   @param alignment The requested alignment. It is ignored. 315   @param alignment The requested alignment. It is ignored.
255   316  
256   @return A pointer to a block of at least `bytes` bytes. 317   @return A pointer to a block of at least `bytes` bytes.
257   318  
258   @throws std::bad_alloc If the underlying `::operator new` fails. 319   @throws std::bad_alloc If the underlying `::operator new` fails.
259   */ 320   */
260   void* 321   void*
261   do_allocate(std::size_t bytes, std::size_t alignment) override; 322   do_allocate(std::size_t bytes, std::size_t alignment) override;
262   323  
263   /** Deallocate through the `std::pmr::memory_resource` interface. 324   /** Deallocate through the `std::pmr::memory_resource` interface.
264   325  
265   Forwards to @ref deallocate_fast, so it has that function's 326   Forwards to @ref deallocate_fast, so it has that function's
266   contract. 327   contract.
267   328  
268   @param p The block to return, as obtained from this resource. 329   @param p The block to return, as obtained from this resource.
269   330  
270   @param bytes The size the block was allocated with. 331   @param bytes The size the block was allocated with.
271   332  
272   @param alignment The alignment the block was allocated with. It is 333   @param alignment The alignment the block was allocated with. It is
273   ignored. 334   ignored.
274   */ 335   */
275   void 336   void
276   do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override; 337   do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override;
277   338  
278   /** Compare this resource with another for equality. 339   /** Compare this resource with another for equality.
279   340  
280   Equality is object identity: two distinct 341   Equality is object identity: two distinct
281   `recycling_memory_resource` objects compare unequal, even though the 342   `recycling_memory_resource` objects compare unequal, even though the
282   pools they draw from are static and therefore shared. 343   pools they draw from are static and therefore shared.
283   344  
284   @param other The resource to compare against. 345   @param other The resource to compare against.
285   346  
286   @return `true` if `other` is the same object as `*this`; otherwise 347   @return `true` if `other` is the same object as `*this`; otherwise
287   `false`. 348   `false`.
288   */ 349   */
289   bool 350   bool
HITCBC 290   2 do_is_equal(const memory_resource& other) const noexcept override 351   2 do_is_equal(const memory_resource& other) const noexcept override
291   { 352   {
HITCBC 292   2 return this == &other; 353   2 return this == &other;
293   } 354   }
294   }; 355   };
295   BOOST_CAPY_MSVC_WARNING_POP 356   BOOST_CAPY_MSVC_WARNING_POP
296   357  
297   /** Returns pointer to the default recycling memory resource. 358   /** Returns pointer to the default recycling memory resource.
298   359  
299   The returned pointer is valid for the lifetime of the program. 360   The returned pointer is valid for the lifetime of the program.
300   This is the default allocator used by run_async. 361   This is the default allocator used by run_async.
301   362  
302   @return Pointer to the recycling memory resource. 363   @return Pointer to the recycling memory resource.
303   364  
304   @see @ref recycling_memory_resource 365   @see @ref recycling_memory_resource
305   @see @ref run_async 366   @see @ref run_async
306   */ 367   */
307   BOOST_CAPY_DECL 368   BOOST_CAPY_DECL
308   std::pmr::memory_resource* 369   std::pmr::memory_resource*
309   get_recycling_memory_resource() noexcept; 370   get_recycling_memory_resource() noexcept;
310   371  
311   } // namespace capy 372   } // namespace capy
312   } // namespace boost 373   } // namespace boost
313   374  
314   #endif 375   #endif