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