Re: Sans SSE

Je viens de corriger la boucle, il est difficile d'éviter les jumps (dans le code ci-dessus, il aurait fallu utiliser "|" au lieu de "&").

J'ai également ajouté les options de compilation suggérées au-dessus, et le prefetch sur le premier algo :

$ gcc -march=native -funroll-all-loops -O3 -g test.c -o test.x
$ ./test.x 
C1 = 138643 (499999984), C2 = 89029 (499999984)

size_t find_int_c(int k, const int* v, size_t n)
{
 for (size_t i = 0; i != n; ++i) {
 if (v[i] == k) {
 return i;
 }
 __builtin_prefetch(v + i + 512, 0, 1);
 }
 return n;
}
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;) {
 index = 0;
 if (v[i] == k) index = 1;
 else if (v[i + 1] == k) index = 2;
 else if (v[i + 2] == k) index = 3;
 else if (v[i + 3] == k) index = 4;
 else if (v[i + 4] == k) index = 5;
 else if (v[i + 5] == k) index = 6;
 else if (v[i + 6] == k) index = 7;
 else if (v[i + 7] == k) index = 8;
 if (index != 0) i += n;
 i += 8;
 __builtin_prefetch(v + i + 512, 0, 1);
 }
 i -= n + 8;
 if (index == 0) return n;
 if (index == 1) return i;
 if (index == 2) return i + 1;
 if (index == 4) return i + 2;
 if (index == 8) return i + 3;
 if (index == 16) return i + 4;
 if (index == 32) return i + 5;
 if (index == 64) return i + 6;
 if (index == 128) return i + 7;
}

Les gains sont bien moins importants dans ce cas. On peut cela dit avoir envie d'éviter de dérouler toutes les boucles.. Puisque cela fait grossir la section code. Bref. On gagne quand même 40 % avec le déroulage manuel.