Borner un tableau - Optimisation

Bonjour à toutes et à tous,

je viens vers vous pour une question d'optimisation de bornes de tableau.
Le problème est extrêmement simple, nous avons un tableau, et on veut le borner (lui affecter un min et un max). Au lieu de la borne, on aurait pu faire n'importe quel traitement, peu importe.

Je poste le code utilisé :

Code:

---

1 2 3 4

for (j=0;j<WIDTH*HEIGHT;j++) { imagedata[j] = min(max(buffer[j],0),4095); }

---

Peut-on faire plus rapide que ceci ?

J'ai aussi remarqué qu'il y avait une grosse différence de temps d'exécution entre un memcpy et une affectation via une boucle. J'ai essayé de lire la doc de memcpy mais j'avoue ne pas comprendre comment ils gagnent autant de temps. Une explication serait la bienvenue :)

Merci d'avance,

Martin.

Citation:

---

Envoyé par tinte

Peut-on faire plus rapide que ceci ?

---

Bonjour

Passer par un pointeur...

Code:

---

1 2 3 4

for (j=0, ptI=imagedata, ptB=buffer;j<WIDTH*HEIGHT;j++, ptI++, ptB++) { (*ptI) = min(max(*ptB, 0), 4095); }

---

Citation:

---

Envoyé par tinte

J'ai aussi remarqué qu'il y avait une grosse différence de temps d'exécution entre un memcpy et une affectation via une boucle. J'ai essayé de lire la doc de memcpy mais j'avoue ne pas comprendre comment ils gagnent autant de temps. Une explication serait la bienvenue :)

---

Probablement parce que memcpy travaille sur des octets et utilise lui-aussi des pointeurs pour se déplacer d'un octet à l'autre

Exemple

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int main() { double tab[100]={...}; double copie[100];   copy1(copie, tab, 100); copy2(copie, tab, 100 * sizeof(double)); }   void copy1(double *c, double *o, size_t n) { size_t i; for (i=0; i < n; i++) c[i]=o[i]; }   void copy2(void *c, void *o, size_t n) { size_t i; char *ptC; char *ptO; for (i=0, ptC=c, ptO=o; i < n; i++, ptC++, ptO++) (*ptC)=(*ptO); }

---

A chaque fois que tu accèdes à tab[i], le processus repart de tab pour lui appliquer un déplacement de "i * taille_element". Avec un pointeur déjà positionné, ce décalage ne se fait plus...

Citation:

---

Envoyé par tinte

Peut-on faire plus rapide que ceci ?

---

Tu pourrais avoir un gain en utilisant des instructions SIMD (les compilateurs font des progrès en auto-vectorisation mais c’est pas encore le pied, il faut souvent les aider (préciser l’alignement de tes données par exemple) voire le faire soi-même).

Citation:

---

Envoyé par Sve@r

A chaque fois que tu accèdes à tab[i], le processus repart de tab pour lui appliquer un déplacement de "i * taille_element". Avec un pointeur déjà positionné, ce décalage ne se fait plus...

---

Ça c’est vrai si tu compiles sans optimisation et/ou que ton compilateur est pourri…
N’importe quel compilateur décent avec un minimum d’optimisation devrait fournir un code équivalent pour les deux versions. Il ne faut pas espérer de gain avec ça.

Le vrai gain vient de copier par paquet de 4 ou 8 bytes (voir plus si tu utilises les instructions vectorielles) au lieu de byte par byte.

Mais le vrai secret de memcpy c’est que, souvent, le compilateur possède sa propre implémentation (intrinsic) qu’il peut utiliser au lieu de la version fournit par la libc. Étant donné que le code fait partie du compilateur, il est connu et le compilateur peut donc présumer plus de choses et faire plus d’optimisation (voire choisir une version adapté à ton CPU).
Enfin, même sans cela, les libc viennent avec une version optimisée (voir plusieurs versions*: pour certaines fonctions la GNU libc à une version C + des versions en assembleurs qui utilisent SSE2, SSE3, …).

Avec des unsigned tu peux supprimer le minimum :mrgreen:

Et apparemment le code le plus simple est assez rapide (pas d'appel de fonction) et surtout si tu es sûr que tes valeurs sont faiblement au delà du maximum:

Code:

---

1 2 3 4 5

#define CLAMP(VAL, MAX) ((VAL <= MAX)? VAL: MAX);     imagedata[j] = CLAMP(buffer[j], 4095)

---