c++ - 为 boost::deque 保留 block 分配器？

Question

我想做 boost::container::deque 重用释放的 block 而不是释放它们然后分配新的 block 。boost::container::deque 允许的唯一配置选项是 compile-time specification of the block size (就项目或字节数而言)。
实际上，指定 block 大小是我想要使用的东西，但我也想指定在空闲后将保留的 block 数，并在需要新 block 时重用。但是，如图所示 here , 对于 boost::container::deque这个号码是0 ，所以它会在 block 空闲时立即释放!我想创建一个双端队列，这个数字等于 1 .
我看到了通过指定自定义分配器来实现这一目标的机会。考虑一下这个丑陋的:

template < typename Block >
struct PreservingAllocator : std::allocator<Block>
{
  using std::allocator<Block>::allocator;

  Block* allocate(size_t nn)
  {
    if (nn == 1) if (auto oldBlock = m_reserve->exchange(nullptr); !!oldBlock) return oldBlock;
    return std::allocator<Block>::allocate(nn);
  }

  void deallocate(Block* block, size_t nn)
  {
    if (nn == 1) block = m_reserve->exchange(block);
    if (!!block) std::allocator<Block>::deallocate(block, nn);
  }

private:
  static constexpr auto Deleter = [](std::atomic<Block*>* pointer)
  {
    if (!!pointer) if (auto block = pointer->exchange(nullptr); !!block)
      std::allocator<Block>{}.deallocate(block,1);
   delete pointer;
  };

  std::shared_ptr<std::atomic<Block*>> m_reserve = {new std::atomic<Block*>{nullptr},Deleter};
};

所以问题是。

如何为 boost::container::deque 指定 block 分配器( block ，而不是元素!)？

如果有办法，那么这样的规范会支持带状态的分配器吗？

如果是，那么上面提到的分配器会去吗？

毕竟，如果不是这样，我怎么能创建一个双端队列，它不会释放至少一个被释放的 block ，并且在以后需要一个新 block 时会重用它？

Answer 1

这给了我一个更多地使用分配器的借口。我选择了多态分配器——尽管这只是切线相关¹。

Aside: The relation is that with custom allocators you often want to propagate the allocator to nested types that are allocator-aware. See "Advanced" below

样本元素类型

struct X {
    std::string key, value;
};

它并没有变得更简单，尽管它允许我们尝试分享
稍后使用嵌套字符串的分配器。
跟踪内存资源
让我们创建一个跟踪内存资源。这很简单，我们将转发到标准 new/delete :

namespace pmr = boost::container::pmr;

struct tracing_resource : pmr::memory_resource {
    uint64_t n = 0, total_bytes = 0;

    virtual void* do_allocate(std::size_t bytes, std::size_t alignment) override {
        n += 1;
        total_bytes += bytes;
        return pmr::new_delete_resource()->allocate(bytes, alignment);
    }

    virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override {
        if (p) {
            n -= 1;
            total_bytes -= bytes;
        }
        return pmr::new_delete_resource()->deallocate(p, bytes, alignment);
    }

    virtual bool do_is_equal(const memory_resource& other) const noexcept override {
        return pmr::new_delete_resource()->is_equal(other);
    }
};

我们可以检查n (分配数量)以及在整个测试代码中各个点分配的总字节数。
测试程序
让我们一起放在main ，从我们的示踪剂开始:

tracing_resource tracer;

让我们在上面挂载一个池化资源:

pmr::unsynchronized_pool_resource res(&tracer);

auto allocations = [&] {
    fmt::print("alloc: #{}, {} bytes, cached = {}\n", tracer.n, tracer.total_bytes, cache_buckets(res));
};
allocations();

这将打印

alloc: #0, 0 bytes, cached = {0, 0, 0, 0, 0, 0, 0, 0, 0}

就在门口。
现在，让我们开始(重新)以各种模式分配一些双端队列:

pmr::deque<X> collection(&res);
auto report = [&] {
    fmt::print("collection = {}\nalloc: #{}, {} bytes, cached = {}\n", collection, tracer.n, tracer.total_bytes, cache_buckets(res));
};

std::vector data1 { X{"1", "eins"}, {"2", "zwei"},  {"3", "drei"}, };
std::vector data2 { X{"4", "vier"},   {"5", "fuenf"}, {"6", "sechs"}, };
std::vector data3 { X{"7", "sieben"}, {"8", "acht"},  {"9", "neun"}, };

auto i = 0;
for (auto const& data : {data1, data2, data3}) {
    for (auto el : data) {
        (i%2)
            ? collection.push_back(el)
            : collection.push_front(el);
    }

    report();

    collection.clear();
    report();
}

这将在容器的不同末端附加不同的序列。我们不会
做很多突变，因为当我们制作字符串时这会变得有趣
使用汇集的资源)。
现场演示
Live On Compiler Explorer

#include <boost/container/pmr/deque.hpp>
#include <boost/container/pmr/unsynchronized_pool_resource.hpp>

// debug output
#include <range/v3/all.hpp>
#include <fmt/ranges.h>
#include <fmt/ostream.h>
#include <iomanip>

namespace pmr = boost::container::pmr;

struct tracing_resource : pmr::memory_resource {
    uint64_t n = 0, total_bytes = 0;

    virtual void* do_allocate(std::size_t bytes, std::size_t alignment) override {
        n += 1;
        total_bytes += bytes;
        return pmr::new_delete_resource()->allocate(bytes, alignment);
    }

    virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override {
        if (p) {
            n -= 1;
            total_bytes -= bytes;
        }
        return pmr::new_delete_resource()->deallocate(p, bytes, alignment);
    }

    virtual bool do_is_equal(const memory_resource& other) const noexcept override {
        return pmr::new_delete_resource()->is_equal(other);
    }
};

struct X {
    std::string key, value;

    friend std::ostream& operator<<(std::ostream& os, X const& x) {
        return os << "(" << std::quoted(x.key) << ", " << std::quoted(x.value) << ")";
    }
};

auto cache_buckets(pmr::unsynchronized_pool_resource& res) {
    using namespace ::ranges;
    return views::iota(0ull)
        | views::take_exactly(res.pool_count())
        | views::transform([&](auto idx) {
            return res.pool_cached_blocks(idx);
        });
}

int main() {
    tracing_resource tracer;
    {
        pmr::unsynchronized_pool_resource res(&tracer);

        auto allocations = [&] {
            fmt::print("alloc: #{}, {} bytes, cached = {}\n", tracer.n, tracer.total_bytes, cache_buckets(res));
        };
        allocations();

        {
            pmr::deque<X> collection(&res);
            auto report = [&] {
                fmt::print("collection = {}\nalloc: #{}, {} bytes, cached = {}\n", collection, tracer.n, tracer.total_bytes, cache_buckets(res));
            };

            std::vector data1 { X{"1", "eins"}, {"2", "zwei"},  {"3", "drei"}, };
            std::vector data2 { X{"4", "vier"},   {"5", "fuenf"}, {"6", "sechs"}, };
            std::vector data3 { X{"7", "sieben"}, {"8", "acht"},  {"9", "neun"}, };
                            
            auto i = 0;
            for (auto const& data : {data1, data2, data3}) {
                for (auto el : data) {
                    (i%2)
                        ? collection.push_back(el)
                        : collection.push_front(el);
                }

                report();

                collection.clear();
                report();
            }
        }

        allocations();
    }

    fmt::print("alloc: #{}, {} bytes\n", tracer.n, tracer.total_bytes);
}

打印

alloc: #0, 0 bytes, cached = {0, 0, 0, 0, 0, 0, 0, 0, 0}
collection = {("3", "drei"), ("2", "zwei"), ("1", "eins")}
alloc: #4, 1864 bytes, cached = {0, 0, 0, 0, 0, 1, 0, 0, 0}
collection = {}
alloc: #4, 1864 bytes, cached = {0, 0, 0, 0, 0, 2, 0, 0, 0}
collection = {("6", "sechs"), ("5", "fuenf"), ("4", "vier")}
alloc: #4, 1864 bytes, cached = {0, 0, 0, 0, 0, 2, 0, 0, 0}
collection = {}
alloc: #4, 1864 bytes, cached = {0, 0, 0, 0, 0, 2, 0, 0, 0}
collection = {("9", "neun"), ("8", "acht"), ("7", "sieben")}
alloc: #4, 1864 bytes, cached = {0, 0, 0, 0, 0, 2, 0, 0, 0}
collection = {}
alloc: #4, 1864 bytes, cached = {0, 0, 0, 0, 0, 2, 0, 0, 0}
alloc: #4, 1864 bytes, cached = {0, 0, 1, 0, 0, 3, 0, 0, 0}
alloc: #0, 0 bytes

先进的
正如所 promise 的，我们可以让元素类型分配器感知并显示传播:

 #include <boost/container/pmr/string.hpp>
 // ...

 struct X {
     using allocator_type = pmr::polymorphic_allocator<X>;
 
     template<typename K, typename V>
     explicit X(K&& key, V&& value, allocator_type a = {})
         : key(std::forward<K>(key), a), value(std::forward<V>(value), a) {}
 
     pmr::string key, value;
 };

让我们修改测试驱动程序以替换字符串文字中的元素:

std::vector data1 { std::pair{"1", "eins"}, {"2", "zwei"},  {"3", "drei"}, };
std::vector data2 { std::pair{"4", "vier"},   {"5", "fuenf"}, {"6", "sechs"}, };
std::vector data3 { std::pair{"7", "sieben"}, {"8", "acht"},  {"9", "neun"}, };
                
auto i = 0;
for (auto const& data : {data1, data2, data3}) {
    for (auto [k,v] : data) {
        (i%2)
            ? collection.emplace_back(k, v)
            : collection.emplace_front(k, v);
    }

为了更好地衡量，让我们也改变嵌套字符串值之一:

    collection.at(1).value.append(50, '*'); // thwart SSO
    report();

    collection.at(1).value = "sept";
    report();

再次演示 Live On Compiler Explorer

#include <boost/container/pmr/deque.hpp>
#include <boost/container/pmr/string.hpp>
#include <boost/container/pmr/unsynchronized_pool_resource.hpp>

// debug output
#include <range/v3/all.hpp>
#include <fmt/ranges.h>
#include <fmt/ostream.h>
#include <iomanip>

namespace pmr = boost::container::pmr;

struct tracing_resource : pmr::memory_resource {
    uint64_t n = 0, total_bytes = 0;

    virtual void* do_allocate(std::size_t bytes, std::size_t alignment) override {
        n += 1;
        total_bytes += bytes;
        return pmr::new_delete_resource()->allocate(bytes, alignment);
    }

    virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override {
        if (p) {
            n -= 1;
            total_bytes -= bytes;
        }
        return pmr::new_delete_resource()->deallocate(p, bytes, alignment);
    }

    virtual bool do_is_equal(const memory_resource& other) const noexcept override {
        return pmr::new_delete_resource()->is_equal(other);
    }
};

struct X {
    using allocator_type = pmr::polymorphic_allocator<X>;

    template<typename K, typename V>
    explicit X(K&& key, V&& value, allocator_type a = {})
        : key(std::forward<K>(key), a), value(std::forward<V>(value), a) {}

    pmr::string key, value;

    friend std::ostream& operator<<(std::ostream& os, X const& x) {
        return os << "(" << std::quoted(x.key.c_str()) << ", " << std::quoted(x.value.c_str()) << ")";
    }
};

auto cache_buckets(pmr::unsynchronized_pool_resource& res) {
    using namespace ::ranges;
    return views::iota(0ull)
        | views::take_exactly(res.pool_count())
        | views::transform([&](auto idx) {
            return res.pool_cached_blocks(idx);
        });
}

int main() {
    tracing_resource tracer;
    {
        pmr::unsynchronized_pool_resource res(&tracer);

        auto allocations = [&] {
            fmt::print("alloc: #{}, {} bytes, cached = {}\n", tracer.n, tracer.total_bytes, cache_buckets(res));
        };
        allocations();

        {
            pmr::deque<X> collection(&res);
            auto report = [&] {
                fmt::print("collection = {}\nalloc: #{}, {} bytes, cached = {}\n", collection, tracer.n, tracer.total_bytes, cache_buckets(res));
            };

            std::vector data1 { std::pair{"1", "eins"}, {"2", "zwei"},  {"3", "drei"}, };
            std::vector data2 { std::pair{"4", "vier"},   {"5", "fuenf"}, {"6", "sechs"}, };
            std::vector data3 { std::pair{"7", "sieben"}, {"8", "acht"},  {"9", "neun"}, };
                            
            auto i = 0;
            for (auto const& data : {data1, data2, data3}) {
                for (auto [k,v] : data) {
                    (i%2)
                        ? collection.emplace_back(k, v)
                        : collection.emplace_front(k, v);
                }

                report();

                collection.at(1).value.append(50, '*'); // thwart SSO
                report();

                collection.at(1).value = "sept";
                report();

                collection.clear();
                report();
            }
        }

        allocations();
    }

    fmt::print("alloc: #{}, {} bytes\n", tracer.n, tracer.total_bytes);
}

打印:

alloc: #0, 0 bytes, cached = {0, 0, 0, 0, 0, 0, 0, 0, 0}
collection = {("3", "drei"), ("2", "zwei"), ("1", "eins")}
alloc: #4, 1864 bytes, cached = {0, 0, 0, 0, 0, 1, 0, 0, 0}
collection = {("3", "drei"), ("2", "zwei**************************************************"), ("1", "eins")}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 0, 0, 1, 0, 0, 0}
collection = {("3", "drei"), ("2", "sept"), ("1", "eins")}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 0, 0, 1, 0, 0, 0}
collection = {}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 1, 0, 2, 0, 0, 0}
collection = {("6", "sechs"), ("5", "fuenf"), ("4", "vier")}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 1, 0, 2, 0, 0, 0}
collection = {("6", "sechs"), ("5", "fuenf**************************************************"), ("4", "vier")}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 0, 0, 2, 0, 0, 0}
collection = {("6", "sechs"), ("5", "sept"), ("4", "vier")}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 0, 0, 2, 0, 0, 0}
collection = {}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 1, 0, 2, 0, 0, 0}
collection = {("9", "neun"), ("8", "acht"), ("7", "sieben")}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 1, 0, 1, 0, 0, 0}
collection = {("9", "neun"), ("8", "acht**************************************************"), ("7", "sieben")}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 0, 0, 1, 0, 0, 0}
collection = {("9", "neun"), ("8", "sept"), ("7", "sieben")}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 0, 0, 1, 0, 0, 0}
collection = {}
alloc: #5, 2008 bytes, cached = {0, 0, 0, 1, 0, 2, 0, 0, 0}
alloc: #5, 2008 bytes, cached = {0, 0, 1, 1, 0, 3, 0, 0, 0}
alloc: #0, 0 bytes

结论
虽然我选择了多态分配器，因为它们支持 scoped_allocator_adaptor<> - 样式传播默认情况下，以上所有内容都可以使用静态类型分配器创建。
它确实表明，如果您使用池分配器，则双端队列行为将变为池化。

Aside: Pool allocators exist that are able to forgo cleanup, which can be valid in some scenarios, e.g. where the entire memory pool lives on the stack anyways. This is a common allocation optimization technique, allowing large numbers of deallocations/destructions to be skipped.

解决列表中的更多问题:

问:如何为 boost::container::deque 指定 block 分配器
( block ，而不是元素!)？
答:我认为分配器本质上总是被调用 block ，
因为双端队列的工作方式。

问:如果有办法，那么这样的规范是否支持分配器
与状态？
答:标准库和 Boost Container 都应该支持
这些天有状态的分配器。如有疑问，Boost Container 有您的
背部。

问:如果是，那么上面提到的分配器会去吗？
答:我没有仔细看，但你可以把它放在同一个测试台上
找出答案

问:毕竟，如果不是这样，我怎么能做一个不会
至少释放一个释放的 block ，并在稍后重用它
需要新的区 block 吗？
答:往上看。我不确定我是否理解“在
至少一个”子句，但我确实注意到 Boost 的双端队列实现确实可以
一个“私有(private) map ”分配——大概是为了一些 block 记账开销
- 一直存在直到 deque 对象被销毁。本次分配
不会在(默认)构造时发生，而是在以后发生。