Die Demonstration der Speicherbereinigung ist schneller als die manuelle Speicherverwaltung

23

Ich habe an vielen Orten gelesen (heck, ich habe auch so selbst geschrieben) , dass die Garbage Collection könnte (theoretisch) schneller als die manuelle Speicherverwaltung.

Es ist jedoch viel schwieriger, das zu zeigen, als es zu erzählen.
Ich habe eigentlich nie gesehen jedes Stück Code, der diesen Effekt in Aktion zeigt.

Hat jemand Code (oder weiß, wo ich ihn finden kann), der diesen Leistungsvorteil demonstriert?

Mehrdad
quelle
5
Das Problem mit GC ist, dass die meisten Implementierungen nicht deterministisch sind, so dass 2 Läufe sehr unterschiedliche Ergebnisse haben können, ganz zu schweigen davon, dass es schwierig ist, die richtigen Vergleichsvariablen zu isolieren
Ratschenfreak
@ratchetfreak: Wenn Sie Beispiele kennen, die in 70% der Fälle nur schneller sind, ist das auch für mich in Ordnung. Zumindest im Hinblick auf den Durchsatz muss es eine Möglichkeit geben, die beiden zu vergleichen (die Latenz würde wahrscheinlich nicht funktionieren).
Mehrdad
1
Nun, das ist etwas knifflig, da Sie immer manuell tun können, was dem GC einen Vorteil gegenüber dem gibt, was Sie manuell getan haben. Vielleicht ist es besser, dies auf "Standard" -Tools für die manuelle Speicherverwaltung zu beschränken (malloc () / free (), eigene Zeiger, gemeinsame Zeiger mit refcount, schwache Zeiger, keine benutzerdefinierten Zuweiser)? Wenn Sie benutzerdefinierte Allokatoren zulassen (die je nach Art des von Ihnen angenommenen Programmierers realistischer oder weniger realistisch sind), können Sie den Aufwand für diese Allokatoren einschränken. Ansonsten ist die manuelle Strategie "Kopieren, was der GC in diesem Fall tut" immer mindestens so schnell wie der GC.
1
Mit "Kopieren, was der GC tut" meine ich nicht "Erstellen Sie Ihren eigenen GC" (obwohl zu beachten ist, dass dies theoretisch in C ++ 11 und höher möglich ist, was eine optionale Unterstützung für einen GC einführt ). Ich meinte, wie ich es bereits in demselben Kommentar formuliert habe: "Mach, was dem GC einen Vorteil gegenüber dem gibt, was du manuell gemacht hast." Wenn beispielsweise die Cheney-ähnliche Komprimierung dieser Anwendung sehr hilft, können Sie manuell ein ähnliches Zuordnungs- und Komprimierungsschema mit benutzerdefinierten intelligenten Zeigern für die Zeigerkorrektur implementieren. Mit Techniken wie einem Schattenstapel können Sie außerdem in C oder C ++ auf Kosten zusätzlicher Arbeit nach Roots suchen.
1
@ Ike: Ist schon okay. Sehen Sie, warum ich die Frage gestellt habe? Das war der springende Punkt meiner Frage - die Leute finden alle möglichen Erklärungen, die Sinn machen sollten , aber jeder stolpert, wenn man sie auffordert, eine Demonstration zu liefern, die beweist, dass das, was sie sagen, in der Praxis richtig ist. Der springende Punkt dieser Frage war, ein für allemal zu zeigen, dass dies tatsächlich in der Praxis geschehen kann.
Mehrdad

Antworten:

26

Besuchen Sie http://blogs.msdn.com/b/ricom/archive/2005/05/10/416151.aspx und folgen Sie allen Links, um zu sehen, wie Rico Mariani und Raymond Chen (beide sehr kompetente Programmierer bei Microsoft) gegeneinander antreten . Raymond würde den nicht verwalteten verbessern, Rico würde darauf reagieren, indem er das Gleiche bei den verwalteten optimiert.

Mit im Wesentlichen null Optimierungsaufwand begannen die verwalteten Versionen um ein Vielfaches schneller als das Handbuch. Irgendwann schlug das Handbuch die gemanagten, aber nur durch die Optimierung auf ein Niveau, auf das die meisten Programmierer nicht mehr wollen würden. In allen Versionen war die Speichernutzung des Handbuchs deutlich besser als die des verwalteten.

btilly
quelle
+1 für das Zitieren eines tatsächlichen Beispiels mit Code :) obwohl die ordnungsgemäße Verwendung von C ++ - Konstrukten (wie swap) nicht so schwierig ist und Sie wahrscheinlich in Bezug auf die Leistung recht einfach dahin bringen würde ...
Mehrdad
5
Möglicherweise können Sie Raymond Chen bei der Leistung übertreffen. Ich bin zuversichtlich, dass ich es nicht kann, wenn er nicht krank ist. Ich arbeite viel härter und habe Glück. Ich weiß nicht, warum er nicht die Lösung gewählt hat, die Sie gewählt hätten. Ich bin sicher, er hatte Gründe dafür
btilly
Ich habe hier den Code von Raymond kopiert und zum Vergleich hier meine eigene Version geschrieben . Die ZIP-Datei, die die Textdatei enthält, befindet sich hier . Auf meinem Computer läuft meine in 14 ms und die von Raymond in 21 ms. Sofern ich nichts falsch gemacht habe (was möglich ist), ist sein 215-Zeilen-Code 50% langsamer als meine 48-Zeilen-Implementierung, auch ohne die Verwendung von Speicherzuordnungsdateien oder benutzerdefinierten Speicherpools (die er verwendet hat). Meins ist halb so lang wie die C # -Version. Habe ich es falsch gemacht oder beobachtest du dasselbe?
Mehrdad
1
@Mehrdad Eine alte Kopie von gcc auf diesem Laptop rausholen Ich kann berichten, dass weder Ihr Code noch sein Code kompiliert werden, geschweige denn irgendetwas damit zu tun. Die Tatsache, dass ich nicht auf Windows bin, erklärt das wahrscheinlich. Nehmen wir jedoch an, dass Ihre Zahlen und Ihr Code korrekt sind. Führen sie dasselbe auf einem zehn Jahre alten Compiler und Computer durch? (Schau dir an, wann der Blog geschrieben wurde.) Vielleicht, vielleicht auch nicht. Nehmen wir an, dass dies der Fall ist, dass er (als C-Programmierer) nicht wusste, wie man C ++ richtig verwendet usw. Was bleibt uns übrig?
btilly
1
Wir haben ein vernünftiges C ++ - Programm, das in verwalteten Speicher übersetzt und beschleunigt werden kann. Aber wo kann die C ++ - Version optimiert und weiter beschleunigt werden. Wir sind uns alle einig: Das allgemeine Muster, das immer dann auftritt, wenn verwalteter Code schneller ist als nicht verwalteter. Wir haben jedoch immer noch ein konkretes Beispiel für vernünftigen Code von einem guten Programmierer, der in einer verwalteten Version schneller war.
btilly
5

Als Faustregel gilt, dass es keine kostenlosen Mittagessen gibt.

GC nimmt den Kopfschmerzen der manuellen Speicherverwaltung und verringert die Wahrscheinlichkeit, Fehler zu machen. In einigen Situationen ist eine bestimmte GC-Strategie die optimale Lösung für das Problem. In diesem Fall zahlen Sie keine Strafe für die Verwendung. Aber es gibt andere, bei denen andere Lösungen schneller sind. Da Sie immer höhere Abstraktionen von einer niedrigeren Ebene simulieren können, aber nicht umgekehrt, können Sie effektiv beweisen, dass höhere Abstraktionen auf keinen Fall schneller sein können als niedrigere im Allgemeinen.

GC ist ein Spezialfall der manuellen Speicherverwaltung

Es kann eine Menge Arbeit oder mehr Fehler sein, manuell eine bessere Leistung zu erzielen, aber das ist eine andere Geschichte.

Guy Sirton
quelle
1
Das ergibt für mich keinen Sinn. Um Ihnen ein paar konkrete Beispiele zu geben: 1) Die Allokatoren und Schreibbarrieren in Produktions-GCs sind handgeschriebene Assembler, weil C zu ineffizient ist In höheren (funktionalen) Sprachen ausgeführt, die nicht vom C-Compiler ausgeführt werden und daher nicht in C ausgeführt werden können. Stack-Walking ist ein weiteres Beispiel für etwas, das von höheren Sprachen unterhalb der C-Ebene ausgeführt wird.
Jon Harrop
2
1) Ich würde den spezifischen Code sehen müssen, um zu kommentieren, aber wenn die handgeschriebenen Allokatoren / Barrieren in Assembler schneller sind, dann benutze handgeschriebenen Assembler. Ich bin nicht sicher, was das mit GC zu tun hat. 2) Sehen Sie sich das hier an: stackoverflow.com/a/9814654/441099 Es geht nicht darum, ob eine Nicht-GC-Sprache die Tail-Rekursion für Sie eliminieren kann. Der Punkt ist, dass Sie Ihren Code so schnell oder schneller umwandeln können. Ob der Compiler einer bestimmten Sprache dies automatisch für Sie erledigen kann, ist eine Frage der Bequemlichkeit. In einer ausreichend niedrigen Abstraktion können Sie dies jederzeit selbst tun, wenn Sie dies wünschen.
Guy Sirton
1
Dieses Tail-Call-Beispiel in C funktioniert nur für den Spezialfall einer Funktion, die sich selbst aufruft. C kann den allgemeinen Fall von Funktionen, die sich gegenseitig aufrufen, nicht verarbeiten. Zu einem Assembler zu fallen und eine unendliche Zeit für die Entwicklung anzunehmen, ist eine Tarpit von Turing.
Jon Harrop
3

Es ist einfach, eine künstliche Situation zu konstruieren, in der GC unendlich effizienter ist als manuelle Methoden. Stellen Sie einfach sicher, dass es nur eine "Wurzel" für den Garbage Collector gibt und dass alles Garbage ist, sodass der GC-Schritt sofort abgeschlossen ist.

Wenn Sie darüber nachdenken, ist dies das Modell, das beim Sammeln des Speichers verwendet wird, der einem Prozess zugeordnet ist. Der Prozess stirbt, alles, was es an Speicher gibt, ist Müll, wir sind fertig. Selbst in der Praxis ist ein Prozess, der startet, läuft und stirbt und keine Spur hinterlässt, möglicherweise effizienter als ein Prozess, der für immer startet und läuft.

Bei praktischen Programmen, die in Sprachen mit Garbage Collection geschrieben sind, liegt der Vorteil der Garbage Collection nicht in der Geschwindigkeit, sondern in der Korrektheit und Einfachheit.

ddyer
quelle
Wenn es einfach ist, ein künstliches Beispiel zu konstruieren, würde es Ihnen etwas ausmachen, ein einfaches zu zeigen?
Mehrdad
1
@Mehrdad Er hat ein einfaches erklärt. Schreiben Sie ein Programm, in dem die GC-Version vor dem Beenden keinen Garbage Run ausführt. Die manuelle speicherverwaltete Version wird langsamer sein, da sie explizit Dinge verfolgt und freigibt.
btilly
3
@btilly: "Schreiben Sie ein Programm, in dem die GC-Version vor dem Beenden keinen Garbage Run ausführt." ... die Speicherbereinigung überhaupt nicht durchzuführen ist ein Speicherverlust, der auf das Fehlen eines funktionierenden GC zurückzuführen ist, und keine Leistungsverbesserung, die auf das Vorhandensein eines GC zurückzuführen ist! Das ist, als würde man abort()C ++ aufrufen, bevor das Programm beendet wird. Es ist ein sinnloser Vergleich; Sie sammeln nicht einmal Müll, sondern lassen nur den Speicher auslaufen. Man kann nicht sagen, dass die Müllabfuhr schneller (oder langsamer) ist, wenn man nicht zuerst Müll sammelt ...
Mehrdad
Um ein extremes Beispiel zu geben, müssten Sie ein komplettes System mit Ihrem eigenen Heap und Heap-Management definieren. Dies wäre ein großartiges Studentenprojekt, aber zu groß, um in diesen Spielraum zu passen. Sie würden es ziemlich gut machen, wenn Sie ein Programm schreiben, das Arrays mit zufälliger Größe auf eine Weise zuweist und freigibt, die für Speicherverwaltungsmethoden ohne GC-Unterstützung stressig ist.
4.
3
@Mehrdad Nicht so. Das Szenario sieht so aus, dass die GC-Version niemals den Schwellenwert erreicht hat, ab dem sie einen Durchlauf durchgeführt hätte, und nicht, dass die ordnungsgemäße Ausführung für einen anderen Datensatz fehlgeschlagen wäre. Das wird für die GC-Version trivial sehr gut, ist aber kein guter Prädiktor für die spätere Leistung.
btilly
2

Es sollte berücksichtigt werden, dass GC nicht nur eine Speichermanagementstrategie ist. Es stellt auch Anforderungen an das gesamte Design der Sprache und der Laufzeitumgebung, die Kosten (und Nutzen) verursachen. Beispielsweise muss eine Sprache, die GC unterstützt, in eine Form kompiliert werden, in der Zeiger nicht vor dem Garbage Collector verborgen werden können und die im Allgemeinen nur von sorgfältig verwalteten Systemprimitiven erstellt werden kann. Ein weiterer Gesichtspunkt ist die Schwierigkeit, die Garantien für die Reaktionszeit einzuhalten, da GC einige Schritte auferlegt, die ausgeführt werden müssen, um vollständig zu sein.

Wenn Sie also eine Sprache haben, in der Datenmüll gesammelt wird, und die Geschwindigkeit mit manuell verwaltetem Speicher im selben System vergleichen, müssen Sie den Aufwand für die Unterstützung der Datenmüllsammlung auch dann bezahlen, wenn Sie sie nicht verwenden.

ddyer
quelle
2

Schneller ist zweifelhaft. Es kann jedoch ultraschnell, nicht wahrnehmbar oder schneller sein, wenn es von der Hardware unterstützt wird. Es gab schon vor langer Zeit solche Designs für LISP-Maschinen. Man baute den GC in das Speichersubsystem der Hardware ein, so dass die Haupt-CPU nicht wusste, dass es dort war. Wie viele spätere Designs wurde der GC gleichzeitig mit dem Hauptprozessor ausgeführt, ohne dass Pausen erforderlich waren. Ein moderneres Design sind Vega 3-Maschinen von Azul Systems, auf denen Java-Code viel schneller ausgeführt wird als bei JVMs, die speziell entwickelte Prozessoren und einen pausenlosen GC verwenden. Google sie, wenn Sie wissen möchten, wie schnell GC (oder Java) sein kann.

Nick P
quelle
2

Ich habe ziemlich viel daran gearbeitet und einige davon hier beschrieben . Ich habe den Böhm-GC in C ++ verglichen, indem ich ihn zugewiesen, mallocaber nicht freigegeben, zugewiesen und freigegeben habe, freeund einen in C ++ geschriebenen, benutzerdefinierten Markierungsbereich-GC, der alle mit dem OCaml-Aktien-GC verglichen wurde, auf dem ein listenbasierter n-Königinnen-Löser ausgeführt wird. Die GC von OCaml war in allen Fällen schneller. Die Programme C ++ und OCaml wurden absichtlich so geschrieben, dass dieselben Zuweisungen in derselben Reihenfolge ausgeführt werden.

Sie können die Programme natürlich neu schreiben, um das Problem zu lösen, indem Sie nur 64-Bit-Ganzzahlen und keine Zuordnungen verwenden. Obwohl schneller, würde das den Punkt der Übung zunichte machen (was die Leistung eines neuen GC-Algorithmus vorhersagen sollte, an dem ich mit einem in C ++ erstellten Prototyp gearbeitet habe).

Ich habe viele Jahre in der Industrie verbracht, um echten C ++ - Code auf verwaltete Sprachen zu portieren. In fast jedem Einzelfall stellte ich erhebliche Leistungsverbesserungen fest, von denen viele wahrscheinlich auf die manuelle Speicherverwaltung durch GC zurückzuführen waren. Die praktische Einschränkung ist nicht, was mit einem Mikrobenchmark erreicht werden kann, sondern was vor Ablauf einer Frist erreicht werden kann und GC-basierte Sprachen bieten so große Produktivitätsverbesserungen, dass ich nie zurückblickte. Ich benutze immer noch C und C ++ auf eingebetteten Geräten (Mikrocontrollern), aber selbst das ändert sich jetzt.

Jon Harrop
quelle
+1 danke. Wo können wir den Benchmark-Code sehen und ausführen?
Mehrdad
Der Code ist über den Ort verstreut. Ich habe die Version für die Markenregion hier veröffentlicht: groups.google.com/d/msg/…
Jon Harrop
1
Es gibt Ergebnisse für sowohl threadsicher als auch unsicher.
Jon Harrop
1
@Mehrdad: "Haben Sie solche potenziellen Fehlerquellen beseitigt?" Ja. OCaml verfügt über ein sehr einfaches Kompilierungsmodell ohne Optimierungen wie die Escape-Analyse. OCamls Darstellung des Verschlusses ist tatsächlich wesentlich langsamer als die der C ++ - Lösung, daher sollte tatsächlich eine benutzerdefinierte Darstellung verwendet werden, List.filterwie dies bei C ++ der Fall ist. Aber ja, Sie haben mit Sicherheit recht, dass einige RC-Operationen vermieden werden können. Das größte Problem, das ich in der Natur sehe, ist jedoch, dass die Leute nicht die Zeit haben, solche Optimierungen von Hand auf großen industriellen Codebasen durchzuführen.
Jon Harrop
2
Ja absolut. Kein zusätzlicher Aufwand zum Schreiben, aber das Schreiben von Code ist nicht der Engpass mit C ++. Pflegecode ist. Das Verwalten von Code mit dieser Art von zufälliger Komplexität ist ein Albtraum. Die meisten industriellen Codebasen bestehen aus Millionen von Codezeilen. Damit willst du dich einfach nicht auseinandersetzen müssen. Ich habe gesehen, wie Leute alles in shared_ptrnur umwandelten , um Parallelitätsfehler zu beheben. Der Code ist viel langsamer, aber jetzt funktioniert er.
Jon Harrop
-1

Ein solches Beispiel weist notwendigerweise ein schlechtes manuelles Speicherzuweisungsschema auf.

Nimm den besten Müllsammler an GC. Intern gibt es Methoden, um Speicher zuzuweisen, zu bestimmen, welcher Speicher freigegeben werden kann, und Methoden, um ihn endgültig freizugeben. Zusammen nehmen diese weniger Zeit in Anspruch als alle anderen GC; einige Zeit wird in den anderen Methoden der verbracht GC.

Stellen Sie sich nun einen manuellen Zuweiser vor, der denselben Zuweisungsmechanismus wie verwendet GCund dessen free()Aufruf nur den Speicher freigibt, der nach derselben Methode wie freigegeben werden soll GC. Es gibt weder eine Scan-Phase noch eine der anderen Methoden. Es dauert notwendigerweise weniger Zeit.

MSalters
quelle
2
Ein Garbage-Collector kann oft viele Objekte freigeben, ohne dass der Speicher nach jedem in einen nützlichen Zustand versetzt werden muss. Betrachten Sie die Aufgabe, alle Elemente, die ein bestimmtes Kriterium erfüllen, aus einer Array-Liste zu entfernen. Das Entfernen eines einzelnen Elements aus einer N-Element-Liste ist O (N); Entfernen von M Elementen aus einer Liste von N, eins zu einem Zeitpunkt ist O (M * N). Das Entfernen aller Elemente, die ein Kriterium erfüllen, in einem einzigen Durchgang durch die Liste ist jedoch O (1).
Superkatze
@supercat: freeKann auch Chargen sammeln. (Und natürlich ist das Entfernen aller Elemente, die ein Kriterium erfüllen, immer noch O (N), wenn auch nur aufgrund der
Listenüberquerung
Das Entfernen aller Elemente, die ein Kriterium erfüllen, ist mindestens O (N). Sie haben Recht, dass freein einem Batch-Collect-Modus gearbeitet werden könnte, wenn jedem Speicherelement ein Flag zugeordnet wäre, obwohl GC in einigen Situationen immer noch die Nase vorn haben kann. Wenn man M Referenzen hat, die L verschiedene Elemente aus einer Menge von N Dingen identifizieren, ist die Zeit, um jede Referenz, auf die keine Referenz existiert, zu entfernen und den Rest zu konsolidieren, O (M) und nicht O (N). Wenn man M zusätzlichen Platz zur Verfügung hat, kann die Skalierungskonstante ziemlich klein sein. Außerdem erfordert die Kompaktifizierung in einem Nicht-Scan-GC-System ...
supercat
@supercat: Nun, es ist sicherlich nicht O (1), wie dein letzter Satz im ersten Kommentar besagt.
MSalters
1
@MSalters: "Und was würde ein deterministisches Schema daran hindern, einen Kindergarten zu haben?" Nichts. OCamls Tracing-Garbage-Collector ist deterministisch und verwendet einen Kindergarten. Aber es ist nicht "manuell" und ich denke, Sie missbrauchen das Wort "deterministisch".
Jon Harrop