La complessità temporale dell’allocazione della memoria

Qual è la complessità temporale dell’assegnazione dynamic della memoria usando new, malloc, ecc.? So molto poco su come vengono implementati gli allocatori di memoria, ma presumo che la risposta sia che dipende dall’implementazione. Pertanto, si prega di rispondere per alcuni dei casi più comuni / implementazioni.

Modifica: Ricordo vagamente di aver sentito che l’allocazione dell’heap è illimitata nel peggiore dei casi, ma sono davvero interessato al caso medio / tipico.

Una delle cose che devi capire quando hai a che fare con la notazione O è che spesso è molto importante capire cos’è n . Se n è qualcosa di relativo a qualcosa che puoi controllare (es .: il numero di elementi in una lista che vuoi ordinare) allora ha senso guardarlo attentamente.

Nella maggior parte delle implementazioni di heap, n è il numero di blocchi contigui di memoria gestiti dal gestore. Questo non è decisamente qualcosa di solito sotto il controllo del cliente. L’unica cosa sul quale il cliente ha veramente il controllo è la dimensione del frammento di memoria che desidera. Spesso questo non ha alcuna relazione con la quantità di tempo che l’allocatore richiede. Un n grande potrebbe essere assegnato rapidamente come un n piccolo, o potrebbe richiedere molto più tempo, o potrebbe anche essere inutilizzabile. Tutto questo potrebbe cambiare per lo stesso n a seconda di come venivano allocate le precedenti allocazioni e deallocazioni da altri client. Quindi, in realtà, a meno che non si stia implementando un heap, la risposta corretta è che non è deterministico .

Questo è il motivo per cui i programmatori in tempo reale difficili cercano di evitare l’allocazione dynamic (dopo l’avvio).

La complessità temporale per un allocatore di heap può essere diversa su sistemi diversi, a seconda di cosa potrebbero essere ottimizzati.

Sui sistemi desktop, l’allocatore di heap utilizza probabilmente una combinazione di diverse strategie, incluse le allocazioni recenti nella cache, gli elenchi lookaside per le dimensioni di allocazione comuni, i contenitori di blocchi di memoria con determinate caratteristiche di dimensione, ecc. Per tentare di mantenere un tempo di allocazione inferiore, mantenendo inoltre gestibile la frammentazione. Vedere le note per l’implementazione di malloc di Doug Lea per una panoramica delle varie tecniche utilizzate: http://g.oswego.edu/dl/html/malloc.html

Per i sistemi più semplici, potrebbe essere utilizzata una strategia di primo adattamento o migliore adattamento, con i blocchi liberi memorizzati in una lista collegata (che darebbe un tempo O (N) con N come numero di blocchi liberi). Ma un sistema di storage più sofisticato come un albero AVL potrebbe essere usato per essere in grado di localizzare blocchi liberi in tempo O (log N) ( http://www.oocities.org/wkaras/heapmm/heapmm.html ).

Un sistema in tempo reale potrebbe utilizzare un allocatore di heap come TLSF (Segregate Fit a due livelli), che ha un costo di allocazione O (1): http://www.gii.upv.es/tlsf/

Penserei che sarebbe generalmente O (n) dove n è il numero di blocchi di memoria disponibili (dal momento che devi scansionare i blocchi di memoria disponibili per trovarne uno adatto).

Detto questo, ho visto ottimizzazioni che possono renderlo più veloce, in particolare mantenendo più elenchi di blocchi disponibili a seconda delle loro gamme di dimensioni (quindi i blocchi inferiori a 1k si trovano in un elenco, i blocchi da 1k a 10k sono in un altro elenco e così via ).

Questo è ancora O (n) tuttavia, solo con un n più piccolo.

Sarei interessato a vedere la tua fonte che c’è un’allocazione dell’heap che è illimitata (se, con questo, vuoi dire che potrebbe richiedere per sempre).

Basta controllare come funzionano gli allocatori tipici.

Un allocatore di bump-the-pointer funziona in O (1) , ed è un piccolo ” 1 “.

Per un allocatore di memoria segregata, l’allocazione di k byte significa “restituisce il primo blocco da List ( n )” dove List ( n ) è l’elenco di blocchi di n byte dove n> = k . È ansible che List ( n ) sia vuoto, in modo che un blocco dall’elenco successivo (List ( 2n )) debba essere diviso con entrambi i blocchi risultanti di n byte inseriti in List ( n ), e questo effetto potrebbe incresparsi attraverso tutte le dimensioni disponibili, creando una complessità di O (ns) dove ns è il numero di diverse dimensioni disponibili, e ns = log (N) dove N è la dimensione della dimensione del blocco più grande disponibile, quindi anche quella sarebbe piccola. Nella maggior parte dei casi, soprattutto dopo che un numero di blocchi è stato assegnato e deallocato, la complessità è O (1) .

Solo due osservazioni:

  • TLSF è O (1) nel senso che non ha un singolo ciclo; e gestisce fino a 2 GB. Anche se è davvero difficile da credere, basta controllare il codice.

  • Non è vero che la politica “best fit” (trovare il blocco stretto) è la più adatta per ottenere una piccola frammentazione. È tutt’altro che banale dimostrare questa affermazione, in realtà non è stata dimostrata formalmente, ma ci sono molte prove che vanno in quella direzione. (bel tema di ricerca).