Betrachte zwei Anwendungen: eine (Nummer 1), die malloc() mehrmals aufruft, und die andere (Nummer 2), die malloc() einige Male aufruft. Beide Anwendungen zuweisen die gleiche Speichermenge (davon ausgehen, 100 MB).
Für welche Anwendung wird der nächste Aufruf von malloc() schneller sein, # 1 oder # 2?
Mit anderen Worten: Besitzt malloc() einen Index der zugewiesenen Speicherorte?Minimiert die Anzahl der malloc() -Aufrufe die Leistung?
Natürlich hängt dies vollständig von der malloc-Implementierung ab, aber in diesem Fall werden die meisten malloc-Implementierungen wahrscheinlich die gleiche algorithmische Geschwindigkeit haben, wenn Sie keine freien Aufrufe benötigen.
Wie eine andere Antwort kommentiert, wird es normalerweise eine Liste von freien Blöcken geben, aber wenn Sie nicht frei aufgerufen haben, wird es nur eine geben, also sollte es in beiden Fällen O (1) sein.
Dies setzt voraus, dass der Speicher für den Heap in beiden Fällen groß genug ist. Im Fall # 1 haben Sie mehr Gesamtspeicher zugewiesen, da jede Zuweisung Speicherbedarf für das Speichern von Metadaten mit sich bringt. Daher müssen Sie möglicherweise sbrk() aufrufen, um den Heap im ersten Fall zu vergrößern fügen Sie einen zusätzlichen Overhead hinzu.
Sie werden wahrscheinlich aufgrund von Cache und anderen Effekten zweiter Ordnung anders sein, da die Speicherausrichtungen für die neue Zuordnung nicht die gleichen sein werden.
Wenn Sie einige der Speicherblöcke freigegeben haben, ist es wahrscheinlich, dass # 2 aufgrund der geringeren Fragmentierung schneller ist, und so eine kleinere Liste freier Blöcke zu suchen.
Wenn Sie alle Speicherblöcke freigegeben haben, sollte es genau das gleiche sein, da jede vernünftige freie Implementierung die Blöcke wieder in eine einzige Speicherarena zusammengeführt hat.
Dies sind natürlich Implementierungsdetails, aber normalerweise free() wird den Speicher in eine Liste von freien Blöcken einfügen. malloc() wird dann diese Liste nach einem freien Block anschauen, der die richtige Größe oder größer hat. Nur wenn dies fehlschlägt, fragt der Kernel normalerweise malloc() nach mehr Speicher.
Es gibt auch andere Überlegungen, z. B. wann mehrere zusammenhängende Blöcke zu einem einzigen größeren Block zusammengeführt werden sollen.
Und ein weiterer Grund, dass malloc() ist teuer: Wenn malloc() aus mehreren Threads aufgerufen wird, muss es eine Art von Synchronisation auf diesen globalen Strukturen sein. (d. h. Sperren.) Es gibt malloc() Implementierungen mit verschiedenen Optimierungsschemata, um es für mehrere Threads besser zu machen, aber im Allgemeinen führt die Beibehaltung von Multi-Thread-Sicherheit zu den Kosten, da mehrere Threads um diese Sperren konkurrieren und den Fortschritt gegenseitig blockieren.
Die Antwort ist, dass es abhängt, die meisten der möglichen Langsamkeit kommt eher von malloc() und frei() in Kombination und in der Regel # 1 und # 2 werden von ähnlicher Geschwindigkeit sein.
Alle malloc() - Implementierungen verfügen über einen Indexierungsmechanismus, aber die Geschwindigkeit, mit der ein neuer Block zum Index hinzugefügt wird, hängt normalerweise nicht von der Anzahl der bereits im Index enthaltenen Blöcke ab.
meisten der Langsamkeit der malloc kommt aus zwei Quellen
mein Schreiben besitzen fast standardkonform malloc() ersatzwerkzeug malloc() & & kostenlos() mal von 35% auf 3-4%, und es hat diese beiden Faktoren ernsthaft optimiert. Es wäre wahrscheinlich eine ähnliche Geschwindigkeit gewesen, einen anderen leistungsstarken malloc zu verwenden, aber unsere eigenen waren portabler zu esoterischen Vorrichtungen und natürlich erlaubt frei, an einigen Stellen inlined zu sein.
Malloc muss eine verkettete Liste von freien Blöcken durchlaufen, um einen zu finden, der zugeordnet werden kann. Das braucht Zeit. Also, # 1 wird in der Regel langsamer sein:
Je öfter Sie anrufen malloc, desto mehr Zeit wird es dauern - so die Anzahl der Anrufe reduziert wird Ihnen eine Verbesserung der Geschwindigkeit (wenn auch, ob es von Bedeutung ist, hängt auf Ihre genauen Umstände).
Zusätzlich, wenn Sie viele kleine Blöcke malloc, dann, wie Sie diese Blöcke freigeben, werden Sie den Haufen viel mehr fragmentieren, als wenn Sie nur ein paar große Blöcke zuweisen und freigeben. Es ist also wahrscheinlich, dass Sie viele kleine freie Blöcke auf Ihrem Heap haben, anstatt ein paar große Blöcke, und daher müssen Ihre Mallocs möglicherweise weiter durch die Freiraumlisten suchen, um einen geeigneten Block für die Zuweisung zu finden. Was sie wieder langsamer machen wird.
+1 Heap-Fragmentierung kann Leistung töten, wenn Sie viele kleine Objekte auf dem Heap haben. – pjc50
In Bezug auf den ersten Aufzählungspunkt: Wie andere Antworten erwähnen, wenn Sie nur malloc (und nicht frei) aufrufen, dann wird die Zeit in einer Implementierung mit einer Liste von freien Blöcken konstant bleiben, was der übliche Fall zu sein scheint - mit gelegentlichen Schluckauf wenn Der Haufen muss wachsen. – hmijail
Mein Punkt war, dass das 100-malige Aufrufen einer Funktion den 100-fachen Overhead beim einmaligen Aufruf derselben Funktion verursacht. –
Sie gefragt 2 Fragen:
Sie haben angedeutet, dass sie die gleiche Frage, aber sie sind es nicht. Die Antwort auf die letzte Frage ist JA.
Für was wird schneller sein, ist es unmöglich zu sagen. Dies hängt vom Zuweisungsalgorithmus, vom Maschinenzustand, von 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 schrieb, die viele kleine Blobs des Gedächtnisses verwendete, jedes zugeteilt mit malloc(). Es funktionierte korrekt, war aber langsam. Ich ersetzte die vielen Aufrufe von malloc durch nur einen und schnitt dann den großen Block in meiner App auf. Es war viel viel schneller.
Ich empfehle diesen Ansatz nicht; Es ist nur eine Illustration des Punktes, an dem die Verwendung von malloc die Leistung wesentlich beeinflussen kann.
Mein Rat ist zu messen Sie es.
Es tut mir leid, eine alte Post, aber eine Frage zu stellen; Warum empfehlen Sie diesen Ansatz nicht? – Fingolfin
Ich empfehle es im Allgemeinen nicht.Ich empfehle, die Dinge einfach zu halten. YAGNI. Wenn Sie Leistungsprobleme bei der Speicherzuordnung feststellen, probieren Sie auf jeden Fall verschiedene Ansätze aus und messen Sie sie *. Aber die Speicherzuweisungsalgorithmen haben sich seit dem Auftreten dieses Problems erheblich verbessert. – Cheeso
Sie definieren nicht den relativen Unterschied zwischen "vielen" und "wenigen", aber ich vermute, dass die meisten Mallocs in beiden Szenarien fast identisch funktionieren würden. Die Frage impliziert, dass jeder Aufruf von malloc soviel Overhead hat wie ein Systemaufruf und eine Seitentabelle aktualisiert werden. Wenn Sie einen Malloc-Anruf ausführen, z. 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, so dass spätere Aufrufe nur 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 anrufe, wird der Aufwand in etwa gleich sein. Ich muss nur den größeren zugewiesenen Speicherblock selbst verwalten.
Sie können immer einen besseren Job mit malloc() tun, um einen großen Teil des Speichers zu reservieren 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 Zuweisung des Programms sein könnte.
Ob es eine gute Idee ist, einen eigenen Sub-Allocator zu implementieren, ist eine zweitrangige Frage. Es ist selten, explizite Speicherverwaltung ist bereits schwer genug. Sie benötigen selten eine weitere Codeebene, die Ihr Programm beschädigen und zum Absturz bringen kann, ohne dass Sie eine gute Möglichkeit haben, es zu debuggen. Es sei denn, Sie schreiben einen Debug-Allokator.
Das Zuweisen eines Speicherblocks ist schneller als das Zuweisen vieler Blöcke. Es gibt den Overhead des Systemaufrufs und auch die Suche nach verfügbaren Blöcken. Bei der Programmierung reduziert die Reduzierung der Anzahl der Operationen normalerweise die Ausführungszeit.
Speicherzuordner müssen möglicherweise suchen, um einen Speicherblock mit der richtigen Größe zu finden. Dies erhöht den Overhead der Ausführungszeit.
Bei der Zuweisung kleiner Speicherblöcke im Vergleich zu einem großen Block können jedoch bessere Erfolgschancen bestehen. Programmiert Ihr Programm einen kleinen Block und gibt es frei oder muss es kleine Blöcke zuweisen (und bewahren)? Wenn Speicher fragmentiert wird, sind weniger große Blöcke verfügbar, so dass der Speicherzuordner möglicherweise alle Blöcke zusammenfügen muss, um einen Block zu bilden, der groß genug für die Zuweisung ist.
Wenn Ihr Programm viele kleine Speicherblöcke zuweist und zerstört, sollten Sie vielleicht ein statisches Array zuweisen und dieses für Ihren Speicher verwenden.
Es tut (hat einen Index von zugewiesenen Standorten) - wie würde 'free' funktionieren sonst, aber das muss nicht den nächsten' malloc' Aufruf kleiner machen. Wenn eines der Programme viel freigegeben und freigegeben hat und eine Fragmentierung erzeugt, wird das den nächsten "malloc" -Ruf langsamer machen, da die freie Liste eine lange Kette von Blöcken sein wird, die meisten von ihnen zu klein. –
Eine Beobachtung ist, dass kleinere Speicherbausteine zu einem besseren Ansatz werden können, sobald die Speicherressourcen knapp werden. Es ist vielleicht einfacher, hier und da einen kleinen Block mit freiem Speicher zu finden, als irgendwo einen riesigen Block. Nicht sicher, wie dies die Leistung beeinflussen würde. –
Die malloc/free-Datenstruktur enthält normalerweise eine verknüpfte Liste von freien Blöcken und verfolgt normalerweise keine zugeordneten Blöcke. In der Regel werden den zugeordneten Daten Header vorangestellt. Bei free wird in der Kopfzeile nach der Größe der Zuordnung gesucht und dann zur verknüpften Liste der freien Blöcke hinzugefügt. Es gibt also eine Liste (aber keinen Index) von freien Blöcken und nichts, das die Zuweisungsblöcke verfolgt, außer dem Programmierer selbst. (Natürlich könnte eine malloc-Implementierung dies tun, und es könnte eine ziemlich gute Möglichkeit sein, Speicherlecks zu debuggen.) – benno