unordered_set可以使用不同的分配器为节点和桶列表分别分配内存吗？

Question

unordered_set可以使用不同的分配器为节点和桶列表分别分配内存吗？

12

我想使用带有std::pmr::monotonic_buffer_resource的std::pmr::unordered_map。这两者很搭配，因为该集合的节点是稳定的，所以不需要通过重新分配来创建大量的缓冲区空洞：

 std::pmr::monotonic_buffer_resource res;
 std::pmr::unordered_set<T> set(&res);

那就是说，除了bucket list之外，在set重新散列时需要重新分配，因为它超过了max_load_factor()。假设我无法通过reserve()解决这个问题，并且我真的关心由旧bucket list留下的缓冲区资源中的空洞，那么我的选择是什么？

如果我知道unordered_set是作为std::vector实现的（在某些版本的MSVC中），那么我应该能够使用scoped_allocator为vector和forward_list提供不同的分配器。但是a）我不能在可移植代码中依赖于unordered_set是一个vector，并且b）scoped_allocator是一个分配器，而monotonic_buffer_resource是一个memory_resource，这种阻抗不匹配将导致非常复杂的初始化。

或者我可以编写一个switch_memory_resource，根据请求的大小委托给其他memory_resource。然后，我可以为与节点大小匹配的请求使用monotonic_buffer_resource（但是，我也无法在可移植方式中知道节点的大小），并为其他所有请求使用default_memory_resource()。我可能可以做出合理的猜测，即节点最多为sizeof(struct {void* next; size_t hash; T value;})，通过将其乘以2来添加误差边界，并将其用作两个memory_resource之间的切换点，但我想知道是否有更简洁的方法？

- Marc Mutz - mmutz

2个回答

0

std::pmr::unordered_set 的{{definition}}

using unordered_set = std::unordered_set<Key, Hash, Pred,
                                         std::pmr::polymorphic_allocator<Key>>

这表明它仅用于节点。

但短测试显示它同时用于两者，这让我很难过。因此，唯一的方法就是根据分配的大小进行测试。

此部分表明分配器仅考虑Key。

std::pmr::polymorphic_allocator<**Key**>

在旧的分配器中，有一个重新绑定函数可以将其转换为另一种分配器类型，但我在pmr中没有看到它（请参见注释中的std::allocator_traits）。

我开始写这样的东西。

  void* do_allocate(std::size_t bytes, std::size_t alignment) override {
    if (bytes == first_size)
      return first_alloc->allocate(bytes, alignment);
    return second_alloc->allocate(bytes, alignment);
  }

当我看到已经存在一个预先定义的scoped_allocator_adaptor时，我不知道它是否与pmr兼容，这需要进一步调查。

- Surt

@PabloHalpern 我与Surt的观点相矛盾。 - bolov

@PabloHalpern，分配器提到“Key”而没有其他内容的点。 - Surt

1

@Surt。哦，你是指std::allocator<Key>。这是C++98中分配器规范的不幸遗留问题。实际上，分配器从未用于分配键，因为键是较大节点的一部分。在C++98中规定分配器的传统方式是，即使从未使用过，它们也会在value_type上实例化。这不是描述错误，而是一个令人遗憾的混淆源。 - Pablo Halpern

1

@PabloHalpern 没错，所以那里的类型没有意义，这有点令人困惑。 - Surt

1

@Surt，你没有在std::pmr::polymorphic_allocator中看到rebind的原因是它在std::allocator_traits中存在通用性。一个库应该总是使用std::allocator_traits<allocator_type>::rebind_alloc<Node>而不是allocator_type::rebind<Node>::other。请参见标准中的**[allocator.requirements]和[allocator.traits]**章节。 - Pablo Halpern

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pablo Halpern · Accepted Answer

我几年前提出的仅有的几种具有实用性的分配器类型被采纳进入了C++17标准，它们是一组极简主义的有用分配器。就像你提出的问题所证明的那样，它们并不能为每种情况提供最佳行为。虽然我有一些遗憾错过了一些功能，但它们在大多数情况下仍然很有用。

对于你的具体情况，你说：“假设我不能通过reserve()轻松解决这个问题，并且我真的关心旧桶列表留下的缓冲区资源中的空洞。” 我不确定任何通用分配器能够帮助你。桶列表的几何增长会在任何分配策略中留下空洞。问题是这些空洞是否可以被重新使用和/或最小化。正如你指出的，只有一个非常仔细定制的特定情况下的分配器才能最小化这些空洞。但也许你的假设太强了。

考虑一个std::pmr::vector。这是monotonic_buffer_resource的最坏情况，因为每次重新分配都会导致内存泄漏。即使在这种情况下，最坏的内存浪费也只有50％；即它永远不会比使用完美重用内存块的资源使用两倍多的内存。当然，50％可能非常糟糕，但在你的情况下，我们谈论的远远不到这个数字。对于一个相当大的数据集，桶列表相对于桶和数据本身来说很小，因此您可以使用reserve来最小化重新分配。因此，我的第一个建议是继续使用未经修改的monotonic_buffer_resource，并测量是否出现了不可接受的内存使用情况。第二个实验是使用由(上游)monotonic_buffer_resource支持的unsynchronized_pool_resource。

如果你决定为此创建自定义资源，这可能是有成果甚至有趣的，那么你选择一些较低的阈值传递给单调分配器的方法可能会起作用，并且并不需要太多的工作。您还可以考虑使其自适应：保留最近4个分配大小的列表。如果任何尺寸超过两次，则假定它是您的节点大小，并从单调资源分配这些节点，而其他请求则直接传递给上游资源。但是要小心，只有在您知道发生了什么时才使用此自定义分配器。如果您有一个std::pmr::unordered_set，那么这两种方法都可能导致许多字符串从上游资源分配，从而失去monotonic buffer的好处。如你所见，在桶列表的内存分配方面过于吝啬可能会在通用环境中适得其反。你很可能会发现未修改的monotonic_buffer_resource是更好的选择。

祝你好运，并请在此处报告您的发现。如果您对一个可以解决您的问题（或任何其他常见分配问题）的通用资源有想法，我很乐意听取。标准中肯定还有一些有用的资源类型的空间。