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
61   
    round_up_pow2(std::size_t n) noexcept
59   
    round_up_pow2(std::size_t n) noexcept
62   
    {
60   
    {
63   
        return n <= min_class_size ? min_class_size : std::bit_ceil(n);
61   
        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
67   
    get_class_index(std::size_t rounded) noexcept
65   
    get_class_index(std::size_t rounded) noexcept
68   
    {
66   
    {
69   
        std::size_t idx = std::countr_zero(rounded) - 6;  // 64 = 2^6
67   
        std::size_t idx = std::countr_zero(rounded) - 6;  // 64 = 2^6
70   
        return idx < num_classes ? idx : num_classes;
68   
        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  
78   
        void* pop() noexcept
76   
        void* pop() noexcept
79   
        {
77   
        {
80   
            if(count == 0)
78   
            if(count == 0)
81   
                return nullptr;
79   
                return nullptr;
82   
            return ptrs[--count];
80   
            return ptrs[--count];
83   
        }
81   
        }
84  
82  
85   
        // Peter Dimov's idea
83   
        // Peter Dimov's idea
86   
        void* pop(bucket& b) noexcept
84   
        void* pop(bucket& b) noexcept
87   
        {
85   
        {
88   
            if(count == 0)
86   
            if(count == 0)
89   
                return nullptr;
87   
                return nullptr;
90   
            for(std::size_t i = 0; i < count; ++i)
88   
            for(std::size_t i = 0; i < count; ++i)
91   
                b.ptrs[i] = ptrs[i];
89   
                b.ptrs[i] = ptrs[i];
92   
            b.count = count - 1;
90   
            b.count = count - 1;
93   
            count = 0;
91   
            count = 0;
94   
            return b.ptrs[b.count];
92   
            return b.ptrs[b.count];
95   
        }
93   
        }
96  
94  
97   
        bool push(void* p) noexcept
95   
        bool push(void* p) noexcept
98   
        {
96   
        {
99   
            if(count >= bucket_capacity)
97   
            if(count >= bucket_capacity)
100   
                return false;
98   
                return false;
101   
            ptrs[count++] = p;
99   
            ptrs[count++] = p;
102   
            return true;
100   
            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  
110   
        ~pool()
108   
        ~pool()
111   
        {
109   
        {
112   
            for(auto& b : buckets)
110   
            for(auto& b : buckets)
113   
                while(b.count > 0)
111   
                while(b.count > 0)
114   
                    ::operator delete(b.pop());
112   
                    ::operator delete(b.pop());
115   
        }
113   
        }
116   
    };
114   
    };
117  
115  
118   
    static pool& local() noexcept
116   
    static pool& local() noexcept
119   
    {
117   
    {
120   
        static thread_local pool p;
118   
        static thread_local pool p;
121   
        return p;
119   
        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*
140   
    allocate_fast(std::size_t bytes, std::size_t)
138   
    allocate_fast(std::size_t bytes, std::size_t)
141   
    {
139   
    {
142   
        std::size_t rounded = round_up_pow2(bytes);
140   
        std::size_t rounded = round_up_pow2(bytes);
143   
        std::size_t idx = get_class_index(rounded);
141   
        std::size_t idx = get_class_index(rounded);
144   
        if(idx >= num_classes)
142   
        if(idx >= num_classes)
145   
            return ::operator new(bytes);
143   
            return ::operator new(bytes);
146   
        auto& lp = local();
144   
        auto& lp = local();
147   
        if(auto* p = lp.buckets[idx].pop())
145   
        if(auto* p = lp.buckets[idx].pop())
148   
            return p;
146   
            return p;
149   
        return allocate_slow(rounded, idx);
147   
        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
159   
    deallocate_fast(void* p, std::size_t bytes, std::size_t)
157   
    deallocate_fast(void* p, std::size_t bytes, std::size_t)
160   
    {
158   
    {
161   
        std::size_t rounded = round_up_pow2(bytes);
159   
        std::size_t rounded = round_up_pow2(bytes);
162   
        std::size_t idx = get_class_index(rounded);
160   
        std::size_t idx = get_class_index(rounded);
163   
        if(idx >= num_classes)
161   
        if(idx >= num_classes)
164   
        {
162   
        {
165   
            ::operator delete(p);
163   
            ::operator delete(p);
166   
            return;
164   
            return;
167   
        }
165   
        }
168   
        auto& lp = local();
166   
        auto& lp = local();
169   
        if(lp.buckets[idx].push(p))
167   
        if(lp.buckets[idx].push(p))
170   
            return;
168   
            return;
171   
        deallocate_slow(p, idx);
169   
        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
182   
    do_is_equal(const memory_resource& other) const noexcept override
180   
    do_is_equal(const memory_resource& other) const noexcept override
183   
    {
181   
    {
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