2D-Array und Verarbeitungszeiten bei sehr ähnlichen Funktionen

Sunday

Ich erzeuge auf folgende Art ein 2D-Array vom Typ T. In diesem speichere
ich Bildinformationen.

typedef  unsigned long    u_long;
typedef  unsigned char    u_char;

// Array-Klasse (Auszug)
template <class T> class TArray2D
{
  private:

    T** Data;
    int Width, Height, Size;

  public:

    void Alloc(int AWidth, int AHeight);

    T*   GetData()   { return Data[0]; }
    int  GetWidth()  { return Width;   }
    int  GetHeight() { return Height;  } 
}

// Speicher für Array reservieren
template <class T> void TArray2D<T>::Alloc(int AWidth, int AHeight)
{
  Width  = AWidth;
  Height = AHeight;
  Size   = Width * Height;

  T **T1 = new T *[Height];
  T  *T2 = new T  [Size];

  if (T1 && T2)
  {
    for (u_long y = 0; y < Height; y++)
      T1[y] = T2 + (y * Width);

    Data = T1;

    // alles auf 0 setzen
    memset(Data[0], 0, Size * sizeof(T));
  }
}  

// Funktion rotiert das Array 'Source' um 90 Grad im Uhrzeigersinn
void Rotate90(TArray2D *Source, TArray2D *Target)
{
  u_char *SLine  = Source->GetData(); // Zeiger auf Array-Daten holen
  u_char *TLine  = Target->GetData();
  u_long  Height = Source->GetHeight();
  u_long  Width  = Source->GetWidth();
  u_char *SL     = SLine;
  u_char *TL     = TLine;

  u_long  x, y, xPos;

  for (y = 0; y < Height; y++)
  {
    xPos = Height - y - 1;

    for (x = 0; x < Width; x++)
      *(TL + (x * Height) + xPos) = *SL++;
  }
}

// Funktion rotiert das Array 'Source' um 180 Grad im Uhrzeigersinn
void Rotate180(TArray2D *Source, TArray2D *Target)
{
  u_char *SLine  = Source->GetData(); // Zeiger auf Array-Daten holen
  u_char *TLine  = Target->GetData();
  u_long  Height = Source->GetHeight();
  u_long  Width  = Source->GetWidth();
  u_char *SL     = SLine;
  u_char *TL     = TLine;

  u_long  x, y, yPos;

  for (y = 0; y < Height; y++)
  {
    yPos = (Height - y - 1) * Width;

    for (x = 0; x < Width; x++)
      *(TLine + yPos + (Width - x - 1)) = *SL++;
  }
}

Problem ist nun folgendes:

Ich habe ein Bild der Grösse 4096x4096 Bildpunkte (Grauwertbild).

Wenn ich jetzt diese Bild um 90 Grad rotiere so braucht mein Rechner ca. 1.7 Sekunden.
Wenn ich das Bild dagegen um 180 Grad drehen lasse, so benötigt er nur ca. 120 Millisekunden.

Woran kann das liegen?

Beide verwendeten Funktion sind oben aufgelistet.

Liegt das an der Art wie ich das Array anlege? Der Vorteil besteht ja darin über einen
einzigen Index (0 bis Höhe*Breite) auf sämtliche Array-Elemente zugreifen zu können.

Jester

Das liegt wahrscheinlich am Cache. Im 180 Grad Fall liest Du immer Zeilenweise. Der Prozessor liest also immer gleich ganz viel mit in den Cache was Du brauchen kannst. Im 90 Grad-Fall liest Du spaltenweise. Das heißt nahezu jeder Speicherzugriff wird einen Cache-Miss erzeugen. Das ist nicht wirklich schön.

MfG Jester

was könnte man da tun?

bekommt man den dirketen zugriff auf alle elemente des array (über eine schleife) auch auf eine andere art hin?

wenn ich es wie folgt mache, funktionierts ja nicht, da die reservierten speicherbereiche kreuz und quer im heap liegen könnten.

u_char **Array2D = new u_char *[Height];

for (int i = 0; i < Height; i++)
  Array2D[i] = new u_char[Width];

Sunday

nach weiteren tests ist mir nun aufgefallen, dass dieses langsame abarbeiten nur bei bildern mit einer breite und höhe von 2^x bildpunkten auftritt.

Jester

Wie sieht's eigentlich mit kleineren Bildern aus? Funktioniert es da? Vielleicht kannst Du das dann rekursiv machen? Man dreht ein Bild, in dem man es in vier Teile teilt und die an die entsprechende Stelle dreht... Und das so lange, bis Du bei einer vorher ausgemessenen Größe bist von der Du weißt, daß sie noch ordentlich schnell ist.