Ce code peut-il être optimisé ?

Question

J'ai un code de traitement d'image qui boucle sur deux tableaux d'octets multidimensionnels (de même taille). Il prend une valeur dans le tableau source, effectue un calcul dessus, puis stocke le résultat dans un autre tableau.

int xSize = ResultImageData.GetLength(0);
int ySize = ResultImageData.GetLength(1);

for (int x = 0; x < xSize; x++)
{                
   for (int y = 0; y < ySize; y++) 
   {                                                
      ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
                                    (AlphaImageData[x, y] * OneMinusAlphaValue));
   }
}

La boucle prend actuellement ~11ms, ce qui je suppose est principalement dû à l'accès aux valeurs des tableaux d'octets car le calcul est assez simple (2 multiplications et 1 addition).

Y a-t-il quelque chose que je puisse faire pour accélérer le processus ? C'est une partie critique de mon programme et ce code est appelé 80-100 fois par seconde, donc tout gain de vitesse, même minime, fera une différence. En outre, pour le moment, xSize = 768 et ySize = 576, mais cela augmentera à l'avenir.

Mise à jour : Merci à Guffa (voir réponse ci-dessous), le code suivant me fait gagner 4-5ms par boucle. Bien que ce soit non sécurisé code.

int size = ResultImageData.Length;
int counter = 0;
unsafe
{
    fixed (byte* r = ResultImageData, c = CurrentImageData, a = AlphaImageData)
    {
        while (size > 0)
        {
            *(r + counter) = (byte)(*(c + counter) * AlphaValue + 
                                    *(a + counter) * OneMinusAlphaValue);
            counter++;
            size--;
        }
    }
}

Answer 1

Il s'agit de calculs indépendants, donc si vous disposez d'un processeur multicœur, vous devriez pouvoir tirer parti de la parallélisation des calculs. Notez que vous devrez conserver les threads et leur donner du travail à faire, car la surcharge liée à la création des threads rendra probablement cette opération plus lente que rapide si les threads sont recréés à chaque fois.

L'autre solution qui pourrait fonctionner est de confier le travail au processeur graphique. Regardez cette question pour quelques idées, par exemple, utiliser Accélérateur .

Answer 2

Pour obtenir une réelle amélioration de ce code, vous devriez utiliser des pointeurs pour accéder aux tableaux, ce qui supprime tous les calculs d'index et la vérification des limites.

int size = ResultImageData.Length;
unsafe 
{
   fixed(byte* rp = ResultImageData, cp = CurrentImageData, ap = AlphaImageData) 
   {
      byte* r = rp;
      byte* c = cp;
      byte* a = ap;
      while (size > 0) 
      {
         *r = (byte)(*c * AlphaValue + *a * OneMinusAlphaValue);
         r++;
         c++;
         a++;
         size--;
      }
   }
}

Edit :
Les variables fixes ne peuvent pas être modifiées, j'ai donc ajouté du code pour copier les pointeurs vers de nouveaux pointeurs qui peuvent être modifiés.

Answer 3

Une option serait d'utiliser du code non sécurisé : fixer le tableau en mémoire et utiliser les opérations sur les pointeurs. Je doute cependant que l'augmentation de la vitesse soit aussi spectaculaire.

Une remarque : comment se passe ton timing ? Si vous utilisez DateTime, sachez que cette classe a une mauvaise résolution. Vous devriez ajouter une boucle externe et répéter l'opération disons dix fois -- je parie que le résultat est inférieur à 110ms.

for (int outer = 0; outer < 10; ++outer)
{
    for (int x = 0; x < xSize; x++)
    {                
         for (int y = 0; y < ySize; y++) 
         {                                                
              ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
                                             (AlphaImageData[x, y] * OneMinusAlphaValue));
         }
    }
}

Answer 4

Puisqu'il apparaît que chaque cellule de la matrice est calculée de manière totalement indépendante des autres. Vous pourriez envisager de confier cette tâche à plusieurs fils. Pour éviter le coût de la création de threads, vous pouvez utiliser un pool de threads.

Si la matrice est de taille suffisante, cela pourrait représenter un gain de vitesse très appréciable. D'un autre côté, si elle est trop petite, elle peut ne pas aider (voire nuire). Mais cela vaut la peine d'essayer.

Un exemple (pseudo-code) pourrait être le suivant :

void process(int x, int y) {
    ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
        (AlphaImageData[x, y] * OneMinusAlphaValue));
}

ThreadPool pool(3); // 3 threads big

int xSize = ResultImageData.GetLength(0);
int ySize = ResultImageData.GetLength(1);

for (int x = 0; x < xSize; x++) {
     for (int y = 0; y < ySize; y++)  {
         pool.schedule(x, y);  // this will add all tasks to the pool's work queue
     }
}

pool.waitTilFinished(); // wait until all scheduled tasks are complete

EDIT : Michael Meadows a mentionné dans un commentaire que plinq pourrait être une alternative appropriée : http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 5

Je vous recommande d'effectuer quelques tests à vide pour déterminer quelles sont vos limites théoriques. Par exemple, retirez le calcul à l'intérieur de la boucle et voyez combien de temps vous gagnez. Essayez de remplacer la double boucle par une boucle unique qui s'exécute le même nombre de fois et voyez combien de temps cela vous fait gagner. Vous serez alors sûr de suivre la bonne voie pour l'optimisation (les deux voies que je vois sont l'aplatissement de la double boucle en une seule boucle et le traitement de la multiplication [l'utilisation d'une table de consultation serait peut-être plus rapide]).