2012-05-20 17 views
7

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?Efficienza: char array vs int array

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.

+0

Non riesco a pensare a nessuna ragione perché "char" sarebbe più lento. Se possibile, forse a seconda delle operazioni che stai facendo, potrebbe essere più veloce. Su target embedded con architettura a 8 bit, le operazioni 'int' sarebbero più lente. – jedwards

+0

Forse, ma una matrice 'char' occupa meno memoria, che potrebbe renderla più veloce di una matrice' int', se ha abbastanza elementi. –

risposta

5

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.

+0

+1, ma hai il tuo 'typedef' nel modo sbagliato. –

+0

Eh - questo è imbarazzante - risolto ora. Grazie :-) – Brendan

4

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.

+0

Sono d'accordo con la prima frase, ma non implicherebbe che la rappresentazione int (su una macchina a 32 bit) richiederebbe la memoria 4x? Sì, i blocchi saranno contigui, ma non della stessa dimensione. – jedwards

+0

Ho aggiornato la mia risposta per chiarire questo punto (ho pensato che il lettore avrebbe capito, ma forse avrei dovuto essere più esplicito). –

+0

Penso che la frase che mi ha colpito sia "è improbabile che uno dei due sarà diverso in termini di utilizzo totale della memoria". - I termini di utilizzo totale della memoria, saranno diversi, uno 4x la dimensione dell'altro. – jedwards

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.

+0

+1! Questa sarà la prova definitiva che conferma le affermazioni. Entrambe le grandi risposte, è un peccato che posso sceglierne una. – PALEN