Verwenden Sie realloc() auf einem dynamisch zugewiesenen 2D-Array eine gute Idee?

Question

Ich bin vor allem an der Lebensfähigkeit von Schrumpf so ein Array interessiert.

Ich arbeite an einem Projekt, bei dem ich einzelne malloc() - Aufrufe verwendet habe, um einzelne mittelgroße 2D-Arrays zu erstellen. (Jeweils nur einige Dutzend MiB, höchstens.) Die Sache ist, dass über die Lebensdauer eines der Arrays sein Inhalt dramatisch in der Größe schrumpft (um mehr als die Hälfte). Offensichtlich könnte ich die Array-Größe einfach für die gesamte Lebensdauer des Programms belassen. (Es ist nur eine x MiB auf einem System mit GiB RAM verfügbar.) Aber wir sprechen davon, dass mehr als die Hälfte des zugewiesenen Speicherplatzes lange bevor das Programm beendet wird, und aufgrund der Art, wie ich bin, außer Gebrauch kommen Mit dem Array werden alle überlebenden Daten in einer zusammenhängenden Reihe von Zeilen (am Anfang des Blocks) gehalten. Es scheint eine Verschwendung zu sein, an all dem RAM festzuhalten, wenn ich es wirklich nicht brauche.

Während ich weiß, dass realloc() verwendet werden kann, um dynamisch erstellte Arrays zu verkleinern, ist ein 2D-Array komplexer. Ich denke, ich verstehe das Speicherlayout davon (da ich die Funktion implementiert habe, die es strukturiert), aber dies treibt die Grenzen meines Verständnisses der Sprache und der Funktionsweise ihrer Compiler. Offensichtlich müsste ich mit Zeilen arbeiten (und mit den Zeilenzeigern umgehen), nicht nur Bytes, aber ich weiß nicht, wie vorhersehbar das Ergebnis von all dem sein würde.

Und ja, ich muss das Array mit einem einzigen malloc() erstellen. Das Objekt hat mehrere Millionen Zeilen. Ich habe versucht, eine Schleife zu malloc() jeder Zeile getrennt, aber das Programm immer um rund 100.000 malloc() s eingefroren.

für den Hintergrund, die Quelle ich diese Anordnung zu konstruieren bin ist wie folgt:

char ** alloc_2d_arr(int cnum, int rnum) { 
     /* ((bytes for row pointers + (bytes for data)) */ 
     char **mtx = malloc(rnum * sizeof (char *) + rnum * cnum * sizeof (char)); 

     /* Initialize each row pointer to the first cell of its row */ 
     char *p = (char *) (mtx + rnum); 
     for (int i = 0; i < rnum; i++) { 
       mtx[i] = p + i * cnum; 
     } 

     return mtx; 
} 

Answer 1

multidimensionalen Arrays verwenden, kann dies mit oder ohne Zeiger auf variabler Länge Arrays durchgeführt werden. Da Sie wahrscheinlich keinen zusätzlichen Speicher reservieren möchten, wird dies an Ort und Stelle geschehen.

Zunächst wird eine 20 um 10 Array zuteilen:

int (*array)[10] = malloc(sizeof(int) * 20 * 10); 
for(size_t i = 0 ; i < 20 ; i++) 
    for(size_t j = 0 ; j < 10 ; j++) 
      array[i][j] = i * 100 + j; 

Wenn Sie die Anzahl der Zeilen ändern möchten, keine Elemente bewegt werden müssen, nur ein realloc benötigt wird. Ändern der Zeilenanzahl auf 15 ist trivial:

array = realloc(array , sizeof(int) * 15 * 10); 

Wenn Sie die Anzahl der Spalten ändern möchten, dann müssen die Elemente verschoben werden. Da wir die erste Spalte nicht kopieren müssen, beginnt der Kopiervorgang mit dem zweiten. Die Funktion memmove wird verwendet, um Speicherüberlappungen zu vermeiden, die in diesem Fall nicht auftreten können, aber dies könnte der Fall sein, wenn die neue Spaltenanzahl größer ist. Außerdem vermeidet es Alias-Probleme. Beachten Sie, dass dieser Code nur definiert wird, weil wir reservierten Speicher verwenden. Lassen Sie sich die Säule bis 3 zählen ändern:

int (*newarray)[3] = (int(*)[3])array; 
for(size_t j = 1 ; j < 15 ; j++) 
    memmove(newarray[j] , array[j] , sizeof(int) * 3); 
newarray = realloc(array , sizeof(int) * 15 * 3); 

Arbeitsbeispiel: https://ideone.com/JMdJO0

Wenn die neue Spaltenanzahl passiert sein, größer als die alten, dann wird der Speicher hat ersten umverteilt werden (einfach zu erhalten mehr Platz), und dann wird die Spaltenkopie statt in der letzten Spalte ausgeführt.