Line data    Source code

       1              : //
       2              : // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
       3              : //
       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)
       6              : //
       7              : // Official repository: https://github.com/cppalliance/capy
       8              : //
       9              : 
      10              : #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
      11              : #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
      12              : 
      13              : #include <boost/capy/detail/config.hpp>
      14              : 
      15              : #include <bit>
      16              : #include <cstddef>
      17              : #include <memory_resource>
      18              : #include <mutex>
      19              : 
      20              : namespace boost {
      21              : namespace capy {
      22              : 
      23              : /** Recycling memory resource with size-class buckets.
      24              : 
      25              :     This memory resource recycles memory blocks using power-of-two
      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
      28              :     block sharing.
      29              : 
      30              :     Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
      31              :     Allocations larger than 2048 bytes bypass the pools entirely.
      32              : 
      33              :     This is the default allocator used by run_async when no allocator
      34              :     is specified.
      35              : 
      36              :     @par Thread Safety
      37              :     Thread-safe. The thread-local pool requires no synchronization.
      38              :     The global pool uses a mutex for cross-thread access.
      39              : 
      40              :     @par Example
      41              :     @code
      42              :     auto* mr = get_recycling_memory_resource();
      43              :     run_async(ex, mr)(my_task());
      44              :     @endcode
      45              : 
      46              :     @see get_recycling_memory_resource
      47              :     @see run_async
      48              : */
      49              : class recycling_memory_resource : public std::pmr::memory_resource
      50              : {
      51              :     static constexpr std::size_t num_classes = 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
      54              :     static constexpr std::size_t bucket_capacity = 16;
      55              : 
      56              :     static std::size_t
      57         7492 :     round_up_pow2(std::size_t n) noexcept
      58              :     {
      59         7492 :         return n <= min_class_size ? min_class_size : std::bit_ceil(n);
      60              :     }
      61              : 
      62              :     static std::size_t
      63         7492 :     get_class_index(std::size_t rounded) noexcept
      64              :     {
      65         7492 :         std::size_t idx = std::countr_zero(rounded) - 6;  // 64 = 2^6
      66         7492 :         return idx < num_classes ? idx : num_classes;
      67              :     }
      68              : 
      69              :     struct bucket
      70              :     {
      71              :         std::size_t count = 0;
      72              :         void* ptrs[bucket_capacity];
      73              : 
      74         3839 :         void* pop() noexcept
      75              :         {
      76         3839 :             if(count == 0)
      77           93 :                 return nullptr;
      78         3746 :             return ptrs[--count];
      79              :         }
      80              : 
      81              :         // Peter Dimov's idea
      82           93 :         void* pop(bucket& b) noexcept
      83              :         {
      84           93 :             if(count == 0)
      85           93 :                 return nullptr;
      86            0 :             for(std::size_t i = 0; i < count; ++i)
      87            0 :                 b.ptrs[i] = ptrs[i];
      88            0 :             b.count = count - 1;
      89            0 :             count = 0;
      90            0 :             return b.ptrs[b.count];
      91              :         }
      92              : 
      93         3750 :         bool push(void* p) noexcept
      94              :         {
      95         3750 :             if(count >= bucket_capacity)
      96            4 :                 return false;
      97         3746 :             ptrs[count++] = p;
      98         3746 :             return true;
      99              :         }
     100              :     };
     101              : 
     102              :     struct pool
     103              :     {
     104              :         bucket buckets[num_classes];
     105              : 
     106           51 :         ~pool()
     107              :         {
     108          357 :             for(auto& b : buckets)
     109          399 :                 while(b.count > 0)
     110           93 :                     ::operator delete(b.pop());
     111           51 :         }
     112              :     };
     113              : 
     114              :     BOOST_CAPY_DECL static pool& local() noexcept;
     115              :     BOOST_CAPY_DECL static pool& global() noexcept;
     116              :     BOOST_CAPY_DECL static std::mutex& global_mutex() noexcept;
     117              : 
     118              : protected:
     119              :     BOOST_CAPY_DECL void*
     120              :     do_allocate(std::size_t bytes, std::size_t) override;
     121              : 
     122              :     BOOST_CAPY_DECL void
     123              :     do_deallocate(void* p, std::size_t bytes, std::size_t) override;
     124              : 
     125              :     bool
     126            0 :     do_is_equal(const memory_resource& other) const noexcept override
     127              :     {
     128            0 :         return this == &other;
     129              :     }
     130              : };
     131              : 
     132              : /** Returns pointer to the default recycling memory resource.
     133              : 
     134              :     The returned pointer is valid for the lifetime of the program.
     135              :     This is the default allocator used by run_async.
     136              : 
     137              :     @return Pointer to the recycling memory resource.
     138              : 
     139              :     @see recycling_memory_resource
     140              :     @see run_async
     141              : */
     142              : BOOST_CAPY_DECL
     143              : std::pmr::memory_resource*
     144              : get_recycling_memory_resource() noexcept;
     145              : 
     146              : } // namespace capy
     147              : } // namespace boost
     148              : 
     149              : #endif