Benutzerdefinierte Heap-Allokatoren

Die meisten Programme können bei der Heap-Zuweisung recht beiläufig sein, selbst in dem Maße, in dem funktionale Programmiersprachen lieber neue Objekte zuweisen als alte zu ändern, und der Garbage Collector sich Gedanken über die Freigabe von Dingen machen lässt.

In der eingebetteten Programmierung, dem stillen Sektor, gibt es jedoch viele Anwendungen, in denen Sie die Heap-Zuweisung aufgrund von Speicher- und Echtzeitbeschränkungen überhaupt nicht verwenden können. Die Anzahl der Objekte jedes Typs, die behandelt werden, ist Teil der Spezifikation, und alles ist statisch zugeordnet.

Die Programmierung von Spielen (zumindest bei Spielen, bei denen es darum geht, die Hardware voranzutreiben) liegt manchmal dazwischen: Sie können die dynamische Zuordnung verwenden, aber es gibt genügend Speicher und weiche Echtzeitbeschränkungen, sodass Sie den Allokator nicht als Black Box behandeln können geschweige denn die Garbage Collection verwenden, sodass Sie benutzerdefinierte Allokatoren verwenden müssen. Dies ist einer der Gründe, warum C ++ in der Spielebranche immer noch weit verbreitet ist. Damit können Sie Dinge wie http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html tun

Welche anderen Domänen befinden sich in diesem Zwischengebiet? Wo werden neben Spielen häufig benutzerdefinierte Allokatoren verwendet?

Jedes Mal, wenn Sie eine Anwendung mit einem leistungsintensiven kritischen Pfad haben, sollten Sie sich Gedanken darüber machen, wie Sie mit dem Speicher umgehen. Die meisten clientseitigen Endbenutzeranwendungen fallen nicht in diese Kategorie, da sie primär ereignisgesteuert sind und die meisten Ereignisse aus Interaktionen mit dem Benutzer stammen und nicht so viele (wenn überhaupt) Leistungseinschränkungen bestehen.

Viele Back-End-Programme sollten sich jedoch darauf konzentrieren, wie der Speicher behandelt wird, da viele dieser Software skaliert werden können, um eine höhere Anzahl von Clients, eine größere Anzahl von Transaktionen und mehr Datenquellen zu verarbeiten. Sobald Sie beginnen Wenn Sie die Grenzen überschreiten, können Sie mit der Analyse des Arbeitsspeichers Ihrer Softwarebenutzer beginnen und benutzerdefinierte Zuordnungsschemata schreiben, die auf Ihre Software zugeschnitten sind, anstatt sich auf einen vollständig generischen Speicherzuweiser zu verlassen, der für jeden denkbaren Anwendungsfall geschrieben wurde.

Um nur einige Beispiele zu nennen ... In meiner ersten Firma habe ich an einem Historian-Paket gearbeitet, einer Software, die für das Sammeln / Speichern / Archivieren von Prozesssteuerungsdaten verantwortlich ist (denken Sie an eine Fabrik, ein Kernkraftwerk oder eine Ölraffinerie mit 10 Millionen Sensoren). wir würden diese Daten speichern). Jedes Mal, wenn wir einen Leistungsengpass analysierten, der den Historian daran hinderte, mehr Daten zu verarbeiten, lag das Problem meistens darin, wie der Speicher behandelt wurde. Wir haben große Anstrengungen unternommen, um sicherzustellen, dass malloc / free nicht aufgerufen wurden, es sei denn, sie waren absolut notwendig.

In meinem aktuellen Job arbeite ich an einem digitalen Überwachungsvideorecorder und einem Analysepaket. Bei 30 fps empfängt jeder Kanal alle 33 Millisekunden ein Videobild. Auf der von uns verkauften Hardware können wir problemlos 100 Videokanäle aufnehmen. Dies ist also ein weiterer Fall, um sicherzustellen, dass im kritischen Pfad (Netzwerkaufruf => Erfassungskomponenten => Rekorderverwaltungssoftware => Speicherkomponenten => Festplatte) keine dynamischen Speicherzuordnungen vorhanden sind. Wir haben einen benutzerdefinierten Frame-Allokator, der Puffer mit hoher Größe enthält und LIFO verwendet, um zuvor zugewiesene Puffer wiederzuverwenden. Wenn Sie 600 KB Speicher benötigen, erhalten Sie möglicherweise 1024 KB Puffer, der Speicherplatz verschwendet. Da dieser Speicher jedoch speziell auf unsere Verwendung zugeschnitten ist, bei der jede Zuordnung nur von kurzer Dauer ist, funktioniert er sehr gut, da der Puffer verwendet wird.

Bei der von mir beschriebenen Art von Anwendungen (Verschieben vieler Daten von A nach B und Behandeln einer großen Anzahl von Clientanforderungen) ist das Hin- und Herbewegen auf den Heap und zurück eine Hauptursache für CPU-Leistungsengpässe. Das Reduzieren der Heap-Fragmentierung auf ein Minimum ist ein sekundärer Vorteil. Soweit ich jedoch feststellen kann, implementieren die meisten modernen Betriebssysteme bereits Heaps mit geringer Fragmentierung (zumindest weiß ich, dass Windows dies tut, und ich würde hoffen, dass dies auch andere tun). Persönlich habe ich in mehr als 12 Jahren in solchen Umgebungen Probleme mit der CPU-Auslastung im Zusammenhang mit Heap gesehen, während ich noch nie ein System gesehen habe, das tatsächlich unter fragmentiertem Heap gelitten hat.

Videoverarbeitung, VFX, Betriebssysteme usw. Oft werden sie jedoch überbeansprucht. Die Datenstruktur und der Allokator müssen nicht getrennt werden, um eine effiziente Allokation zu erreichen.

Zum Beispiel bedeutet dies eine Menge zusätzlicher Komplexität, um die effiziente Zuweisung von Baumknoten in einem Octree vom Octree selbst zu trennen und sich auf einen externen Allokator zu verlassen. Es ist nicht unbedingt eine Verletzung von SRP, diese beiden Bedenken zusammenzuführen und es in die Verantwortung des Octree zu legen, viele Knoten gleichzeitig zusammenhängend zuzuweisen, da dies die Anzahl der Änderungsgründe nicht erhöht. Es kann praktisch gesehen es verringern.

In C ++, zum Beispiel, einer der verzögerten Nebenwirkungen von Standard - Containern mit stützt sich auf einem externen allocator hat verknüpften Strukturen wie std::mapund std::listfast nutzlos durch die C ++ Gemeinschaft betrachtet, da sie Benchmarking sie gegenstd::allocatorwährend diese Datenstrukturen jeweils einen Knoten zuweisen. Natürlich werden Ihre verknüpften Strukturen in diesem Fall eine schlechte Leistung erbringen, aber die Dinge wären so anders verlaufen, wenn die effiziente Zuweisung von Knoten für verknüpfte Strukturen eher als Verantwortung einer Datenstruktur als als Aufgabe eines Zuweisers angesehen worden wäre. Sie können aus anderen Gründen wie Speicherverfolgung / Profilerstellung weiterhin eine benutzerdefinierte Zuordnung verwenden. Wenn Sie sich jedoch darauf verlassen, dass der Zuweiser verknüpfte Strukturen effizient macht, während Sie versuchen, Knoten einzeln zuzuweisen, sind alle standardmäßig äußerst ineffizient. Das wäre in Ordnung, wenn es eine bekannte Einschränkung gäbe, dass verknüpfte Strukturen jetzt einen benutzerdefinierten Allokator wie eine freie Liste benötigen, um einigermaßen effizient zu sein und das Auslösen von Cache-Fehlern links und rechts zu vermeiden. Weitaus praktischer könnte so etwas gewesen seinstd::list<T, BlockSize, Alloc>, wobei BlockSizedie Anzahl der zusammenhängenden Knoten angegeben wird, die gleichzeitig für die freie Liste zugewiesen werden sollen (die Angabe von 1 würde effektiv dazu führen, std::listwie es jetzt ist).

Aber es gibt keine solche Einschränkung, die dann dazu führt, dass eine ganze Gemeinschaft von Dummköpfen ein Kult-Mantra wiederholt, dass verknüpfte Listen nutzlos sind, z

Ein weiterer Bereich, in dem Sie möglicherweise einen benutzerdefinierten Allokator benötigen, besteht darin, die Heap-Fragmentierung zu verhindern . Im Laufe der Zeit kann Ihr Heap kleine Objekte zuordnen, die im gesamten Heap fragmentiert sind. Wenn Ihr Programm den Heapspeicher nicht zusammenhalten kann und Ihr Programm ein größeres Objekt zuweisen soll, muss es mehr Speicher vom System beanspruchen, da es keinen freien Block zwischen Ihrem vorhandenen, fragmentierten Heap finden kann (zu viele kleine) Objekte sind im Weg). Die Gesamtspeicherauslastung Ihres Programms nimmt mit der Zeit zu und Sie verbrauchen unnötig zusätzliche Speicherseiten. Dies ist also ein ziemlich großes Problem für Programme, von denen erwartet wird, dass sie über einen längeren Zeitraum ausgeführt werden (denken Sie an Datenbanken, Server usw. usw.).

Wo werden neben Spielen häufig benutzerdefinierte Allokatoren verwendet?

Facebook

Schauen Sie sich jemalloc an , mit dem Facebook seine Heap-Leistung verbessert und die Fragmentierung verringert.