Vector performance in Go and C++

Please consider these two snippets in GO and C++11. In C++ std::vector is a doubling-array which has amortized O(1) insert operation. How to achieve the same performance in GO? Problem is that this GO code is about 3 times slower on my hardware. Run many times.

Compiled:

• 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 version (vec.go):

<!-- language: 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 version (vec.cc):

<!-- language: c++ -->

#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's specification doesn't require any particular complexity for append(), but in practice it's also implemented in ammortized constant time, as described in the answer to this question.

The current implementation works as follows: for array sizes below 1024, it doubles as needed, and above 1024 it increases to 1.25x the original size. Increasing by 1.25x is still amortized constant time, but it has the effect of imposing a higher amortized constant factor than an implementation that always doubles. However 1.25x wastes less memory overall.

If you're getting different performance behavior by only a few times (even at very large N), then you're seeing different constant factors in play. I've noted myself that the machine code produced by the gc compiler is much more efficient than that generated by gccgo.

To verify for yourself that Go is operating in ammortized constant time, try plotting the time it takes to run your algorithm for several different values of N.

I've already answered your computational complexity question: append complexity. It is amortized constant time.

My results from your benchmark.

$ rm vec
$ cat 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);
        }
}
$ g++ -O2 -std=gnu++11 -o vec vec.cc
$ time ./vec
real	0m1.360s
user	0m0.536s
sys	0m0.816s
$ rm vec
$ cat 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)
	}
}
$ go version
go version devel +6b696a34e0af Sun Aug 03 15:14:59 2014 -0700 linux/amd64
$ go build vec.go
$ time ./vec
real	0m2.590s
user	0m1.192s
sys	0m1.388s
$ 

If you know the number of elements before hand, you can preallocate it with:

s := make([]X, 0, N)
for i := 0; i < N; i++ {
    s = append(s, x)
}

Also use Go 1.3, the compiler got some optimizations.

And for better vectorization, try gccgo