Frage Kann dieser Code optimiert werden?


Ich habe einen Bildverarbeitungscode, der zwei mehrdimensionale Byte-Arrays (der gleichen Größe) durchläuft. Es nimmt einen Wert aus dem Quell-Array, führt eine Berechnung durch und speichert das Ergebnis in einem anderen Array.

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));
   }
}

Die Schleife dauert derzeit ~ 11ms, was vermutlich hauptsächlich auf den Zugriff auf die Byte-Array-Werte zurückzuführen ist, da die Berechnung ziemlich einfach ist (2 Multiplikationen und 1 Addition).

Kann ich etwas tun, um dies zu beschleunigen? Es ist ein zeitkritischer Teil meines Programms und dieser Code wird 80-100 Mal pro Sekunde aufgerufen, so dass jede Geschwindigkeitssteigerung, egal wie klein sie auch sein mag, einen Unterschied machen wird. Auch im Moment xSize = 768 und ySize = 576, aber dies wird in Zukunft zunehmen.

Aktualisieren: Dank an Güffel (siehe Antwort unten), der folgende Code spart mir 4-5ms pro Schleife. Obwohl es ist unsicher 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--;
        }
    }
}

7
2018-03-31 17:41


Ursprung


Antworten:


Um einen echten speadup für diesen Code zu erhalten, müssen Sie Zeiger verwenden, um auf die Arrays zuzugreifen, wodurch alle Indexberechnungen und die Überprüfung der Grenzen entfernt werden.

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--;
      }
   }
}

Bearbeiten:
Feste Variablen können nicht geändert werden, daher habe ich Code hinzugefügt, um die Zeiger auf neue Zeiger zu kopieren, die geändert werden können.


5
2018-03-31 18:17



Dies sind alles unabhängige Berechnungen. Wenn Sie also eine Multicore-CPU haben, sollten Sie in der Lage sein, durch Parallelisierung der Berechnung einen gewissen Nutzen zu erzielen. Beachten Sie, dass Sie die Threads beibehalten und sie einfach weiterreichen müssen, da der Overhead der Thread-Erstellung dieses wahrscheinlich langsamer und nicht schneller macht, wenn die Threads jedes Mal neu erstellt werden.

Die andere Sache, die funktionieren kann, ist das Abarbeiten der Arbeit für den Grafikprozessor. Ansehen diese Frage für einige Ideen, zum Beispiel, verwenden Beschleuniger.


5
2018-03-31 17:49



Eine Option wäre die Verwendung von unsicherem Code: Fixieren des Arrays im Speicher und Verwenden von Zeigeroperationen. Ich bezweifle jedoch, dass der Geschwindigkeitsanstieg so dramatisch sein wird.

Eine Anmerkung: Wie geht es Ihnen? Wenn Sie DateTime verwenden, beachten Sie, dass diese Klasse eine schlechte Auflösung hat. Sie sollten eine äußere Schleife hinzufügen und die Operation zehnmal wiederholen - ich wette, das Ergebnis ist weniger als 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));
         }
    }
}

4
2018-03-31 17:44



Seit es erscheint dass jede Zelle in der Matrix völlig unabhängig von den anderen berechnet wird. Vielleicht möchten Sie prüfen, ob mehr als ein Thread dies erledigt. Um die Kosten für das Erstellen von Threads zu vermeiden, könnten Sie einen Thread-Pool haben.

Wenn die Matrix von ausreichender Größe ist, könnte dies ein sehr guter Geschwindigkeitsgewinn sein. Auf der anderen Seite, wenn es zu klein ist, kann es nicht helfen (sogar verletzen). Einen Versuch wert.

Ein Beispiel (Pseudocode) könnte so aussehen:

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

BEARBEITEN:  Michael Meadows in einem Kommentar erwähnt, dass Plinq eine geeignete Alternative sein kann: http://msdn.microsoft.com/en-us/magazine/cc163329.aspx


4
2018-03-31 17:48



Ich würde empfehlen, ein paar leere Tests zu machen, um herauszufinden, was Ihre theoretischen Grenzen sind. Nehmen Sie zum Beispiel die Berechnung aus der Schleife heraus und sehen Sie, wie viel Zeit gespart wird. Versuchen Sie, die doppelte Schleife durch eine einzelne Schleife zu ersetzen, die dieselbe Anzahl von Malen ausführt und wie viel Zeit gespeichert wird. Dann können Sie sicher sein, dass Sie den richtigen Weg für die Optimierung gehen (die zwei Pfade, die ich sehe, reduzieren die doppelte Schleife in eine einzige Schleife und arbeiten mit der Multiplikation [vielleicht wäre eine Lookup-Tabelle schneller]).


3
2018-03-31 17:50



Nur sehr schnell, Sie können eine Optimierung erhalten, indem Sie rückwärts einlaufen lassen und mit 0 vergleichen. Die meisten CPUs haben eine schnelle Operation zum Vergleich mit 0.

Z.B.

int xSize = ResultImageData.GetLength(0) -1;
int ySize = ResultImageData.GetLength(1) -1; //minor optimization suggested by commenter

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

Sehen http://dotnepperls.com/Content/Decrement-Optimization.aspx


3
2018-03-31 17:55



Sie leiden wahrscheinlich an Boundschecking. Wie Jon Skeet sagt, ist ein gezacktes Array anstelle eines multidimensionalen (d. H data[][] Anstatt von data[,]) wird schneller sein, so seltsam das auch scheinen mag.

Der Compiler wird optimiert

for (int i = 0; i < data.Length; i++) 

durch Eliminieren der Bereichsüberprüfung pro Element. Aber es ist eine Art Spezialfall, es wird nicht dasselbe für GetLength () sein.

Aus demselben Grund war es auch eine schlechte Sache, die Eigenschaft Length zwischenzuspeichern oder zu hissen (sie in eine Variable wie xSize zu schreiben), obwohl ich dies mit Framework 3.5 nicht überprüfen konnte


3
2018-03-31 18:11



Versuchen Sie, die x- und y-for-Schleifen für ein lineareres Speicherzugriffsmuster und (also) weniger Cache-Misses auszutauschen.

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

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

2
2018-04-01 16:52



Wenn Sie LockBits verwenden, um in den Image-Puffer zu gelangen, sollten Sie y in der äußeren Schleife und x in der inneren Schleife durchlaufen, so wie es im Speicher gespeichert ist (nach Zeile, nicht nach Spalte). Ich würde sagen, dass 11ms verdammt schnell ist.


1
2018-03-31 17:43



Müssen die Bilddaten in einem mehrdimensionalen (rechteckigen) Array gespeichert werden? Wenn Sie stattdessen gezackte Arrays verwenden, stellen Sie möglicherweise fest, dass im JIT mehr Optimierungen verfügbar sind (einschließlich Entfernen der Überprüfung der Grenzen).


1
2018-03-31 17:43



Wenn CurrentImageData und / oder AlphaImageData nicht jedes Mal geändert werden, wenn Sie Ihr Code-Snippet ausführen, können Sie das Produkt speichern, bevor Sie das angezeigte Code-Snippet ausführen, und diese Multiplikation in Ihren Schleifen vermeiden.

Edit: Eine andere Sache, an die ich gerade dachte: Manchmal sind Int-Operationen schneller als Byte-Operationen. Versetzen Sie dies mit Ihrer Prozessor-Cache-Auslastung (Sie erhöhen die Datengröße erheblich und erhöhen das Risiko eines Cache-Miss).


1
2018-03-31 18:02