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   
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 bucket
69   
    struct bucket
70   
    {
70   
    {
71   
        std::size_t count = 0;
71   
        std::size_t count = 0;
72   
        void* ptrs[bucket_capacity];
72   
        void* ptrs[bucket_capacity];
73  
73  
74   
        void* pop() noexcept
74   
        void* pop() noexcept
75   
        {
75   
        {
76   
            if(count == 0)
76   
            if(count == 0)
77   
                return nullptr;
77   
                return nullptr;
78   
            return ptrs[--count];
78   
            return ptrs[--count];
79   
        }
79   
        }
80  
80  
81   
        // Peter Dimov's idea
81   
        // Peter Dimov's idea
82   
        void* pop(bucket& b) noexcept
82   
        void* pop(bucket& b) noexcept
83   
        {
83   
        {
84   
            if(count == 0)
84   
            if(count == 0)
85   
                return nullptr;
85   
                return nullptr;
86   
            for(std::size_t i = 0; i < count; ++i)
86   
            for(std::size_t i = 0; i < count; ++i)
87   
                b.ptrs[i] = ptrs[i];
87   
                b.ptrs[i] = ptrs[i];
88   
            b.count = count - 1;
88   
            b.count = count - 1;
89   
            count = 0;
89   
            count = 0;
90   
            return b.ptrs[b.count];
90   
            return b.ptrs[b.count];
91   
        }
91   
        }
92  
92  
93   
        bool push(void* p) noexcept
93   
        bool push(void* p) noexcept
94   
        {
94   
        {
95   
            if(count >= bucket_capacity)
95   
            if(count >= bucket_capacity)
96   
                return false;
96   
                return false;
97   
            ptrs[count++] = p;
97   
            ptrs[count++] = p;
98   
            return true;
98   
            return true;
99   
        }
99   
        }
100   
    };
100   
    };
101  
101  
102   
    struct pool
102   
    struct pool
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   
    BOOST_CAPY_DECL static pool& local() noexcept;
114   
    BOOST_CAPY_DECL static pool& local() noexcept;
115   
    BOOST_CAPY_DECL static pool& global() noexcept;
115   
    BOOST_CAPY_DECL static pool& global() noexcept;
116   
    BOOST_CAPY_DECL static std::mutex& global_mutex() noexcept;
116   
    BOOST_CAPY_DECL static std::mutex& global_mutex() noexcept;
117  
117  
118   
protected:
118   
protected:
119   
    BOOST_CAPY_DECL void*
119   
    BOOST_CAPY_DECL void*
120   
    do_allocate(std::size_t bytes, std::size_t) override;
120   
    do_allocate(std::size_t bytes, std::size_t) override;
121  
121  
122   
    BOOST_CAPY_DECL void
122   
    BOOST_CAPY_DECL void
123   
    do_deallocate(void* p, std::size_t bytes, std::size_t) override;
123   
    do_deallocate(void* p, std::size_t bytes, std::size_t) override;
124  
124  
125   
    bool
125   
    bool
126   
    do_is_equal(const memory_resource& other) const noexcept override
126   
    do_is_equal(const memory_resource& other) const noexcept override
127   
    {
127   
    {
128   
        return this == &other;
128   
        return this == &other;
129   
    }
129   
    }
130   
};
130   
};
131  
131  
132   
/** Returns pointer to the default recycling memory resource.
132   
/** Returns pointer to the default recycling memory resource.
133  
133  
134   
    The returned pointer is valid for the lifetime of the program.
134   
    The returned pointer is valid for the lifetime of the program.
135   
    This is the default allocator used by run_async.
135   
    This is the default allocator used by run_async.
136  
136  
137   
    @return Pointer to the recycling memory resource.
137   
    @return Pointer to the recycling memory resource.
138  
138  
139   
    @see recycling_memory_resource
139   
    @see recycling_memory_resource
140   
    @see run_async
140   
    @see run_async
141   
*/
141   
*/
142   
BOOST_CAPY_DECL
142   
BOOST_CAPY_DECL
143   
std::pmr::memory_resource*
143   
std::pmr::memory_resource*
144   
get_recycling_memory_resource() noexcept;
144   
get_recycling_memory_resource() noexcept;
145  
145  
146   
} // namespace capy
146   
} // namespace capy
147   
} // namespace boost
147   
} // namespace boost
148  
148  
149   
#endif
149   
#endif