go和c++的map性能对比
Golang小白一枚,正在不断学习积累知识,现将学习到的知识记录一下,也是将我的所得分享给大家!而今天这篇文章《go和c++的map性能对比》带大家来了解一下##content_title##,希望对大家的知识积累有所帮助,从而弥补自己的不足,助力实战开发!
我不明白为什么 golang 在这个操作上比 c++ 快了 10 倍,甚至 go 中的映射查找比 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++以获得更好的性能。
解决方案
已更新以测量 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.89489 秒。
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) );
}
};
确定“c++ 的速度”(几乎对于任何特定事物)有点困难,因为它可能取决于很多变量,例如您使用的编译器。例如,对于此代码的 c++ 版本,我通常会发现 gcc 和 msvc 之间存在 2:1 左右的差异。
就 c++ 和 go 之间的差异而言,我猜这主要是由于哈希表实现方式的差异。一个明显的一点是,go 的 map 实现一次以 8 个元素为一个块来分配数据空间。至少在我见过的标准库实现中,std::unordered_map
每个块仅放置一项。
我们预计这意味着在典型情况下,c++ 代码将从堆/空闲存储中执行更多数量的单独分配,因此其速度将在很大程度上取决于堆管理器的速度。 go 版本还应该具有更高的引用局部性,以便更好地利用缓存。
考虑到这些差异,我对您只看到 10:1 的差异感到有点惊讶。我的直接猜测会(稍微)高于这个数字,但众所周知,一次测量值胜过 100 次猜测。
参考
Go's Map Implementation
liststdc++ unordered_map
libc++ unordered_map
理论要掌握,实操不能落!以上关于《go和c++的map性能对比》的详细介绍,大家都掌握了吧!如果想要继续提升自己的能力,那么就来关注编程网公众号吧!
免责声明:
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341