Przeprowadziłem eksperymenty wydajnościowe w Go z mnożeniem macierzy i otrzymałem nieoczekiwane wyniki.Go: Nieoczekiwana wydajność podczas uzyskiwania dostępu do tablicy poprzez plasterki (plaster 2D)
Wariant 1:
func newMatrix(n int) [][]int {
m := make([][]int, n)
buf := make([]int, n*n)
for i := range m {
m[i] = buf[i*n : (i+1)*n]
}
return m
}
func mult1(m1, m2, res [][]int) [][]int {
for i := range m1 {
for k := range m1[0] {
for j := range m2[0] {
res[i][j] += m1[i][k] * m2[k][j]
}
}
}
return res
}
z tablicy liniowego utworzyć wiele cięć, które stanowią rzędy macierzy.
Wariant 2:
func mult2(m1, m2, res []int, n int) []int {
for i := 0; i < n; i++ {
for k := 0; k < n; k++ {
for j := 0; j < n; j++ {
res[i*n+j] += m1[i*n+k] * m2[k*n+j]
}
}
}
return res
}
W tej wersji, wystarczy użyć liniowy układ i indeks do tego mnożenia.
Mnożenie 2 2048x2048 matryce dają następujący czas wykonywania:
version 1: 35.550813801s
version 2: 19.090223468s
Wersja 2 jest prawie dwa razy szybciej.
Użyłem poniżej podejście do pomiarów:
start := time.Now()
mult(m1, m2, m3)
stop := time.Now()
Jestem świadomy wykorzystujące plastry dać kolejną warstwę zadnie, które mogłyby mieć wpływ na wydajność pamięci podręcznej, ale nie spodziewałem się, że będzie tak duża różnica. Niestety nie znalazłem żadnego dobrego narzędzia, które współpracuje z komputerem Mac, które może analizować wydajność pamięci podręcznej w Go, więc nie mogę powiedzieć na pewno, czy to właśnie powoduje różnicę wydajności.
Sądzę, że pytam, czy to oczekiwane zachowanie, czy jest coś, czego mi brakuje?
Oprogramowanie i sprzęt: Przejdź do wersji 1.4.2 darwin/amd64; OS X 10.10.3; Czterordzeniowy rdzeń 2 GHz i7.
Szybkie monitorowanie pierwszego punktu: macierz jest przechowywana w obu przypadkach w ten sam sposób w pamięci, tj. Jako tablica 1D. Jedyna różnica polega na tym, jak mam do niego dostęp. W wersji 1 używam plasterków 2D, aw wersji 2 używam plasterka liniowego. Nie odczuwam tak dużych różnic w wydajności w innych językach, np. Jawa. Czy wiesz, dlaczego tak się dzieje? – Carlj901
Istnieje różnica między używaniem [] [] int i [] int. Drugi przypadek oznacza, że tablica jest przechowywana w sposób ciągły (1D). Pierwszy uważam za 2D i musisz zapłacić wszystkie wspomniane kary. Jest szansa, że Java może dokonać optymalizacji w czasie i zmienić kod w locie, więc różnice w wydajności nie będą duże. – VAndrei
Jeśli spojrzysz na kod wersji 1, zobaczysz, że przydzielam jedną dużą tablicę n * n, a następnie tworzę plasterki dla każdego wiersza, który wskazuje na tę tablicę liniową. – Carlj901