Ho giocato con alcuni esempi di array in C. Voglio capire di più su concetti di memoria, allineamento e cache. Soprattutto su grandi matrici su heap. A volte lavoro su immagini grandi (estremamente grandi), ecco perché è importante per me, ma non importa per quello che sto chiedendo ora.
Ho scritto un esempio seguente:
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <GLFW/glfw3.h>
#define ARRAY_NUM 1000000 * 1000 // GIG
int main(int argc, char *argv[]) {
if(!glfwInit()) {
exit(EXIT_FAILURE);
}
uint64_t *array = malloc(sizeof(uint64_t) * ARRAY_NUM);
double time_start = glfwGetTime();
for(uint64_t i = 0; i < ARRAY_NUM; ++i) {
array[i] = 0xff;
}
double time_end = glfwGetTime();
free(array);
glfwTerminate();
double performance = ((ARRAY_NUM * sizeof(uint64_t))/1000000) / (time_end - time_start);
printf("Done in %f\n", (time_end - time_start));
printf("Performance: %f MB/s\n", performance);
exit(EXIT_SUCCESS);
}
Con 1 concerto assegnato ricevo:
Done in 36.126213
Performance: 221.445854 MB/s
300 meg I get:
Done in 7.564931
Performance: 317.253391 MB/s
200 meg I get:
Done in 1.279391
Performance: 1250.594728 MB/s
100 meg I get:
Done in 0.355763
Performance: 2248.685313 MB/s
10 meg I get:
Done in 0.036575
Performance: 2187.315761 MB/s
e 1 meg ho:
Done in 0.004050
Performance: 1975.160383 MB/s
Naturalmente, i tempi variano tra il 5-10% tra le corse.
Ora, quello che mi chiedo qui è che cosa può e deve essere fatto per avere un throughput massimo costante che si possa ottenere per attraversare gli array sull'heap - specialmente quelli grandi. Qualcosa mi dice che anche i numeri più alti di 2+ GB / s non sono i numeri migliori qui, e quello che mi interessa è il risultato di 1 meg vs 10 e 100 - sembra che la cache si scaldi solo dopo un certo tempo.
Sto usando C99 (gcc5) e la mia comprensione è che con malloc e uint64_t dovrei avere già una memoria allineata. Se no, c'è forse un modo sicuro per farlo? Se questo è il colpevole del tutto, naturalmente. Forse sto colpendo male le linee della cache, o colpendo le pagine VM del sistema operativo che non le piace? Dove si potrebbe iniziare a ottimizzare l'accesso lineare all'interno di un array di grandi dimensioni?
dettagli:
- L'ho fatto su un MacbookAir4,2 (I5-2557M) del 2011 con 4 GB di RAM e SSD (forse questo è il problema - una quantità bassa di RAM e malloc non sono in grado di ottenere il blocco in una volta sola? Devo testare questo sulla mia workstation quando ci arrivo)
- gcc 5.2.0 (homebrew) con flag:
-pedantic -std=c99 -Wall -Werror -Wextra -Wno-unused -O9(yeah, niner ... Io uso 3 altrimenti, ma non si sa mai) con addizionali e flag di libreria e flag di framework per usare il timer glfw che tendo ad usare. Potrei averlo fatto senza, non importa.
Modifica
Dopo alcuni pensieri con cui Erik mi ha impiantato, ho fatto un altro test. Mostrando alcune delle cose relative alla pre-raccolta e, si spera, anche alla cache.
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // memcpy
#include <inttypes.h>
#include <GLFW/glfw3.h>
#define ARRAY_NUM 1000000 * 125 // GIG
int main(int argc, char *argv[]) {
double performance = 0.0;
if(!glfwInit()) {
exit(EXIT_FAILURE);
}
uint64_t *array = malloc(sizeof(uint64_t) * ARRAY_NUM);
uint64_t *array_copy = malloc(sizeof(uint64_t) * ARRAY_NUM);
double time_start = glfwGetTime();
for(uint64_t i = 0; i < ARRAY_NUM; ++i) {
array[i] = 0xff;
}
double time_end = glfwGetTime();
performance = ((ARRAY_NUM * sizeof(uint64_t))/1000000) / (time_end - time_start);
printf("Init done in %f - size of array: %lu MBs (x2)\n", (time_end - time_start), (ARRAY_NUM*sizeof(uint64_t)/1000000));
printf("Performance: %f MB/s\n\n", performance);
performance = 0;
time_start = glfwGetTime();
for(uint64_t i = 0; i < ARRAY_NUM; ++i) {
array_copy[i] = array[i];
}
time_end = glfwGetTime();
performance = ((ARRAY_NUM * sizeof(uint64_t))/1000000) / (time_end - time_start);
printf("Copying (linear) done in %f\n", (time_end - time_start));
printf("Performance: %f MB/s\n\n", performance);
performance = 0;
time_start = glfwGetTime();
for(uint64_t i = 0; i < ARRAY_NUM; i=i+8) {
array_copy[i] = array[i];
if(i < (ARRAY_NUM-8)) {
array_copy[i+1] = array[i+1];
array_copy[i+2] = array[i+2];
array_copy[i+3] = array[i+3];
array_copy[i+4] = array[i+4];
array_copy[i+5] = array[i+5];
array_copy[i+6] = array[i+6];
array_copy[i+7] = array[i+7];
}
}
time_end = glfwGetTime();
performance = ((ARRAY_NUM * sizeof(uint64_t))/1000000) / (time_end - time_start);
printf("Copying (stride 8) done in %f\n", (time_end - time_start));
printf("Performance: %f MB/s\n\n", performance);
const int imax = 100;
double performance_average = 0.0;
for(int j = 0; j < imax; ++j) {
uint64_t tmp = 0;
performance = 0;
time_start = glfwGetTime();
for(uint64_t i = 0; i < ARRAY_NUM; i=i+8) {
tmp = array[i];
if(i < (ARRAY_NUM-8)) {
tmp = array[i+1];
tmp = array[i+2];
tmp = array[i+3];
tmp = array[i+4];
tmp = array[i+5];
tmp = array[i+6];
tmp = array[i+7];
}
}
time_end = glfwGetTime();
performance = ((ARRAY_NUM * sizeof(uint64_t))/1000000) / (time_end - time_start);
performance_average += performance;
printf("[%d/%d] Performance stride 8: %f MB/s\r", j+1, imax, performance);
fflush(stdout);
}
performance_average = performance_average / imax;
printf("\nAverage: %f MB/s\n\n", performance_average);
performance_average = 0.0;
for(int j = 0; j < imax; ++j) {
uint64_t tmp = 0;
performance = 0;
time_start = glfwGetTime();
for(uint64_t i = 0; i < ARRAY_NUM; ++i) {
tmp = array[i];
}
time_end = glfwGetTime();
performance = ((ARRAY_NUM * sizeof(uint64_t))/1000000) / (time_end - time_start);
performance_average += performance;
printf("[%d/%d] Performance dumb: %f MB/s\r", j+1, imax, performance);
fflush(stdout);
}
performance_average = performance_average / imax;
printf("\nAverage: %f MB/s\n\n", performance_average);
performance = 0;
time_start = glfwGetTime();
memcpy(array_copy, array, ARRAY_NUM*sizeof(uint64_t));
time_end = glfwGetTime();
performance = ((ARRAY_NUM * sizeof(uint64_t))/1000000) / (time_end - time_start);
printf("Copying (memcpy) done in %f\n", (time_end - time_start));
printf("Performance: %f MB/s\n", performance);
free(array);
free(array_copy);
glfwTerminate();
exit(EXIT_SUCCESS);
}
Se non vuoi usare il timer di glfw, sostituiscilo con il tuo. Lo compilo con -pedantic -std=c99 -Wall -Werror -Wextra -Wno-unused -O0 e -fprefetch-loop-arrays non sembra avere effetti, quindi l'ho lasciato fuori.
Ora posso vedere gli effetti del pre-recupero in gioco. Ecco un esempio di output:
Init done in 0.784799 - size of array: 1000 MBs (x2)
Performance: 1274.211087 MB/s
Copying (linear) done in 2.086404
Performance: 479.293545 MB/s
Copying (stride 8) done in 0.313592
Performance: 3188.856625 MB/s
[100/100] Performance stride 8: 6458.897164 MB/s
Average: 6393.163000 MB/s
[100/100] Performance dumb: 2597.816831 MB/s
Average: 2530.225830 MB/s
Copying (memcpy) done in 0.202581
Performance: 4936.303056 MB/s
Puoi vedere come la lettura di 8 valori per loop (valore arbitrario per ora) produce più del doppio della larghezza di banda! Ciò che mi ha sorpreso è che la copia era aumentata di +6 volte. Ho incluso memcpy come riferimento, che è ancora più veloce. Gioco interessante Mi piacerebbe sapere di più su cosa cercare e come affrontare la lettura / scrittura ottimale su array e, eventualmente, payloads non banali (ho scelto uint64_t in questo caso).
EDIT2:
con una falcata di 40 (non di più, non di meno - 320bytes) ho ottenuto letture di ~ 7800 MB / s. Che è più vicino al massimo di 10600 (1333 MHz DDR3).