Stavo facendo alcune sperimentazioni sulle prestazioni in Go con moltiplicazione di matrici e ho ottenuto alcuni risultati imprevisti.Go: prestazioni impreviste durante l'accesso a un array attraverso una porzione di slice (slice 2D)
Versione 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
}
Dalla schiera lineare creare più sezioni che rappresentano le righe della matrice.
Versione 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
}
In questa versione ho sufficiente utilizzare una schiera lineare e l'indice in esso dalla moltiplicazione.
Moltiplicando 2 2048x2048 matrici danno il seguente tempo di esecuzione:
version 1: 35.550813801s
version 2: 19.090223468s
versione 2 è quasi due volte più veloce.
ho usato l'approccio seguito per prendere le misure:
start := time.Now()
mult(m1, m2, m3)
stop := time.Now()
Sono consapevole che utilizzano fette do un altro livello di indirezione che possono influire sul prestazioni della cache, tuttavia non mi aspettavo che sarebbe stato un così grande differenza. Purtroppo non ho trovato alcun buon strumento, che funzioni con Mac, in grado di analizzare l'efficienza della cache in Go, quindi non posso dire con certezza se questo è ciò che sta causando la differenza di prestazioni.
Quindi suppongo che sto chiedendo è questo comportamento previsto o c'è qualcosa che mi manca?
Software e hardware: Vai versione 1.4.2 darwin/amd64; OS X 10.10.3; I7 quad-core a 2 GHz.
Follow-up rapido per quanto riguarda il primo punto: la matrice viene memorizzata nello stesso modo in memoria in entrambi i casi, vale a dire come un array 1D. L'unica differenza sta nel modo in cui accedo. Nella versione 1 utilizzo le sezioni 2D e nella versione 2 utilizzo una sezione lineare. Inoltre, non ho riscontrato differenze di prestazioni così elevate in altre lingue, ad es. Giava. Sai perché potrebbe essere? – Carlj901
C'è una differenza tra l'utilizzo di [] [] int e [] int. Il secondo caso indica che l'array è memorizzato in modo contiguo (1D). Il primo che considero 2D e devi pagare tutte le sanzioni citate. C'è una possibilità che Java possa fare ottimizzazioni just in time e cambiare il tuo codice al volo, quindi le differenze di prestazioni non saranno importanti. – VAndrei
Se si guarda il codice della versione 1, si nota che alloco un grande array n * n e quindi creo sezioni per ogni riga che punta a questo array lineare. – Carlj901