Go和C中的矢量性能

请考虑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值运行算法所需的时间.

相关文章
相关标签/搜索