Tipo entero más rápido para arquitecturas comunes

stdint c

Question

El encabezado stdint.h carece de int_fastest_t y uint_fastest_t para corresponderse con los tipos {,u}int_fastX_t . Para las instancias donde el ancho del tipo entero no importa, ¿cómo se elige el tipo de entero que permite procesar la mayor cantidad de bits con la menor penalización al rendimiento? Por ejemplo, si uno estaba buscando el primer bit configurado en un búfer usando un enfoque ingenuo, se podría considerar un bucle como este:

// return the bit offset of the first 1 bit
size_t find_first_bit_set(void const *const buf)
{
    uint_fastest_t const *p = buf; // use the fastest type for comparison to zero
    for (; *p == 0; ++p); // inc p while no bits are set
    // return offset of first bit set
    return (p - buf) * sizeof(*p) * CHAR_BIT + ffsX(*p) - 1;
}

Naturalmente, usar char resultado más operaciones que int . Pero long long podría resultar en operaciones más costosas que la sobrecarga de usar int en un sistema de 32 bits y así sucesivamente.

Mi suposición actual es para las arquitecturas principales, el uso de long es la apuesta más segura: es de 32 bits en sistemas de 32 bits y de 64 bits en sistemas de 64 bits.

Answer 1

La respuesta es int si. Al menos en C ++, donde 3.9.1 / 2 del estándar dice:

Las int simples tienen el tamaño natural sugerido por la arquitectura del entorno de ejecución

Espero que lo mismo sea cierto para C, aunque no tengo ninguno de los documentos de estándares.

Answer 2

Si está compilando con gcc, le recomendaría usar __builtin_ffs () para encontrar el primer conjunto de bits:

Función incorporada: int __builtin_ffs (unsigned int x) Devuelve uno más el índice del menos significativo de 1 bit de x, o si x es cero, devuelve cero.

Esto se compilará en (a menudo una sola) instrucción de ensamblaje nativo.

Answer 3

Si quiere estar seguro de que tiene la implementación más rápida, ¿por qué no comparar cada uno de los sistemas que espera ejecutar en lugar de tratar de adivinar?

Answer 4

Teóricamente, int es la mejor apuesta. Debería asignarse al tamaño de registro nativo de la CPU y, por lo tanto, ser "óptimo" en el sentido que usted está preguntando.

Sin embargo, todavía puede encontrar que un int-64 o int-128 es más rápido en algunas CPU que en un int-32, porque aunque son más grandes que el tamaño de registro, reducirán el número de iteraciones de su ciclo, y por lo tanto pueden trabaje de forma más eficiente minimizando los gastos generales de bucle y / o aprovechando DMA para cargar / almacenar los datos más rápidamente.

(Por ejemplo, en los procesadores ARM-2 se necesitaron 4 ciclos de memoria para cargar un registro de 32 bits, pero solo 5 ciclos para cargar dos de forma secuencial y 7 ciclos para cargar 4 secuencialmente. La rutina que sugiera anteriormente se optimizaría para usarla como muchos registros, ya que podría liberar (8 a 10 por lo general), y por lo tanto, podría ejecutar hasta 3 o 4 veces más rápido mediante el uso de múltiples registros por iteración de bucle)

La única forma de estar seguro es escribiendo varias rutinas y luego perfilarlas en la máquina objetivo específica para descubrir cuál produce el mejor rendimiento.

Answer 5

int_fast8_t es siempre el tipo entero más rápido en una implementación correcta. Nunca puede haber tipos enteros menores que 8 bits (porque se CHAR_BIT>=8 ), y dado que int_fast8_t es el tipo de entero más rápido con al menos 8 bits, es por lo tanto el tipo de entero más rápido, el período.

Answer 6

No es posible responder a esta pregunta ya que la pregunta es incompleta. Como una analogía, considera la pregunta:

¿Cuál es el vehículo más rápido?

¿Un Bugatti Veyron ? Ciertamente rápido, pero no sirve para ir de Londres a Nueva York.

Lo que falta de la pregunta es el contexto en el que se usará el entero. En el ejemplo anterior, dudo que veas mucha diferencia entre los valores de 8, 32 o 64 bits si la matriz es grande y escasa, ya que estar llegando a los límites de ancho de banda de memoria antes de los límites de CPU.

El punto principal es que la arquitectura no define qué tamaño tienen los distintos tipos de enteros, sino que es el diseñador del compilador el que lo hace. El diseñador sopesará cuidadosamente los pros y los contras de varios tamaños para cada tipo de arquitectura dada y elegirá la más adecuada.

Supongo que se eligió el int de 32 bits en el sistema de 64 bits porque para la mayoría de las operaciones que se usan para 32 bits son suficientes. Dado que el ancho de banda de la memoria es un factor limitante, el ahorro en el uso de la memoria fue probablemente el factor primordial.

Answer 7

Supongo que los tipos size_t (para un tipo sin signo) y ptrdiff_t (para un tipo con signo) generalmente corresponderán a tipos de entero bastante eficientes en cualquier plataforma dada.

Pero nada puede probar eso que inspeccionar el ensamblador producido y hacer puntos de referencia.

Editar , incluyendo los diferentes comentarios, aquí y en otras respuestas:

size_t y ptrdiff_t son los únicos typedefs que son normativos en C99 y para los cuales se puede suponer razonablemente que están relacionados con la arquitectura.

Hay 5 diferentes rangos posibles para tipos enteros estándar ( char , short , int , long , long long ). Todas las fuerzas van hacia tener tipos de ancho 8, 16, 32, 64 y en un futuro próximo 128. Como consecuencia, int se atascará en 32 bits. Su definición no tendrá nada que ver con la eficiencia en la plataforma, sino que estará restringida por ese requisito de ancho.

Answer 8

Para todas las arquitecturas mainstream existentes, long es el tipo más rápido en la actualidad para el rendimiento del bucle.

Answer 9

No estoy seguro de entender realmente la pregunta, pero ¿por qué no estás usando int ? Citando de mi (copia de borrador libre del incorrecto, es decir C ++) el estándar, "Los colores normales tienen el tamaño natural sugerido por la arquitectura del entorno de ejecución".

Pero creo que si quieres tener el tipo entero óptimo para una determinada operación, será diferente dependiendo de qué operación sea. Intentar encontrar el primer bit en un búfer de datos grande, o encontrar un número en una secuencia de enteros o moverlos, bien podría tener tipos óptimos completamente diferentes.

EDITAR:

Para lo que sea, hice un pequeño punto de referencia. En mi sistema particular (Intel i7 920 con Linux, gcc -O3) resulta que las entradas largas (64 bits) son bastante más rápidas que las simples (32 bits), en este ejemplo en particular. Hubiera supuesto todo lo contrario.