Zu GC oder nicht zu GC

70

Ich habe kürzlich zwei wirklich nette und lehrreiche Sprachgespräche gesehen:

Diese erste von Herb Sutter zeigt alle netten und coolen Funktionen von C ++ 0x, warum die Zukunft von C ++ besser als je zuvor erscheint und wie M $ in diesem Spiel als guter Kerl gilt. Der Vortrag dreht sich um Effizienz und wie die Minimierung der Heap-Aktivität sehr oft die Leistung verbessert.

Das andere , von Andrei Alexandrescu, motiviert einen Übergang von C / C ++ zu seinem neuen Spiel-Wechsler D . Die meisten Sachen von D scheinen wirklich gut motiviert und gestaltet zu sein. Eines hat mich jedoch überrascht, nämlich dass D auf Garbage Collection drängt und dass alle Klassen nur durch Referenz erstellt werden . Noch verwirrender ist, dass das Buch The D Programming Language Ref Manual speziell im Abschnitt über Ressourcenmanagement Folgendes zitiert:

Durch die Speicherbereinigung entfällt der mühsame, fehleranfällige Speicherzuordnungs-Tracking-Code, der in C und C ++ erforderlich ist. Dies bedeutet nicht nur eine viel schnellere Entwicklungszeit und geringere Wartungskosten, sondern das resultierende Programm läuft häufig schneller !

Dies steht im Widerspruch zu Sutters ständigem Gerede über die Minimierung der Heap-Aktivität. Ich respektiere sowohl Sutters als auch Alexandrescous Erkenntnisse sehr und bin daher etwas verwirrt über diese beiden Schlüsselfragen

  1. Führt das Erstellen von Klasseninstanzen nicht nur als Referenz zu einer Menge unnötiger Heap-Aktivitäten?

  2. In welchen Fällen können wir die Garbage Collection verwenden, ohne die Laufzeitleistung zu beeinträchtigen?

Nordlöw
quelle
2
Natürlich meinst du " Objekte erstellen " :)
xtofl
6
7 Upvotes und 3 Close Votes. Dies ist aus meiner Sicht eine großartige Frage! Kümmer dich nicht darum!
David Heffernan
1
Ich muss zugeben, ich bin ein wenig abgeneigt gegenüber dem Kerl, der sagt, M $ sei ein guter Kerl :)
Tom Zych
14
Es ist eine religiöse Frage, denn die einfache Antwort lautet "Gib Affen niemals Atomwaffen". Die Speicherverwaltung sollte in 98% der Fälle automatisch erfolgen (ich habe gerade eine Zahl gezogen), für andere 2% gibt es immer noch C ++.
c69
7
@ c69 Dies ist eine Frage für die anderen 2%. Dürfen wir keine Fragen stellen?
David Heffernan

Antworten:

45

So beantworten Sie Ihre beiden Fragen direkt:

  1. Ja, das Erstellen von Klasseninstanzen als Referenz führt zu einer Menge Heap-Aktivität, aber :

    ein. In D haben Sie structebenso wie class. A structhat Wertesemantik und kann alles, was eine Klasse kann, außer Polymorphismus.

    b. Polymorphismus und Wertesemantik haben aufgrund des Schnittproblems nie gut zusammengearbeitet .

    c. Wenn Sie in D wirklich eine Klasseninstanz auf dem Stapel in einem leistungskritischen Code zuweisen müssen und sich nicht um den Sicherheitsverlust kümmern, können Sie dies über die scopedFunktion ohne unangemessenen Aufwand tun .

  2. GC kann mit der manuellen Speicherverwaltung vergleichbar oder schneller sein, wenn:

    ein. Sie ordnen den Stapel nach Möglichkeit weiterhin zu (wie dies normalerweise in D der Fall ist), anstatt sich bei allem auf den Heap zu verlassen (wie dies häufig in anderen GC-Sprachen der Fall ist).

    b. Sie haben einen erstklassigen Garbage Collector (Ds aktuelle GC-Implementierung ist zugegebenermaßen etwas naiv, obwohl in den letzten Versionen einige wichtige Optimierungen vorgenommen wurden, sodass sie nicht so schlecht ist wie sie war).

    c. Sie weisen hauptsächlich kleine Objekte zu. Wenn Sie hauptsächlich große Arrays zuweisen und die Leistung ein Problem darstellt, möchten Sie möglicherweise einige davon auf den C-Heap umstellen (Sie haben Zugriff auf Cs Malloc und frei in D) oder, wenn er eine bestimmte Lebensdauer hat, auf einen anderen Allokator wie RegionAllocator . (RegionAllocator wird derzeit diskutiert und verfeinert, um schließlich in die Standardbibliothek von D aufgenommen zu werden.)

    d. Die Raumeffizienz ist Ihnen nicht so wichtig. Wenn Sie den GC zu häufig ausführen, um den Speicherbedarf extrem gering zu halten, leidet die Leistung.

Dsimcha
quelle
22

Der Grund, warum das Erstellen eines Objekts auf dem Heap langsamer ist als das Erstellen auf dem Stapel, besteht darin, dass die Speicherzuweisungsmethoden beispielsweise die Heap-Fragmentierung berücksichtigen müssen. Das Zuweisen von Speicher auf dem Stapel ist so einfach wie das Inkrementieren des Stapelzeigers (eine Operation mit konstanter Zeit).

Mit einem komprimierenden Garbage Collector müssen Sie sich jedoch keine Gedanken über die Heap-Fragmentierung machen. Die Heap-Zuweisungen können so schnell sein wie die Stack-Zuweisungen. Auf der Seite Garbage Collection für die Programmiersprache D wird dies ausführlicher erläutert.

Die Behauptung, dass GC-Sprachen schneller ausgeführt werden, geht wahrscheinlich davon aus, dass viele Programme viel häufiger Speicher auf dem Heap zuweisen als auf dem Stapel. Angenommen, die Heap-Zuweisung könnte in einer GC-Sprache schneller sein, dann haben Sie gerade einen großen Teil der meisten Programme optimiert (Heap-Zuweisung).

Jack Edmonds
quelle
Aha! Sehr interessant. Ich werde das untersuchen. Vielen Dank!
Nordlöw
Es geht darum, das Standardverhalten der Sprache an den durchschnittlichen Anwendungsfall anzupassen (zu optimieren), oder? Das bedeutet nicht, dass einige Algorithmen bei ausgeschaltetem GC immer noch eine bessere Leistung erbringen, was D übrigens unterstützt. Meiner Meinung nach sollte dieser flexible Ansatz mehr Menschen zufrieden stellen.
Nordlöw
8
GCs sind ineffizient, ebenso wie die falsche Verwendung von malloc. Das Verwalten Ihres Speichers durch Dinge wie Speicherpools wird viel schneller sein als ein GC.
Pubby
7
@Pubby: GCs können Speicherpools intern verwenden. Es ist üblicher, dass sie Dinge nach Generationen aufteilen (was sehr gut funktioniert, da die meisten Objekte nur von kurzer Dauer sind). Das eigentliche Problem von GC ist, dass es tendenziell mehr Speicher als andere Methoden verwendet und dadurch die Lokalität des CPU-Cache (und damit die Geschwindigkeit) verringert.
Donal Fellows
Die Zuweisung (aber nicht die Freigabe) ist für einen komprimierenden Garbage Collector sehr schnell, aber die Seite sagt nicht wirklich, dass D einen komprimierenden Garbage Collector hat, sondern lediglich, dass "moderne Garbage Collectors" komprimieren. Tatsächlich bin ich mir sicher, dass ich irgendwo auf der Website von D gelesen habe, dass der GC nicht komprimiert, aber ich kann die Referenz nicht wieder finden.
Qwertie
13

Eine Antwort auf 1):

Solange Ihr Heap zusammenhängend ist , ist das Zuweisen auf ihm genauso billig wie das Zuweisen auf dem Stapel.

Während Sie außerdem Objekte zuweisen, die nebeneinander liegen, ist Ihre Speicher-Caching-Leistung großartig.

Solange Sie nicht den Garbage Collector laufen müssen, ist keine Leistung verloren , und die Haufen bleibt angrenzend.

Das sind die guten Nachrichten :)

Antwort auf 2):

Die GC-Technologie hat große Fortschritte gemacht. Heutzutage sind sie sogar in Echtzeit erhältlich. Das bedeutet, dass die Gewährleistung eines zusammenhängenden Speichers ein richtliniengesteuertes, implementierungsabhängiges Problem ist.

Also wenn

  • Sie können sich einen Echtzeit-GC leisten
  • Ihre Anwendung enthält genügend Zuordnungspausen
  • es kann Ihre freie Liste einen freien Block halten

Möglicherweise erzielen Sie eine bessere Leistung.

Antwort auf die nicht gestellte Frage:

Wenn Entwickler von Speicherverwaltungsproblemen befreit sind, haben sie möglicherweise mehr Zeit, um sich mit Aspekten der tatsächlichen Leistung und Skalierbarkeit ihres Codes zu befassen . Das ist auch ein nicht technischer Faktor, der ins Spiel kommt.

xtofl
quelle
Es liegt also an der Art und Weise des Algorithmus, Daten in der richtigen Reihenfolge zuzuweisen und darauf zuzugreifen.
Nordlöw
@Nordloew: Die Beseitigung der Fragmentierung hätte nur geringe Auswirkungen auf die effektiv benötigte Anzahl von Seiten. Die Zugriffsreihenfolge hat einen größeren Effekt, ist hier jedoch nicht im Geltungsbereich.
xtofl
7
"Solange Ihr Heap zusammenhängend ist, ist das Zuweisen auf ihm genauso billig wie das Zuweisen auf dem Stapel." - Nun, das Zuweisen von nVariablen auf dem Stapel in C ++ ist eine Maschinenanweisung. Aufräumen ist Null.
Karoly Horvath
1
Ja, aber in DI bet werden immer noch lokale Objekte auf dem Stapel erstellt. Sie haben lediglich den Compiler veranlasst, sich um den Unterschied zwischen Heap / Stack zu kümmern, genau wie in C ++ kümmert sich der Compiler darum, was in welchen Registern abläuft.
Mooing Duck
@MooingDuck: Ich hatte auch das Gefühl, dass solche Entscheidungen in den meisten Fällen vom Compiler anstelle des Programmierers getroffen werden könnten. Haben Sie einen Hinweis auf die D-Methode, um diese Dinge zu tun?
Nordlöw
4

Es handelt sich weder um "Garbage Collection" noch um "langwierigen fehleranfälligen" handgeschriebenen Code. Intelligente Zeiger, die wirklich intelligent sind, können Ihnen eine Stapelsemantik verleihen und bedeuten, dass Sie niemals "Löschen" eingeben, aber nicht für die Speicherbereinigung bezahlen. Hier ist ein weiteres Video von Herb , das den Punkt macht - sicher und schnell - genau das wollen wir.

Kate Gregory
quelle
5
Intelligente Zeiger zählen nur die Ref-Zählung, und die Ref-Zählung ist nur die GC eines armen Mannes. Das Ref-Zählen verursacht auch Leistungskosten für das Inkrementieren / Dekrementieren aller Zählungen (nach einigen alten Studien des Boehm GC ist das Ref-Zählen oft langsamer als das Verfolgen von GC) und verarbeitet keine Zyklen.
Dsimcha
1
Das Ref-Zählen kann auch zu einem erheblichen Aufblähen des Codes führen: Einfache Zeigerzuweisungen werden entweder zu Funktionsaufrufen oder sind inline. Beide sind deutlich größer als ein einfacher mov(insbesondere wenn der Destruktorcode inline ist). Wenn die Zeiger von Threads gemeinsam genutzt werden, benötigen Sie möglicherweise sogar zusätzlichen Code, um sicherzustellen, dass die Zählinkremente / -dekremente atomar sind.
Peter Alexander
1
@dsimcha: Ich habe mich schon seit einiger Zeit in diesem Stil entwickelt und es ist bemerkenswert einfach, mit just T*und zu arbeiten scoped_ptr<T>, von denen beide als Referenz gezählt werden.
BCS
3
@dsmicha: Der meiste C ++ - Code benötigt überhaupt keine erneut gezählten gemeinsam genutzten Zeiger ... In den meisten Fällen reicht ein einfacher unique_ptr aus, der keinerlei Overhead verursacht. Selbst wenn Sie neu gezählte Zeiger verwenden müssen (kann die meiste Zeit leicht vermieden werden, aber manchmal spart die Verwendung von shared_ptrs viel Arbeit), benötigen Sie in den meisten Fällen immer noch nicht so viele Zuweisungen oder Kopien davon.
Smerlin
4

Ein weiterer zu berücksichtigender Punkt ist die 80: 20-Regel. Es ist wahrscheinlich, dass die überwiegende Mehrheit der von Ihnen zugewiesenen Plätze irrelevant ist und Sie nicht viel über einen GC gewinnen, selbst wenn Sie die Kosten dort auf Null drücken könnten. Wenn Sie dies akzeptieren, kann die Einfachheit, die Sie durch die Verwendung eines GC erzielen können, die Kosten für dessen Verwendung verdrängen. Dies gilt insbesondere dann, wenn Sie das Kopieren vermeiden können. Was D bietet, ist ein GC für die 80% -Fälle und der Zugriff auf die Stapelzuweisung und Malloc für die 20%.

BCS
quelle
3

Selbst wenn Sie einen idealen Garbage Collector hätten, wäre er langsamer gewesen als das Erstellen von Dingen auf einem Stapel. Sie müssen also eine Sprache haben, die beides gleichzeitig erlaubt. Darüber hinaus besteht die einzige Möglichkeit, mit Garbage Collector die gleiche Leistung wie mit manuell verwalteten Speicherzuordnungen zu erzielen (richtig ausgeführt), darin, die gleichen Funktionen mit dem Speicher auszuführen, die erfahrene Entwickler in vielen Fällen durchgeführt hätten erfordern, dass Entscheidungen eines Garbage Collectors zur Kompilierungszeit getroffen und zur Laufzeit ausgeführt werden. Normalerweise verlangsamt die Speicherbereinigung die Arbeit, Sprachen, die nur mit dynamischem Speicher arbeiten, sind langsamer und die Vorhersagbarkeit der Ausführung von Programmen, die in diesen Sprachen geschrieben sind, ist gering, während die Ausführungslatenz höher ist. Ehrlich gesagt verstehe ich persönlich nicht, warum man einen Müllsammler brauchen würde. Das manuelle Verwalten des Speichers ist nicht schwierig. Zumindest nicht in C ++. Natürlich macht es mir nichts aus, wenn der Compiler Code generiert, der alle Dinge für mich bereinigt, wie ich es getan hätte, aber dies scheint im Moment nicht möglich zu sein.


quelle
Dies ist auch meine aktuelle Ansicht. Vielen Dank für Ihre gründliche Antwort.
Nordlöw
"Speicherverwaltung" ist nicht schwer ... Stimmt - aber ich habe viele Fehler beim Lernen gemacht und auch viele Co-Entwickler gesehen, und ich werde wahrscheinlich in Zukunft neue Fehler machen. "keine Speicherverwaltung" ist eine Größenordnung einfacher :)
xtofl
@xtofl: Glaubst du nicht, dass es dir nicht nur schwer fällt, es zu lernen, sondern auch viel nützliches Verständnis dafür, wie Dinge funktionieren? Zum Beispiel habe ich einen Freund, der in Informatik promoviert hat, Programme in Java hat und nicht einmal weiß, dass (fast) alles in Java dynamisch zugeordnet ist? Und er hat keine Ahnung von Zeigern gegen Objekte auf Stapeln usw. Ich bin Assembler, C und C ++ sehr dankbar, dass sie mich tatsächlich motiviert haben, zu lernen, wie Computer funktionieren und außerhalb der Box leben.
1
@Vlad: Aber muss er wirklich etwas davon wissen?
GManNickG
2
@ GMan: Ich stimme dir vollkommen zu. Wenn Sie an einer der beiden angesehensten IT-Universitäten in den USA promoviert haben, denken Sie, Sie wissen, wie Computer funktionieren. Deshalb hat er sich für einen Job auf niedrigerer Ebene angemeldet, bei dem Dinge auf niedriger Ebene wichtig sind und schlimm gescheitert sind. Wenn Sie sich an Ihre Domain halten - sicher. Es ist nicht nur in Ordnung, diese Dinge nicht zu wissen, es ist Realität. Zum Beispiel weiß ich nicht, wie Computer von nichts zu "erledigt" gebaut werden, und wenn Sie mir 100 Jahre zurückschicken, muss ich Toiletten putzen, um meinen Lebensunterhalt zu verdienen ... :-(
3

In vielen Fällen kann ein Compiler die Heap-Zuordnung zurück zur Stack-Zuordnung optimieren. Dies ist der Fall, wenn Ihr Objekt den lokalen Bereich nicht verlässt.

Ein anständiger Compiler wird xim folgenden Beispiel mit ziemlicher Sicherheit einen Stapel zuweisen:

void f() {
    Foo* x = new Foo();
    x->doStuff(); // Assuming doStuff doesn't assign 'this' anywhere
    // delete x or assume the GC gets it
}

Was der Compiler tut, heißt Escape-Analyse .

Außerdem könnte D theoretisch einen sich bewegenden GC haben , was potenzielle Leistungsverbesserungen durch eine verbesserte Cache-Nutzung bedeutet, wenn der GC Ihre Heap-Objekte zusammenfasst. Es bekämpft auch die Haufenfragmentierung, wie in der Antwort von Jack Edmonds erläutert. Ähnliche Dinge können mit der manuellen Speicherverwaltung durchgeführt werden, aber es ist zusätzliche Arbeit.

mpartel
quelle
2
hmmmm. Das würde von meinen Tools als Speicherverlust markiert werden ... ist das D oder C ++, das Sie dort schreiben?
xtofl
@xtofl Sagen wir C ++ mit einem GC. Das Konzept ist jedoch allgemein.
Partel
1
Tatsächlich kann eine solche Optimierung nicht durchgeführt werden, es sei denn, der Compiler weiß, dass weder Fooder Konstruktor noch doStuffein Verweis auf xoder etwas Internes in ihm durchgesickert sind. In D würde der Compiler wissen, dass wenn beide Funktionen wären pure, da dies garantiert, dass auf kein veränderliches Modul oder statische Variablen zugegriffen wird, aber in den meisten Sprachen kann er dies nicht ohne Prüfung der Körper dieser Funktionen (was die meisten Compiler nicht tun) ), weil eine globale oder Klassenvariable in einer dieser Funktionen mit einem internen Wert x- einschließlich sich xselbst - versehen werden könnte.
Jonathan M Davis
1
Welche C ++ - Compiler führen diese Optimierung aus Interesse tatsächlich durch?
Steve Jessop
2
Do verwendet den C-Linker, sodass genau die Optimierung der Verbindungszeit durchgeführt wird, wie dies normalerweise in C oder C ++ der Fall ist. Wenn dies eine Funktion ist pure, kann der D-Compiler erkennen, dass keine Referenzen entgehen, da pureFunktionen nicht auf veränderbare statische oder Modulvariablen zugreifen können, diese Art der Optimierung jedoch trotzdem nicht durchführen würden. Theoretisch könnte es sein, aber ich glaube nicht, dass ein D-Compiler jemals Klassen als Optimierung auf den Stapel legt.
Jonathan M Davis
2

Ein inkrementeller GC mit niedriger Priorität sammelt Müll, wenn keine Task mit hoher Priorität ausgeführt wird. Die Threads mit hoher Priorität werden schneller ausgeführt, da keine Speicherfreigabe erfolgt. Dies ist die Idee von Henrikssons RT Java GC, siehe http://www.oracle.com/technetwork/articles/javase/index-138577.html

Jonas W.
quelle
1

Die Speicherbereinigung verlangsamt tatsächlich den Code. Es fügt dem Programm zusätzliche Funktionen hinzu, die zusätzlich zu Ihrem Code ausgeführt werden müssen. Es gibt auch andere Probleme damit, wie zum Beispiel, dass der GC erst ausgeführt wird, wenn tatsächlich Speicher benötigt wird. Dies kann zu kleinen Speicherlecks führen. Ein weiteres Problem ist, wenn eine Referenz nicht ordnungsgemäß entfernt wird, der GC sie nicht aufnimmt und erneut zu einem Leck führt. Mein anderes Problem mit GC ist, dass es die Faulheit bei Programmierern fördert. Ich bin ein Befürworter des Lernens der Konzepte der Speicherverwaltung auf niedriger Ebene, bevor ich auf eine höhere Ebene springe. Es ist wie in der Mathematik. Sie lernen, wie man nach den Wurzeln eines Quadrats löst oder wie man zuerst eine Ableitung von Hand nimmt, dann lernen Sie, wie man es auf dem Taschenrechner macht. Verwenden Sie diese Dinge als Werkzeug, nicht als Krücken.

Wenn Sie Ihre Leistung nicht beeinträchtigen möchten, sollten Sie sich über den GC und die Verwendung von Heap und Stack im Klaren sein.

MGZero
quelle
Einer der Punkte eines GC (zumindest einiger Arten von GCs) ist, dass das ordnungsgemäße Entfernen einer Referenz darin besteht, sie zu überschreiben. Beachten Sie, dass dies selbst in Nicht-GC-Ländern ein Fehler (ein baumelnder Zeiger) ist.
BCS
@BCS Natürlich ist das genau das, worauf ich mich beziehe. Ich habe viele Programmierer gesehen, die nur ihre Zeiger baumeln lassen, aber ich sehe viel seltener in Nicht-GC-Sprachen. Sie haben nicht die Sicherheitsdecke, die Ihnen sagt, dass Sie mit der Speicherverwaltung etwas entspannter umgehen können, daher sind Sie eher vorsichtig. Dies geht Hand in Hand mit meinem Standpunkt zur Faulheit!
MGZero
0

Mein Punkt ist, dass GC Malloc unterlegen ist, wenn Sie normale prozedurale Programmierung durchführen. Sie gehen einfach von Prozedur zu Prozedur, ordnen sie zu und geben sie frei, verwenden globale Variablen und deklarieren einige Funktionen _inline oder _register. Dies ist C-Stil.

Sobald Sie jedoch eine höhere Abstraktionsschicht erreicht haben, müssen Sie mindestens die Referenzzählung durchführen. Sie können also als Referenz übergeben, zählen und freigeben, sobald der Zähler Null ist. Dies ist gut und Malloc überlegen, nachdem die Anzahl und Hierarchie der Objekte zu schwierig für die manuelle Verwaltung geworden ist. Dies ist im C ++ - Stil. Sie definieren Konstruktoren und Destruktoren, um die Zähler zu erhöhen. Sie kopieren und ändern, sodass das gemeinsam genutzte Objekt in zwei Teile geteilt wird, sobald ein Teil davon von einer Partei geändert wurde, eine andere Partei jedoch weiterhin den ursprünglichen Wert benötigt. So können Sie eine große Datenmenge von Funktion zu Funktion übergeben, ohne zu überlegen, ob Sie Daten hier kopieren oder nur einen Zeiger dorthin senden müssen. Das Nachzählen erledigt diese Entscheidungen für Sie.

Dann kommt die ganz neue Welt, Schließungen, funktionale Programmierung, Ententypisierung, Zirkelverweise, asynchrone Ausführung. Code und Daten beginnen sich zu vermischen. Sie übergeben die Funktion häufiger als normale Daten als Parameter. Sie erkennen, dass die Metaprogrammierung ohne Makros oder Vorlagen durchgeführt werden kann. Ihr Code fängt an, in den Himmel einzutauchen und festen Boden zu verlieren, weil Sie etwas in Rückrufen von Rückrufen von Rückrufen ausführen, Daten nicht mehr verwurzelt werden, Dinge asynchron werden und Sie von Schließungsvariablen abhängig werden. Hier ist also eine zeitgesteuerte, speicherwandelnde GC die einzig mögliche Lösung, da sonst Schließungen und Zirkelverweise überhaupt nicht möglich sind. Dies ist JavaScript-Methode.

Sie haben D erwähnt, aber D ist in C ++ immer noch verbessert. Daher wählen Sie wahrscheinlich Malloc- oder Ref-Counting in Konstruktoren, Stapelzuordnungen und globale Variablen (auch wenn es sich um komplizierte Bäume von Entitäten aller Art handelt).

exebook
quelle