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