代码之家 › 专栏 › 技术社区 › Marc Mutz - mmutz

无序的_集能否为节点和存储桶列表使用不同的分配器?

c++pmr unordered-set allocator c++17 c++

Marc Mutz - mmutz · 技术社区 · 5 年前

我想用一个 std::pmr::unordered_map 用一个 std::pmr::monotonic_buffer_resource .这两种方法很好地结合在一起,因为集合的节点是稳定的,所以我不会通过重新分配在缓冲区资源中创建很多漏洞:

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

也就是说,除了桶列表之外,当集合超过指定值时,需要重新分配桶列表 max_load_factor() .假设我不能 reserve() 我的出路是,实际上我关心的是旧的桶列表在增长后在缓冲区资源中留下的漏洞,我的选择是什么?

如果我知道的话 unordered_set 实现为 std::vector<std::forward_list> ,就像在(某些版本的)MSVC中一样,那么我应该能够使用 scoped_allocator 为 vector 还有 forward_list .但是a)我不能依赖 无序集 成为一个 vector<forward_list> 在可移植代码和b)中 作用域分配程序 是一个 Allocator 鉴于 monotonic_buffer_resource 是一个 memory_resource ,阻抗失配将导致非常复杂的初始化。

或者我可以写一封信 switch_memory_resource 代表其他人 内存资源 s取决于请求的大小。然后我可以使用 单调缓冲资源 对于与节点大小相匹配的请求(但是,我也无法通过便携方式知道),以及 default_memory_resource() 其他一切。我可能会有根据地猜测,节点最多 sizeof(struct {void* next; size_t hash; T value;}) ,通过将其乘以2来增加一些误差,并将其用作两者之间的分界点 内存资源 s、但我想知道是否有更干净的方法?

0 回复 | 直到 5 年前

Pablo Halpern 5 年前

我几年前提出的少量具体资源类型被C++17采用,这是一组最简单的有用分配器。正如你的问题所证明的,它们并不能为每种情况提供最佳的行为。没有太多的调谐拨号盘,我对功能缺失感到遗憾,但它们在大多数情况下仍然有用。

对于你的具体情况,你说“假设我不能” reserve() 我的出路是,实际上我关心的是旧的桶列表在增长后在缓冲区资源中留下的漏洞。“我不确定是否有任何通用的分配器能帮到你。存储桶列表的几何增长会在任何分配策略中留下漏洞。问题是这些漏洞是否可以重复使用和/或最小化。正如你所指出的,只有针对特定情况精心定制的分配器才能将这些漏洞最小化。但也许你的假设是:他们太强大了。

考虑一下 std::pmr::vector<int> .这是最糟糕的情况 monotonic_buffer_resource 因为每次重新分配都会导致内存泄漏。然而,即使在这种情况下,最糟糕的内存浪费也只有50%;i、例如,它使用的内存永远不会超过完全重用内存块的资源的两倍。诚然,50%可能非常糟糕,但在你的情况下,我们谈论的要少得多。对于一个相当大的集合,与存储桶和数据本身相比,存储桶列表很小,您可以使用 reserve 尽量减少再分配。所以我的第一条建议是继续使用 单调缓冲资源 在没有改变的情况下,测量你是否有不可接受的内存使用。第二个实验是使用 unsynchronized_pool_resource 由(上游)的 单调缓冲资源 .

如果您决定为此目的创建一个自定义资源,这可能会很有成效,甚至可能会很有趣,那么选择一些较低的阈值来传递给单调分配器的方法可能会奏效,而且实际上不会花费很多精力。你也可以考虑使之适应:保留最后一个,比如说,4个分配大小的列表。如果任何大小得到两次以上的点击,那么假设它是您的节点大小,并从单调资源中分配这些节点,而其他请求则直接传递到上游资源。但是,要小心,只有在知道发生了什么情况时才使用这种自定义分配器。如果你有 std::pmr::unordered_set<std::pmr::string> ,则这两种方法都可能导致许多字符串从上游资源分配,从而失去单调缓冲区的好处。正如你所见,在一般情况下,对存储空间过于吝啬可能会适得其反。你可能会发现未经修改的 单调缓冲资源 这是一个更好的选择。

祝你好运,请在这里报告你的发现。另外,如果你有一个想法 通用型 资源,可以解决您的问题(或任何其他常见的分配问题),我很乐意听到它。标准中当然还有一些更有用的资源类型。

Surt 5 年前

这个 definition 属于 std::pmr::unordered_set

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

这表明它仅用于节点。

但是 short test 这两个词都用,这让我很难过。因此,唯一的办法将是测试分配的规模。

这部分表示分配器只考虑 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);
  }

当我看到已经存在pmr前 scoped_allocator_adaptor 我不知道它是否与 pmr ,这将需要进一步调查。