Index/include / boost / capy / ex / recycling_memory_resource.hpp

include/boost/capy/ex/recycling_memory_resource.hpp

93.9% Lines (46 / 49) 100.0% Functions (8 / 8)
[ ] prev/next file n p prev/next uncovered line
recycling_memory_resource.hpp
f(x) Functions (8)
Function Calls Lines Blocks
boost::capy::recycling_memory_resource::round_up_pow2(unsigned long) :58 433156x 100.0% 100.0% boost::capy::recycling_memory_resource::get_class_index(unsigned long) :64 433156x 100.0% 86.0% boost::capy::recycling_memory_resource::bucket::pop() :75 221240x 100.0% 100.0% boost::capy::recycling_memory_resource::bucket::pop(boost::capy::recycling_memory_resource::bucket&) :83 210832x 100.0% 100.0% boost::capy::recycling_memory_resource::bucket::push(void*) :94 426239x 100.0% 100.0% boost::capy::recycling_memory_resource::allocate_fast(unsigned long, unsigned long) :186 216578x 88.9% 83.0% boost::capy::recycling_memory_resource::deallocate_fast(void*, unsigned long, unsigned long) :218 216578x 87.5% 89.0% boost::capy::recycling_memory_resource::do_is_equal(std::pmr::memory_resource const&) const :290 2x 100.0% 100.0%
Line TLA Hits Source Code
1 //
2 // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3 // Copyright (c) 2026 Michael Vandeberg
4 //
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)
7 //
8 // Official repository: https://github.com/cppalliance/capy
9 //
10
11 #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
12 #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
13
14 #include <boost/capy/detail/config.hpp>
15
16 #include <bit>
17 #include <cstddef>
18 #include <memory_resource>
19 #include <mutex>
20
21 namespace boost {
22 namespace capy {
23
24 /** Recycles freed blocks through per-thread pools, with a shared pool for cross-thread reuse.
25
26 This memory resource recycles memory blocks using power-of-two
27 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 block sharing.
30
31 Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
32 Allocations larger than 2048 bytes bypass the pools entirely.
33
34 This is the default allocator used by run_async when no allocator
35 is specified.
36
37 @par Thread Safety
38 Thread-safe. The thread-local pool requires no synchronization.
39 The global pool uses a mutex for cross-thread access.
40
41 @par Example
42 @par !example example
43
44
45 @see get_recycling_memory_resource
46 @see run_async
47 */
48 BOOST_CAPY_MSVC_WARNING_PUSH
49 BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
50 class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
51 {
52 static constexpr std::size_t num_classes = 6;
53 static constexpr std::size_t min_class_size = 64; // 2^6
54 static constexpr std::size_t max_class_size = 2048; // 2^11
55 static constexpr std::size_t bucket_capacity = 16;
56
57 static std::size_t
58 433156x round_up_pow2(std::size_t n) noexcept
59 {
60 433156x return n <= min_class_size ? min_class_size : std::bit_ceil(n);
61 }
62
63 static std::size_t
64 433156x get_class_index(std::size_t rounded) noexcept
65 {
66 433156x std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
67 433156x return idx < num_classes ? idx : num_classes;
68 }
69
70 struct bucket
71 {
72 std::size_t count = 0;
73 void* ptrs[bucket_capacity] = {};
74
75 221240x void* pop() noexcept
76 {
77 221240x if(count == 0)
78 210833x return nullptr;
79 10407x return ptrs[--count];
80 }
81
82 // Peter Dimov's idea
83 210832x void* pop(bucket& b) noexcept
84 {
85 210832x if(count == 0)
86 210117x return nullptr;
87 4800x for(std::size_t i = 0; i < count; ++i)
88 4085x b.ptrs[i] = ptrs[i];
89 715x b.count = count - 1;
90 715x count = 0;
91 715x return b.ptrs[b.count];
92 }
93
94 426239x bool push(void* p) noexcept
95 {
96 426239x if(count >= bucket_capacity)
97 415117x return false;
98 11122x ptrs[count++] = p;
99 11122x return true;
100 }
101 };
102
103 struct pool
104 {
105 bucket buckets[num_classes];
106
107 // No destructor: a non-trivial dtor forces a guard variable on the
108 // thread_local in local(), checked on every alloc/free. Constant
109 // initialization plus a trivial dtor makes that access a bare TLS
110 // load. Cached blocks are instead reclaimed explicitly: per-thread
111 // by arm_thread_cleanup() at thread exit, and the global pool by
112 // global()'s holder destructor at process exit.
113 };
114
115 #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \
116 !defined(BOOST_CAPY_STATIC_LINK)
117 // 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,
119 // which the library's thread-exit cleanup never drains.
120 static pool& local() noexcept;
121 #else
122 static pool& local() noexcept
123 {
124 static thread_local pool p;
125 return p;
126 }
127 #endif
128
129 static pool& global() noexcept;
130 static std::mutex& global_mutex() noexcept;
131
132 void* allocate_slow(std::size_t rounded, std::size_t idx);
133 void deallocate_slow(void* p, std::size_t idx);
134
135 // Register a thread-exit callback that drains this thread's local
136 // 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
138 // is clear. Returns false once that callback has run: nothing drains
139 // the local pool after it, so frees must bypass it.
140 static bool arm_thread_cleanup() noexcept;
141
142 // Guard-free flag (constinit bool, trivial dtor): set once cleanup is
143 // armed, and cleared again when the cleanup has run.
144 #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \
145 !defined(BOOST_CAPY_STATIC_LINK)
146 static bool& thread_armed() noexcept;
147 #else
148 static bool& thread_armed() noexcept
149 {
150 static thread_local bool armed = false;
151 return armed;
152 }
153 #endif
154
155 public:
156 /** Destroy the resource.
157
158 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
160 drained at thread exit, and the global pool at process exit.
161 */
162 ~recycling_memory_resource();
163
164 /** Allocate without virtual dispatch.
165
166 Handles the fast path inline (thread-local bucket pop)
167 and falls through to the slow path for global pool or
168 heap allocation.
169
170 A request larger than the largest size class (2048 bytes)
171 bypasses the pools and goes straight to `::operator new`.
172
173 The second parameter is the requested alignment, and it is ignored.
174 Every block comes from `::operator new`, so blocks carry the
175 implementation's default new alignment and no more.
176
177 @param bytes The number of bytes to allocate.
178
179 @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
181 requested.
182
183 @throws std::bad_alloc If the underlying `::operator new` fails.
184 */
185 void*
186 216578x allocate_fast(std::size_t bytes, std::size_t)
187 {
188 216578x std::size_t rounded = round_up_pow2(bytes);
189 216578x std::size_t idx = get_class_index(rounded);
190 216578x if(idx >= num_classes)
191 ✗ return ::operator new(bytes);
192 216578x auto& lp = local();
193 216578x if(auto* p = lp.buckets[idx].pop())
194 5745x return p;
195 210833x return allocate_slow(rounded, idx);
196 }
197
198 /** Deallocate without virtual dispatch.
199
200 Handles the fast path inline (thread-local bucket push)
201 and falls through to the slow path for global pool or
202 heap deallocation.
203
204 The block is cached in the pool of the thread that frees it, not
205 the thread that allocated it.
206
207 The third parameter is the alignment the block was allocated with,
208 and it is ignored, as it is on allocation.
209
210 @param p The block to return. It must have come from
211 @ref allocate_fast or @ref do_allocate on this resource.
212
213 @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
215 in the wrong bucket.
216 */
217 void
218 216578x deallocate_fast(void* p, std::size_t bytes, std::size_t)
219 {
220 216578x std::size_t rounded = round_up_pow2(bytes);
221 216578x std::size_t idx = get_class_index(rounded);
222 216578x if(idx >= num_classes)
223 {
224 ✗ ::operator delete(p);
225 ✗ return;
226 }
227 // Arms thread-exit cleanup for any thread that caches via
228 // deallocate, including consumer threads that never hit a slow
229 // path; after that cleanup, the block bypasses the local pool.
230 216578x auto& armed = thread_armed();
231 216578x if(!armed)
232 {
233 362x if(!arm_thread_cleanup())
234 {
235 4x deallocate_slow(p, idx);
236 4x return;
237 }
238 358x armed = true;
239 }
240 216574x auto& lp = local();
241 216574x if(lp.buckets[idx].push(p))
242 6913x return;
243 209661x deallocate_slow(p, idx);
244 }
245
246 protected:
247 /** Allocate through the `std::pmr::memory_resource` interface.
248
249 Forwards to @ref allocate_fast, so it has that function's contract.
250 Call `allocate_fast` directly to skip the virtual dispatch.
251
252 @param bytes The number of bytes to allocate.
253
254 @param alignment The requested alignment. It is ignored.
255
256 @return A pointer to a block of at least `bytes` bytes.
257
258 @throws std::bad_alloc If the underlying `::operator new` fails.
259 */
260 void*
261 do_allocate(std::size_t bytes, std::size_t alignment) override;
262
263 /** Deallocate through the `std::pmr::memory_resource` interface.
264
265 Forwards to @ref deallocate_fast, so it has that function's
266 contract.
267
268 @param p The block to return, as obtained from this resource.
269
270 @param bytes The size the block was allocated with.
271
272 @param alignment The alignment the block was allocated with. It is
273 ignored.
274 */
275 void
276 do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override;
277
278 /** Compare this resource with another for equality.
279
280 Equality is object identity: two distinct
281 `recycling_memory_resource` objects compare unequal, even though the
282 pools they draw from are static and therefore shared.
283
284 @param other The resource to compare against.
285
286 @return `true` if `other` is the same object as `*this`; otherwise
287 `false`.
288 */
289 bool
290 2x do_is_equal(const memory_resource& other) const noexcept override
291 {
292 2x return this == &other;
293 }
294 };
295 BOOST_CAPY_MSVC_WARNING_POP
296
297 /** Returns pointer to the default recycling memory resource.
298
299 The returned pointer is valid for the lifetime of the program.
300 This is the default allocator used by run_async.
301
302 @return Pointer to the recycling memory resource.
303
304 @see recycling_memory_resource
305 @see run_async
306 */
307 BOOST_CAPY_DECL
308 std::pmr::memory_resource*
309 get_recycling_memory_resource() noexcept;
310
311 } // namespace capy
312 } // namespace boost
313
314 #endif
315