请考虑GO和C 11中的这两个片段.在C std :: vector中是一个双重数组,它具有摊销的O(1)插入操作.如何在GO中实现相同的性能？问题是这个GO代码在我的硬件上慢了大约3倍.跑多次.
编译：
> go build vec.go(去版本go1.2.1 linux / amd64)
> g -O2 -std = gnu 11 -o vec vec.cc(g(Ubuntu 4.8.2-19ubuntu1)4.8.2)
GO版(vec.go)：
package main
type X struct {
x int32
y float64
}
const N int = 80000000
func main() {
x := X{123,2.64}
s := make([]X,1)
for i := 0; i < N; i++ {
s = append(s,x)
}
}
C 11版(vec.cc)：
#include <vector>
const int N = 80000000;
struct X {
int x;
double y;
};
int main(void)
{
X x{123,2.64};
std::vector<X> s(1);
for (int i = 0; i < N; ++i) {
s.push_back(x);
}
}
解决方法
Go的规范并不要求append()具有任何特定的复杂性,但在实践中它也是在固定的常量时间内实现的,如
this question的答案中所述.
当前实现的工作原理如下：对于1024以下的数组大小,它根据需要加倍,而在1024以上则增加到原始大小的1.25倍.增加1.25倍仍然是摊销的固定时间,但它具有比总是加倍的实施施加更高的摊销常数因子的效果.然而1.25倍的浪费总体上减少了内存.
如果你的性能行为只有几次(即使是非常大的N),那么你会看到不同的常数因素在起作用.我已经注意到gc编译器生成的机器代码比gccgo生成的机器代码更有效.
为了验证Go是否以固定的常数时间运行,请尝试绘制为几个不同的N值运行算法所需的时间.
