c++ - 为什么 unordered_map "find + insert"比 "insert + check for success"快？

Question

我使用 unordered_map 作为稀疏 3D 数组 (128 x 128 x 128) 将值插入到网格中，前提是网格单元仍然空闲。

到目前为止，我总是使用 find() 检查单元格是否空闲，如果是，那么我使用 insert() 或 emplace() 添加了一个元素。现在我发现我可以使用 insert 和 emplace 的返回值来检查元素是否已添加，或者 map 中是否已经存在具有相同键的元素。我认为这可以提高性能，因为我可以完全删除 find 的使用。

事实证明，不是通过插入而不查找来提高性能，而是性能实际上下降了，我不知道为什么。

我已将我的应用程序简化为这个示例，其中点是随机生成的，然后插入到网格中。

#include <unordered_map>
#include <random>
#include <chrono>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>

using std::cout;
using std::endl;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::chrono::duration_cast;
using std::unordered_map;

int num_elements = 5'000'000;


void findThenInsert(){
    cout << endl << "find and emplace" << endl;

    auto start = high_resolution_clock::now();

    std::mt19937 gen(123);
    std::uniform_real_distribution<> dis(0, 128);

    unordered_map<int, int> grid;
    int count = 0;
    for(int i = 0; i < num_elements; i++){
        float x = dis(gen);
        float y = dis(gen);
        float z = (cos(x*0.1) * sin(x*0.1) + 1.0) * 64.0;

        int index = int(x) + int(y) * 128 + int(z) * 128 * 128;
        auto it = grid.find(index);
        if(it == grid.end()){
            grid.emplace(index, count);
            count++;
        }
    }

    cout << "elements: " << count << endl;
    cout << "load factor: " << grid.load_factor() << endl;

    auto end = high_resolution_clock::now();
    long long duration = duration_cast<milliseconds>(end - start).count();
    float seconds = duration / 1000.0f;
    cout << seconds << "s" << endl;
}


void insertThenCheckForSuccess(){
    cout << endl << "emplace and check success" << endl;

    auto start = high_resolution_clock::now();

    std::mt19937 gen(123);
    std::uniform_real_distribution<> dis(0, 128);

    unordered_map<int, int> grid;
    int count = 0;
    for(int i = 0; i < num_elements; i++){
        float x = dis(gen);
        float y = dis(gen);
        float z = (cos(x*0.1) * sin(x*0.1) + 1.0) * 64.0;

        int index = int(x) + int(y) * 128 + int(z) * 128 * 128;
        auto it = grid.emplace(index, count);
        if(it.second){
            count++;
        }
    }

    cout << "elements: " << count << endl;
    cout << "load factor: " << grid.load_factor() << endl;

    auto end = high_resolution_clock::now();
    long long duration = duration_cast<milliseconds>(end - start).count();
    float seconds = duration / 1000.0f;
    cout << seconds << "s" << endl;
}

int main(){

    findThenInsert();
    insertThenCheckForSuccess();

}

在这两种情况下， map 的大小都是 82901，所以我假设结果完全相同。

find and emplace:   0.937semplace then check: 1.268s

Answer 1

问题在于 emplace 的规范对于有效的关联容器，即使在失败情况下也需要分配；这种分配和重新分配的成本在 find-then-insert 策略中占主导地位。

这是因为 emplace指定为 emplace-construct value_type (即 pair<Key const, T> )来自其转发的参数；只有在构建了该对后，它才能对 key 进行哈希处理以检查它是否已经存在。 (它不能只接受第一个参数，因为它可能是 std::piecewise_construct 。)它也不能构造 pair在自动存储中，然后将其移动到节点中，因为 emplace未指定需要可复制甚至可移动的 value_type ，因此它必须在每次调用时执行潜在的昂贵节点分配。 (请注意，有序关联容器也有同样的问题，但与分配成本相比，探测的 O(log n) 成本更为显着。)

除非您的插入预计在大多数情况下都能成功，否则最好使用 find-then-emplace 而不是 emplace-then-test。您也可以使用 insert ，只要您确定您调用的是 value_type重载而不是转发到 emplace 的模板.

这是(可能)在 C++17 中修复的，它(应该)有 try_emplace ，具有与 emplace 相似的语义，但在失败情况下提高了性能。 (语义上的区别是映射类型在失败情况下不是 emplace-constructed；这使得例如将 unique_ptr 存储为映射类型成为可能。)