Eficiencia: matriz de caracteres frente a matriz int

Question

Estoy programando un juego y quiero representar una placa con una matriz. Estoy buscando la eficiencia ya que voy a hacer muchas iteraciones. En este caso, tanto una matriz int o una matriz char parece conveniente para la representación de la placa. ¿Hay alguna diferencia en términos de eficiencia al hacer operaciones en una matriz int y una matriz char?

Sospecho que dado que cada elemento de la matriz char tiene un tamaño de 1 byte, puede ser más lento debido a una representación diferente en la memoria (considere una computadora moderna que tenga al menos 32 bits para la representación int) ... ¿derecho?

Gracias de antemano.

EDIT: Voy a generar árboles de juego, por eso la eficiencia es tan importante y las pequeñas diferencias en el consumo de tiempo pueden marcar una gran diferencia.

Answer 1

¿Para qué CPU/s?

Algunas CPU no pueden acceder directamente a nada más pequeño que "algo", y el compilador necesita generar una secuencia de instrucciones de "carga, desplazamiento y máscara" para acceder a bytes individuales. El uso de int debería ganar para este caso.

Algunas CPU pueden acceder a los bytes sin problemas. En este caso (si hay datos suficientes involucrados) es probable que el problema sea el tamaño de la memoria caché y/o el ancho de banda de la memoria; y (al menos para 80x86) esperaría que char ganara simplemente porque se empaqueta más información en cada línea de caché.

¿Para qué algoritmo/s?

Si puede lanzar SIMD, es probable que char gane. Por ejemplo, con SIMD de 128 bits puede procesar 16 bytes por instrucción o 4 (32 bits) enteros por instrucción y char puede ser 4 veces más rápido debido a esto solo.

El mejor consejo sería utilizar algo como:

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

A continuación, puede perfilar y cambiarlo en cualquier momento.

Answer 2

char s generalmente alineados en 1 byte y int s generalmente alineados en 4 bytes. Suponiendo que está trabajando con una máquina que sigue este estándar, ambas matrices almacenarán su contenido como bloques contiguos de memoria (la matriz int es 4 veces el tamaño de la matriz char). Por lo tanto, es poco probable que ninguno sea diferente en términos de cómo utilizan un trozo de memoria asignada.

Dicho esto, incluso si la representación de la memoria subyacente fuera diferente, dudo que afecte el rendimiento de su programa.

Answer 3

Pruébalo y mira. Utilice la opción -S para gcc para obtener el código ensamblador:

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

ver si hay diferencias obvias en la longitud del código generado. Esta no es necesariamente toda la historia, ya que necesita comprender al ensamblador para juzgar las diferencias. Pero podría darte una pista, probablemente ese int y char serán más o menos lo mismo.

Tenga en cuenta que si mezcla tipos, es casi seguro que obtendrá un código ligeramente más lento con matrices de caracteres. Por lo tanto, si almacena los datos en la matriz char y luego los "procesa" de alguna manera usando tipos int, probablemente obtendrá una instrucción adicional cada vez que se realice una conversión entre los dos. Pruébalo con -S.