optimiser le code en courant alternatif sur la boucle imbriquée

Question

je le code suivant

for(i=0;i<16;i++) 
    for(j=0;j<16;j++) 
    { 
    in=(i+u*j+rl+rc)&15; 
    jn=(v*i+(u*v+1)*j+rc)&15; 
    x1[i*16+j]=x2[in*16+jn]; 
    } 

des notes:

1. rl, rc, u et v sont des valeurs Randome vont de 0 à 15
2. x1 et x2 sont des tableaux de 256 valeurs, la plage de chaque valeur de tableau est comprise entre 0 et 255
3. si je veux mettre en œuvre ce code en utilisant la table de consultation est nécessaire 16MB et cette grande mémoire

Answer 1

Une certaine idée, vous pouvez essayer:

Vous pouvez construire une table de consultation pour toutes les combinaisons de u et v, qui nécessiteraient que 64k de mémoire. rl et rc fonctionnent comme des décalages constants horizontalement et verticalement (ils peuvent être déplacés à la dernière instruction et ne doivent pas participer au calcul de in et jn). Cela réduirait la quantité de maths que vous avez à faire.

Comme avec toutes les autres optimisations de performances, vous devez d'abord voir si c'est vraiment le goulot d'étranglement. Il se pourrait que la mémoire soit beaucoup plus lente et que l'introduction d'une grande table de consultation ne ferait que ralentir les choses.

Answer 2

Voici une idée:

Essayez d'extraire des parties du calcul qui ne changent pas à l'extérieur au moins l'intérieur boucle. Par exemple, i + rl + rc du calcul in n'a pas besoin d'être à l'intérieur de la boucle. Une fois que vous avez cela, vous réalisez que la valeur de in augmente de u à chaque itération, modulo 16 bien sûr. Donc, au lieu de faire une multiplication, vous pouvez faire une addition.

Le calcul jn a aussi quelques citations à extraire. Bien sûr, cela suppose que vous sachiez qu'il s'agit d'un goulot d'étranglement au niveau des performances (profile it!) Et que le compilateur n'est pas assez intelligent pour effectuer une telle optimisation. En cas de doute, inspectez l'ensemble.