Line data 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 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 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 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 93 : if(count == 0)
89 93 : return nullptr;
90 0 : for(std::size_t i = 0; i < count; ++i)
91 0 : b.ptrs[i] = ptrs[i];
92 0 : b.count = count - 1;
93 0 : count = 0;
94 0 : return b.ptrs[b.count];
95 : }
96 :
97 3750 : bool push(void* p) noexcept
98 : {
99 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 357 : for(auto& b : buckets)
113 399 : while(b.count > 0)
114 93 : ::operator delete(b.pop());
115 51 : }
116 : };
117 :
118 7585 : static pool& local() noexcept
119 : {
120 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 3746 : if(idx >= num_classes)
145 0 : return ::operator new(bytes);
146 3746 : auto& lp = local();
147 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 3746 : if(idx >= num_classes)
164 : {
165 0 : ::operator delete(p);
166 0 : return;
167 : }
168 3746 : auto& lp = local();
169 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 0 : do_is_equal(const memory_resource& other) const noexcept override
183 : {
184 0 : 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
|
