如何在频繁调用的函数中优化重用大型 std::unordered_map 作为临时变量？

Question

带有工作示例的简化问题：我想多次重用 std::unordered_map （我们称之为 umap），类似于以下虚拟代码（它不做任何有意义的事情）。我怎样才能让这段代码运行得更快？

#include <iostream>
#include <unordered_map>
#include <time.h>

unsigned size = 1000000;

void foo(){
    std::unordered_map<int, double> umap;
    umap.reserve(size);
    for (int i = 0; i < size; i++) {
        // in my real program: umap gets filled with meaningful data here
        umap.emplace(i, i * 0.1);
    }
    // ... some code here which does something meaningful with umap
}

int main() {

    clock_t t = clock();

    for(int i = 0; i < 50; i++){
        foo();
    }

    t = clock() - t;
    printf ("%f s\n",((float)t)/CLOCKS_PER_SEC);

    return 0;
}

在我的原始代码中，我想将矩阵条目存储在 umap 中。每次调用 foo 时，键值从 0 开始到 N，每次调用 foo 时 N 可以不同，但​​索引的上限为 10M。此外，值可以不同（与此处的虚拟代码相反，虚拟代码始终是i*0.1）。

我尝试创建一个非局部变量，以避免每次调用时umap重复分配内存。这需要在 的末尾umap.reserve()调用，但事实证明这实际上比使用局部变量慢（我测量了它）。umap.clear()foo

Answer 1

我不认为有什么好的方法可以直接完成你正在寻找的东西——也就是说，如果不清除地图，你就无法清除地图。我想你可以预先分配一些地图，然后将其中每一张作为“一次性地图”使用一次，然后在下次通话期间继续使用下一张地图，但我怀疑这会给整体加速，因为最后你必须立即清除所有这些，并且在任何情况下，这都将是 RAM 密集型且对缓存不友好的（在现代 CPU 中，RAM 访问通常是最重要的）性能瓶颈，因此最小化缓存未命中次数是最大化效率的方法）。

我的建议是，如果清除速度如此重要，您可能需要完全放弃使用unordered_map，而是使用更简单的东西，例如std::vector- 在这种情况下，您可以简单地保留一些有效项目 -向量整数，“清除”向量只需将计数设置回零即可。（当然，这意味着您牺牲了unordered_map的快速查找属性，但也许您在计算的这个阶段不需要它们？）