c++ - std::unordered_map 的桶数意外增长

Question

我想使用 std::unordered 映射作为容量有限的软件缓存。也就是说，我在构造函数中设置了存储桶的数量(不介意它实际上可能会变得更大)，并按照以下方式插入新数据(如果尚未存在):

1. 如果数据所属的存储桶不为空，我将用插入的数据替换其节点(通过 C++17 提取-插入模式)。
2. 否则，我只需插入数据即可。

模拟此方法的最小示例如下:

#include <iostream>
#include <unordered_map>

std::unordered_map<int, int> m(2);

void insert(int a) {
   auto idx = m.bucket(a);
   if (m.bucket_size(idx) > 0) {
      const auto& key = m.begin(idx)->first;
      auto nh = m.extract(key);
      nh.key() = a;
      nh.mapped() = a;
      m.insert(std::move(nh));
   }
   else
      m.insert({a, a});
}

int main() {
   for (int i = 0; i < 1000; i++) {
      auto bc1 = m.bucket_count();
      insert(i);
      auto bc2 = m.bucket_count();
      if (bc1 != bc2) std::cerr << bc2 << std::endl;
   }
}

问题是，使用 GCC 8.1(我可以在生产环境中使用)，存储桶计数不是固定的，而是增长的；输出如下:

7
17
37
79 
167
337
709
1493

现场演示:https://wandbox.org/permlink/c8nnEU52NsWarmuD

更新信息:else 分支中的存储桶计数始终增加:https://wandbox.org/permlink/p2JaHNP5008LGIpL .

但是，当我使用 GCC 9.1 或 Clang 8.0 时，存储桶计数保持固定(错误流中不会打印任何输出)。

我的问题是这是否是旧版本 libstdc++ 中的错误，或者我的方法不正确并且我无法以这种方式使用 std::unordered_map 。

---

此外，我发现当我将 max_load_factor 设置为某个非常高的数字时，问题就消失了，例如

m.max_load_factor(1e20f);

但我不想在生产代码中依赖这样一个“脆弱”的解决方案。

Answer 1

不幸的是，您遇到的问题似乎是 std::unordered_map 的旧实现中的错误。这个问题在 g++-9 中消失了，但如果您仅限于 g++-8，我建议滚动您自己的哈希缓存。

滚动我们自己的哈希缓存

值得庆幸的是，您想要编写的缓存类型实际上比编写完整的哈希表更简单，主要是因为如果值偶尔从表中删除也没关系。为了看看这有多困难，我编写了自己的版本。

那么它是什么样子的？

假设您有一个想要缓存的昂贵函数。当使用递归实现编写斐波那契函数时，由于它调用自身，因此在输入方面需要指数时间，这是臭名昭著的。

// Uncached version

long long fib(int n) {
    if(n <= 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2); 
}

让我们使用 Cache 类将其转换为缓存版本，稍后我将向您展示该类。我们实际上只需要在函数中添加一行代码即可:

// Cached version; much faster

long long fib(int n) {
    static auto fib = Cache(::fib, 1024); // fib now refers to the cache, instead of the enclosing function
    if(n <= 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);   // Invokes cache
}

第一个参数是您要缓存的函数(在本例中为 fib 本身)，第二个参数是容量。对于 n == 40，未缓存版本的运行时间为 487,000 微秒。缓存版本呢？只需 16 微秒即可初始化缓存、填充缓存并返回值! <强> You can see it run here. 。初始访问后，从缓存中检索存储的值大约需要 6 纳秒。

(如果编译器资源管理器显示程序集而不是输出，请单击它旁边的选项卡。)

我们如何编写这个Cache类？

这是它的一个紧凑的实现。 Cache 类存储以下内容

• bool 数组，用于跟踪哪些存储桶具有值
• 键数组
• 值数组
• 位掩码和哈希函数
• 用于计算表格中没有的值的函数

为了计算值，我们:

• 检查 key 是否存储在表中
• 如果键不在表中，则计算并存储值
• 返回存储的值

代码如下:

template<class Key, class Value, class Func>
class Cache {
    static size_t calc_mask(size_t min_cap) {
        size_t actual_cap = 1;
        while(actual_cap <= min_cap) {
            actual_cap *= 2;
        }
        return actual_cap - 1; 
    }
    size_t mask = 0;
    std::unique_ptr<bool[]> isEmpty; 
    std::unique_ptr<Key[]> keys;
    std::unique_ptr<Value[]> values;
    std::hash<Key> hash;
    Func func; 
   public:
    Cache(Cache const& c) 
      : mask(c.mask)
      , isEmpty(new bool[mask + 1])
      , keys(new Key[mask + 1])
      , values(new Value[mask + 1])
      , hash(c.hash)
      , func(c.func)
    {
        std::copy_n(c.isEmpty.get(), capacity(), isEmpty.get());
        std::copy_n(c.keys.get(), capacity(), keys.get());
        std::copy_n(c.values.get(), capacity(), values.get());
    }
    Cache(Cache&&) = default; 
    Cache(Func func, size_t cap)
      : mask(calc_mask(cap))
      , isEmpty(new bool[mask + 1])
      , keys(new Key[mask + 1])
      , values(new Value[mask + 1])
      , hash()
      , func(func) {
        std::fill_n(isEmpty.get(), capacity(), true); 
    }
    Cache(Func func, size_t cap, std::hash<Key> const& hash)
      : mask(calc_mask(cap))
      , isEmpty(new bool[mask + 1])
      , keys(new Key[mask + 1])
      , values(new Value[mask + 1])
      , hash(hash)
      , func(func) {
        std::fill_n(isEmpty.get(), capacity(), true); 
    }
    

    Value operator()(Key const& key) const {
        size_t index = hash(key) & mask;
        auto& value = values[index]; 
        auto& old_key = keys[index]; 
        if(isEmpty[index] || old_key != key) {
            old_key = key; 
            value = func(key); 
            isEmpty[index] = false; 
        }
        return value;
    }
    size_t capacity() const {
        return mask + 1;
    }
};
template<class Key, class Value>
Cache(Value(*)(Key), size_t) -> Cache<Key, Value, Value(*)(Key)>;