将std::vectors存储在google::dense_hash_map中会使速度变慢

Question

我需要将uint64->[uint64列表]（每个哈希表的列表长度是恒定的）进行映射。

我已经尝试使用google::dense_hash_map的两种方式：

1. google::dense_hash_map<uint64, std::array<uint64, 10>, Hash64> //这里以10为例 2. google::dense_hash_map<uint64, std::vector<uint64>, Hash64> (1) 比(2)快得多（3倍）。问题是，我不想在编译时定义数组的大小，而是在定义哈希表时定义它，是否有其他可能的选项？

我的大部分操作都是修改哈希表中的值，有时我会删除所有元素，以便可以使用相同的已分配内存。

- voichek

---

第二个选项以何种方式更慢？你是如何确定的？你在测量什么？ - Athos vk

与std::unordered_map相比，它看起来如何？ - Yksisarvinen

(1)比google::dense_hash_map执行更快的原因与它使用的容器有关，而不是google::dense_hash_map本身。相比于std::vector，std::array是一个更简单的容器，复制std::array比复制std::vector更为简单。实际代码可能存在一些低效的操作，例如通过值传递参数等，这会放大std::vector在这方面的低效性。找到自己代码的低效之处并加以修复，问题并不在dense_hash_map中。 - Sam Varshavchik

std::vector 将其元素存储在动态分配的缓冲区中，这涉及到访问元素时的间接寻址，并可能导致更多的缓存未命中。我不熟悉 google::dense_hash_map 的内部机制，但我认为使用 std::array 可以更紧凑地存储数组元素在内存中，因此较少需要（缓慢的）动态内存分配。 - Daniel Langr

@DanielLangr 这类似于使用线性探测的平面哈希表，首先在一个类型不可知的元表上完成。查找通常具有很少的元素访问。 - Passer By

Answer 1

你可以尝试使用一些内存池来避免动态分配并获得更紧凑（缓存友好）的内存使用。这是一个非常简单的示例解决方案，与 boost::dense_hash_map 一起使用效果很好：

template <typename T>
class pooled_rt_array {
   public:
      static void init_pool(size_t capacity) {
         pool_.resize(capacity);
         top_ = pool_.data();
      }

      pooled_rt_array() : data_(top_), size_(0) { }

      pooled_rt_array(size_t size) : data_(top_), size_(size) {
         assert(top_ + size <= pool_.data() + pool_.size()); // not safe, in fact
         top_ += size;
      }

      T & operator[](size_t n) { return *(data_ + n); }
      const T & operator[](size_t n) const { return *(data_ + n); }
      size_t size() const { return size_; }

   private:
      T * data_;
      size_t size_;

      static std::vector<T> pool_;
      static T * top_;
};

template <typename T>
std::vector<T> pooled_rt_array<T>::pool_;

template <typename T>
T * pooled_rt_array<T>::top_;

一个简单的用法：

int main() {
    using value_t = pooled_rt_array<uint64_t>;
    google::hash_dense_map<uint64_t, value_t
       /* , std::hash<uint64_t>, std::equal_to<uint64_t> */
    > m;
    m.set_empty_key(0xFFFFFFFFFFFFFFFF);

    size_t n;
    std::cin >> n;
    value_t::init_pool(1000000 * n); // pool for 1000000 arrays
    value_t a(n);
    for (size_t i = 0; i < a.size(); i++) a[i] = i;
    m[0] = std::move(a);
}

我还进行了一些基准测试，这比将std::vector存储在映射中要快得多。

如果所有数组的大小都相同，甚至可以从pooled_rt_array中删除size_成员变量，这将使其实例具有单个指针的大小。

---

请注意，有更为复杂的方式来利用内存池，例如Boost提供的方式。例如，您可以使用一些特殊的池感知分配器，并将它们与std::vector一起使用。

- Daniel Langr