Qual è la convenzione per l'indicizzazione di array 2D con coordinate x/y in C?

Question

Ho scritto un programma piccolo, in cui ho dovuto usare il sistema di coordinate a bordo (x/y in array 2d) e stavo pensando se dovessi usare l'indicizzazione come array[x][y], che mi sembra più naturale o array[y][x] che corrisponderebbe meglio il modo in cui la matrice è rappresentata in memoria. Credo che entrambi questi metodi funzioneranno se sono coerente e si tratta solo di problemi di denominazione, ma che dire delle convenzioni quando si scrivono programmi più grandi?

Answer 1

Nel mio campo (manipolazione delle immagini) la convenzione [y][x] è più comune. Qualunque cosa tu faccia, sii coerente e documentala bene.

Answer 2

Si dovrebbe anche considerare che cosa si intende fare con questi array e se questo è fondamentale per il tempo.

Come menzionato nei commenti: L'elemento a[r][c+1] è proprio accanto a a[r][c]. Questo fatto potrebbe avere un impatto considerevole sulle prestazioni durante l'iterazione su array più grandi. Un corretto ordine trasversale farà sì che le linee della cache siano completamente sfruttate: quando si accede a un indice di array, si ritiene che sia "probabile" che in seguito si accederà all'indice successivo e verrà caricato un intero blocco di memoria nel cache. Se successivamente si accede a una posizione di memoria completamente diversa (ovvero, una nella riga successiva), questa larghezza di banda della cache viene sprecata.

Se possibile, provare a utilizzare un ordine di attraversamento che si adatti al layout di memoria effettivo.

_{(Naturalmente, questo è molto di "convenzioni" e "abitudini": Quando si scrive un accesso matrice come a[row][col], questo viene generalmente interpretato come accesso matrice a[y][x], grazie alla convenzione del x-asse essendo orizzontale e l'asse y essendo verticale ...)}

Ecco un piccolo esempio che dimostra il potenziale impatto sulle prestazioni di un "sbagliato" ordine di attraversamento:

#include <stdlib.h> 
#include <stdio.h> 
#include <time.h> 

float computeSumRowMajor(float **array, int rows, int cols) 
{ 
    float sum = 0; 
    for (int r=0; r<rows; r++) 
    { 
     for (int c=0; c<cols; c++) 
     { 
      sum += array[r][c]; 
     } 
    } 
    return sum; 
} 

float computeSumColMajor(float **array, int rows, int cols) 
{ 
    float sum = 0; 
    for (int c=0; c<cols; c++) 
    { 
     for (int r=0; r<rows; r++) 
     { 
      sum += array[r][c]; 
     } 
    } 
    return sum; 
} 


int main() 
{ 
    int rows = 5000; 
    int cols = 5000; 
    float **array = (float**)malloc(rows*sizeof(float*)); 
    for (int r=0; r<rows; r++) 
    { 
     array[r] = (float*)malloc(cols*sizeof(float)); 
     for (int c=0; c<cols; c++) 
     { 
      array[r][c] = 0.01f; 
     } 
    } 

    clock_t start, end; 

    start = clock(); 
    float sumRowMajor = 0; 
    for (int i=0; i<10; i++) 
    { 
     sumRowMajor += computeSumRowMajor(array, rows, cols); 
    } 
    end = clock(); 
    double timeRowMajor = ((double) (end - start))/CLOCKS_PER_SEC;  

    start = clock(); 
    float sumColMajor = 0; 
    for (int i=0; i<10; i++) 
    { 
     sumColMajor += computeSumColMajor(array, rows, cols); 
    } 
    end = clock(); 
    double timeColMajor = ((double) (end - start))/CLOCKS_PER_SEC;  

    printf("Row major %f, result %f\n", timeRowMajor, sumRowMajor); 
    printf("Col major %f, result %f\n", timeColMajor, sumColMajor); 
    return 0; 
} 

_{(scuse se ho violato alcune best practice qui, io sono usua un ragazzo Java ...)}

Per me, l'accesso alla riga principale è quasi un ordine di grandezza più veloce dell'accesso alla colonna principale. Naturalmente, i numeri esatti saranno pesantemente dipendono dal sistema di destinazione, ma il problema generale dovrebbe essere lo stesso su tutti i target.