c++ - Go 和 C++ 中的 vector 性能

Question

请考虑 GO 和 C++11 中的这两个片段。在 C++ 中，std::vector 是一个加倍数组，它具有分摊 O(1) 插入操作。如何在GO中实现相同的性能？问题是这个 GO 代码在我的硬件上慢了大约 3 倍。多次运行。

编译:

• go build vec.go (go version 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() 没有任何特殊的复杂性要求，但在实践中它也是在摊销常数时间内实现的，如对 this question 的回答中所述。 .

当前的实现方式如下:对于小于 1024 的数组大小，它会根据需要加倍，而大于 1024 时它会增加到原始大小的 1.25 倍。增加 1.25 倍仍然是摊销常数时间，但它具有比始终加倍的实现强加更高摊销常数因子的效果。但是，1.25 倍总体上浪费的内存更少。

如果您只获得几次不同的性能行为(即使在非常大的 N 时)，那么您会看到不同的常量因素在起作用。我自己注意到 gc 编译器生成的机器码比 gccgo 生成的机器码要高效得多。

要亲自验证 Go 是否在摊销常数时间内运行，请尝试绘制针对多个不同 N 值运行算法所需的时间。