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