quanto è efficiente l'ordinamento e la ricerca in malloc / free?

Tutte le tecniche di gestione della memoria che hai descritto presuppongono un elenco di blocchi di memoria liberi collegati singolarmente o doppiamente.

È certamente possibile utilizzare qualcosa di diverso da un elenco collegato per gestire la memoria, e ci sono gestori di memoria che fanno proprio questo , utilizzando un albero AVL o qualcosa di simile. Ma poi non stai più parlando di algoritmi in termini di ricerche lineari.

La maggior parte delle implementazioni moderne di malloc sono estremamente efficienti senza utilizzare strategie di adattamento in tempo lineare e invece possono spesso utilizzare operazioni a tempo costante. Vedi allocatori di slab come esempio.

Detto questo, ho notato che sembra che tu abbia interesse a scrivere un allocatore di memoria più veloce di malloc . Spero non ti dispiaccia, ma penso che sia un'idea molto controproducente. Quando cerchi di soddisfare tutti i requisiti di malloc come thread-safety e la capacità di allocare e liberare blocchi di memoria di dimensioni arbitrarie, è quasi imbattibile (forse un esperto di architettura di computer di Intel o qualcosa potrebbe essere in grado di inventare qualcosa leggermente migliore). Oltre a questo, di solito non è l'algoritmo di allocazione a costare così tanto, ad esempio, gli errori di pagina e le perdite obbligatorie della cache nel processo di caricamento di quella memoria che è un costo inevitabile ogni volta che si richiede nuova memoria dall'heap.

Il modo più semplice per ottenere più prestazioni dal codice con il collo di bottiglia di malloc e free è quello di usarle meno spesso. È possibile allocare un'enorme quantità di memoria e quindi collegarla alle aree del codice che ne hanno bisogno, potenzialmente in modo diretto e sequenziale (prestare attenzione all'allineamento) se non è necessario liberare la memoria di singoli blocchi finché non si hai finito con l'operazione (a quel punto puoi liberare tutta la memoria raggruppata in una volta), o dire, usando una lista libera se tutti i blocchi di memoria che stai allocando sono della stessa dimensione (nel qual caso non lo fai nemmeno preoccuparsi dell'allineamento). E se sai che ne hai solo bisogno per un dato thread, puoi raggruppare la memoria in modo lock-free.