Go和C++中的矢量性能

Question

请考虑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);
        }
}

Answer 1

Go的规范并不需要任何特定的复杂性append(),但实际上它也是在固定的常量时间内实现的,如本问题的答案中所述.

当前的实现如下工作:对于小于1024的数组,它根据需要加倍,而在1024以上它增加到原始大小的1.25倍.增加1.25倍仍然是摊销的固定时间,但它具有比总是加倍的实施施加更高的摊销常数因子的效果.然而,整体内存浪费了1.25倍.

如果你的性能行为只有几次(即使是非常大的N),那么你会看到不同的常数因素在起作用.我已经注意到gc编译器生成的机器代码比生成的机器代码更有效gccgo.

为了验证Go是否以固定的常数时间运行,请尝试绘制为几个不同的N值运行算法所需的时间.