Array vs Slice: dostęp do prędkości

Question

To pytanie dotyczy szybkości dostępu do elementów z tablic i plasterków, a nie o wydajności przekazywania ich do funkcji jako argumentów.

spodziewałbym tablice się szybciej niż plastry w większości przypadków, ponieważ kawałek to struktura danych opisująca ciągłą część tablicy i tak nie może być dodatkowy etap zaangażowany podczas uzyskiwania dostępu do elementów plasterka (pośrednio elementy jego podstawowej tablicy).

Więc napisałem mały test, aby przetestować partię prostych operacji. Istnieją 4 funkcje odniesienia, pierwszy 2 Test globalny plaster i światowym tablicy, pozostałe 2 testy lokalny plaster i lokalnej tablicy:

var gs = make([]byte, 1000) // Global slice 
var ga [1000]byte   // Global array 

func BenchmarkSliceGlobal(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     for j, v := range gs { 
      gs[j]++; gs[j] = gs[j] + v + 10; gs[j] += v 
     } 
    } 
} 

func BenchmarkArrayGlobal(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     for j, v := range ga { 
      ga[j]++; ga[j] = ga[j] + v + 10; ga[j] += v 
     } 
    } 
} 

func BenchmarkSliceLocal(b *testing.B) { 
    var s = make([]byte, 1000) 
    for i := 0; i < b.N; i++ { 
     for j, v := range s { 
      s[j]++; s[j] = s[j] + v + 10; s[j] += v 
     } 
    } 
} 

func BenchmarkArrayLocal(b *testing.B) { 
    var a [1000]byte 
    for i := 0; i < b.N; i++ { 
     for j, v := range a { 
      a[j]++; a[j] = a[j] + v + 10; a[j] += v 
     } 
    } 
} 

Pobiegłem testu wielokrotnie, tutaj jest typowe wyjście (go test -bench .*):

BenchmarkSliceGlobal  300000    4210 ns/op 
BenchmarkArrayGlobal  300000    4123 ns/op 
BenchmarkSliceLocal  500000    3090 ns/op 
BenchmarkArrayLocal  500000    3768 ns/op 

Analizując wyniki:

dostępie do globalny kawałek jest nieco wolniejszy niż dostęp do globalnej tablicy, która jest, jak się spodziewałem:
4210 vs 4123 ns/OP

Ale z dostępem do lokalnej kawałek jest znacznie szybszy niż dostęp do lokalnej tablicy:
3090 vs 3768 ns/OP

Moje pytanie brzmi: Jaki jest tego powód?

Uwagi

Próbowałem różnych następujące rzeczy, ale żaden zmienił wynik:

• wielkość tablicy/wycinka (próbowaliśmy 100, 1000, 10000)
• zamówienie funkcji benchmarków:
• typ elementu tablicy/plasterka (wypróbowano byte i int)

Answer 1

Porównując the amd64 assembly zarówno BenchmarkArrayLocal i BenchmarkSliceLocal (zbyt długi, aby zmieścić się w tym poście):

Wersja tablicy wczytuje adres a z pamięci kilka razy, praktycznie na każdej operacji tablica-Access:

LEAQ "".a+1000(SP),BX 

Zważywszy wersji plaster jest obliczanie wyłącznie na rejestrach po załadowaniu raz z pamięci:

LEAQ (DX)(SI*1),BX 

Nie jest to rozstrzygająca, ale prawdopodobnie przyczyna. Powód jest taki, że obie metody są praktycznie identyczne.Innym ważnym szczegółem jest to, że wersja tablicy wywołuje runtime.duffcopy, która jest dość długą procedurą składania, podczas gdy wersja plastrem nie.

Answer 2

Wersja Go 1.8 może wyeliminować niektóre testy zasięgu, więc różnica jest większa.

BenchmarkSliceGlobal-4 500000 3220 ns/op BenchmarkArrayGlobal-4 1000000 1287 ns/op BenchmarkSliceLocal-4 1000000 1267 ns/op BenchmarkArrayLocal-4 1000000 1301 ns/op

Na tablicach polecam użyć rozmiarach od potęgi dwójki i to logiczne i działanie. W ten sposób na pewno kompilator eliminuje czek. Tak więc var ga [1024]byte z ga[j & 1023].