std::unordered_map 的桶数意外增长

Question

我想使用std::unordered地图作为容量有限的软件缓存。也就是说，我在构造函数中设置了存储桶的数量（不介意它实际上可能会变大）并通过以下方式插入新数据（如果还没有的话）：

如果数据所属的桶不为空，我将其节点替换为插入的数据（通过 C++17 提取-插入模式）。
不然我就直接插入数据

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

#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（在生产环境中对我可用），存储桶计数不是固定的而是增长的；输出为：

现场演示：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);

但我不想在生产代码中依赖这样的 "fragile" 解决方案。

Answer 1

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

滚动我们自己的哈希缓存

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

它长什么样子？

假设您有一个昂贵的函数要缓存。当使用递归实现编写时，斐波那契函数因调用自身而需要输入的指数时间而臭名昭著。

// Uncached version

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

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

// 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 微秒即可初始化缓存、填充缓存和 return 值！ You can see it run here.。在初始访问之后，从缓存中检索存储的值大约需要 6 纳秒.

（如果 Compiler Explorer 显示程序集而不是输出，请单击它旁边的选项卡。）

这个怎么写`Cache`class?

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

布尔值数组，跟踪哪些桶有值
一组键
一组值
位掩码和哈希函数
用于计算不在 table

为了计算一个值，我们：

检查密钥是否存储在 table
如果key不在table中，计算并存储值
Return储值

代码如下：

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)>;

std::unordered_map 的桶数意外增长

Number of buckets of std::unordered_map grows unexpectedly

c++

gcc

caching

unordered-map

libstdc++

滚动我们自己的哈希缓存

它长什么样子？

这个怎么写`Cache`class?

std::unordered_map 的桶数意外增长

Number of buckets of std::unordered_map grows unexpectedly

c++

gcc

caching

unordered-map

libstdc++

滚动我们自己的哈希缓存

它长什么样子？

这个怎么写Cacheclass?

这个怎么写`Cache`class?