Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
23.10.2006, 15:22 Uhr
Archimedes

Hi Coder und Performancefetischisten,

es existiert ja schon paralleler Beitrag über Matheoperatoren. Da ich im Quellcode selber nur noch wenig optimieren kann, stellt sich die Frage, ob man for-Schleifen durch andere Anordnung (Reihenfolge) die Performance verbessern kann.

Der Fall: 3 geschachtelte for-Schleifen.
Die Aufgabe: Ein Bild Pixel für Pixel durchlaufen und auf jedem Pixel Untersuchungen berechnen.
Die Schleifen:
1. for-Schleife: Höhe des Bildes (ca 400 Pixel)
2. for-Schleife: Breite des Bildes (ca 400 Pixel)
3. for-Schleife: Rechenintensive Untersuchung durch Transformation des Bildes (20 for-Durchläufe)
Das Ziel: Maximale Geschwindigkeit ! Es geht um eine Echtzeitanforderung. Sollte ich den "C"-Code nicht schnell genug bekommen, so muss ich auf Assembler zurück greifen (und davor grauts mir ! ;-))

Meine Vermutung:
Da ich in 2 Felder nacheinander schreibe (in 3. for-Schleife), muss im Cache viel gesprungen werden (Speichersprünge). Dieser Zugriff schätze ich als Flaschenhals ein.
Aufgrund eines Optimierungstools weis ich auch ganz genau, dass die Performance in den beiden Zeilen hängen bleibt, in welchen in die Felder geschrieben wird.

Da ich jeden Pixel durchlaufen und untersuchen muss, kann ich die Schleifen nicht weiter "kastrieren".

Meine Frage:
Kann ich durch andere Reihenfolge der for-Schleifen viel Performance gewinnen ?
Gibt es weitere Möglichkeiten, bei diesem Problem einen Geschwindigkeitsgewinn zu bekommen ?

Vielen Dank,
Grüsse,
Archi

Dieser Post wurde am 23.10.2006 um 15:40 Uhr von Archimedes editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
23.10.2006, 21:03 Uhr
~Robert
Gast

Hi Archimedes !

Loop unrolling koennte z.B etwas bringen. Beim unrolling haengt es wiederum davon ab, wie die Befehle aneinander gereiht werden.
Koenntest du vielleicht mal die komplette(n) Funktion(en) in einen der beiden Threads posten ?
Dann kann man das auch mal selber ein bisschen testen.

Robert

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
24.10.2006, 08:11 Uhr
ao

(Operator)

Zitat von Archimedes:

Da ich in 2 Felder nacheinander schreibe (in 3. for-Schleife), muss im Cache viel gesprungen werden (Speichersprünge). Dieser Zugriff schätze ich als Flaschenhals ein.

Kannst du anstatt einer innersten Schleife zwei nacheinander machen, und in der ersten Schleife nur das erste Feld schreiben und in der zweiten nur das zweite, also so:

C++:

for (...) // äußere Schleife
{
    for (...) // mittlere Schleife
    {
        for (...) // erste innere Schleife
        {
              feld1[i] = ....;
        }

        for (...) // zweite innere Schleife
        {
              feld2[i] = ....;
        }
    }
}

Ansonsten stell mal fest, wo genau die Performance auf der Strecke bleibt, ob in der Zuweisung an die Feldvariable oder in der Berechnung des Ausdrucks rechts vom Gleich-Zeichen.

ao

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
24.10.2006, 09:29 Uhr
Archimedes

C++:

   maxHeight = iHeight + iStart_y;
   maxWidth  = iWidth + iStart_x;

   for( i = iStart_y; i < maxHeight; i++ )
   {
      pSrcPix = pALine;
      pBtrPix = pBLine;

      for( j = iStart_x; j < maxWidth; j++ )
      {
         fInfo1 = *pSrcPix;
         pSrcPix++;
         fInfo2 = *pSrcPix;
         pSrcPix++;
         fAlpha   = *pSrcPix;
         pSrcPix++;
         fBetrag = *pBtrPix;
         pBtrPix++;

         if( fInfo1 > 0.0000001 && (long)( fInfo2 * 100 ) >= 0.0 )
         {
            fValue= ( fInfo1 - fInfo2 ) / ( fInfo1 + fInfo2 );
            fQual = q * q;

            if( fValue > fMinValue )
            {
               if( fAlpha == ( PI / 2 ) || fAlpha == -( PI / 2 ))
               {
                  m = 0;
                  b = j;
                  lInv = 1;
               }
               else
               {
                  m = tan( fAlpha );
                  b = i - m * j;
                  lInv = 0;
               }

               if( lInv == 0 && ( m >= -1 && m <= 1 ))   // -1 <= m <= 1
               {
                  x_min = (long)( j - ( CVC_MAXRADIUS - 3 )  * cos( fAlpha ));
                  x_max = (long)( j + ( CVC_MAXRADIUS - 3 )  * cos( fAlpha ));
                  if( x_min < 0 ) x_min = 0;
                  if( x_max >= iWidth ) x_max = iWidth;

                  for( x = x_min; x < x_max; x += 2)
                  {
                     y = (long)( m * x + b );
                     if( y >= 0 && y < iHeight )
                     {
                        tmp1 = j - x;
                        tmp2 = i - y;
                        r = a * e * h;   // Dummy
                        coord = (( x >> 1 ) * iHHeight + ( y >> 1 )) * CVC_MAXRADIUS + ( r >> 1 );
                        plHImg[coord]+= fQual;   // Feld1
                        plHCnt[coord]++;           // Feld2
                     }
                  }
               }
               else
               {
                  if( !lInv )
                  {
                     m = 1 / m;
                     b = j - m * i;
                  }
                  if( fAlpha > 0 )
                  {
                     y_min = (long)( i - ( CVC_MAXRADIUS - 3 )  * sin( fAlpha ));
                     y_max = (long)( i + ( CVC_MAXRADIUS - 3 )  * sin( fAlpha ));
                  }
                  else
                  {
                     y_min = (long)( i + ( CVC_MAXRADIUS - 3 )  * sin( fAlpha ));
                     y_max = (long)( i - ( CVC_MAXRADIUS - 3 )  * sin( fAlpha ));
                  }
                  if( y_min < 0 ) y_min = 0;
                  if( y_max >= iHeight ) y_max = iHeight;

                  for( y = y_min; y < y_max; y += 2 )
                  {
                     x = (long)( m * y + b );
                     if( x >= 0 && x < iWidth )
                     {
                        r = a * e * h;   // Dummy
                        coord = (( x >> 1 ) * iHHeight + ( y >> 1 )) * CVC_MAXRADIUS + ( r >> 1 );
                        plHImg[coord]+= fQual;   // Feld1
                        plHCnt[coord]++;           // Feld2
                     }
                  }
               }
            }
            else
            {
            }
         }
         else
         {
         }
      }
      pALine += next_a_line;
      pBLine += next_b_line;
   }
   return( ret );
}

Ich brauche die 2 Felder direkt nacheinander. Eine neue For-Schleife wäre ein Schritt in die falsche Richtung (meiner Meinung). Ich werde den Algo wohl nochmal modifizieren. Ich habe einen neuen mathematischen Ansatz, bei dem ich die Fallunterscheidung in der 2. For-Schleife heraus kürzen kann, und die 2 inneren For-Schleifen (3. Ebene) zu einer merge.

Das Performance-Problem liegt im Aufruf und Zuweisung der Feldeinträge. Da bin ich mir sicher (hab die Performance im "C", als auch im Assembler-Code sichtbar).

Grüsse,
Archi

Dieser Post wurde am 24.10.2006 um 09:39 Uhr von Archimedes editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
24.10.2006, 18:05 Uhr
virtual
Sexiest Bit alive
(Operator)

Ich habe mir jetzt die Schleife nicht angeschaut, aber du Benutzt öfters sin/cos/tan:

C++:

x_min = (long)( j - ( CVC_MAXRADIUS - 3 ) * cos( fAlpha ));
x_max = (long)( j + ( CVC_MAXRADIUS - 3 ) * cos( fAlpha

kann man cos(fAlpha) nicht schon mal in eine variable schreiben und dann wiederverwenden?
Analoges dann für sin(fAlpha)

mit tan = sin/cos kannst Du Dir dann den tangens Aufruf komplett sparen: der scheint nur für m gebraucht zu werden, dh es reicht aus, sin udn cos (betraglich) zu vergleichen. Ausserdem kannst Du die variable lInv aus diese Weise Quit werden, weil die ja nur ein diskriminator für den Fall cos(fAlpha)==0 ist.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Dieser Post wurde am 24.10.2006 um 18:06 Uhr von virtual editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: