1   
//
1   
//
2   
// Copyright (c) 2025 Vinnie Falco (vinnie dot falco at gmail dot com)
2   
// Copyright (c) 2025 Vinnie Falco (vinnie dot falco at gmail dot 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   
class recycling_memory_resource : public std::pmr::memory_resource
50   
{
50   
{
51   
    static constexpr std::size_t num_classes = 6;
51   
    static constexpr std::size_t num_classes = 6;
52   
    static constexpr std::size_t min_class_size = 64;   // 2^6
52   
    static constexpr std::size_t min_class_size = 64;   // 2^6
53   
    static constexpr std::size_t max_class_size = 2048; // 2^11
53   
    static constexpr std::size_t max_class_size = 2048; // 2^11
54   
    static constexpr std::size_t bucket_capacity = 16;
54   
    static constexpr std::size_t bucket_capacity = 16;
55  
55  
56   
    static std::size_t
56   
    static std::size_t
57   
    round_up_pow2(std::size_t n) noexcept
57   
    round_up_pow2(std::size_t n) noexcept
58   
    {
58   
    {
59   
        return n <= min_class_size ? min_class_size : std::bit_ceil(n);
59   
        return n <= min_class_size ? min_class_size : std::bit_ceil(n);
60   
    }
60   
    }
61  
61  
62   
    static std::size_t
62   
    static std::size_t
63   
    get_class_index(std::size_t rounded) noexcept
63   
    get_class_index(std::size_t rounded) noexcept
64   
    {
64   
    {
65   
        std::size_t idx = std::countr_zero(rounded) - 6;  // 64 = 2^6
65   
        std::size_t idx = std::countr_zero(rounded) - 6;  // 64 = 2^6
66   
        return idx < num_classes ? idx : num_classes;
66   
        return idx < num_classes ? idx : num_classes;
67   
    }
67   
    }
68  
68  
69   
    struct pool
69   
    struct pool
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   
        bucket buckets[num_classes];
104   
        bucket buckets[num_classes];
105  
105  
106   
        ~pool()
106   
        ~pool()
107   
        {
107   
        {
108   
            for(auto& b : buckets)
108   
            for(auto& b : buckets)
109   
                while(b.count > 0)
109   
                while(b.count > 0)
110   
                    ::operator delete(b.pop());
110   
                    ::operator delete(b.pop());
111   
        }
111   
        }
112   
    };
112   
    };
113  
113  
114   
    static pool&
114   
    static pool&
115   
    local() noexcept
115   
    local() noexcept
116   
    {
116   
    {
117   
        static thread_local pool p;
117   
        static thread_local pool p;
118   
        return p;
118   
        return p;
119   
    }
119   
    }
120  
120  
121   
    static pool&
121   
    static pool&
122   
    global() noexcept
122   
    global() noexcept
123   
    {
123   
    {
124   
        static pool p;
124   
        static pool p;
125   
        return p;
125   
        return p;
126   
    }
126   
    }
127  
127  
128   
    static std::mutex&
128   
    static std::mutex&
129   
    global_mutex() noexcept
129   
    global_mutex() noexcept
130   
    {
130   
    {
131   
        static std::mutex mtx;
131   
        static std::mutex mtx;
132   
        return mtx;
132   
        return mtx;
133   
    }
133   
    }
134  
134  
135   
protected:
135   
protected:
136   
    void*
136   
    void*
137   
    do_allocate(std::size_t bytes, std::size_t) override
137   
    do_allocate(std::size_t bytes, std::size_t) override
138   
    {
138   
    {
139   
        std::size_t rounded = round_up_pow2(bytes);
139   
        std::size_t rounded = round_up_pow2(bytes);
140   
        std::size_t idx = get_class_index(rounded);
140   
        std::size_t idx = get_class_index(rounded);
141  
141  
142   
        if(idx >= num_classes)
142   
        if(idx >= num_classes)
143   
            return ::operator new(bytes);
143   
            return ::operator new(bytes);
144  
144  
145   
        if(auto* p = local().buckets[idx].pop())
145   
        if(auto* p = local().buckets[idx].pop())
146   
            return p;
146   
            return p;
147  
147  
148   
        {
148   
        {
149   
            std::lock_guard<std::mutex> lock(global_mutex());
149   
            std::lock_guard<std::mutex> lock(global_mutex());
150   
            if(auto* p = global().buckets[idx].pop(local().buckets[idx]))
150   
            if(auto* p = global().buckets[idx].pop(local().buckets[idx]))
151   
                return p;
151   
                return p;
152   
        }
152   
        }
153  
153  
154   
        return ::operator new(rounded);
154   
        return ::operator new(rounded);
155   
    }
155   
    }
156  
156  
157   
    void
157   
    void
158   
    do_deallocate(void* p, std::size_t bytes, std::size_t) override
158   
    do_deallocate(void* p, std::size_t bytes, std::size_t) override
159   
    {
159   
    {
160   
        std::size_t rounded = round_up_pow2(bytes);
160   
        std::size_t rounded = round_up_pow2(bytes);
161   
        std::size_t idx = get_class_index(rounded);
161   
        std::size_t idx = get_class_index(rounded);
162  
162  
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  
168  
169   
        if(local().buckets[idx].push(p))
169   
        if(local().buckets[idx].push(p))
170   
            return;
170   
            return;
171  
171  
172   
        {
172   
        {
173   
            std::lock_guard<std::mutex> lock(global_mutex());
173   
            std::lock_guard<std::mutex> lock(global_mutex());
174   
            if(global().buckets[idx].push(p))
174   
            if(global().buckets[idx].push(p))
175   
                return;
175   
                return;
176   
        }
176   
        }
177  
177  
178   
        ::operator delete(p);
178   
        ::operator delete(p);
179   
    }
179   
    }
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  
187  
188   
/** Returns pointer to the default recycling memory resource.
188   
/** Returns pointer to the default recycling memory resource.
189  
189  
190   
    The returned pointer is valid for the lifetime of the program.
190   
    The returned pointer is valid for the lifetime of the program.
191   
    This is the default allocator used by run_async.
191   
    This is the default allocator used by run_async.
192  
192  
193   
    @return Pointer to the recycling memory resource.
193   
    @return Pointer to the recycling memory resource.
194  
194  
195   
    @see recycling_memory_resource
195   
    @see recycling_memory_resource
196   
    @see run_async
196   
    @see run_async
197   
*/
197   
*/
198   
BOOST_CAPY_DECL
198   
BOOST_CAPY_DECL
199   
std::pmr::memory_resource*
199   
std::pmr::memory_resource*
200   
get_recycling_memory_resource() noexcept;
200   
get_recycling_memory_resource() noexcept;
201  
201  
202   
} // namespace capy
202   
} // namespace capy
203   
} // namespace boost
203   
} // namespace boost
204  
204  
205   
#endif
205   
#endif