. /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 - #ifdef _MSC_VER 49 + BOOST_CAPY_MSVC_WARNING_PUSH
50 - # pragma warning(push) 50 + BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
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 51   class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
54   { 52   {
55   static constexpr std::size_t num_classes = 6; 53   static constexpr std::size_t num_classes = 6;
56   static constexpr std::size_t min_class_size = 64; // 2^6 54   static constexpr std::size_t min_class_size = 64; // 2^6
57   static constexpr std::size_t max_class_size = 2048; // 2^11 55   static constexpr std::size_t max_class_size = 2048; // 2^11
58   static constexpr std::size_t bucket_capacity = 16; 56   static constexpr std::size_t bucket_capacity = 16;
59   57  
60   static std::size_t 58   static std::size_t
HITCBC 61   9780 round_up_pow2(std::size_t n) noexcept 59   10108 round_up_pow2(std::size_t n) noexcept
62   { 60   {
HITCBC 63   9780 return n <= min_class_size ? min_class_size : std::bit_ceil(n); 61   10108 return n <= min_class_size ? min_class_size : std::bit_ceil(n);
64   } 62   }
65   63  
66   static std::size_t 64   static std::size_t
HITCBC 67   9780 get_class_index(std::size_t rounded) noexcept 65   10108 get_class_index(std::size_t rounded) noexcept
68   { 66   {
HITCBC 69   9780 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6 67   10108 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
HITCBC 70   9780 return idx < num_classes ? idx : num_classes; 68   10108 return idx < num_classes ? idx : num_classes;
71   } 69   }
72   70  
73   struct bucket 71   struct bucket
74   { 72   {
75   std::size_t count = 0; 73   std::size_t count = 0;
76   void* ptrs[bucket_capacity]; 74   void* ptrs[bucket_capacity];
77   75  
HITCBC 78   4997 void* pop() noexcept 76   5206 void* pop() noexcept
79   { 77   {
HITCBC 80   4997 if(count == 0) 78   5206 if(count == 0)
HITCBC 81   107 return nullptr; 79   152 return nullptr;
HITCBC 82   4890 return ptrs[--count]; 80   5054 return ptrs[--count];
83   } 81   }
84   82  
85   // Peter Dimov's idea 83   // Peter Dimov's idea
HITCBC 86   107 void* pop(bucket& b) noexcept 84   152 void* pop(bucket& b) noexcept
87   { 85   {
HITCBC 88   107 if(count == 0) 86   152 if(count == 0)
HITCBC 89   107 return nullptr; 87   152 return nullptr;
MISUBC 90   ✗ for(std::size_t i = 0; i < count; ++i) 88   ✗ for(std::size_t i = 0; i < count; ++i)
MISUBC 91   ✗ b.ptrs[i] = ptrs[i]; 89   ✗ b.ptrs[i] = ptrs[i];
MISUBC 92   ✗ b.count = count - 1; 90   ✗ b.count = count - 1;
MISUBC 93   ✗ count = 0; 91   ✗ count = 0;
MISUBC 94   ✗ return b.ptrs[b.count]; 92   ✗ return b.ptrs[b.count];
95   } 93   }
96   94  
HITCBC 97   4894 bool push(void* p) noexcept 95   5063 bool push(void* p) noexcept
98   { 96   {
HITCBC 99   4894 if(count >= bucket_capacity) 97   5063 if(count >= bucket_capacity)
HITCBC 100   4 return false; 98   9 return false;
HITCBC 101   4890 ptrs[count++] = p; 99   5054 ptrs[count++] = p;
HITCBC 102   4890 return true; 100   5054 return true;
103   } 101   }
104   }; 102   };
105   103  
106   struct pool 104   struct pool
107   { 105   {
108   bucket buckets[num_classes]; 106   bucket buckets[num_classes];
109   107  
HITCBC 110   67 ~pool() 108   80 ~pool()
111   { 109   {
HITCBC 112   469 for(auto& b : buckets) 110   560 for(auto& b : buckets)
HITCBC 113   509 while(b.count > 0) 111   632 while(b.count > 0)
HITCBC 114   107 ::operator delete(b.pop()); 112   152 ::operator delete(b.pop());
HITCBC 115   67 } 113   80 }
116   }; 114   };
117   115  
HITCBC 118   9887 static pool& local() noexcept 116   10260 static pool& local() noexcept
119   { 117   {
HITCBC 120   9887 static thread_local pool p; 118   10260 static thread_local pool p;
HITCBC 121   9887 return p; 119   10260 return p;
122   } 120   }
123   121  
124   static pool& global() noexcept; 122   static pool& global() noexcept;
125   static std::mutex& global_mutex() noexcept; 123   static std::mutex& global_mutex() noexcept;
126   124  
127   void* allocate_slow(std::size_t rounded, std::size_t idx); 125   void* allocate_slow(std::size_t rounded, std::size_t idx);
128   void deallocate_slow(void* p, std::size_t idx); 126   void deallocate_slow(void* p, std::size_t idx);
129   127  
130   public: 128   public:
131   ~recycling_memory_resource(); 129   ~recycling_memory_resource();
132   130  
133   /** Allocate without virtual dispatch. 131   /** Allocate without virtual dispatch.
134   132  
135   Handles the fast path inline (thread-local bucket pop) 133   Handles the fast path inline (thread-local bucket pop)
136   and falls through to the slow path for global pool or 134   and falls through to the slow path for global pool or
137   heap allocation. 135   heap allocation.
138   */ 136   */
139   void* 137   void*
HITCBC 140   4890 allocate_fast(std::size_t bytes, std::size_t) 138   5054 allocate_fast(std::size_t bytes, std::size_t)
141   { 139   {
HITCBC 142   4890 std::size_t rounded = round_up_pow2(bytes); 140   5054 std::size_t rounded = round_up_pow2(bytes);
HITCBC 143   4890 std::size_t idx = get_class_index(rounded); 141   5054 std::size_t idx = get_class_index(rounded);
HITCBC 144   4890 if(idx >= num_classes) 142   5054 if(idx >= num_classes)
MISUBC 145   ✗ return ::operator new(bytes); 143   ✗ return ::operator new(bytes);
HITCBC 146   4890 auto& lp = local(); 144   5054 auto& lp = local();
HITCBC 147   4890 if(auto* p = lp.buckets[idx].pop()) 145   5054 if(auto* p = lp.buckets[idx].pop())
HITCBC 148   4783 return p; 146   4902 return p;
HITCBC 149   107 return allocate_slow(rounded, idx); 147   152 return allocate_slow(rounded, idx);
150   } 148   }
151   149  
152   /** Deallocate without virtual dispatch. 150   /** Deallocate without virtual dispatch.
153   151  
154   Handles the fast path inline (thread-local bucket push) 152   Handles the fast path inline (thread-local bucket push)
155   and falls through to the slow path for global pool or 153   and falls through to the slow path for global pool or
156   heap deallocation. 154   heap deallocation.
157   */ 155   */
158   void 156   void
HITCBC 159   4890 deallocate_fast(void* p, std::size_t bytes, std::size_t) 157   5054 deallocate_fast(void* p, std::size_t bytes, std::size_t)
160   { 158   {
HITCBC 161   4890 std::size_t rounded = round_up_pow2(bytes); 159   5054 std::size_t rounded = round_up_pow2(bytes);
HITCBC 162   4890 std::size_t idx = get_class_index(rounded); 160   5054 std::size_t idx = get_class_index(rounded);
HITCBC 163   4890 if(idx >= num_classes) 161   5054 if(idx >= num_classes)
164   { 162   {
MISUBC 165   ✗ ::operator delete(p); 163   ✗ ::operator delete(p);
MISUBC 166   ✗ return; 164   ✗ return;
167   } 165   }
HITCBC 168   4890 auto& lp = local(); 166   5054 auto& lp = local();
HITCBC 169   4890 if(lp.buckets[idx].push(p)) 167   5054 if(lp.buckets[idx].push(p))
HITCBC 170   4886 return; 168   5045 return;
HITCBC 171   4 deallocate_slow(p, idx); 169   9 deallocate_slow(p, idx);
172   } 170   }
173   171  
174   protected: 172   protected:
175   void* 173   void*
176   do_allocate(std::size_t bytes, std::size_t) override; 174   do_allocate(std::size_t bytes, std::size_t) override;
177   175  
178   void 176   void
179   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;
180   178  
181   bool 179   bool
MISUBC 182   ✗ do_is_equal(const memory_resource& other) const noexcept override 180   ✗ do_is_equal(const memory_resource& other) const noexcept override
183   { 181   {
MISUBC 184   ✗ return this == &other; 182   ✗ return this == &other;
185   } 183   }
186   }; 184   };
187 - #ifdef _MSC_VER 185 + BOOST_CAPY_MSVC_WARNING_POP
188 - # pragma warning(pop)  
189 - #endif  
190   186  
191   /** Returns pointer to the default recycling memory resource. 187   /** Returns pointer to the default recycling memory resource.
192   188  
193   The returned pointer is valid for the lifetime of the program. 189   The returned pointer is valid for the lifetime of the program.
194   This is the default allocator used by run_async. 190   This is the default allocator used by run_async.
195   191  
196   @return Pointer to the recycling memory resource. 192   @return Pointer to the recycling memory resource.
197   193  
198   @see recycling_memory_resource 194   @see recycling_memory_resource
199   @see run_async 195   @see run_async
200   */ 196   */
201   BOOST_CAPY_DECL 197   BOOST_CAPY_DECL
202   std::pmr::memory_resource* 198   std::pmr::memory_resource*
203   get_recycling_memory_resource() noexcept; 199   get_recycling_memory_resource() noexcept;
204   200  
205   } // namespace capy 201   } // namespace capy
206   } // namespace boost 202   } // namespace boost
207   203  
208   #endif 204   #endif