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