Best Practice zum Erstellen von Millionen kleiner temporärer Objekte

Was sind die "Best Practices" zum Erstellen (und Freigeben) von Millionen kleiner Objekte?

Ich schreibe ein Schachprogramm in Java und der Suchalgorithmus generiert ein einzelnes "Verschieben" -Objekt für jede mögliche Bewegung, und eine nominelle Suche kann leicht über eine Million Bewegungsobjekte pro Sekunde generieren. Die JVM GC war in der Lage, die Belastung meines Entwicklungssystems zu bewältigen, aber ich bin daran interessiert, alternative Ansätze zu untersuchen, die:

1. Minimieren Sie den Aufwand für die Speicherbereinigung und
2. Reduzieren Sie den maximalen Speicherbedarf für Systeme der unteren Preisklasse.

Die überwiegende Mehrheit der Objekte ist sehr kurzlebig, aber etwa 1% der generierten Bewegungen werden beibehalten und als beibehaltener Wert zurückgegeben. Daher müsste jede Pooling- oder Caching-Technik die Möglichkeit bieten, bestimmte Objekte von der Wiederverwendung auszuschließen .

Ich erwarte keinen vollständig ausgearbeiteten Beispielcode, würde mich aber über Vorschläge für weitere Lektüre / Recherchen oder Open-Source-Beispiele ähnlicher Art freuen.

Führen Sie die Anwendung mit ausführlicher Speicherbereinigung aus:

java -verbose:gc

Und es wird Ihnen sagen, wann es sammelt. Es würde zwei Arten von Sweeps geben, einen schnellen und einen vollständigen Sweep.

[GC 325407K->83000K(776768K), 0.2300771 secs]
[GC 325816K->83372K(776768K), 0.2454258 secs]
[Full GC 267628K->83769K(776768K), 1.8479984 secs]

Der Pfeil steht vor und nach der Größe.

Solange es sich nur um GC und nicht um eine vollständige GC handelt, sind Sie sicher zu Hause. Der reguläre GC ist ein Kopiersammler in der "jungen Generation", sodass Objekte, auf die nicht mehr verwiesen wird, einfach vergessen werden. Genau das möchten Sie.

Das Lesen der Garbage Collection-Optimierung für Java SE 6 HotSpot Virtual Machine ist wahrscheinlich hilfreich.

Seit Version 6 verwendet der Servermodus von JVM eine Escape-Analysetechnik . Wenn Sie es verwenden, können Sie GC insgesamt vermeiden.

Nun, hier gibt es mehrere Fragen in einer!

1 - Wie werden kurzlebige Objekte verwaltet?

Wie bereits erwähnt, kann die JVM perfekt mit einer großen Menge kurzlebiger Objekte umgehen, da sie der schwachen Generationshypothese folgt .

Beachten Sie, dass es sich um Objekte handelt, die den Hauptspeicher (Heap) erreicht haben. Dies ist nicht immer der Fall. Viele von Ihnen erstellte Objekte hinterlassen nicht einmal ein CPU-Register. Betrachten Sie zum Beispiel diese for-Schleife

for(int i=0, i<max, i++) {
  // stuff that implies i
}

Denken wir nicht an das Abrollen von Schleifen (eine Optimierung, die die JVM stark an Ihrem Code ausführt). Wenn maxgleich ist Integer.MAX_VALUE, kann die Ausführung Ihrer Schleife einige Zeit dauern. Die iVariable wird jedoch niemals aus dem Schleifenblock entkommen. Daher legt die JVM diese Variable in einem CPU-Register ab, erhöht sie regelmäßig, sendet sie jedoch niemals an den Hauptspeicher zurück.

Das Erstellen von Millionen von Objekten ist also keine große Sache, wenn sie nur lokal verwendet werden. Sie werden tot sein, bevor sie in Eden gelagert werden, sodass der GC sie nicht einmal bemerkt.

2 - Ist es sinnvoll, den Overhead des GC zu reduzieren?

Wie immer kommt es darauf an.

Zunächst sollten Sie die GC-Protokollierung aktivieren, um eine klare Übersicht über die Vorgänge zu erhalten. Sie können es mit aktivieren -Xloggc:gc.log -XX:+PrintGCDetails.

Wenn Ihre Anwendung viel Zeit in einem GC-Zyklus verbringt, optimieren Sie den GC, andernfalls lohnt es sich möglicherweise nicht wirklich.

Wenn Sie beispielsweise alle 100 ms einen jungen GC haben, der 10 ms benötigt, verbringen Sie 10% Ihrer Zeit im GC und Sie haben 10 Sammlungen pro Sekunde (was riesig ist). In einem solchen Fall würde ich keine Zeit mit GC-Tuning verbringen, da diese 10 GC / s immer noch vorhanden wären.

3 - Einige Erfahrungen

Ich hatte ein ähnliches Problem mit einer Anwendung, die eine große Menge einer bestimmten Klasse erstellte. In den GC-Protokollen habe ich festgestellt, dass die Erstellungsrate der Anwendung etwa 3 GB / s betrug, was viel zu viel ist (komm schon ... 3 Gigabyte Daten pro Sekunde ?!).

Das Problem: Zu viele häufige GCs, die durch zu viele erstellte Objekte verursacht werden.

In meinem Fall habe ich einen Speicherprofiler angehängt und festgestellt, dass eine Klasse einen großen Prozentsatz aller meiner Objekte darstellt. Ich habe die Instanziierungen aufgespürt, um herauszufinden, dass es sich bei dieser Klasse im Grunde genommen um ein Paar Boolescher Werte handelt, die in ein Objekt eingewickelt sind. In diesem Fall standen zwei Lösungen zur Verfügung:

• Überarbeiten Sie den Algorithmus so, dass ich kein Paar Boolescher Werte zurückgebe, sondern zwei Methoden, die jeden Booleschen Wert separat zurückgeben

• Zwischenspeichern Sie die Objekte, da Sie wissen, dass es nur 4 verschiedene Instanzen gibt

Ich entschied mich für die zweite, da sie die Anwendung am wenigsten beeinträchtigte und leicht einzuführen war. Ich habe Minuten gebraucht, um eine Factory mit einem nicht threadsicheren Cache einzurichten (ich brauchte keine Thread-Sicherheit, da ich schließlich nur 4 verschiedene Instanzen haben würde).

Die Zuweisungsrate sank auf 1 GB / s, ebenso wie die Häufigkeit junger GC (geteilt durch 3).

Hoffentlich hilft das !

Wenn Sie nur Wertobjekte haben (dh keine Verweise auf andere Objekte) und wirklich, aber ich meine wirklich Tonnen und Tonnen von ihnen, können Sie direkt ByteBuffersmit nativer Bytereihenfolge verwenden [letzteres ist wichtig] und Sie benötigen einige hundert Zeilen von Code zum Zuweisen / Wiederverwenden + Getter / Setter. Getter sehen ähnlich auslong getQuantity(int tupleIndex){return buffer.getLong(tupleInex+QUANTITY_OFFSSET);}

Das würde das GC-Problem fast vollständig lösen, solange Sie nur einmal zuweisen, dh einen großen Teil, und dann die Objekte selbst verwalten. Anstelle von Referenzen hätten Sie nur einen Index (dh int) für den ByteBuffer, der weitergegeben werden muss. Möglicherweise müssen Sie den Speicher auch selbst ausrichten.

Die Technik würde sich wie eine Anwendung anfühlen C and void*, aber mit etwas Verpackung ist sie erträglich. Ein Leistungsnachteil könnte darin bestehen, zu überprüfen, ob der Compiler ihn nicht beseitigt. Ein großer Vorteil ist die Lokalität, wenn Sie die Tupel wie Vektoren verarbeiten. Das Fehlen des Objekt-Headers verringert auch den Speicherbedarf.

Abgesehen davon ist es wahrscheinlich, dass Sie keinen solchen Ansatz benötigen, da die junge Generation praktisch aller JVM-Unternehmen trivial stirbt und die Zuweisungskosten nur ein Hinweis sind. Die Zuordnungskosten können etwas höher sein, wenn Sie finalFelder verwenden, da diese auf einigen Plattformen (nämlich ARM / Power) einen Speicherzaun erfordern. Auf x86 ist dies jedoch kostenlos.

Angenommen, Sie stellen fest, dass GC ein Problem ist (wie andere darauf hinweisen, dass dies möglicherweise nicht der Fall ist), implementieren Sie Ihre eigene Speicherverwaltung für Ihren Sonderfall, dh eine Klasse, die unter massiver Abwanderung leidet. Probieren Sie das Pooling von Objekten aus. Ich habe Fälle gesehen, in denen es recht gut funktioniert. Das Implementieren von Objektpools ist ein ausgetretener Weg, sodass Sie hier nicht erneut nachsehen müssen. Achten Sie auf Folgendes:

• Multithreading: Die Verwendung von lokalen Thread-Pools funktioniert möglicherweise für Ihren Fall
• Hintergrunddatenstruktur: Verwenden Sie ArrayDeque, da es beim Entfernen eine gute Leistung erbringt und keinen Zuordnungsaufwand hat
• Begrenzen Sie die Größe Ihres Pools :)

Vor / nach usw. messen usw.

Ich habe ein ähnliches Problem festgestellt. Versuchen Sie zunächst, die Größe der kleinen Objekte zu verringern. Wir haben einige Standardfeldwerte eingeführt, die auf sie in jeder Objektinstanz verweisen.

Beispielsweise hat MouseEvent einen Verweis auf die Point-Klasse. Wir haben Punkte zwischengespeichert und auf sie verwiesen, anstatt neue Instanzen zu erstellen. Gleiches gilt beispielsweise für leere Zeichenfolgen.

Eine andere Quelle waren mehrere Boolesche Werte, die durch einen Int ersetzt wurden. Für jeden Booleschen Wert verwenden wir nur ein Byte des Int.

Ich habe dieses Szenario vor einiger Zeit mit XML-Verarbeitungscode behandelt. Ich habe Millionen von XML-Tag-Objekten erstellt, die sehr klein (normalerweise nur eine Zeichenfolge) und extrem kurzlebig waren (ein Fehlschlagen einer XPath- Prüfung bedeutete, dass keine Übereinstimmung vorliegt, also verwerfen Sie sie).

Ich habe einige ernsthafte Tests durchgeführt und bin zu dem Schluss gekommen, dass ich mit einer Liste verworfener Tags nur eine Geschwindigkeitsverbesserung von etwa 7% erzielen konnte, anstatt neue zu erstellen. Nach der Implementierung stellte ich jedoch fest, dass für die freie Warteschlange ein Mechanismus zum Bereinigen erforderlich war, wenn sie zu groß wurde. Dadurch wurde meine Optimierung vollständig aufgehoben, sodass ich sie auf eine Option umstellte.

Zusammenfassend - wahrscheinlich nicht wert - aber ich bin froh zu sehen, dass Sie darüber nachdenken, es zeigt, dass Sie sich interessieren.

Da Sie ein Schachprogramm schreiben, gibt es einige spezielle Techniken, die Sie für eine anständige Leistung verwenden können. Ein einfacher Ansatz besteht darin, ein großes Array von Longs (oder Bytes) zu erstellen und es als Stapel zu behandeln. Jedes Mal, wenn Ihr Bewegungsgenerator Bewegungen erstellt, werden einige Zahlen auf den Stapel geschoben, z. B. von Quadrat zu Quadrat. Während Sie den Suchbaum auswerten, werden Sie Bewegungen ausführen und eine Board-Darstellung aktualisieren.

Wenn Sie Ausdruckskraft wünschen, verwenden Sie Objekte. Wenn Sie Geschwindigkeit wollen (in diesem Fall), gehen Sie nativ.

Eine Lösung, die ich für solche Suchalgorithmen verwendet habe, besteht darin, nur ein Verschiebungsobjekt zu erstellen, es mit einer neuen Verschiebung zu mutieren und die Verschiebung dann rückgängig zu machen, bevor der Bereich verlassen wird. Sie analysieren wahrscheinlich jeweils nur einen Zug und speichern dann irgendwo den besten Zug.

Wenn dies aus irgendeinem Grund nicht möglich ist und Sie die maximale Speichernutzung verringern möchten, finden Sie hier einen guten Artikel zur Speichereffizienz: http://www.cs.virginia.edu/kim/publicity/pldi09tutorials/memory-efficient-java- tutorial.pdf

Erstellen Sie einfach Ihre Millionen von Objekten und schreiben Sie Ihren Code auf die richtige Weise: Behalten Sie keine unnötigen Verweise auf diese Objekte bei. GC erledigt den Drecksjob für Sie. Sie können wie erwähnt mit ausführlicher GC herumspielen, um zu sehen, ob sie wirklich GC-fähig sind. In Java geht es um das Erstellen und Freigeben von Objekten. :) :)

Ich denke, Sie sollten über die Stapelzuweisung in Java und die Escape-Analyse lesen.

Wenn Sie sich eingehender mit diesem Thema befassen, werden Sie möglicherweise feststellen, dass Ihre Objekte nicht einmal auf dem Heap zugeordnet sind und von GC nicht so erfasst werden, wie Objekte auf dem Heap sind.

Es gibt eine Wikipedia-Erklärung zur Escape-Analyse mit einem Beispiel dafür, wie dies in Java funktioniert:

http://en.wikipedia.org/wiki/Escape_analysis

Ich bin kein großer Fan von GC, deshalb versuche ich immer, Wege zu finden, um das zu umgehen. In diesem Fall würde ich die Verwendung des Objektpoolmusters vorschlagen :

Die Idee ist, das Erstellen neuer Objekte zu vermeiden, indem Sie sie in einem Stapel speichern, damit Sie sie später wiederverwenden können.

Class MyPool
{
   LinkedList<Objects> stack;

   Object getObject(); // takes from stack, if it's empty creates new one
   Object returnObject(); // adds to stack
}

Objektpools bieten enorme (manchmal 10-fache) Verbesserungen gegenüber der Objektzuweisung auf dem Heap. Aber die obige Implementierung unter Verwendung einer verknüpften Liste ist sowohl naiv als auch falsch! Die verknüpfte Liste erstellt Objekte, um ihre interne Struktur zu verwalten und den Aufwand aufzuheben. Ein Ringpuffer, der ein Array von Objekten verwendet, funktioniert gut. In dem Beispiel give (ein Schachprogramm, das Züge verwaltet) sollte der Ringpuffer in ein Halterobjekt für die Liste aller berechneten Züge eingewickelt werden. Es werden dann nur die Objektreferenzen des Bewegungsinhabers weitergegeben.