Complessità temporale dell'allocazione della memoria

Question

Qual è la complessità temporale dell'allocazione dinamica della memoria usando new, malloc, ecc.? So molto poco su come sono implementati gli allocatori di memoria, ma presumo che la risposta sia che dipende dall'implementazione. Pertanto, rispondi per alcuni dei casi / implementazioni più comuni.

Modifica: Ricordo vagamente di aver sentito che l'allocazione dell'heap non ha limiti nel caso peggiore, ma sono davvero interessato al caso medio / tipico.

Answer 1

Una delle cose che devi capire quando hai a che fare con la notazione O è che spesso è molto importante capire cosa sia n . Se n è qualcosa correlato a qualcosa che puoi controllare (ad esempio: il numero di elementi in un elenco che vuoi ordinare), allora ha senso guardarlo duro.

Nella maggior parte delle implementazioni di heap, n è il numero di blocchi di memoria contigui gestiti dal gestore. Questo è decisamente non qualcosa in genere sotto il controllo del cliente. L'unica n su cui il cliente ha davvero il controllo è la dimensione della porzione di memoria che desidera. Spesso ciò non ha alcuna relazione con il tempo impiegato dall'allocatore. Una grande n potrebbe essere allocata altrettanto rapidamente di una piccola n , oppure potrebbe richiedere molto più tempo o potrebbe anche essere inservibile. Tutto ciò potrebbe cambiare per la stessa n a seconda di come sono arrivate le allocazioni e le deallocazioni precedenti di altri clienti. Quindi, a meno che tu non stia implementando un heap, allora la risposta corretta è che non è -deterministic .

Ecco perché i programmatori in tempo reale cercano di evitare l'allocazione dinamica (dopo l'avvio).

Answer 2

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

Sui sistemi desktop, l'allocatore dell'heap probabilmente utilizza una combinazione di diverse strategie, tra cui memorizzazione nella cache di allocazioni recenti, elenchi di lookas per dimensioni di allocazione comuni, bin di blocchi di memoria con determinate caratteristiche di dimensione, ecc. per provare a mantenere basso il tempo di allocazione ma anche a mantenere frammentazione gestibile. Vedi le note per l'implementazione 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 adattamento ottimale, con i blocchi liberi memorizzati in un elenco collegato (che darebbe un tempo O (N) con N pari al numero di blocchi liberi). Ma un sistema di archiviazione più sofisticato come un albero AVL potrebbe essere utilizzato per individuare blocchi liberi nel 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 (Two-Level Segregate Fit), che ha un costo di allocazione O (1): http://www.gii.upv.es/tlsf/

Answer 3

Penso che sarebbe generalmente O (n) dove n è il numero di blocchi di memoria disponibili (poiché è necessario 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 meno di 1k sono in un elenco, i blocchi da 1k a 10k sono in un altro elenco e così via).

Questo è comunque O (n), solo con una n più piccola

Sarei interessato a vedere la tua fonte che c'è un'allocazione di heap che non ha limiti (se, con ciò, vuoi dire che potrebbe richiedere per sempre).

Answer 4

Scopri come funzionano gli allocatori tipici.

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

Per un allocatore di memoria segregata, l'allocazione di k byte significa "restituire il primo blocco dall'elenco ( n )" dove List ( n ) è l'elenco di blocchi di n byte in cui n > = k . potrebbe scoprire che Lista ( n ) è vuota, quindi un blocco dalla lista successiva (Lista ( 2n ) dovrebbe essere diviso con entrambi i blocchi risultanti di n byte inseriti in Elenco ( n ) e questo effetto potrebbe increspare tutte le dimensioni disponibili, rendendo complessità di O (ns) dove ns è il numero di diverse dimensioni disponibili e ns = log (N) dove N è la dimensione di la più grande dimensione del blocco disponibile, quindi anche quella sarebbe piccola. Nella maggior parte dei casi, specialmente dopo che un certo numero di blocchi sono stati allocati e deallocati, la complessità è O (1) .

Answer 5

Solo due osservazioni:

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

• Non è vero che il "migliore adattamento" la politica (trova il blocco stretto) è la più adatta a ottenere una piccola frammentazione. È tutt'altro che banale dimostrare questa affermazione, in realtà non è stato formalmente provato ma ci sono molte prove che vanno in quella direzione. (bel tema di ricerca).