Constant Time std::unordered_map<size_t, size_t> 和个人 hashmap 实现

Question

我实现了自己的哈希图，我想将其与 std::unordered_map 进行基准测试。我使用如下函数来测量设置、成功获取和不成功获取所需的纳秒数：

size_t umap_put_speed(std::unordered_map<size_t, size_t> &umap, size_t key, size_t value){
    auto t1 = high_resolution_clock::now();
    umap[key] = value;
    auto t2 = high_resolution_clock::now();
    auto ns_int = duration_cast<nanoseconds>(t2 - t1);
    return ns_int.count();
}

size_t umap_get_speed(std::unordered_map<size_t, size_t> &umap, size_t key){
    auto t1 = high_resolution_clock::now();
    umap.find(key);
    auto t2 = high_resolution_clock::now();
    auto ns_int = duration_cast<nanoseconds>(t2 - t1);
    return ns_int.count();
}

size_t single_put_speed(HashMap<size_t, size_t, GenericHash<size_t> > &hmap, size_t key, size_t value){
    auto t1 = high_resolution_clock::now();
    hmap.put(key, value);
    auto t2 = high_resolution_clock::now();
    auto ns_int = duration_cast<nanoseconds>(t2 - t1);
    return ns_int.count();
}

size_t single_get_speed(HashMap<size_t, size_t, GenericHash<size_t> > &hmap, size_t key){
    size_t value;
    auto t1 = high_resolution_clock::now();
    hmap.get(key, value);
    auto t2 = high_resolution_clock::now();
    auto ns_int = duration_cast<nanoseconds>(t2 - t1);
    return ns_int.count();
}

然后我将时间写入 CSV 文件，如下所示：

void test_put_speed(){
    std::ofstream benchmark_put;
    benchmark_put.open("benchmarks/put.csv");
    
    benchmark_put << "Num Entries,Linear Map,Unordered Map\n";
    
    // Declare hashmaps
    HashMap<size_t, size_t, GenericHash<size_t> > lmap(SMALL_SIZE);
    std::unordered_map<size_t, size_t> umap;
    
    // Put times
    size_t time_lmap_put = 0;
    size_t time_umap_put = 0;
    
    size_t count = 0;
    for(size_t i = 0; i < MAX_ELEM; i++){
        if(count == WINDOW_SIZE){
            benchmark_put << i << ", ";
            benchmark_put << time_lmap_put/(count) << ", ";
            benchmark_put << time_umap_put/(count) << "\n";
    
            time_lmap_put = 0;
            time_umap_put = 0;
    
            count = 0;
        }
    
        time_lmap_put += lmap_put_speed(lmap, i, i);
        time_umap_put += umap_put_speed(umap, i, i);
    
        count += 1;
    }    
}

但是，我得到以下纳秒的插入、成功搜索和不成功搜索：

我知道 hashmap 的设计平均需要 O(1) 时间，但是对于超过一百万的项目，我会认为我添加的项目会从缓存泄漏到主内存中，从而导致访问变慢。我从根本上做错了什么吗？或者我对为什么我期望性能变慢的理解不正确？

Answer 1

虽然这本身不是解决方案，但它是我最终获得一些令我更满意的结果的方式。我改变了两件事。首先，我没有测量单独的插入、查找和删除，而是测量了将 K 个操作链接在一起所花费的时间。这让我更清楚地了解我的实施与 unordered_map 相比有多少 faster/slower。我的新功能如下所示：

double umap_insert_speed(std::unordered_map<size_t, size_t> &umap, std::vector<size_t> keys){
    auto t1 = steady_clock::now();
    for(size_t key : keys){
        umap[key] = 1;    
    }
    auto t2 = steady_clock::now();
    duration<double> s_double = t2 - t1;
    return s_double.count();
}

生成的图表如下所示：

我改变的第二件事是如何在不调用 emplace 函数的情况下绕过我的计时函数。我只是在循环中添加了一个运行总和，所以我将使用放置的值：

double umap_emplace_speed(std::unordered_map<size_t, size_t> &umap, std::vector<size_t> keys){
    size_t value;
    size_t sum = 0;
    auto t1 = steady_clock::now();
    for(size_t key: keys){
        umap.emplace(key, value);
        sum += value;
    }
    auto t2 = steady_clock::now();
    duration<double> s_double = t2 - t1;
    return s_double.count();
}

Constant Time std::unordered_map<size_t, size_t> 和个人 hashmap 实现

Constant Time std::unordered_map<size_t, size_t> and personal hashmap implementation

c++

hashmap