go 和 c++ 之间的地图性能比较

Question

我不明白golang怎么在这个操作上比c++快10倍，甚至go中的map查找比c++快3倍。

这是 C++ 片段

#include <iostream>

#include <unordered_map>

#include <chrono>

std::chrono::nanoseconds elapsed(std::chrono::steady_clock::time_point start) {

    std::chrono::steady_clock::time_point now = std::chrono::high_resolution_clock::now();

    return std::chrono::duration_cast<std::chrono::nanoseconds>(now - start);

}

void make_map(int times) {

    std::unordered_map<double, double> hm;

    double c = 0.0;

    for (int i = 0; i < times; i++) {

        hm[c] = c + 10.0;

        c += 1.0;

    }

}

int main() {

    std::chrono::steady_clock::time_point start_time = std::chrono::high_resolution_clock::now();

    make_map(10000000);

    printf("elapsed %lld", elapsed(start_time).count());

}

这是 golang 片段：

func makeMap() {

    o := make(map[float64]float64)

    var i float64 = 0

    x := time.Now()

    for ; i <= 10000000; i++ {

        o[i] = i+ 10

    }

    TimeTrack(x)

}

func TimeTrack(start time.Time) {

    elapsed := time.Since(start)

    // Skip this function, and fetch the PC and file for its parent.

    pc, _, _, _ := runtime.Caller(1)

    // Retrieve a function object this functions parent.

    funcObj := runtime.FuncForPC(pc)

    // Regex to extract just the function name (and not the module path).

    runtimeFunc := regexp.MustCompile(`^.*\.(.*)$`)

    name := runtimeFunc.ReplaceAllString(funcObj.Name(), "$1")

    log.Println(fmt.Sprintf("%s took %s", name, elapsed))

}

我想知道的是如何优化 c++ 以获得更好的性能。

Answer 1

很难确定“C++ 的速度”（对于几乎任何特定事物），因为它可能取决于相当多的变量，例如您使用的编译器。例如，对于此代码的 C++ 版本，我通常会看到 gcc 和 msvc 之间存在 2:1 左右的差异。至于 C++ 和 Go 之间的差异，我猜这主要归结于哈希表的实现方式的差异。一个明显的一点是 Go 的 map 实现一次以 8 个元素的块为单位分配数据空间。至少我见过的标准库实现，std::unordered_map每个块只放置一个项目。我们希望这意味着在典型情况下，C++ 代码将从堆/空闲存储中进行大量的单独分配，因此它的速度将更多地取决于堆管理器的速度。Go 版本还应该具有更高的引用位置，以便更好地使用缓存。考虑到这些差异，我有点惊讶您只看到 10:1 的差异。我的直接猜测会（稍微）高于这个数值——但众所周知，一次测量值超过 100 次猜测。

Answer 2

已更新以测量cpp和的类似操作go。它在调用制图函数之前开始测量，并在函数返回时结束测量。两个版本都在地图中保留空间并返回创建的地图（从中打印了几个数字）。稍作修改cpp：#include <iostream>#include <unordered_map>#include <chrono>std::unordered_map<double, double> make_map(double times) {&nbsp; &nbsp; std::unordered_map<double, double> m(times);&nbsp; &nbsp; for (double c = 0; c < times; ++c) {&nbsp; &nbsp; &nbsp; &nbsp; m[c] = c + 10.0;&nbsp; &nbsp; }&nbsp; &nbsp; return m;}int main() {&nbsp; &nbsp; std::chrono::high_resolution_clock::time_point start_time = std::chrono::high_resolution_clock::now();&nbsp; &nbsp; auto m = make_map(10000000);&nbsp; &nbsp; std::chrono::high_resolution_clock::time_point end_time = std::chrono::high_resolution_clock::now();&nbsp; &nbsp; auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end_time-start_time);&nbsp; &nbsp; std::cout << elapsed.count()/1000000000. << "s\n";&nbsp; &nbsp; std::cout << m[10] << "\n"&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; << m[9999999] << "\n";&nbsp; &nbsp;&nbsp;}% g++ -DNDEBUG -std=c++17 -Ofast -o perf perf.cpp% ./perf2.81886s201e+07稍作修改的go版本：package mainimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "time")func make_map(elem float64) map[float64]float64 {&nbsp; &nbsp; m := make(map[float64]float64, int(elem))&nbsp; &nbsp; var i float64 = 0&nbsp; &nbsp; for ; i < elem; i++ {&nbsp; &nbsp; &nbsp; &nbsp; m[i] = i + 10&nbsp; &nbsp; }&nbsp; &nbsp; return m}func main() {&nbsp; &nbsp; start_time := time.Now()&nbsp; &nbsp; r := make_map(10000000)&nbsp; &nbsp; end_time := time.Now()&nbsp; &nbsp; fmt.Println(end_time.Sub(start_time))&nbsp; &nbsp; fmt.Println(r[10])&nbsp; &nbsp; fmt.Println(r[9999999])}% go build -a perf.go% ./perf1.967707381s201.0000009e+07它看起来不像更新前那样平局。使 cpp 版本变慢的一件事是double. 当用一个非常糟糕（但很快）的哈希器替换它时，我把时间降到了 1.89489s。struct bad_hasher {&nbsp; &nbsp; size_t operator()(const double& d) const {&nbsp; &nbsp; &nbsp; &nbsp; static_assert(sizeof(double)==sizeof(size_t));&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *reinterpret_cast<const size_t*>( reinterpret_cast<const std::byte*>(&d) );&nbsp; &nbsp; }};

Answer 3

无意义的微基准测试产生无意义的结果。继续@mrclx和@TedLyngmo的微基准线程，修复@TedLyngmo 的 Go 微基准中的错误：perf.go:package mainimport (    "fmt"    "time")func makeMap(elem float64) time.Duration {    x := time.Now()    o := make(map[float64]float64, int(elem))    var i float64 = 0    for ; i < elem; i++ {        o[i] = i + 10    }    t := time.Now()    return t.Sub(x)}func main() {    r := makeMap(10000000)    fmt.Println(r)}输出：$ go versiongo version devel +11af353531 Tue Feb 12 14:48:26 2019 +0000 linux/amd64$ go build -a perf.go$ ./perf1.649880112s$ perf.cpp:#include <iostream>#include <unordered_map>#include <chrono>void make_map(double times) {    std::unordered_map<double, double> hm;    hm.reserve(static_cast<size_t>(times)); // <- good stuff    for (double c = 0; c < times; ++c) {        hm[c] = c + 10.0;    }}int main() {    std::chrono::high_resolution_clock::time_point start_time = std::chrono::high_resolution_clock::now();    make_map(10000000);    std::chrono::high_resolution_clock::time_point end_time = std::chrono::high_resolution_clock::now();    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end_time-start_time);    std::cout << elapsed.count()/1000000000. << "s\n";}输出：$ g++ --versiong++ (Ubuntu 8.2.0-7ubuntu1) 8.2.0$ g++ -DNDEBUG -std=c++17 -Ofast -o perf perf.cpp$ ./perf3.09203s$