为何用std::unordered_map的C++实现比等效Python字典实现慢很多？

为提升效率，采用坐标转换(x,y)->1000*x+y，代码用于解决OEIS序列A337663相关问题，核心逻辑是在棋盘上添加1并移除，以此衡量性能，同时跟踪棋盘上数字相邻位置的总和。

代码实现与运行耗时 #

C++实现（耗时约1秒） #

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <ctime>

using namespace std;
//I Know this is bad practice, but just for readability for now

void add_update_edges_and_used(int spot, unordered_map<int, unordered_set<int>> &edge_sums_to_locations, unordered_map<int, int> &edge_locations_to_sums,
                               unordered_set<int> &used_locations, int current_number) {
    used_locations.insert(spot);

    vector<int> neighbors { spot+1000,spot-1000,
                            spot+1,spot-1,
                            spot+1000+1,spot-1000+1,
                            spot+1000-1,spot-1000-1 };

    for (int neighbor : neighbors) {
        if (used_locations.count(neighbor) == 0) {
            if (edge_locations_to_sums.count(neighbor)) {
                edge_sums_to_locations.at(edge_locations_to_sums.at(neighbor)).erase(neighbor);
                edge_locations_to_sums.at(neighbor) += current_number;
            } else {
                edge_locations_to_sums.insert({neighbor, current_number});
            }

            int new_neighbor_sum = edge_locations_to_sums[neighbor];
            if (edge_sums_to_locations.count(new_neighbor_sum)) {
                edge_sums_to_locations.at(new_neighbor_sum).insert(neighbor);
            } else {
                unordered_set<int> new_edge_sum_locations;
                new_edge_sum_locations.insert(neighbor);
                edge_sums_to_locations.insert({new_neighbor_sum, new_edge_sum_locations});
            }

        }
    }
}

int main() {

    std::clock_t start_time = std::clock();

    unordered_map<int, unordered_set<int>> edge_sums_to_locations;
    unordered_map<int, int> edge_locations_to_sums;
    unordered_set<int> used_locations;


    for (int q=0; q<1000; q++) {
        edge_sums_to_locations.clear();
        edge_locations_to_sums.clear();
        used_locations.clear();

        for (int i=0; i<100; i++) {
            add_update_edges_and_used(i*4, edge_sums_to_locations, edge_locations_to_sums,
                                      used_locations, 1);
        }
    }

    std::clock_t tot_time = std::clock() - start_time;
    std::cout << "Time: "
              << ((double) tot_time) / (double) CLOCKS_PER_SEC
              << " seconds" << std::endl;

    return 0;
}

Python实现（耗时约0.4秒） #

import time
def add_update_edges_and_used(spot, edge_sums_to_locations, edge_locations_to_sums, 
                              used_locations, current_number):
    used_locations.add(spot)
    
    neighbors = {spot+1000,spot-1000,
                spot+1,spot-1,
                spot+1000+1,spot-1000+1,
                spot+1000-1,spot-1000-1}
    unused_neighbors = neighbors.difference(used_locations)
    
    for neighbor in unused_neighbors:
        if neighbor in edge_locations_to_sums.keys():
            edge_sums_to_locations[edge_locations_to_sums[neighbor]].remove(neighbor)
            edge_locations_to_sums[neighbor] += current_number
        else:
            edge_locations_to_sums[neighbor] = current_number
        new_neighbor_sum = edge_locations_to_sums[neighbor]
        if new_neighbor_sum in edge_sums_to_locations.keys():
            edge_sums_to_locations[new_neighbor_sum].add(neighbor)
        else:
            edge_sums_to_locations[new_neighbor_sum] = {neighbor}
            
start_time = time.time()
start_cpu_time = time.clock()

for q in range(1000):
    edge_sums_to_locations = {} #unordered map of ints to unordered set of ints
    edge_locations_to_sums = {} #unordered map of ints to ints
    used_locations = set() #unordered set of ints

    for i in range(100):
        add_update_edges_and_used(i*4, edge_sums_to_locations, edge_locations_to_sums, 
                                  used_locations, 1)

print(f'CPU time {time.clock() - start_cpu_time}')
print(f'Wall time {time.time() - start_time}')

经性能分析，规模扩大后差异依然存在，根源在于insert和remove操作，以下是该现象的原因及优化方案：

性能差异原因 #

• 标准库实现差异：Python的dict和set是高度优化的哈希表实现，针对常见操作做了大量工程优化，哈希冲突处理、内存预分配策略更贴合这类场景；而C标准库的unordered_map/unordered_set，不同编译器的实现效率有差异，部分场景下哈希函数性能、内存分配开销更高。另外Python的set.difference是底层C实现的批量操作，比C逐个遍历调用count更高效。
• 内存开销：C++中插入新的unordered_set到unordered_map时，需要构造并拷贝容器，内存分配与拷贝开销大；Python创建集合是轻量级操作，内存管理更灵活。
• 边界检查与循环开销：C的unordered_map::at会做额外边界检查，而Python字典访问的边界检查开销相对更低；同时C循环内逐个判断邻居是否被使用，比Python批量计算未使用邻居的额外判断更多。

C++代码优化方案 #

• 替换高性能容器：用Abseil或Boost库的flat_hash_map/flat_hash_set替代标准库容器，这类容器采用更紧凑的内存布局和高效哈希算法，能大幅提升插入、查找、删除性能。
• 优化邻居处理逻辑：模仿Python的批量处理，先收集所有未使用的邻居再统一处理，减少循环内的count调用次数：

  std::unordered_set<int> neighbors{spot+1000, spot-1000, spot+1, spot-1,
                                   spot+1001, spot-999, spot+999, spot-1001};
  std::vector<int> unused_neighbors;
  for (int n : neighbors) {
      if (!used_locations.contains(n)) {
          unused_neighbors.push_back(n);
      }
  }
  for (int neighbor : unused_neighbors) {
      // 原有处理逻辑
  }
  

• 减少边界检查：在确定键存在的情况下，用operator[]替代at访问unordered_map，避免不必要的边界检查开销。
• 开启编译器优化：编译时使用最高级优化选项，GCC/Clang用-O3 -march=native，MSVC用/O2，开启循环展开、函数内联等优化。
• 预分配内存：在每次循环清空容器后，调用reserve为容器预分配足够空间，避免频繁内存重分配：

  edge_sums_to_locations.reserve(1000);
  edge_locations_to_sums.reserve(1000);
  used_locations.reserve(100);
  

内容的提问来源于stack exchange，提问作者Tom