Können die Kosten für GC bei der Analyse der Laufzeit von Worst-Case-Datenstrukturen, die in einer Programmiersprache mit Speicherbereinigung angegeben sind, vernachlässigt werden?

Mir ist gerade aufgefallen, dass ich davon ausgegangen bin, dass meine Frage mit "Ja" beantwortet wurde, aber ich habe keinen guten Grund. Ich stelle mir vor, dass es vielleicht einen Müllsammler gibt, der nachweislich nur die Worst-Case-Verlangsamung einführt . Gibt es eine definitive Referenz, die ich zitieren kann? In meinem Fall arbeite ich an einer rein funktionalen Datenstruktur und verwende Standard ML, wenn diese Details wichtig sind.$O(1)$

Und vielleicht wäre diese Frage noch relevanter, wenn sie auf Datenstrukturen angewendet würde, die beispielsweise in Java spezifiziert sind? Vielleicht gibt es einige relevante Diskussionen in Algorithmen / Datenstruktur-Lehrbüchern, die Java verwenden? (Ich weiß, dass Sedgewick eine Java-Version hat, aber ich habe nur Zugriff auf die C-Version.)

Ja, GC wird zu konstanten Zeiten abgeschrieben. Angenommen, Sie haben einen Algorithmus, der für die Zeit mit einer Spitzenarbeitsmenge der Größe k ausgeführt wird . Beachten Sie nun, dass Sie während der Ausführung des Programms höchstens O ( n ) Wörter zuweisen können und dass die Zeitkosten für das Ausführen eines Kopier-Garbage-Collectors O ( k ) betragen (dh die Kosten für ein gc sind proportional zur Gesamtsumme) Menge der Live-Daten). Wenn Sie also gc höchstens O ( n / k ) Mal ausführen , sind die Gesamtlaufzeitkosten durch O ( n $n$$k$$O(n)$$O(k)$$O(n/k)$$O(n)$Dies bedeutet, dass die fortgeführten Anschaffungskosten des GC konstant sind. Wenn Sie also einen Cheney-ähnlichen Sammler haben, bei dem jeder Halbraum groß ist , ist es leicht zu erkennen, dass eine vollständige Sammlung nicht mehr als einmal alle n / k Schritte aufgerufen werden kann, da die Zuweisung von k Wörtern O ( k ) erfordert. Zeit, und die Arbeitsmenge überschreitet nie die Größe k , wodurch Sie die gewünschte Grenze erhalten. Dies rechtfertigt das Ignorieren von GC-Problemen.$2k$$n/k$$k$$O(k)$$k$

Ein Fall, in dem das Vorhandensein oder Nichtvorhandensein von gc nicht ignoriert werden kann, ist das Schreiben von sperrfreien Datenstrukturen. Viele moderne schlossfreie Datenstrukturen schlossfreie lecken absichtlich den Speicher und verlassen sich auf die Richtigkeit von gc. Dies liegt daran, dass auf einer hohen Ebene die Art und Weise, wie sie arbeiten, darin besteht, einige Daten zu kopieren, Änderungen daran vorzunehmen und zu versuchen, sie mit einem CAS-Befehl atomar zu aktualisieren und dies in einer Schleife auszuführen, bis der CAS erfolgreich ist. Das Hinzufügen einer deterministischen Freigabe zu diesen Algorithmen macht sie viel komplexer, und die Benutzer stören sich oft nicht daran (zumal sie häufig auf Java-ähnliche Umgebungen abzielen).

BEARBEITEN: Wenn Sie nicht abgeschriebene Grenzen möchten, wird dies vom Cheney-Sammler nicht ausgeführt. Bei jedem Aufruf wird das gesamte Live-Set gescannt. Das Schlüsselwort für Google ist "Garbage Collection in Echtzeit", und Djikstra et al. und Steele gab die ersten Echtzeit-Mark-and-Sweep-Sammler, und Baker gab die ersten Echtzeit-Verdichtungs-GC.

@article {dijkstra1978fly,
  title = {{On-the-fly Müllabfuhr: Eine Übung in Zusammenarbeit}},
  author = {Dijkstra, EW und Lamport, L. und Martin, AJ und Scholten, CS und Steffens, EFM},
  journal = {Mitteilungen der ACM},
  volume = {21},
  number = {11},
  pages = {966--975},
  issn = {0001-0782},
  Jahr = {1978},
  publisher = {ACM}
}

@article {steele1975multiprocessing,
  title = {{Multiprocessing-Speicherbereinigung}},
  author = {Steele Jr, GL},
  journal = {Mitteilungen der ACM},
  volume = {18},
  number = {9},
  pages = {495--508},
  issn = {0001-0782},
  Jahr = {1975},
  publisher = {ACM}
}

@article {baker1978list,
  title = {{Listenverarbeitung in Echtzeit auf einem seriellen Computer}},
  author = {Baker Jr, HG},
  journal = {Mitteilungen der ACM},
  volume = {21},
  number = {4},
  pages = {280--294},
  issn = {0001-0782},
  Jahr = {1978},
  publisher = {ACM}
}

$O(n)$

Das Hauptproblem bei der Garbage Collection ist nicht die Komplexität der Berechnungen, sondern die Unvorhersehbarkeit. Dies ist am relevantesten bei der Betrachtung von Echtzeitsystemen. Eine Menge Arbeit an der Garbage Collection in Echtzeit versucht, dieses Problem zu beheben. Andere haben einfach aufgegeben. Beispielsweise basiert die Echtzeitspezifikation für Java auf einem vom Programmierer festgelegten Bereich, der programmgesteuert mit zugewiesen und freigegeben wird.$O(1)$ Kosten, unabhängig von ihrer Größe.

Die endgültige Speicherbereinigungsreferenz lautet:

• Garbage Collection von Richard Jones und Rafael Lin

Ben Zorn hat einige Arbeiten durchgeführt, um die tatsächlichen Kosten verschiedener Algorithmen für die Speicherbereinigung zu messen. In der folgenden neueren Veröffentlichung wird jedoch ein weitaus umfassenderer Vergleich dargestellt:

• Mythen und Realitäten: Die Auswirkungen der Speicherbereinigung auf die Leistung , SM Blackburn, P. Cheng und KS McKinley, ACM SIGMETRICS-Konferenz über Mess- und Modellierungscomputersysteme, S. 25-36, New York, NY, Juni 2004.

Für mehr sehen Sie:

• Eine einheitliche Theorie der Speicherbereinigung, Bacon, Cheng & Rajan, ACM-Konferenz über objektorientierte Programmierung, Systeme, Sprachen und Anwendungen, Vancouver, BC, Kanada, S. 50-68, 2004.