Ridurre al minimo la quantità di chiamate malloc() migliora le prestazioni?

Question

Considerate due applicazioni: una (numero 1) che richiama malloc() molte volte e l'altra (numero 2) che richiama malloc() alcune volte. Entrambe le applicazioni assegnano lo alla stessa quantità di memoria (supponiamo 100 MB).
Per quale applicazione la prossima chiamata malloc() sarà più veloce, n. 1 o n. 2?
In altre parole: malloc() ha un indice delle posizioni allocate in memoria?

Answer 1

Naturalmente questo dipende completamente dall'implementazione di malloc, ma in questo caso, senza chiamate gratuite, la maggior parte delle implementazioni di malloc ti darà probabilmente la stessa velocità algoritmica.

Come un'altra risposta ha commentato, di solito ci sarà una lista di blocchi liberi, ma se non hai chiamato libero, ce ne sarà uno solo, quindi dovrebbe essere O (1) in entrambi i casi.

Ciò presuppone che la memoria allocata per l'heap sia sufficientemente grande in entrambi i casi. Nel caso # 1, avrai assegnato più memoria totale, dato che ogni allocazione implica un overhead di memoria per memorizzare i meta-dati, di conseguenza potresti dover chiamare sbrk(), o equivalente per far crescere l'heap nel caso # 1, che sarebbe aggiungere un overhead aggiuntivo.

Probabilmente saranno diversi a causa della cache e di altri effetti del secondo ordine, poiché gli allineamenti di memoria per la nuova allocazione non saranno gli stessi.

Se hai liberato alcuni blocchi di memoria, è probabile che il n. 2 sia più veloce a causa della minore frammentazione, e quindi una lista più piccola di blocchi liberi da cercare.

Se hai liberato tutti i blocchi di memoria, dovrebbe finire per essere esattamente lo stesso, dal momento che qualsiasi implementazione sana di mente avrà riunito i blocchi in un'unica arena di memoria.

Answer 2

Questi sono ovviamente dettagli di implementazione, ma in genere free() inserirà la memoria in un elenco di blocchi liberi. malloc() quindi esaminerà questo elenco per un blocco libero della dimensione giusta o più grande. In genere, solo se ciò non riesce, il numero malloc() chiede al kernel più memoria.

Ci sono anche altre considerazioni, come quando combinare più blocchi adiacenti in un unico blocco più grande.

E, un altro motivo che malloc() è costoso: Se malloc() è chiamato da più thread, ci deve essere un qualche tipo di sincronizzazione su queste strutture globali. (vale a dire serrature.) Esistono implementazioni malloc() con diversi schemi di ottimizzazione per renderlo migliore per thread multipli, ma in generale, tenerlo aggiunto multi-thread sicuro al costo, in quanto più thread si contenderanno per quei blocchi e blocchi di progresso l'uno sull'altro.

Answer 3

La risposta è che dipende, la maggior parte della potenziale lentezza proviene invece da malloc() e free() in combinazione e di solito i punti # 1 e # 2 avranno velocità simili.

Tutte le implementazioni di malloc() hanno un meccanismo di indicizzazione, ma la velocità di aggiunta di un nuovo blocco all'indice solitamente non dipende dal numero di blocchi già presenti nell'indice.

maggior parte della lentezza di malloc proviene da due fonti

• ricerca di un blocco libero adatto tra i precedentemente liberati (blocchi)
• problemi multiprocessore con bloccaggio

scrittura mia possedere quasi malloc() strumento di sostituzione malloc() quasi malloc() & & libero() tempi dal 35% al ​​3-4%, e ha seriamente ottimizzato questi due fattori. Probabilmente sarebbe stata una velocità simile usare un altro malloc ad alte prestazioni, ma avere la nostra era più portabile a dispositivi esoterici e, naturalmente, consente di essere libero in alcuni punti.

Answer 4

Malloc deve passare attraverso un elenco collegato di blocchi liberi per trovarne uno da allocare. Questo richiede tempo. Così, # 1 di solito è più lenta:

• Quanto più spesso si chiama malloc, più tempo ci vorrà - in modo da ridurre il numero di chiamate vi darà un miglioramento della velocità (anche se è significativo dipenderà sulle tue circostanze esatte).

• Inoltre, se si malloc molti piccoli blocchi, mentre si liberano quei blocchi, si frammenterà l'heap molto più che se si allocano e liberino solo alcuni blocchi di grandi dimensioni. Quindi è probabile che tu abbia molti piccoli blocchi liberi sul tuo heap piuttosto che alcuni grossi blocchi, e quindi i mallocs potrebbero dover cercare ulteriormente attraverso gli elenchi di spazio libero per trovare un blocco adatto da allocare. Chi li renderà di nuovo più lenti.

Answer 5

hai chiesto 2 domande:

• per quale applicazione la chiamata successiva malloc() sarà più veloce, # 1 o 2 #?
• In altre parole: malloc() ha un indice delle posizioni allocate in memoria?

---

Hai implicava che essi sono la stessa domanda, ma non lo sono. La risposta a quest'ultima domanda è SI.

Per quanto sarà più veloce, è impossibile dirlo. Dipende dall'algoritmo di allocatore, dallo stato della macchina, dalla frammentazione nel processo corrente e così via.

La tua idea è buona, però: dovresti pensare a come l'uso di malloc influenzerà le prestazioni. C'era una volta un'app che scrissi che usava un sacco di piccoli blob di memoria, ognuno dei quali era assegnato a malloc(). Ha funzionato correttamente ma era lento. Ho sostituito le molte chiamate a malloc con una sola e poi ho suddiviso quel grande blocco all'interno della mia app. Era molto più veloce.

Non consiglio questo approccio; è solo un'illustrazione del punto che l'uso di malloc può influenzare materialmente le prestazioni.

Il mio consiglio è di misurarlo.

Answer 6

Non si definisce la differenza relativa tra "molti" e "pochi", ma ho il sospetto che la maggior parte dei mallocs funzionerebbero quasi identicamente in entrambi gli scenari. La domanda implica che ogni chiamata a malloc abbia un sovraccarico come una chiamata di sistema e aggiornamenti di tabelle di pagine. Quando fai una chiamata malloc, ad es. malloc (14), in un ambiente non cerebrale, malloc assegna effettivamente più memoria di quella richiesta, spesso un multiplo delle dimensioni della pagina della MMU di sistema. Si ottengono i 14 byte e malloc tiene traccia dell'area appena allocata in modo che le chiamate successive possano solo restituire un blocco della memoria già allocata, fino a quando non viene richiesta più memoria dal sistema operativo.

In altre parole, se chiamo malloc (14) 100 volte o malloc (1400) una volta, il sovraccarico sarà più o meno lo stesso. Dovrò solo gestire il grosso pezzo di memoria assegnato me stesso.

Answer 7

È possibile sempre fare un lavoro migliore utilizzando malloc() per allocare una grande porzione di memoria e suddividerla in modo autonomo. Malloc() è stato ottimizzato per funzionare bene nel caso generale e non prevede alcuna ipotesi sull'utilizzo o meno dei thread o sulla dimensione delle allocazioni del programma.

Se è una buona idea implementare il proprio sub-allocatore è una domanda secondaria. Raramente, la gestione esplicita della memoria è già abbastanza difficile. Raramente hai bisogno di un altro strato di codice che possa rovinare e mandare in crash il tuo programma senza un buon sistema per eseguirne il debug. A meno che non si stia scrivendo un allocatore di debug.

Answer 8

L'allocazione di un blocco di memoria è più veloce dell'assegnazione di molti blocchi. C'è il sovraccarico della chiamata di sistema e anche la ricerca di blocchi disponibili. Nella programmazione la riduzione del numero di operazioni di solito velocizza i tempi di esecuzione.

Gli allocatori di memoria potrebbero dover cercare per trovare un blocco di memoria della dimensione corretta. Ciò aumenta il sovraccarico del tempo di esecuzione.

Tuttavia, ci possono essere migliori possibilità di successo quando si assegnano piccoli blocchi di memoria rispetto a un blocco grande. Il tuo programma sta allocando un piccolo blocco e rilasciandolo o ha bisogno di allocare (e preservare) piccoli blocchi. Quando la memoria si frammenta, sono disponibili meno blocchi, quindi l'allocatore di memoria potrebbe dover unire tutti i blocchi per formare un blocco abbastanza grande per l'allocazione.

Se il programma sta allocando e distruggendo molti piccoli blocchi di memoria, è possibile prendere in considerazione l'assegnazione di un array statico e l'utilizzo di tale memoria.