Ihre eigene malloc-Funktion machen?

Question

Ich habe gelesen, dass einige Spiele ihren eigenen malloc umschreiben, um effizienter zu sein. Ich verstehe nicht, wie das in einer virtuellen Speicherwelt möglich ist. Wenn ich mich richtig erinnere, ruft malloc tatsächlich eine OS-spezifische Funktion auf, die die virtuelle Adresse einer realen Adresse mit der MMU zuordnet. Wie kann also jemand seinen eigenen Speicherzuordner erstellen und echten Speicher zuweisen, ohne den malloc der tatsächlichen Laufzeit aufzurufen?

Dank

Answer 1

Es ist sicherlich möglich, einen Zuweiser effizienter als einen allgemeinen zu schreiben.

Wenn Sie die Eigenschaften Ihrer Zuordnungen kennen, können Sie allgemeine Zuweiser aus dem Wasser blasen.

Fallbeispiel: Vor vielen Jahren mussten wir ein Kommunikationssubsystem (HDLC, X.25 und proprietäre Schichten) für Embedded-Systeme entwerfen und codieren. Die Tatsache, dass wir wussten, dass die maximale Zuweisung immer weniger als 128 Bytes (oder etwas Ähnliches) betragen würde, bedeutete, dass wir uns nicht mit Blöcken von variabler Größe herumschlagen mussten. Jede Zuordnung war für 128 Bytes egal wie viel Sie gefragt haben.

Natürlich, wenn Sie nach mehr gefragt haben, gab es NULL zurück.

Durch die Verwendung von Blöcken fester Länge konnten wir Zuweisungen und De-Zuweisungen erheblich beschleunigen, indem wir Bitmaps und zugehörige Strukturen für Abrechnungsinformationen verwendeten, anstatt sich auf langsamere verknüpfte Listen zu verlassen. Darüber hinaus wurde die Notwendigkeit, freigegebene Blöcke zu vereinigen, nicht benötigt.

Zugegeben, dies war ein spezieller Fall, aber Sie werden feststellen, dass das auch für Spiele so ist. Tatsächlich haben wir dies sogar in einem System für allgemeine Zwecke verwendet, bei dem Zuteilungen unterhalb eines bestimmten Schwellenwerts eine festgelegte Menge an Speicher aus einem selbstverwalteten vorab zugewiesenen Pool erhielten, der auf die gleiche Weise ausgeführt wurde. Alle anderen Zuordnungen (größer als der Schwellenwert oder wenn der Pool vollständig zugewiesen wurde) wurden an die "echte" malloc gesendet.

Answer 2

Eine Sache, die Sie Ihr allocator einen Pool von Speicher zuweisen müssen tun, dann Service-Anfragen aus als (und einen größeren Pool zuzuweisen, wenn es zu Ende geht). Ich bin mir nicht sicher, ob sie das tun.

Answer 3

Siehe How do games like GTA IV not fragment the heap?.

Answer 4

Nur weil malloc() eine Standard-C-Funktion ist, bedeutet das nicht, dass es der niedrigste Zugriff ist, den Sie auf das Speichersystem haben. In der Tat wird malloc() wahrscheinlich in Bezug auf Betriebssystemfunktionen auf niedrigerer Ebene implementiert. Das heißt, Sie könnten diese untergeordneten Schnittstellen auch aufrufen. Sie sind möglicherweise betriebssystemspezifisch, ermöglichen jedoch möglicherweise eine bessere Leistung als die Schnittstelle malloc(). Wenn das der Fall wäre, könnten Sie Ihr eigenes Speicherzuweisungssystem nach Belieben implementieren und vielleicht sogar noch effizienter sein - zum Beispiel durch die Optimierung des Algorithmus für die Merkmale der Größe und Häufigkeit der Zuweisungen, die Sie vornehmen .

Answer 5

Im Allgemeinen ruft malloc eine OS-spezifische Funktion auf, um eine Menge Speicher (mindestens eine VM-Seite) zu erhalten, und teilt diesen Speicher dann in kleinere Teile auf, um zum Aufrufer von malloc zurückzukehren.

Die Malloc-Bibliothek wird auch eine Liste (oder Listen) von freien Blöcken haben, so dass sie oft eine Anfrage erfüllen kann, ohne das Betriebssystem nach mehr Speicher zu fragen. Die Entscheidung, wie viele unterschiedliche Blockgrößen zu handhaben sind, ob Sie versuchen, benachbarte freie Blöcke zu kombinieren usw., sind die Möglichkeiten, die der malloc-Bibliotheksimplementierer ausführen muss.

Es ist möglich, dass Sie die malloc-Bibliothek umgehen und direkt die Betriebssystem-Ebene "gib mir etwas Speicher" -Funktion aufrufen und Ihre eigene Zuweisung/Freigabe innerhalb des vom Betriebssystem erhaltenen Speichers vornehmen. Solche Implementierungen sind wahrscheinlich betriebssystemspezifisch. Eine andere Alternative ist die Verwendung von malloc für anfängliche Zuordnungen, aber Sie behalten Ihren eigenen Cache von freigegebenen Objekten.

Answer 6

Wenn ich mich richtig erinnere, malloc tatsächlich ruft eine OS-spezifische Funktion

Nicht ganz. Die meiste Hardware hat eine Seitengröße von 4 KB. Betriebssysteme stellen im Allgemeinen keine Speicherzuweisungsschnittstelle bereit, die etwas anbietet, das kleiner ist als seitengroße (und seitenausgerichtete) Blöcke.

malloc den größten Teil seiner Zeit damit verbringt, den virtuellen Speicherplatz verwalten, die bereits zugeordnet wurde, und nur fordert gelegentlich mehr Speicher vom Betriebssystem (natürlich hängt dies von der Größe der Elemente, die Sie zuteilen und wie oft Sie free).

Es gibt ein häufiges Missverständnis, dass wenn Sie free etwas ist es sofort an das Betriebssystem zurückgegeben wird. Während dies manchmal auftritt (insbesondere bei größeren Speicherblöcken), ist es im Allgemeinen der Fall, dass der Speicher dem Prozess zugewiesen bleibt und dann später von malloc s erneut verwendet werden kann.

So ist die meiste Arbeit in der Buchhaltung von bereits zugewiesenen virtuellen Raum. Zuweisungsstrategien können viele Ziele haben, wie beispielsweise eine schnelle Operation, eine geringe Speicherverschwendung, eine gute Lokalität, Platz für dynamisches Wachstum (z. B. realloc) und so weiter.

Wenn Sie mehr über Ihr Muster der Speicherzuweisung und -freigabe wissen, können Sie malloc und free für Ihre Nutzungsmuster optimieren oder eine umfangreichere Schnittstelle bereitstellen.

Zum Beispiel können Sie viele gleich große Objekte zuweisen, die die optimalen Zuordnungsparameter ändern können. Oder Sie können immer große Mengen von Objekten auf einmal freigeben. In diesem Fall sollten Sie keine ausgefallenen Dinge tun.

Werfen Sie einen Blick auf memory pools und obstacks.