Laufzeitverhalten delete[]

Hallo!

Ich versuche gerade, eine Matrix-Klasse zu implementieren, und bin dabei auf ein relativ interessantes Laufzeitverhalten von delete[] gestoßen.

Zum Testen habe ich mir ein Array von Matrix-Pointern angelegt, das ich mit Matrizen zufälliger Größe befülle, eine paar Zugriffe mache, und dann wieder lösche.

Zufällig habe ich dann entdeckt, dass die Löschung des Arrays bei einer Größe von 464284 bis 517149 Elementen wesentlich länger dauert, als normal (über 95ms; <464284 benötigt bis ca. 40ms, >517149 benötigt ab ca. 45ms; reproduzierbar, da ich rand() immer gleich initialisiere). Möglicherweise trifft das auch noch auf weitere Bereiche zu, aber ich habe ja nicht wirklich eine Möglichkeit, das erschöpfend zu testen.

Ich habe dann durch valgrind festgestellt, dass, wenn es länger dauert, bei den Aufrufen der Operatoren dann statt

operator delete -> free -> 0x752B0

scheinbar einmal

operator delete -> free -> 0x752B0 -> 0x739D0

aufgerufen wird, wobei in der Funktion dann einmalig die ganze Zeit verbraten wird.

Leider ist es mir nicht gelungen, aus den Funktionspointern auf die entsprechenden C-Library-Funktionen zurückzuschließen, weshalb ich nicht nachvollziehen kann, was da genau passiert.
0x739D0 wird aber scheinbar indirekt von malloc (23 mal) und free (1 mal) aufgerufen.

Kann mir jemand erklären, was da passiert?

Mit freundlichen Grüßen

Christian

Die relevanten Teile der Matrix-Klasse:

template <typename T>
class Matrix
{
public:
  Matrix(const int& numberOfRows, const int& numberOfColums,
         const T& defaultValue);

  const int &NumberOfRows() const;
  const int &NumberOfColumns() const;

  ~Matrix();

private:
  int numberOfRows_;
  int numberOfColumns_;

  T* elements_;
};

template <typename T>
Matrix<T>::Matrix(const int& numberOfRows, const int& numberOfColumns,
                  const T& defaultValue)
  : numberOfRows_   (numberOfRows),
    numberOfColumns_(numberOfColumns),
    elements_       (new T[numberOfRows * numberOfColumns])
{
   if (numberOfRows < 1 || numberOfColumns < 1)
   {
     throw();
   }

  for (int counter = 0; counter < numberOfRows * numberOfColumns; ++counter)
  {
    elements_[counter] = defaultValue;
  }
}

template <typename T>
inline const int& Matrix<T>::NumberOfRows() const
{
  return numberOfRows_;
}

template <typename T>
inline const int& Matrix<T>::NumberOfColumns() const
{
  return numberOfColumns_;
}

template <typename T>
Matrix<T>::~Matrix()
{
  delete[] elements_;
}

Mein Testaufbau (ohne Zeitmessung) sieht ungefähr folgendermaßen aus:

const int numberOfTrials     = 464284;
  const int maxNumberOfRows    = 10;
  const int maxNumberOfColumns = 10;

  srand(123456);

  Matrix<double>** pointer = new Matrix<double>*[numberOfTrials];

  int numberOfRows    = 0;
  int numberOfColumns = 0;
  for (int counter = 0; counter < numberOfTrials; ++counter)
  {
    numberOfRows = 1 + int(double(rand()) / double(RAND_MAX) * double(maxNumberOfRows - 1));
    numberOfColumns = 1 + int(double(rand()) / double(RAND_MAX) * double(maxNumberOfColumns - 1));

    pointer[counter] = new Matrix<double>(numberOfRows, numberOfColumns, 0.0);
  }

  //andere Tests, Zugriffe, etc.

//Dieser Teil braucht jetzt unterschiedlich lange

  for (int counter = 0; counter < numberOfTrials; ++counter)
  {
    delete pointer[counter];
  }

  delete[] pointer;

SeppJ

1. Warum baust du std::vector schlecht nach, anstatt std::vector zu benutzen?
2. Hast du auch alle Optimierungen eingeschaltet? Deinen Testaufbau würde mein Compiler nämlich gänzlich wegoptimieren. Wenn du also eine von Null verschiedene Laufzeit herausbekommst, optimiert dein Compiler wohl nicht.

SeppJ schrieb:

1. Warum baust du std::vector schlecht nach, anstatt std::vector zu benutzen?

Naja, ich bin noch Anfänger.

SeppJ schrieb:

2. Hast du auch alle Optimierungen eingeschaltet? Deinen Testaufbau würde mein Compiler nämlich gänzlich wegoptimieren. Wenn du also eine von Null verschiedene Laufzeit herausbekommst, optimiert dein Compiler wohl nicht.

Grade -02 drangehängt, und es wird dadurch nur generell um ein paar Millisekunden schneller. Ich schreibe in die Matrizen beim Testen Werte rein; der Teil fehlt lediglich im geposteten Code.

MfG

SeppJ

739D0 schrieb:

SeppJ schrieb:

1. Warum baust du std::vector schlecht nach, anstatt std::vector zu benutzen?

Naja, ich bin noch Anfänger.

Schlechte Ausrede. Von deinem Codestil her zu urteilen, bist du weit fortgeschrittener als jemand der die STL nicht kennt.

Gut, ich habe den Test schnell zusammengehackt, wobei ich dann meistens vergesse, dass es die STL überhaupt gibt.
Leider bringt es auch nichts, wenn ich std::vector statt meinem ** verwende. Der Bereich, in dem das Phänomen auftritt, verschiebt sich dann etwas, aber es ist immer noch vorhanden. Bis 500000 Elemente scheint alles zu passen, dann dauert's auf einmal länger, und ab 750000 geht's wieder gewohnt schnell.
Ja, ich weiß, mit so vielen Matrizen wird man selten hantieren, vor allem nicht in der Form, aber das Problem bei der Sache ist eigentlich nur, dass da etwas passiert, dass ich nicht wirklich nachvollziehen kann, und daher mache ich mir Gedanken, ob ich nicht etwas übersehen habe.

MfG

wx++

Also wenn du k Matrizen jeweils zufälliger Größe löschst, tritt dabei genau einmal diese "Anomalie" auf, richtig verstanden? (464284<k<517149)
Welche Größe hat die Matrix, deren Freigabe außergewöhnlich lange dauert?
Lässt sich das auch mit Matrizen konstanter Größe reproduzieren? Mit primitiven Datentypen?

wx++ schrieb:

Also wenn du k Matrizen jeweils zufälliger Größe löschst, tritt dabei genau einmal diese "Anomalie" auf, richtig verstanden? (464284<k<517149)

Ja, das ist genau das, was ich beobachte.

wx++ schrieb:

Welche Größe hat die Matrix, deren Freigabe außergewöhnlich lange dauert?
Lässt sich das auch mit Matrizen konstanter Größe reproduzieren? Mit primitiven Datentypen?

Mit primitiven Datentypen ist es mir jetzt nicht gelungen, das zu reproduzieren, aber das kann auch an der Schrittgröße liegen, mit der ich die Anzahl der Element erhöht habe.
Für Matrizen mit konstanter Größe ist der Bereich etwas anders, aber es tritt ebenfalls auf. Die Matrix, die das Verhalten auslöst, unterscheidet sich also nicht von den anderen.
Anscheinend ist es immer die letzte Matrix im Array.
Allerdings tritt es nicht auf, wenn ich beim Freigeben von hinten nach vorne laufe...

MfG