Efficienza: char array vs int array

Question

Sto programmando un gioco e voglio rappresentare una tavola usando un array. Sto cercando l'efficienza dal momento che sto per fare molte iterazioni. In questo caso, sia un array int che un array char sembrano convenienti per la rappresentazione della scheda. C'è qualche differenza in termini di efficienza quando si eseguono operazioni in un array int e un array di caratteri?

Sospetto che poiché ogni elemento dell'array char ha una dimensione di 1 byte, potrebbe essere più lento a causa di una diversa rappresentazione in memoria (si consideri un computer moderno che ha almeno 32 bit per la rappresentazione int) ... Sono destra?

Grazie in anticipo.

EDIT: Ho intenzione di generare alberi di gioco, ecco perché l'efficienza è così importante e piccole differenze nel consumo di tempo possono fare una grande differenza.

Answer 1

Per quale CPU/s?

Alcune CPU non possono accedere direttamente a qualcosa di più piccolo di "qualcosa" e il compilatore deve generare una sequenza di istruzioni "carica, sposta e maschera" per accedere ai singoli byte. Utilizzare int dovrebbe vincere per questo caso.

Alcune CPU possono accedere ai byte senza problemi. In questo caso (se sono coinvolti abbastanza dati che è importante) è probabile che il problema sia la dimensione della cache e/o la larghezza di banda della memoria; e (almeno per 80x86) mi aspetterei che char vincesse semplicemente perché più dati sono impacchettati in ogni linea della cache.

Per quale algoritmo/s?

Se si riesce a lanciare SIMD, è probabile che sia char a vincere. Ad esempio, con SIMD a 128 bit è possibile elaborare 16 byte per istruzione o 4 (32 bit) interi per istruzione e char potrebbe essere 4 volte più veloce a causa di questo solo.

Il miglior consiglio è di usare qualcosa come:

#ifdef USE_INT 
    typedef int thingy 
#else 
    typedef unsigned char thingy 
#endif 

Poi si può profilo it e cambiarlo in qualsiasi momento.

Answer 2

char s sono generalmente allineati a 1 byte e gli int sono generalmente allineati a 4 byte. Supponendo che si stia lavorando con una macchina che segue questo standard, entrambi gli array memorizzeranno il contenuto come blocchi contigui di memoria (l'array int ha una dimensione pari a 4x della dimensione dell'array char). Pertanto, è improbabile che uno dei due sarà diverso in termini di utilizzo di un blocco di memoria allocata.

Detto questo, anche se la rappresentazione della memoria sottostante era diversa, dubito che possa influire sul rendimento del programma.

Answer 3

Provalo e guarda. Utilizzare il flag -S per gcc per ottenere il codice assembler:

gcc -Wall -S code.c -o code.s 

vedere se ci sono differenze evidenti nella lunghezza del codice generato. Questa non è necessariamente l'intera storia in quanto è necessario comprendere l'assemblatore per giudicare le differenze. Ma potrebbe darti un suggerimento, probabilmente int e char saranno più o meno gli stessi.

Si noti che se si mescolano i tipi, si otterrà quasi certamente un codice leggermente più lento con gli array di caratteri. Quindi, se memorizzi i dati nel char array e poi li "processi" in qualche modo usando i tipi int, probabilmente otterrai un'istruzione extra ogni volta che viene fatta una conversione tra i due. Provalo con -S.