Sans SSE

Il faut utiliser objdump pour observer le code compilé, ensuite, il faut fournir la commande de compilation.

Sans forcer, je divise par 2.6 le temps de la boucle original (j'ai eu la flemme de calculer le résultat exacte).

size_t find_int_c2(const int k, const int* v, const size_t n)
{
 int index = 0;
 size_t i = 0;
 for (; i < n - 8;) {
 int r0 = v[i++] - k;
 index = r0 == 0 ? 1 : index;
 int r1 = v[i++] - k;
 index = r1 == 0 ? 2 & index : index;
 int r2 = v[i++] - k;
 index = r2 == 0 ? 4 & index : index;
 int r3 = v[i++] - k;
 index = r3 == 0 ? 8 & index : index;
 int r4 = v[i++] - k;
 index = r4 == 0 ? 16 & index : index;
 int r5 = v[i++] - k;
 index = r5 == 0 ? 32 & index : index;
 int r6 = v[i++] - k;
 index = r6 == 0 ? 64 & index : index;
 int r7 = v[i++] - k;
 index = r7 == 0 ? 128 & index : index;
 if (index != 0) i += n;
 __builtin_prefetch(v + i + 512, 0, 1);
 }
 return index != -1 ? i + index : n;
}

Voila l'idée, supprimer les Jumps. Je pense que ça peut s'améliorer d'un facteur 2 ou 3.

$ gcc -march=native -O3 -g test.c -o test.x
$ objdump -dS test.x
$ ./test.x 
C1 = 228117 (499999984), C2 = 85911 (999999993)

Le main:

int main() {
 int* tab = malloc(SIZE * 4);
 for (int i = 0; i < SIZE; i++) {
 tab[i] = i;
 }
 clock_t c1 = clock();
 size_t r1 = find_int_c(SIZE - 16, tab, SIZE);
 clock_t c1end = clock();
 clock_t c2 = clock();
 size_t r2 = find_int_c2(SIZE - 16, tab, SIZE);
 clock_t c2end = clock();
 printf("C1 = %ld (%ld), C2 = %ld (%ld)\n", c1end - c1, r1, c2end - c2, r2);
}