Index/ex / recycling_memory_resource.hpp
Prev Index Next

ex/recycling_memory_resource.hpp

80.4% Lines (41/51) 90.0% Functions (9/10) 73.1% Branches (19/26)
ex/recycling_memory_resource.hpp
Line Branch Hits Source Code
1 //
2 // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 // Official repository: https://github.com/cppalliance/capy
8 //
9
10 #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
11 #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
12
13 #include <boost/capy/detail/config.hpp>
14
15 #include <bit>
16 #include <cstddef>
17 #include <memory_resource>
18 #include <mutex>
19
20 namespace boost {
21 namespace capy {
22
23 /** Recycling memory resource with size-class buckets.
24
25 This memory resource recycles memory blocks using power-of-two
26 size classes for O(1) allocation lookup. It maintains a thread-local
27 pool for fast lock-free access and a global pool for cross-thread
28 block sharing.
29
30 Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
31 Allocations larger than 2048 bytes bypass the pools entirely.
32
33 This is the default allocator used by run_async when no allocator
34 is specified.
35
36 @par Thread Safety
37 Thread-safe. The thread-local pool requires no synchronization.
38 The global pool uses a mutex for cross-thread access.
39
40 @par Example
41 @code
42 auto* mr = get_recycling_memory_resource();
43 run_async(ex, mr)(my_task());
44 @endcode
45
46 @see get_recycling_memory_resource
47 @see run_async
48 */
49 #ifdef _MSC_VER
50 # pragma warning(push)
51 # pragma warning(disable: 4275) // non dll-interface base class
52 #endif
53 class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
54 {
55 static constexpr std::size_t num_classes = 6;
56 static constexpr std::size_t min_class_size = 64; // 2^6
57 static constexpr std::size_t max_class_size = 2048; // 2^11
58 static constexpr std::size_t bucket_capacity = 16;
59
60 static std::size_t
61 7492 round_up_pow2(std::size_t n) noexcept
62 {
63
1/2
✓ Branch 0 taken 7492 times.
✗ Branch 1 not taken.
 7492 return n <= min_class_size ? min_class_size : std::bit_ceil(n);
64 }
65
66 static std::size_t
67 7492 get_class_index(std::size_t rounded) noexcept
68 {
69 7492 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
70
1/2
✓ Branch 0 taken 7492 times.
✗ Branch 1 not taken.
 7492 return idx < num_classes ? idx : num_classes;
71 }
72
73 struct bucket
74 {
75 std::size_t count = 0;
76 void* ptrs[bucket_capacity];
77
78 3839 void* pop() noexcept
79 {
80
2/2
✓ Branch 0 taken 93 times.
✓ Branch 1 taken 3746 times.
 3839 if(count == 0)
81 93 return nullptr;
82 3746 return ptrs[--count];
83 }
84
85 // Peter Dimov's idea
86 93 void* pop(bucket& b) noexcept
87 {
88
1/2
✓ Branch 0 taken 93 times.
✗ Branch 1 not taken.
 93 if(count == 0)
89 93 return nullptr;
90 ✗ for(std::size_t i = 0; i < count; ++i)
91 ✗ b.ptrs[i] = ptrs[i];
92 ✗ b.count = count - 1;
93 ✗ count = 0;
94 ✗ return b.ptrs[b.count];
95 }
96
97 3750 bool push(void* p) noexcept
98 {
99
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 3746 times.
 3750 if(count >= bucket_capacity)
100 4 return false;
101 3746 ptrs[count++] = p;
102 3746 return true;
103 }
104 };
105
106 struct pool
107 {
108 bucket buckets[num_classes];
109
110 51 ~pool()
111 {
112
2/2
✓ Branch 0 taken 306 times.
✓ Branch 1 taken 51 times.
 357 for(auto& b : buckets)
113
2/2
✓ Branch 0 taken 93 times.
✓ Branch 1 taken 306 times.
 399 while(b.count > 0)
114 93 ::operator delete(b.pop());
115 51 }
116 };
117
118 7585 static pool& local() noexcept
119 {
120
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 7559 times.
 7585 static thread_local pool p;
121 7585 return p;
122 }
123
124 static pool& global() noexcept;
125 static std::mutex& global_mutex() noexcept;
126
127 void* allocate_slow(std::size_t rounded, std::size_t idx);
128 void deallocate_slow(void* p, std::size_t idx);
129
130 public:
131 ~recycling_memory_resource();
132
133 /** Allocate without virtual dispatch.
134
135 Handles the fast path inline (thread-local bucket pop)
136 and falls through to the slow path for global pool or
137 heap allocation.
138 */
139 void*
140 3746 allocate_fast(std::size_t bytes, std::size_t)
141 {
142 3746 std::size_t rounded = round_up_pow2(bytes);
143 3746 std::size_t idx = get_class_index(rounded);
144
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3746 times.
 3746 if(idx >= num_classes)
145 ✗ return ::operator new(bytes);
146 3746 auto& lp = local();
147
2/2
✓ Branch 1 taken 3653 times.
✓ Branch 2 taken 93 times.
 3746 if(auto* p = lp.buckets[idx].pop())
148 3653 return p;
149 93 return allocate_slow(rounded, idx);
150 }
151
152 /** Deallocate without virtual dispatch.
153
154 Handles the fast path inline (thread-local bucket push)
155 and falls through to the slow path for global pool or
156 heap deallocation.
157 */
158 void
159 3746 deallocate_fast(void* p, std::size_t bytes, std::size_t)
160 {
161 3746 std::size_t rounded = round_up_pow2(bytes);
162 3746 std::size_t idx = get_class_index(rounded);
163
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3746 times.
 3746 if(idx >= num_classes)
164 {
165 ✗ ::operator delete(p);
166 ✗ return;
167 }
168 3746 auto& lp = local();
169
2/2
✓ Branch 1 taken 3742 times.
✓ Branch 2 taken 4 times.
 3746 if(lp.buckets[idx].push(p))
170 3742 return;
171 4 deallocate_slow(p, idx);
172 }
173
174 protected:
175 void*
176 do_allocate(std::size_t bytes, std::size_t) override;
177
178 void
179 do_deallocate(void* p, std::size_t bytes, std::size_t) override;
180
181 bool
182 ✗ do_is_equal(const memory_resource& other) const noexcept override
183 {
184 ✗ return this == &other;
185 }
186 };
187 #ifdef _MSC_VER
188 # pragma warning(pop)
189 #endif
190
191 /** Returns pointer to the default recycling memory resource.
192
193 The returned pointer is valid for the lifetime of the program.
194 This is the default allocator used by run_async.
195
196 @return Pointer to the recycling memory resource.
197
198 @see recycling_memory_resource
199 @see run_async
200 */
201 BOOST_CAPY_DECL
202 std::pmr::memory_resource*
203 get_recycling_memory_resource() noexcept;
204
205 } // namespace capy
206 } // namespace boost
207
208 #endif
209