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) {

    std::unordered_map<double, double> m(times);

    for (double c = 0; c < times; ++c) {

        m[c] = c + 10.0;

    }

    return m;

}

int main() {

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

    auto m = 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";

    std::cout << m[10] << "\n"

              << m[9999999] << "\n";    

}

% g++ -DNDEBUG -std=c++17 -Ofast -o perf perf.cpp

% ./perf

2.81886s

20

1e+07

稍作修改的go版本：

package main

import (

    "fmt"

    "time"

)

func make_map(elem float64) map[float64]float64 {

    m := make(map[float64]float64, int(elem))

    var i float64 = 0

    for ; i < elem; i++ {

        m[i] = i + 10

    }

    return m

}

func main() {

    start_time := time.Now()

    r := make_map(10000000)

    end_time := time.Now()

    fmt.Println(end_time.Sub(start_time))

    fmt.Println(r[10])

    fmt.Println(r[9999999])

}

% go build -a perf.go

% ./perf

1.967707381s

20

1.0000009e+07

它看起来不像更新前那样平局。使 cpp 版本变慢的一件事是double. 当用一个非常糟糕（但很快）的哈希器替换它时，我把时间降到了 1.89489s。

struct bad_hasher {

    size_t operator()(const double& d) const {

        static_assert(sizeof(double)==sizeof(size_t));

        return

            *reinterpret_cast<const size_t*>( reinterpret_cast<const std::byte*>(&d) );

    }

};

Answer 3

无意义的微基准测试产生无意义的结果。

---

继续@mrclx和@TedLyngmo的微基准线程，修复@TedLyngmo 的 Go 微基准中的错误：

perf.go:

package main

import (

    "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 version

go version devel +11af353531 Tue Feb 12 14:48:26 2019 +0000 linux/amd64

$ go build -a perf.go

$ ./perf

1.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++ --version

g++ (Ubuntu 8.2.0-7ubuntu1) 8.2.0

$ g++ -DNDEBUG -std=c++17 -Ofast -o perf perf.cpp

$ ./perf

3.09203s

$