Line data Source code
1 : //
2 : // Copyright (c) 2025 Vinnie Falco (vinnie dot falco at gmail dot 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 : class recycling_memory_resource : public std::pmr::memory_resource
50 : {
51 : static constexpr std::size_t num_classes = 6;
52 : static constexpr std::size_t min_class_size = 64; // 2^6
53 : static constexpr std::size_t max_class_size = 2048; // 2^11
54 : static constexpr std::size_t bucket_capacity = 16;
55 :
56 : static std::size_t
57 9506 : round_up_pow2(std::size_t n) noexcept
58 : {
59 9506 : return n <= min_class_size ? min_class_size : std::bit_ceil(n);
60 : }
61 :
62 : static std::size_t
63 9506 : get_class_index(std::size_t rounded) noexcept
64 : {
65 9506 : std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
66 9506 : return idx < num_classes ? idx : num_classes;
67 : }
68 :
69 : struct pool
70 : {
71 : struct bucket
72 : {
73 : std::size_t count = 0;
74 : void* ptrs[bucket_capacity];
75 :
76 4790 : void* pop() noexcept
77 : {
78 4790 : if(count == 0)
79 117 : return nullptr;
80 4673 : return ptrs[--count];
81 : }
82 :
83 : // Peter Dimov's idea
84 117 : void* pop(bucket& b) noexcept
85 : {
86 117 : if(count == 0)
87 117 : return nullptr;
88 0 : for(std::size_t i = 0; i < count; ++i)
89 0 : b.ptrs[i] = ptrs[i];
90 0 : b.count = count - 1;
91 0 : count = 0;
92 0 : return b.ptrs[b.count];
93 : }
94 :
95 4677 : bool push(void* p) noexcept
96 : {
97 4677 : if(count >= bucket_capacity)
98 4 : return false;
99 4673 : ptrs[count++] = p;
100 4673 : return true;
101 : }
102 : };
103 :
104 : bucket buckets[num_classes];
105 :
106 49 : ~pool()
107 : {
108 343 : for(auto& b : buckets)
109 411 : while(b.count > 0)
110 117 : ::operator delete(b.pop());
111 49 : }
112 : };
113 :
114 : static pool&
115 9463 : local() noexcept
116 : {
117 9463 : static thread_local pool p;
118 9463 : return p;
119 : }
120 :
121 : static pool&
122 121 : global() noexcept
123 : {
124 121 : static pool p;
125 121 : return p;
126 : }
127 :
128 : static std::mutex&
129 121 : global_mutex() noexcept
130 : {
131 : static std::mutex mtx;
132 121 : return mtx;
133 : }
134 :
135 : protected:
136 : void*
137 4753 : do_allocate(std::size_t bytes, std::size_t) override
138 : {
139 4753 : std::size_t rounded = round_up_pow2(bytes);
140 4753 : std::size_t idx = get_class_index(rounded);
141 :
142 4753 : if(idx >= num_classes)
143 80 : return ::operator new(bytes);
144 :
145 4673 : if(auto* p = local().buckets[idx].pop())
146 4556 : return p;
147 :
148 : {
149 117 : std::lock_guard<std::mutex> lock(global_mutex());
150 117 : if(auto* p = global().buckets[idx].pop(local().buckets[idx]))
151 0 : return p;
152 117 : }
153 :
154 117 : return ::operator new(rounded);
155 : }
156 :
157 : void
158 4753 : do_deallocate(void* p, std::size_t bytes, std::size_t) override
159 : {
160 4753 : std::size_t rounded = round_up_pow2(bytes);
161 4753 : std::size_t idx = get_class_index(rounded);
162 :
163 4753 : if(idx >= num_classes)
164 : {
165 80 : ::operator delete(p);
166 80 : return;
167 : }
168 :
169 4673 : if(local().buckets[idx].push(p))
170 4669 : return;
171 :
172 : {
173 4 : std::lock_guard<std::mutex> lock(global_mutex());
174 4 : if(global().buckets[idx].push(p))
175 4 : return;
176 4 : }
177 :
178 0 : ::operator delete(p);
179 : }
180 :
181 : bool
182 0 : do_is_equal(const memory_resource& other) const noexcept override
183 : {
184 0 : return this == &other;
185 : }
186 : };
187 :
188 : /** Returns pointer to the default recycling memory resource.
189 :
190 : The returned pointer is valid for the lifetime of the program.
191 : This is the default allocator used by run_async.
192 :
193 : @return Pointer to the recycling memory resource.
194 :
195 : @see recycling_memory_resource
196 : @see run_async
197 : */
198 : BOOST_CAPY_DECL
199 : std::pmr::memory_resource*
200 : get_recycling_memory_resource() noexcept;
201 :
202 : } // namespace capy
203 : } // namespace boost
204 :
205 : #endif
|
