Go言語のsliceは、擬似的に書くと
type slice struct {
head int,
tail int,
data []interface{}
}
のようになっていて、先頭と最後へのポインタと配列へのポインタを持っていて、hoge[1:5]のようにslice演算をするとheadとtailだけ書き換えて、データはそのまま。
また、append関数はdataのキャパシティを超えた場合にreallocのようなことをしてデータ容量を拡張する。
package main
import (
"fmt"
)
var P = fmt.Println
func main() {
a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
b := a[0:5]
a[0] = 100
c := append(b, 200) //aの６つ目のデータを上書き
P("a", a) //a [100 2 3 4 5 200 7 8 9 10]
P("b", b) //b [100 2 3 4 5]
P("c", c) //c [100 2 3 4 5 200]
}
なので、map処理（同数のリストの写像）であれば、
元となるリストサイズの容量を先に確保しておく方がいいし、
filter処理であっても、期待する数が圧倒的に少ない場合でない限り、先にcapだけでも確保しておく方がよさそうだ。
flat_mapのように要素の数が増える場合は、期待値程度には容量を確保しておくのが良さそうだ。
func WithCap(N int) {
slice := make([]string, 0, N)
for i := 0; i < N; i++ {
slice = append(slice, "hello")
}
fmt.Fprintln(os.Stderr, "with-cap", N, len(slice))
}
func WithoutCap(N int) {
slice := make([]string, 0)
for i := 0; i < N; i++ {
slice = append(slice, "hello")
}
fmt.Fprintln(os.Stderr, "without-cap", N, len(slice))
}
func NoAppend(N int) {
slice := make([]string, N)
for i := 0; i < N; i++ {
slice[i] = "hello"
}
fmt.Fprintln(os.Stderr, "no-append", N, len(slice))
}
このような関数を作って、ベンチマークをとると
BenchmarkWithCap 100000000 18.4 ns/op
BenchmarkWithoutCap 50000000 57.4 ns/op
BenchmarkNoAppend 100000000 10.3 ns/op
}
このようになる。
容量は２倍２倍で確保しているようなので、
log2(N)程度の回数reallocのようなものが走る可能性がある。
src/pkg/runtime/slice.c
static void
growslice1(SliceType *t, Slice x, intgo newcap, Slice *ret)
{
intgo m;
m = x.cap;
// Using newcap directly for m+m < newcap handles
// both the case where m == 0 and also the case where
// m+m/4 wraps around, in which case the loop
// below might never terminate.
if(m+m < newcap)
m = newcap;
else {
do {
if(x.len < 1024)
m += m;
else
m += m/4;
} while(m < newcap);
}
// allocして
makeslice1(t, x.len, m, ret);
// コピー
runtime·memmove(ret->array, x.array, ret->len * t->elem->size);
}
sliceの拡張は1024までは２倍２倍。
そこから先は、capの1/4ずつ増えるっぽい。
なので、このベンチマークの場合、indexアクセスの６倍、cap設定ありの３倍という時間がキャパシティ設定なしの場合はかかっている。
容量の自動拡張があった場合、
場合によっては要素コピーが走る。
ので、もととは違う結果になる。
copy.go
func main() {
a := make([]int, 0)
b := append(a, 10, 20, 30)
b[2] = 3
//ここでキャパシティオーバー
//コピーされてcができる。
c := append(b, 40, 50, 60)
//コピーされているので、cは書き変わるがbは書き変わらない
c[2] = 1
pslice(a)
pslice(b)
pslice(c)
}
func pslice(s []int) {
fmt.Printf("%T len:%d cap:%d %s\n", s, len(s), cap(s), s)
}