include/boost/capy/ex/recycling_memory_resource.hpp

80.4% Lines (41/51) 90.0% List of functions (9/10) 73.1% Branches (19/26)

[ ] prev/next file n p prev/next uncovered line

f(x) Functions (10)

Function Calls Lines Branches Blocks

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		10018x	round_up_pow2(std::size_t n) noexcept
62			{
63	1/2 ✓ Branch 0 taken 10018 times. ✗ Branch 1 not taken.	10018x	return n <= min_class_size ? min_class_size : std::bit_ceil(n);
64			}
65
66			static std::size_t
67		10018x	get_class_index(std::size_t rounded) noexcept
68			{
69		10018x	std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
70	1/2 ✓ Branch 0 taken 10018 times. ✗ Branch 1 not taken.	10018x	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		5116x	void* pop() noexcept
79			{
80	2/2 ✓ Branch 0 taken 107 times. ✓ Branch 1 taken 5009 times.	5116x	if(count == 0)
81		107x	return nullptr;
82		5009x	return ptrs[--count];
83			}
84
85			// Peter Dimov's idea
86		107x	void* pop(bucket& b) noexcept
87			{
88	1/2 ✓ Branch 0 taken 107 times. ✗ Branch 1 not taken.	107x	if(count == 0)
89		107x	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		5013x	bool push(void* p) noexcept
98			{
99	2/2 ✓ Branch 0 taken 4 times. ✓ Branch 1 taken 5009 times.	5013x	if(count >= bucket_capacity)
100		4x	return false;
101		5009x	ptrs[count++] = p;
102		5009x	return true;
103			}
104			};
105
106			struct pool
107			{
108			bucket buckets[num_classes];
109
110		67x	~pool()
111			{
112	2/2 ✓ Branch 0 taken 402 times. ✓ Branch 1 taken 67 times.	469x	for(auto& b : buckets)
113	2/2 ✓ Branch 0 taken 107 times. ✓ Branch 1 taken 402 times.	509x	while(b.count > 0)
114		107x	::operator delete(b.pop());
115		67x	}
116			};
117
118		10125x	static pool& local() noexcept
119			{
120	2/2 ✓ Branch 0 taken 34 times. ✓ Branch 1 taken 10091 times.	10125x	static thread_local pool p;
121		10125x	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		5009x	allocate_fast(std::size_t bytes, std::size_t)
141			{
142		5009x	std::size_t rounded = round_up_pow2(bytes);
143		5009x	std::size_t idx = get_class_index(rounded);
144	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 5009 times.	5009x	if(idx >= num_classes)
145		✗	return ::operator new(bytes);
146		5009x	auto& lp = local();
147	2/2 ✓ Branch 1 taken 4902 times. ✓ Branch 2 taken 107 times.	5009x	if(auto* p = lp.buckets[idx].pop())
148		4902x	return p;
149		107x	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		5009x	deallocate_fast(void* p, std::size_t bytes, std::size_t)
160			{
161		5009x	std::size_t rounded = round_up_pow2(bytes);
162		5009x	std::size_t idx = get_class_index(rounded);
163	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 5009 times.	5009x	if(idx >= num_classes)
164			{
165		✗	::operator delete(p);
166		✗	return;
167			}
168		5009x	auto& lp = local();
169	2/2 ✓ Branch 1 taken 5005 times. ✓ Branch 2 taken 4 times.	5009x	if(lp.buckets[idx].push(p))
170		5005x	return;
171		4x	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