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