Trate
total += (-((i & mask) != 0)) & value[j];
en lugar de
total += ((i & mask) != 0) * value[j];
Esto evita la multiplicación. Si habrá una rama o no depende de si el compilador es lo suficientemente inteligente como para encontrar un código libre de ramificación para - (foo! = 0). (Lo cual es posible, pero me gustaría ser un poco sorprendido.)
(Por supuesto, esto depende de la representación en complemento a dos;. El estándar C es agnóstico en eso)
que te pueden ayudar a cabo el compilador como tal, asumiendo enteros de 32 bits y que se propaga >> firmado el bit de signo:
total += (((int)((i & mask) << (31 - j))) >> 31) & value[j];
es decir, cambiar el conjunto de bits posiblemente-izquierda a la posición más significativa, elegida como int firmado, luego a la derecha todo el camino de regreso a la posición menos significativa, produciendo todos los 0 o todos los 1, bajo los supuestos definidos en la implementación anterior. (No he probado esto.)
Otra posibilidad: considere bloques de (digamos) 4 bits a la vez. Hay 16 secuencias de adición diferentes; puede enviar a código desenrollado para cada uno de ellos, sin pruebas en absoluto dentro de cada bloque de código. La esperanza aquí es que un salto indirecto cueste menos de 4 pruebas y ramas.
Actualización: El uso de andamios de Jonathan Leffler, el método 4 bits-en-un-tiempo es más rápido por un amplio margen en mi MacBook. Negar, y resulta ser casi lo mismo que multiplicar. Me pregunto si el procesador multiplica casos especiales como 0 y 1 más rápido (o no es un caso tan especial si es más rápido para la mayoría de los bits claros o la mayoría de los conjuntos de bits en general).
No codifiqué la respuesta aceptada, ya que es poco probable que sea la más rápida en este punto de referencia en particular (debe obtener la mayor parte de su beneficio al enumerar solo los bits establecidos, obteniendo mejores resultados en conjuntos dispersos, pero la mitad completa se establecen en este punto de referencia). Aquí están mis cambios en el código de Leffler, en caso de que alguien más está extrañamente motivados para dedicar tiempo a esto:
#include <stdio.h>
#include <time.h>
static int value[] =
{
12, 36, 79, 21, 31, 93, 24, 15,
56, 63, 20, 47, 62, 88, 9, 36,
};
static int test_1(int i)
{
int total = 0;
for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
{
if (i & mask)
total += value[j];
}
return(total);
}
static int test_2(int i)
{
int total = 0;
for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
{
total += ((i & mask) != 0) * value[j];
}
return(total);
}
static int test_3(int i)
{
int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
{
total += (mask & 0x0001) * value[j];
}
return(total);
}
static int test_4(int i)
{
int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
{
total += -(mask & 0x0001) & value[j];
}
return(total);
}
static int test_5(int i)
{
int total = 0;
const int *p = value;
for (unsigned mask = i & 0xFFFF; mask != 0; mask >>= 4, p += 4)
{
switch (mask & 0xF)
{
case 0x0: break;
case 0x1: total += p[0]; break;
case 0x2: total += p[1]; break;
case 0x3: total += p[1] + p[0]; break;
case 0x4: total += p[2]; break;
case 0x5: total += p[2] + p[0]; break;
case 0x6: total += p[2] + p[1]; break;
case 0x7: total += p[2] + p[1] + p[0]; break;
case 0x8: total += p[3]; break;
case 0x9: total += p[3] + p[0]; break;
case 0xA: total += p[3] + p[1]; break;
case 0xB: total += p[3] + p[1] + p[0]; break;
case 0xC: total += p[3] + p[2]; break;
case 0xD: total += p[3] + p[2] + p[0]; break;
case 0xE: total += p[3] + p[2] + p[1]; break;
case 0xF: total += p[3] + p[2] + p[1] + p[0]; break;
}
}
return(total);
}
typedef int(*func_pointer)(int);
static func_pointer test[] = { test_1, test_2, test_3, test_4, test_5 };
#define DIM(x)(sizeof(x)/sizeof(*(x)))
int main()
{
int i, j, k;
for (i = 0; i < DIM(test); i++)
{
long sum = 0;
clock_t start = clock();
for (j = 0; j <= 0xFFFF; j += 13)
{
int rv;
for (k = 0; k < 1000; k++)
rv = (*test[i])(j);
sum += rv;
}
clock_t stop = clock();
printf("(sum = %ld) Test %d: %8.6f s\n", sum, i + 1,
(stop - start)/(1.0 * CLOCKS_PER_SEC));
}
}
resultados (gcc -O4 -std=c99 branchmult2.c):
(sum = 1744366) Test 1: 0.225497 s
(sum = 1744366) Test 2: 0.221127 s
(sum = 1744366) Test 3: 0.126301 s
(sum = 1744366) Test 4: 0.124750 s
(sum = 1744366) Test 5: 0.064877 s
Edit 2: decidí la prueba haría ser más realista sin el calificador volatile.
ambos deberían recopilar a lo mismo, dado un compilador cuerdo. iría con la primera opción más legible. ¿Su plataforma admite la ejecución predicada? funcionaría bien aquí, solo hay 1 instrucción para predicar (el complemento), por lo que no necesitaría una bifurcación bona fide en este caso. –
Algo a tener en cuenta: puedes reemplazar '((i & mask)! = 0)' con '!! (i & mask)'. "¡¡¡!!" es un abuso de! operador para crear un operador de "emitir a bool" aplicándolo dos veces. Esto no debería cambiar el ensamblaje generado, pero es un idioma común y más legible para mi ojo. – kquinn
Un recordatorio de que ((i & máscara)! = 0) puede no ser portátil .... falso es 0, verdadero no es 0 .... – Calyth