L'uso di realloc() su un array 2D assegnato dinamicamente è una buona idea?

Question

Sono principalmente interessato alla redditività di che termina come una matrice.

Sto lavorando a un progetto in cui ho utilizzato singole chiamate malloc() per creare singoli array 2D moderatamente grandi. (Ogni poche decine di MiB, al massimo.) La cosa è che nel corso della vita di uno degli array, il suo contenuto si riduce drasticamente in termini di dimensioni (di oltre la metà). Ovviamente, potrei lasciare la dimensione dell'array da solo per la vita del programma. (È solo un x MiB su un sistema con GiB di RAM disponibile.) Ma, stiamo parlando di più della metà dello spazio assegnato che cade in disuso ben prima che il programma termini, e, a causa della natura di come sono usando l'array, tutti i dati sopravvissuti vengono mantenuti in un insieme contiguo di righe (all'inizio del blocco). Sembra uno spreco tenere tutto il RAM se davvero non ne ho bisogno.

Mentre so che realloc() può essere utilizzato per ridurre gli array creati dinamicamente, un array 2D è più complesso. Penso di averne compreso il layout di memoria (dato che ho implementato la funzione che lo struttura), ma questo sta spingendo i limiti della mia comprensione della lingua e del funzionamento dei suoi compilatori. Ovviamente, dovrei lavorare con le righe (e gestire i puntatori di riga), non solo i byte, ma non so quanto sarebbe prevedibile l'esito di tutto ciò.

E, sì, ho bisogno di creare l'array con un singolo malloc(). L'oggetto in questione ha diverse milioni di righe. Ho provato ad usare un ciclo su malloc() ogni riga separatamente, ma il programma si bloccava sempre a circa 100.000 malloc() s.

per lo sfondo, la fonte che sto usando per costruire questi array è come segue:

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

Utilizzando array multidimensionali, questo può essere fatto con o senza puntatori ad array di lunghezza variabile. Dal momento che probabilmente non si desidera allocare alcuna memoria aggiuntiva, questa operazione verrà eseguita.

Prima assegnare un 20 da 10 matrice:

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; 

Se si desidera modificare il numero di righe, senza elementi devono essere spostati, è necessario solo un realloc. La modifica del numero di righe su 15 è banale:

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

Se si desidera modificare il conteggio delle colonne, gli elementi dovranno essere spostati. Dal momento che non è necessario copiare la prima colonna, la copia inizia dal secondo. Il memmove di funzione viene utilizzato per evitare la sovrapposizione di memoria, cosa che in questo caso non può accadere, ma potrebbe accadere se il nuovo conteggio di colonna fosse più grande. Inoltre evita i problemi di aliasing. Si noti che questo codice è definito solo perché stiamo utilizzando la memoria allocata. Cambiamo contare la colonna 3:

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

esempio di lavoro: https://ideone.com/JMdJO0

Se il nuovo numero di colonne sembra essere più grande di quello vecchio, quindi la memoria dovrà essere riassegnati prima (per ottenere semplicemente più spazio), quindi si avvierà la copia della colonna, iniziando invece dall'ultima colonna.