Die Minimierung der Anzahl von malloc() -Aufrufen verbessert die Leistung?

Betrachten Sie zwei Anwendungen: eine (Nr. 1), die malloc() viele Male aufruft, und die andere (Nr. 2), die malloc() einige Male aufruft. Beide Anwendungen weisen die gleich Speichermenge (angenommen 100 MB).
Für welche Anwendung wird der nächste Aufruf von malloc() schneller sein, #1 oder #2?
Mit anderen Worten: Hat malloc() einen Index allozierter Speicherplätze?

Du hast 2 Fragen gestellt:

• Für welche Anwendung wird der nächste Aufruf von malloc() schneller sein, #1 oder #2?
• Mit anderen Worten: Hat malloc() einen Index allozierter Speicherplätze?

Sie haben angedeutet, dass es sich um dieselbe Frage handelt, aber das ist nicht der Fall. Die Antwort auf die letzte Frage lautet JA.

Was schneller sein wird, kann man nicht sagen. Dies hängt vom Zuweisungsalgorithmus, dem Maschinenzustand, der Fragmentierung im aktuellen Prozess usw. ab.

Ihre Idee ist jedoch vernünftig: Sie sollten darüber nachdenken, wie sich die Verwendung von malloc auf die Leistung auswirkt. Es gab einmal eine App, die ich geschrieben habe und die viele kleine Speicherkleckse verwendet hat, die jeweils mit malloc() zugewiesen wurden. Es funktionierte korrekt, war aber langsam. Ich habe die vielen malloc-Aufrufe durch nur einen ersetzt und diesen großen Block dann in meiner App aufgeteilt. Es ging viel viel schneller.

Ich empfehle diesen Ansatz nicht; es ist nur eine Veranschaulichung dafür, dass die Verwendung von malloc die Leistung erheblich beeinträchtigen kann.

Mein Rat ist Messe Es.

Natürlich hängt dies vollständig von der malloc-Implementierung ab, aber in diesem Fall werden Ihnen die meisten malloc-Implementierungen wahrscheinlich die gleiche algorithmische Geschwindigkeit geben, da es keine Aufrufe von free gibt.

Wie eine andere Antwort kommentierte, gibt es normalerweise eine Liste mit freien Blöcken, aber wenn Sie nicht kostenlos angerufen haben, gibt es nur einen, also sollte es in beiden Fällen O (1) sein.

Dies setzt voraus, dass der für den Heap zugewiesene Speicher in beiden Fällen groß genug ist. Im Fall Nr. 1 haben Sie mehr Gesamtspeicher zugewiesen, da jede Zuweisung Speicheraufwand zum Speichern von Metadaten mit sich bringt. Daher müssen Sie möglicherweise sbrk() oder etwas Ähnliches aufrufen, um den Heap in Fall Nr. 1 zu vergrößern, was der Fall wäre fügen Sie einen zusätzlichen Overhead hinzu.

Sie werden wahrscheinlich aufgrund von Cache- und anderen Effekten zweiter Ordnung unterschiedlich sein, da die Speicherausrichtungen für die neue Zuordnung nicht dieselben sein werden.

Wenn Sie einige der Speicherblöcke freigegeben haben, ist es wahrscheinlich, dass Nr. 2 aufgrund der geringeren Fragmentierung schneller ist und daher eine kleinere Liste freier Blöcke zum Durchsuchen enthält.

Wenn Sie alle Speicherblöcke freigegeben haben, sollte es am Ende genau gleich sein, da jede vernünftige freie Implementierung die Blöcke wieder in einen einzigen Speicherbereich zusammengeführt hat.

Malloc muss eine verknüpfte Liste freier Blöcke durchlaufen, um einen zuzuweisenden zu finden. Das braucht Zeit. Also wird Nr. 1 normalerweise langsamer sein:

• Je öfter Sie malloc anrufen, desto mehr Zeit wird es in Anspruch nehmen – so dass die Verringerung der Anzahl der Aufrufe zu einer Geschwindigkeitsverbesserung führt (obwohl dies von Ihren genauen Umständen abhängt, ob dies signifikant ist).

• Wenn Sie viele kleine Blöcke mallocieren, fragmentieren Sie den Heap außerdem viel stärker, wenn Sie diese Blöcke freigeben, als wenn Sie nur einige wenige große Blöcke zuweisen und freigeben. Daher werden Sie am Ende wahrscheinlich eher viele kleine freie Blöcke auf Ihrem Heap haben als ein paar große Blöcke, und daher müssen Ihre Mallocs möglicherweise die Listen mit freiem Speicherplatz weiter durchsuchen, um einen geeigneten Block zum Zuweisen zu finden. Was sie wieder langsamer macht.

Dies sind natürlich Implementierungsdetails, aber typisch free() fügt den Speicher in eine Liste freier Blöcke ein. malloc() sucht dann in dieser Liste nach einem freien Block, der die richtige Größe hat oder größer ist. Normalerweise nur, wenn dies fehlschlägt malloc() Fragen Sie den Kernel nach mehr Speicher.

Es gibt auch andere Überlegungen, z. B. wann mehrere benachbarte Blöcke zu einem einzigen, größeren Block zusammengeführt werden sollen.

Und ein weiterer Grund dafür malloc() ist teuer: Wenn malloc() von mehreren Threads aufgerufen wird, müssen diese globalen Strukturen irgendwie synchronisiert werden. (dh Schleusen.) Es gibt malloc() Implementierungen mit unterschiedlichen Optimierungsschemata, um es für mehrere Threads besser zu machen, aber im Allgemeinen erhöht die Multi-Thread-Sicherheit die Kosten, da mehrere Threads um diese Sperren konkurrieren und den Fortschritt gegenseitig blockieren.

Du kannst stets machen Sie einen besseren Job mit malloc(), um einen großen Teil des Speichers zuzuweisen und ihn selbst zu unterteilen. Malloc() wurde optimiert, um im allgemeinen Fall gut zu funktionieren, und macht keine Annahmen darüber, ob Sie Threads verwenden oder nicht, oder wie groß die Zuweisungen des Programms sein könnten.

Ob es eine gute Idee ist, einen eigenen Suballocator zu implementieren, ist eine sekundäre Frage. Das ist selten der Fall, die explizite Speicherverwaltung ist schon schwer genug. Sie brauchen selten eine weitere Codeschicht, die Ihr Programm vermasseln und zum Absturz bringen kann, ohne dass es eine gute Möglichkeit gibt, es zu debuggen. Es sei denn, Sie schreiben einen Debug-Zuordner.

Die Antwort ist, dass es davon abhängt, dass der größte Teil der potenziellen Langsamkeit eher von malloc() und free() in Kombination kommt und normalerweise #1 und #2 von ähnlicher Geschwindigkeit sind.

Alle malloc()-Implementierungen haben einen Indizierungsmechanismus, aber die Geschwindigkeit, mit der ein neuer Block zum Index hinzugefügt wird, hängt normalerweise nicht von der Anzahl der Blöcke ab, die sich bereits im Index befinden.

Der größte Teil der Langsamkeit von malloc stammt aus zwei Quellen

• Suche nach einem geeigneten freien Block unter den zuvor freigegebenen (Blöcken)
• Multi-Prozessor-Probleme mit Sperren

Das Schreiben meines eigenen, fast standardkonformen malloc()-Ersatzwerkzeugs malloc() && free() malloc() && free() malloc() malloc() && free() Mal von 35% auf 3-4%, und es hat diese beiden Faktoren ernsthaft optimiert. Es wäre wahrscheinlich eine ähnliche Geschwindigkeit gewesen, einen anderen Hochleistungs-Malloc zu verwenden, aber unser eigener war besser auf esoterische Geräte übertragbar und erlaubte natürlich, an einigen Stellen kostenlos inliniert zu werden.

Sie definieren den relativen Unterschied zwischen “vielen” und “wenigen” nicht, aber ich vermute, dass die meisten Mallocs in beiden Szenarien fast identisch funktionieren würden. Die Frage impliziert, dass jeder Aufruf von malloc so viel Overhead hat wie ein Systemaufruf und Seitentabellenaktualisierungen. Wenn Sie einen malloc-Aufruf machen, zB malloc(14), in einer nicht hirntoten Umgebung, wird malloc tatsächlich mehr Speicher zuweisen, als Sie verlangen, oft ein Vielfaches der System-MMU-Seitengröße. Sie erhalten Ihre 14 Bytes und malloc verfolgt den neu zugewiesenen Bereich, sodass spätere Aufrufe einfach einen Teil des bereits zugewiesenen Speichers zurückgeben können, bis mehr Speicher vom Betriebssystem angefordert werden muss.

Mit anderen Worten, wenn ich malloc(14) 100 Mal oder malloc(1400) einmal aufrufe, ist der Overhead ungefähr gleich. Ich muss nur den größeren zugewiesenen Speicherblock selbst verwalten.