Esistono dei buoni algoritmi per implementare un heap che minimizza la frammentazione?

3

In questo momento sto provando a creare un heap che richiede un allineamento di 8 byte e ho cercato in giro online alcuni buoni metodi che avrebbero ridotto al minimo la quantità di frammentazione. Meno frammentazione è l'ideale, e anche quelli che rallenteranno molto sono una considerazione (ma la velocità è anche un sotto-obiettivo qui)

Qualcuno ha avuto qualche esperienza con Heaps che potrebbe farmi sapere a cosa fare attenzione quando si parla di questo? Qualsiasi input è apprezzato

    
posta Dark Templar 11.10.2011 - 19:33
fonte

1 risposta

2

Un ammasso coalescente allevierà (ma non eviterà) la frammentazione coalesciando blocchi liberi adiacenti. Ogni volta che liberi un blocco, guarda i blocchi successivi e precedenti nella tua lista. Se entrambi (o possibilmente entrambi) sono liberi, puoi combinarli per formare un blocco grande. Alcune implementazioni rimandano la coalescenza fino a quando l'allocazione fallisce, a quel punto l'allocatore percorre l'heap e cerca i blocchi liberi adiacenti da unire fino a quando non ne trova uno abbastanza grande da soddisfare la richiesta. Ciò offre migliori prestazioni nel caso medio, ma le prestazioni nel caso peggiore sono molto peggiori. L'unione dei blocchi al momento della deallocazione ammortizza il costo su tutte le deallocations, quindi non c'è molta differenza tra le prestazioni dei casi migliori e quelle peggiori.

    
risposta data 11.10.2011 - 21:51
fonte

Leggi altre domande sui tag