Ist es im Vergleich zu C / C ++ viel schwieriger, die Leistung von Java zu optimieren? [geschlossen]

11

Verhindert die "Magie" der JVM den Einfluss eines Programmierers auf Mikrooptimierungen in Java? Ich habe kürzlich in C ++ gelesen, dass manchmal die Reihenfolge der Datenelemente Optimierungen liefern kann (gewährt in der Mikrosekundenumgebung), und ich nahm an, dass einem Programmierer die Hände gebunden sind, wenn es darum geht, die Leistung von Java zu beeinträchtigen.

Ich schätze, dass ein anständiger Algorithmus größere Geschwindigkeitsgewinne bietet, aber wenn Sie den richtigen Algorithmus haben, ist Java aufgrund der JVM-Steuerung schwieriger zu optimieren?

Wenn nicht, könnten die Leute Beispiele dafür geben, welche Tricks Sie in Java verwenden können (neben einfachen Compiler-Flags).

user997112
quelle
14
Das Grundprinzip jeder Java-Optimierung lautet: Die JVM hat es wahrscheinlich schon besser gemacht als Sie. Bei der Optimierung werden meistens sinnvolle Programmierpraktiken befolgt und die üblichen Dinge wie das Verketten von Zeichenfolgen in einer Schleife vermieden.
Robert Harvey
3
Das Prinzip der Mikrooptimierung in allen Sprachen ist, dass der Compiler es bereits besser gemacht hat als Sie. Das andere Prinzip der Mikrooptimierung in allen Sprachen ist, dass das Aufbringen von mehr Hardware billiger ist als die Mikrooptimierung durch den Programmierer. Programmierer müssen dazu neigen, Skalierungsprobleme (suboptimale Algorithmen) zu lösen, aber Mikrooptimierung ist Zeitverschwendung. Manchmal ist eine Mikrooptimierung auf eingebetteten Systemen sinnvoll, auf denen nicht mehr Hardware installiert werden kann. Android, das Java verwendet, und eine eher schlechte Implementierung zeigen jedoch, dass die meisten von ihnen bereits über genügend Hardware verfügen.
Jan Hudec
1
Für "Java Performance Tricks", die es wert sind, studiert zu werden, sind: Effektives Java , Angelika Langer Links - Java Performance und leistungsbezogene Artikel von Brian Goetz in Java Theorie und Praxis und Threading Lightly- Reihe hier
Mücke
2
Seien Sie äußerst vorsichtig mit Tipps und Tricks - die JVM, Betriebssysteme und Hardware werden weiterentwickelt - Sie sollten am besten die Methode zur Leistungsoptimierung erlernen und Verbesserungen für Ihre spezielle Umgebung anwenden :-)
Martijn Verburg
In einigen Fällen kann eine VM zur Laufzeit Optimierungen vornehmen, die zur Kompilierungszeit nicht praktikabel sind. Die Verwendung von verwaltetem Speicher kann die Leistung verbessern, hat jedoch häufig auch einen höheren Speicherbedarf. Nicht verwendeter Speicher wird nach Bedarf freigegeben und nicht so schnell wie möglich.
Brian

Antworten:

5

Sicher, auf der Ebene der Mikrooptimierung wird die JVM einige Dinge tun, über die Sie im Vergleich zu C und C ++ nur wenig Kontrolle haben.

Auf der anderen Seite wirkt sich die Vielzahl der Compiler-Verhaltensweisen mit C und C ++ weitaus stärker negativ auf Ihre Fähigkeit aus, Mikrooptimierungen auf vage portable Weise durchzuführen (auch über Compiler-Revisionen hinweg).

Dies hängt davon ab, welche Art von Projekt Sie optimieren, auf welche Umgebungen Sie abzielen und so weiter. Und am Ende spielt es keine Rolle, da Sie ohnehin ein paar Größenordnungen bessere Ergebnisse aus Optimierungen von Algorithmen, Datenstrukturen und Programmdesign erhalten.

Telastyn
quelle
Es kann sehr wichtig sein, wenn Sie feststellen, dass Ihre App nicht über Kerne skaliert
James
@ James - Möchtest du das näher erläutern?
Telastyn
1
Sehen Sie hier für einen Anfang: mechanische-sympathy.blogspot.co.uk/2011/07/false-sharing.html
James
1
@James, die Skalierung über Kerne hinweg hat sehr wenig mit der Implementierungssprache zu tun (ausgenommen Python!) Und mehr mit der Anwendungsarchitektur.
James Anderson
29

Mikrooptimierungen sind fast nie die Zeit wert, und fast alle einfachen Optimierungen werden automatisch von Compilern und Laufzeiten durchgeführt.

Es gibt jedoch einen wichtigen Bereich der Optimierung, in dem sich C ++ und Java grundlegend unterscheiden, nämlich den Massenspeicherzugriff. C ++ verfügt über eine manuelle Speicherverwaltung. Dies bedeutet, dass Sie das Datenlayout und die Zugriffsmuster der Anwendung optimieren können, um die Caches voll auszunutzen. Dies ist ziemlich schwierig, etwas spezifisch für die Hardware, auf der Sie arbeiten (daher können Leistungssteigerungen auf anderer Hardware verschwinden), aber wenn es richtig gemacht wird, kann es zu einer absolut atemberaubenden Leistung führen. Natürlich zahlen Sie dafür mit dem Potenzial für alle Arten von schrecklichen Fehlern.

Mit einer Garbage-Collected-Sprache wie Java können diese Optimierungen nicht im Code durchgeführt werden. Einige können zur Laufzeit ausgeführt werden (automatisch oder durch Konfiguration, siehe unten), andere sind einfach nicht möglich (der Preis, den Sie für den Schutz vor Speicherverwaltungsfehlern zahlen).

Wenn nicht, könnten die Leute Beispiele dafür geben, welche Tricks Sie in Java verwenden können (neben einfachen Compiler-Flags).

Compiler-Flags sind in Java irrelevant, da der Java-Compiler fast keine Optimierung vornimmt. die Laufzeit tut.

In der Tat haben Java-Laufzeiten eine Vielzahl von Parametern , die angepasst werden können, insbesondere in Bezug auf den Garbage Collector. Diese Optionen sind nicht "einfach" - die Standardeinstellungen sind für die meisten Anwendungen gut. Um eine bessere Leistung zu erzielen, müssen Sie genau verstehen, was die Optionen bewirken und wie sich Ihre Anwendung verhält.

Michael Borgwardt
quelle
1
+1: im Grunde das, was ich in meiner Antwort geschrieben habe, vielleicht eine bessere Formulierung.
Klaim
1
+1: Sehr gute Punkte, sehr prägnant erklärt: "Das ist ziemlich schwierig ... aber wenn es richtig gemacht wird, kann es zu einer absolut atemberaubenden Leistung führen. Natürlich zahlen Sie dafür mit dem Potenzial für alle Arten von schrecklichen Fehlern . "
Giorgio
1
@ MartinBa: Sie zahlen mehr für die Optimierung der Speicherverwaltung. Wenn Sie nicht versuchen, die Speicherverwaltung zu optimieren, ist die C ++ - Speicherverwaltung nicht so schwierig (vermeiden Sie sie vollständig über STL oder machen Sie es mit RAII relativ einfach). Natürlich erfordert die Implementierung von RAII in C ++ mehr Codezeilen als nichts in Java (dh weil Java dies für Sie erledigt).
Brian
3
@ Martin Ba: Grundsätzlich ja. Baumelnde Zeiger, Pufferüberläufe, nicht initialisierte Zeiger, Fehler in der Zeigerarithmetik, alles Dinge, die ohne manuelle Speicherverwaltung einfach nicht existieren. Um den Speicherzugriff zu optimieren, müssen Sie viel manuelles Speichermanagement durchführen.
Michael Borgwardt
1
Es gibt ein paar Dinge, die Sie in Java tun können. Eines ist das Objekt-Pooling, das die Wahrscheinlichkeit der Speicherlokalität von Objekten maximiert (im Gegensatz zu C ++, wo es die Speicherlokalität garantieren kann).
RokL
5

[...] (gewährt in der Mikrosekundenumgebung) [...]

Mikrosekunden summieren sich, wenn wir Millionen bis Milliarden von Dingen durchlaufen. Eine persönliche vtune / Mikrooptimierungssitzung aus C ++ (keine algorithmischen Verbesserungen):

T-Rex (12.3 million facets):
Initial Time: 32.2372797 seconds
Multithreading: 7.4896073 seconds
4.9201039 seconds
4.6946372 seconds
3.261677 seconds
2.6988536 seconds
SIMD: 1.7831 seconds
4-valence patch optimization: 1.25007 seconds
0.978046 seconds
0.970057 seconds
0.911041 seconds

Alles außer "Multithreading", "SIMD" (handgeschrieben, um den Compiler zu schlagen) und der 4-Valenz-Patch-Optimierung waren Speicheroptimierungen auf Mikroebene. Auch der ursprüngliche Code ab den Anfangszeiten von 32 Sekunden wurde bereits ziemlich stark optimiert (theoretisch optimale algorithmische Komplexität), und dies ist eine kürzlich durchgeführte Sitzung. Die Verarbeitung der Originalversion lange vor dieser letzten Sitzung dauerte mehr als 5 Minuten.

Die Optimierung der Speichereffizienz kann in einem Single-Thread-Kontext häufig von mehreren bis zu Größenordnungen und in Multithread-Kontexten hilfreich sein (die Vorteile eines effizienten Speicher-Rep multiplizieren sich häufig mit mehreren Threads in der Mischung).

Zur Bedeutung der Mikrooptimierung

Ich bin ein wenig aufgeregt über die Idee, dass Mikrooptimierungen Zeitverschwendung sind. Ich bin damit einverstanden, dass es ein guter allgemeiner Rat ist, aber nicht jeder tut es falsch, basierend auf Ahnungen und Aberglauben und nicht auf Messungen. Richtig gemacht, führt dies nicht unbedingt zu einer Mikrowirkung. Wenn wir Intels eigenen Embree (Raytracing-Kernel) nehmen und nur den einfachen skalaren BVH testen, den sie geschrieben haben (kein Ray-Paket, das exponentiell schwerer zu schlagen ist), und dann versuchen, die Leistung dieser Datenstruktur zu übertreffen, kann dies am meisten sein Demütigende Erfahrung, selbst für einen Veteranen, der jahrzehntelang daran gewöhnt war, Code zu profilieren und zu optimieren. Und das alles aufgrund von Mikrooptimierungen. Ihre Lösung kann über hundert Millionen Strahlen pro Sekunde verarbeiten, wenn ich Industrieprofis im Raytracing gesehen habe, die das können. '

Es gibt keine Möglichkeit, eine einfache Implementierung eines BVH mit nur einem algorithmischen Fokus vorzunehmen und mehr als hundert Millionen Primärstrahlschnittpunkte pro Sekunde gegen einen optimierenden Compiler (sogar Intels eigenen ICC) herauszuholen. Ein unkomplizierter erhält oft nicht einmal eine Million Strahlen pro Sekunde. Es sind Lösungen von professioneller Qualität erforderlich, um oft sogar einige Millionen Strahlen pro Sekunde zu erhalten. Es ist eine Mikrooptimierung auf Intel-Ebene erforderlich, um über hundert Millionen Strahlen pro Sekunde zu erhalten.

Algorithmen

Ich denke, Mikrooptimierung ist nicht wichtig, solange die Leistung auf der Ebene von Minuten bis Sekunden, z. B. Stunden bis Minuten, nicht wichtig ist. Wenn wir einen schrecklichen Algorithmus wie die Blasensortierung als Beispiel für eine Masseneingabe verwenden und ihn dann sogar mit einer grundlegenden Implementierung der Zusammenführungssortierung vergleichen, kann die Verarbeitung des ersteren Monate dauern, der letztere möglicherweise 12 Minuten von quadratischer vs linearithmischer Komplexität.

Der Unterschied zwischen Monaten und Minuten wird wahrscheinlich dazu führen, dass die meisten Menschen, auch diejenigen, die nicht in leistungskritischen Bereichen arbeiten, die Ausführungszeit als inakzeptabel betrachten, wenn Benutzer monatelang warten müssen, um ein Ergebnis zu erhalten.

Wenn wir die nicht mikrooptimierte, unkomplizierte Zusammenführungssortierung mit der Quicksortierung vergleichen (die der Zusammenführungssortierung überhaupt nicht algorithmisch überlegen ist und nur Verbesserungen auf Mikroebene für die Referenzlokalität bietet), wird die mikrooptimierte Quicksortierung möglicherweise abgeschlossen 15 Sekunden im Gegensatz zu 12 Minuten. Es kann durchaus akzeptabel sein, Benutzer 12 Minuten warten zu lassen (Kaffeepause).

Ich denke, dieser Unterschied ist für die meisten Menschen zwischen 12 Minuten und 15 Sekunden wahrscheinlich vernachlässigbar, und deshalb wird die Mikrooptimierung oft als nutzlos angesehen, da sie oft nur dem Unterschied zwischen Minuten und Sekunden entspricht und nicht Minuten und Monaten. Der andere Grund, warum ich es für nutzlos halte, ist, dass es oft auf Bereiche angewendet wird, die keine Rolle spielen: ein kleiner Bereich, der nicht einmal kurvenreich und kritisch ist und einen fragwürdigen Unterschied von 1% ergibt (was sehr wohl nur Rauschen sein kann). Aber für Leute, die sich für diese Art von Zeitunterschieden interessieren und bereit sind, sie zu messen und richtig zu machen, lohnt es sich, zumindest die Grundkonzepte der Speicherhierarchie zu beachten (insbesondere die oberen Ebenen in Bezug auf Seitenfehler und Cache-Fehler). .

Java lässt viel Raum für gute Mikrooptimierungen

Puh, sorry - mit dieser Art von Schimpfen beiseite:

Verhindert die "Magie" der JVM den Einfluss eines Programmierers auf Mikrooptimierungen in Java?

Ein bisschen, aber nicht so viel, wie die Leute vielleicht denken, wenn Sie es richtig machen. Wenn Sie beispielsweise Bildverarbeitung in nativem Code mit handgeschriebenem SIMD, Multithreading und Speicheroptimierungen (Zugriffsmuster und möglicherweise sogar Darstellung je nach Bildverarbeitungsalgorithmus) durchführen, können Sie problemlos 32 Millionen Pixel pro Sekunde für 32 Sekunden verarbeiten. Bit-RGBA-Pixel (8-Bit-Farbkanäle) und manchmal sogar Milliarden pro Sekunde.

Es ist unmöglich, in Java irgendwo in die Nähe zu kommen, wenn Sie sagen, dass Sie ein PixelObjekt erstellt haben (dies allein würde die Größe eines Pixels von 4 Byte auf 16 auf 64-Bit erhöhen).

Sie könnten jedoch viel näher kommen, wenn Sie das PixelObjekt meiden , ein Array von Bytes verwenden und ein ImageObjekt modellieren . Java ist dort immer noch ziemlich kompetent, wenn Sie anfangen, Arrays einfacher alter Daten zu verwenden. Ich habe diese Art von Dingen schon einmal in Java ausprobiert und war ziemlich beeindruckt, vorausgesetzt , Sie erstellen nicht überall ein paar kleine Teeny-Objekte, die viermal größer als normal sind (z. B. Verwendung intanstelle von Integer), und beginnen, Bulk-Interfaces wie eine zu modellieren ImageSchnittstelle, nicht PixelSchnittstelle. Ich würde sogar sagen, dass Java mit der C ++ - Leistung mithalten kann, wenn Sie einfache alte Daten und keine Objekte (große Arrays von floatz Float. B. nicht ) durchlaufen .

Vielleicht noch wichtiger als die Speichergrößen ist, dass ein Array von inteine zusammenhängende Darstellung garantiert. Ein Array von Integernicht. Kontiguität ist häufig für die Referenzlokalität wesentlich, da mehrere Elemente (z. intsB. 16 ) alle in eine einzelne Cache-Zeile passen und möglicherweise vor der Räumung mit effizienten Speicherzugriffsmustern zusammen zugegriffen werden können. In der Zwischenzeit kann eine einzelne Integerirgendwo im Speicher gestrandet sein, wobei der umgebende Speicher irrelevant ist, nur um diesen Speicherbereich in eine Cache-Zeile zu laden, nur um eine einzelne Ganzzahl vor der Räumung zu verwenden, im Gegensatz zu 16 Ganzzahlen. Auch wenn wir wunderbar Glück und Umgebung hattenIntegersWenn alle im Speicher nebeneinander liegen, können wir nur 4 in eine Cache-Zeile einfügen, auf die vor der Räumung zugegriffen werden kann, da Integersie viermal größer ist, und das ist im besten Fall.

Und es gibt viele Mikrooptimierungen, da wir unter derselben Speicherarchitektur / -hierarchie vereint sind. Speicherzugriffsmuster spielen keine Rolle, egal welche Sprache Sie verwenden. Konzepte wie das Kacheln / Blockieren von Schleifen werden in C oder C ++ im Allgemeinen weitaus häufiger angewendet, aber sie kommen Java ebenso zugute.

Ich habe kürzlich in C ++ gelesen, dass manchmal die Reihenfolge der Datenelemente Optimierungen liefern kann, [...]

Die Reihenfolge der Datenelemente spielt in Java im Allgemeinen keine Rolle, aber das ist meistens eine gute Sache. In C und C ++ ist es aus ABI-Gründen oft wichtig, die Reihenfolge der Datenelemente beizubehalten, damit Compiler sich nicht damit anlegen. Dort arbeitende menschliche Entwickler müssen darauf achten, ihre Datenelemente in absteigender Reihenfolge (größte bis kleinste) anzuordnen, um zu vermeiden, dass beim Auffüllen Speicherplatz verschwendet wird. Mit Java kann die JIT anscheinend die Mitglieder im laufenden Betrieb für Sie neu anordnen, um eine korrekte Ausrichtung zu gewährleisten und gleichzeitig das Auffüllen zu minimieren. Vorausgesetzt, dies ist der Fall, automatisiert dies etwas, was durchschnittliche C- und C ++ - Programmierer häufig schlecht machen können, und verschwendet auf diese Weise Speicher ( Dies verschwendet nicht nur Speicher, sondern verschwendet häufig Geschwindigkeit, indem der Schritt zwischen AoS-Strukturen unnötig erhöht und mehr Cache-Fehler verursacht werden. Es' Es ist eine sehr roboterhafte Sache, Felder neu anzuordnen, um die Polsterung zu minimieren. Idealerweise beschäftigen sich Menschen damit nicht. Die einzige Zeit, in der die Feldanordnung auf eine Weise von Bedeutung sein kann, bei der ein Mensch die optimale Anordnung kennen muss, ist, wenn das Objekt größer als 64 Byte ist und wir Felder basierend auf dem Zugriffsmuster (nicht optimaler Auffüllung) anordnen - in diesem Fall Dies könnte ein menschlicheres Unterfangen sein (erfordert das Verständnis kritischer Pfade, von denen einige Informationen sind, die ein Compiler möglicherweise nicht vorhersehen kann, ohne zu wissen, was Benutzer mit der Software tun werden).

Wenn nicht, könnten die Leute Beispiele dafür geben, welche Tricks Sie in Java verwenden können (neben einfachen Compiler-Flags).

Der größte Unterschied in Bezug auf eine optimierende Mentalität zwischen Java und C ++ besteht für mich darin, dass Sie in C ++ in einem leistungskritischen Szenario möglicherweise Objekte verwenden können, die ein wenig (winzig) mehr als Java sind. Zum Beispiel kann C ++ eine Ganzzahl ohne jeglichen Overhead in eine Klasse einbinden (überall Benchmarking). Java muss diesen Overhead für Metadatenzeiger + Ausrichtungsauffüllung pro Objekt haben, weshalb er Booleangrößer ist als boolean(aber im Gegenzug bietet er einheitliche Vorteile der Reflexion und die Möglichkeit, alle Funktionen zu überschreiben, die nicht finalfür jedes einzelne UDT markiert sind ).

In C ++ ist es etwas einfacher, die Kontiguität von Speicherlayouts über inhomogene Felder hinweg zu steuern (z. B. Verschachtelung von Floats und Ints in ein Array durch eine Struktur / Klasse), da die räumliche Lokalität häufig verloren geht (oder zumindest die Kontrolle verloren geht). in Java beim Zuweisen von Objekten über den GC.

... aber oft teilen die leistungsstärksten Lösungen diese ohnehin auf und verwenden ein SoA-Zugriffsmuster über zusammenhängende Arrays einfacher alter Daten. Für die Bereiche, in denen Spitzenleistung erforderlich ist, sind die Strategien zur Optimierung des Speicherlayouts zwischen Java und C ++ häufig dieselben. Oft müssen Sie diese winzigen objektorientierten Schnittstellen zugunsten von Schnittstellen im Sammlungsstil abreißen, die beispielsweise Hot / Kaltfeldaufteilung, SoA-Wiederholungen usw. Inhomogene AoSoA-Wiederholungen scheinen in Java unmöglich zu sein (es sei denn, Sie haben nur ein rohes Array von Bytes oder ähnliches verwendet), aber dies ist in seltenen Fällen der Fall, in denen beideSequentielle und Direktzugriffsmuster müssen schnell sein und gleichzeitig eine Mischung von Feldtypen für heiße Felder aufweisen. Für mich ist der größte Teil des Unterschieds in der Optimierungsstrategie (auf der allgemeinen Ebene) zwischen diesen beiden umstritten, wenn Sie nach Spitzenleistungen streben.

Die Unterschiede variieren erheblich, wenn Sie einfach nach einer "guten" Leistung greifen. Wenn Sie nicht so viel mit kleinen Objekten wie Integervs. tun intkönnen, kann dies eher eine PITA sein, insbesondere in Bezug auf die Art und Weise, wie sie mit Generika interagiert . Es ist etwas schwieriger, nur eine generische Datenstruktur als zentrales Optimierungsziel in Java zu erstellen, das für usw. funktioniert int, floatwährend diese größeren und teuren UDTs vermieden werden. In den leistungskritischsten Bereichen müssen jedoch häufig eigene Datenstrukturen von Hand gerollt werden ohnehin auf einen ganz bestimmten Zweck abgestimmt, so dass es nur für Code ärgerlich ist, der nach guter Leistung strebt, aber nicht nach Spitzenleistung.

Objekt-Overhead

Beachten Sie, dass der Overhead von Java-Objekten (Metadaten und Verlust der räumlichen Lokalität und vorübergehender Verlust der zeitlichen Lokalität nach einem anfänglichen GC-Zyklus) häufig sehr groß ist für Dinge, die wirklich klein sind (wie intvs. Integer) und die in einer Datenstruktur millionenfach gespeichert werden weitgehend zusammenhängend und in sehr engen Schleifen zugänglich. Dieses Thema scheint sehr sensibel zu sein, daher sollte ich klarstellen, dass Sie sich bei großen Objekten wie Bildern keine Gedanken über den Objekt-Overhead machen möchten, sondern nur bei wirklich winzigen Objekten wie einem einzelnen Pixel.

Wenn jemand Zweifel an diesem Teil hat, würde ich vorschlagen, einen Benchmark zwischen der Summierung einer Million Zufallszahlen intsund einer Million Zufallszahlen Integerszu erstellen und dies wiederholt zu tun (der IntegersWille wird nach einem anfänglichen GC-Zyklus im Speicher neu gemischt).

Ultimativer Trick: Schnittstellendesigns, die Raum für Optimierungen lassen

Also der ultimative Java-Trick, wie ich es sehe, wenn Sie es mit einem Ort zu tun haben, der eine schwere Last über kleinen Objekten bewältigt (z. B. a Pixel, ein 4-Vektor, eine 4x4-Matrix, a Particle, möglicherweise sogar ein, Accountwenn er nur wenige kleine Objekte hat Felder) besteht darin, die Verwendung von Objekten für diese kleinen Dinge zu vermeiden und Arrays (möglicherweise miteinander verkettet) aus einfachen alten Daten zu verwenden. Die Objekte wurden dann Sammlung Schnittstellen wie Image, ParticleSystem, Accounts, eine Sammlung von Matrizen oder Vektoren, usw. einzelner Index zugegriffen werden kann, zB Dies ist auch einer der ultimative Design - Tricks in C und C ++, da auch ohne dieses Grundobjekt Aufwand und Durch die Modellierung der Schnittstelle auf der Ebene eines einzelnen Partikels werden die effizientesten Lösungen verhindert.

ChrisF
quelle
1
Angesichts der Tatsache, dass eine schlechte Leistung in der Masse tatsächlich eine gute Chance hat, die Spitzenleistung in den kritischen Bereichen zu überwältigen, kann man den Vorteil einer guten Leistung nicht völlig außer Acht lassen. Und der Trick, ein Array von Strukturen in eine Struktur von Arrays umzuwandeln, bricht etwas zusammen, wenn auf alle (oder fast alle) Werte, die eine der ursprünglichen Strukturen umfassen, gleichzeitig zugegriffen wird. Übrigens: Ich sehe, dass Sie viele alte Beiträge ausgraben und Ihre eigene gute Antwort hinzufügen, manchmal sogar die gute Antwort ;-)
Deduplicator
1
@Deduplicator Hoffe, ich ärgere die Leute nicht, indem ich zu viel stoße! Dieser hat ein bisschen Ranty bekommen - vielleicht sollte ich es ein bisschen verbessern. SoA vs. AoS ist für mich oft eine schwierige Frage (sequentieller vs. zufälliger Zugriff). Ich weiß selten im Voraus, welches ich verwenden soll, da es in meinem Fall oft eine Mischung aus sequentiellem und wahlfreiem Zugriff gibt. Die wertvolle Lektion, die ich oft gelernt habe, ist das Entwerfen von Schnittstellen, die genügend Platz zum Spielen mit der Datendarstellung lassen - etwas sperrigere Schnittstellen, die nach Möglichkeit über große Transformationsalgorithmen verfügen (manchmal nicht möglich, wenn hier und da zufällig auf winzige Bits zugegriffen wird).
1
Nun, ich habe es nur bemerkt, weil die Dinge sehr langsam sind. Und ich nahm mir Zeit für jeden.
Deduplikator
Ich frage mich wirklich, warum ich weggegangen bin user204677. So eine tolle Antwort.
Oligofren
3

Es gibt einen mittleren Bereich zwischen Mikrooptimierung einerseits und guter Wahl des Algorithmus andererseits.

Es ist der Bereich der Beschleunigungen mit konstantem Faktor und kann Größenordnungen ergeben.
Die Art und Weise, wie dies geschieht, besteht darin, ganze Bruchteile der Ausführungszeit abzuschneiden, wie zuerst 30%, dann 20% der verbleibenden Zeit, dann 50% davon usw. für mehrere Iterationen, bis kaum noch etwas übrig ist.

Sie sehen dies nicht in kleinen Demo-Programmen. Wo Sie sehen, ist es in großen seriösen Programmen mit vielen Klassendatenstrukturen, in denen der Aufrufstapel normalerweise viele Schichten tief ist. Ein guter Weg, um die Beschleunigungsmöglichkeiten zu finden, besteht darin , zufällige Stichproben des Programmstatus zu untersuchen.

Im Allgemeinen bestehen die Beschleunigungen aus Dingen wie:

  • Minimieren von Aufrufen newdurch Zusammenführen und Wiederverwenden alter Objekte,

  • Dinge erkennen, die aus Gründen der Allgemeinheit getan werden, anstatt tatsächlich notwendig zu sein,

  • Überarbeitung der Datenstruktur durch Verwendung verschiedener Erfassungsklassen, die das gleiche Big-O-Verhalten aufweisen, jedoch die tatsächlich verwendeten Zugriffsmuster nutzen.

  • Speichern von Daten, die durch Funktionsaufrufe erfasst wurden, anstatt die Funktion erneut aufzurufen (Es ist eine natürliche und amüsante Tendenz von Programmierern anzunehmen, dass Funktionen mit kürzeren Namen schneller ausgeführt werden.)

  • ein gewisses Maß an Inkonsistenz zwischen redundanten Datenstrukturen zu tolerieren, anstatt zu versuchen, sie vollständig mit Benachrichtigungsereignissen in Einklang zu bringen;

  • usw. usw.

Aber natürlich sollte keines dieser Dinge getan werden, ohne dass sich durch Probenahme zuerst herausstellt, dass es sich um Probleme handelt.

Mike Dunlavey
quelle
2

Java (soweit mir bekannt ist) gibt Ihnen keine Kontrolle über die Speicherorte von Variablen im Speicher, sodass es Ihnen schwerer fällt, Dinge wie falsches Teilen und Ausrichten von Variablen zu vermeiden (Sie können eine Klasse mit mehreren nicht verwendeten Mitgliedern auffüllen). Eine andere Sache, von der ich nicht glaube, dass Sie sie nutzen können, sind Anweisungen wie mmpause, aber diese Dinge sind CPU-spezifisch. Wenn Sie also glauben , dass Sie sie brauchen, ist Java möglicherweise nicht die zu verwendende Sprache.

Es gibt die Unsafe- Klasse, die Ihnen Flexibilität in C / C ++ bietet, aber auch die Gefahr von C / C ++ birgt.

Dies kann Ihnen helfen, den Assemblycode zu überprüfen, den die JVM für Ihren Code generiert

Informationen zu einer Java-App, die diese Art von Details betrachtet, finden Sie im von LMAX veröffentlichten Disruptor-Code

James
quelle
2

Diese Frage ist sehr schwer zu beantworten, da sie von Sprachimplementierungen abhängt.

Im Allgemeinen gibt es heutzutage sehr wenig Raum für solche "Mikrooptimierungen". Der Hauptgrund ist, dass Compiler solche Optimierungen während der Kompilierung nutzen. Beispielsweise gibt es keinen Leistungsunterschied zwischen Operatoren vor und nach dem Inkrementieren in Situationen, in denen ihre Semantik identisch ist. Ein anderes Beispiel wäre zum Beispiel eine Schleife wie diese, for(int i=0; i<vec.size(); i++)in der man argumentieren könnte, anstatt die aufzurufensize()Elementfunktion während jeder Iteration Es ist besser, die Größe des Vektors vor der Schleife zu ermitteln und dann mit dieser einzelnen Variablen zu vergleichen, um so einen Aufruf der Funktion pro Iteration zu vermeiden. Es gibt jedoch Fälle, in denen ein Compiler diesen dummen Fall erkennt und das Ergebnis zwischenspeichert. Dies ist jedoch nur möglich, wenn die Funktion keine Nebenwirkungen hat und der Compiler sicher sein kann, dass die Vektorgröße während der Schleife konstant bleibt, sodass sie nur für ziemlich triviale Fälle gilt.

zxcdw
quelle
Was den zweiten Fall betrifft, glaube ich nicht, dass der Compiler ihn in absehbarer Zeit optimieren kann. Um festzustellen, dass es sicher ist, vec.size () zu optimieren, muss nachgewiesen werden, dass sich die Größe ändert, wenn sich der Vektor / Verlust innerhalb der Schleife nicht ändert, was meiner Meinung nach aufgrund des Stoppproblems unentscheidbar ist.
Lie Ryan
@LieRyan Ich habe mehrere (einfache) Fälle gesehen, in denen der Compiler genau identische Binärdateien generiert hat, wenn das Ergebnis manuell "zwischengespeichert" wurde und size () aufgerufen wurde. Ich habe Code geschrieben und es stellt sich heraus, dass das Verhalten stark von der Funktionsweise des Programms abhängt. Es gibt Fälle, in denen der Compiler garantieren kann, dass sich die Vektorgröße während der Schleife nicht ändern kann, und es gibt Fälle, in denen er dies nicht garantieren kann, ähnlich wie das von Ihnen erwähnte Stoppproblem. Im
Moment
2
@Lie Ryan: Viele Dinge, die im allgemeinen Fall unentscheidbar sind, sind für bestimmte, aber häufige Fälle vollkommen entscheidbar, und das ist wirklich alles, was Sie hier brauchen.
Michael Borgwardt
@LieRyan Wenn Sie nur constMethoden für diesen Vektor aufrufen, werden es sicher viele optimierende Compiler herausfinden.
K.Steff
in C #, und ich glaube, ich habe auch in Java gelesen, wenn Sie keine Cache-Größe haben, weiß der Compiler, dass er die Überprüfungen entfernen kann, um festzustellen, ob Sie außerhalb der Array-Grenzen liegen, und wenn Sie die Cache-Größe verwenden, muss er die Überprüfungen durchführen , die in der Regel mehr kosten, als Sie durch Caching sparen. Der Versuch, Optimierer auszutricksen, ist selten ein guter Plan.
Kate Gregory
1

könnten Leute Beispiele geben, welche Tricks Sie in Java verwenden können (neben einfachen Compiler-Flags).

Berücksichtigen Sie neben Verbesserungen der Algorithmen auch die Speicherhierarchie und die Verwendung durch den Prozessor. Die Reduzierung der Speicherzugriffslatenzen bietet große Vorteile, wenn Sie erst einmal verstanden haben, wie die betreffende Sprache ihren Datentypen und Objekten Speicher zuweist.

Java-Beispiel für den Zugriff auf ein Array mit 1000 x 1000 Zoll

Betrachten Sie den folgenden Beispielcode - er greift auf denselben Speicherbereich zu (ein 1000x1000-Array von Ints), jedoch in einer anderen Reihenfolge. Auf meinem Mac mini (Core i7, 2,7 GHz) ist die Ausgabe wie folgt: Dies zeigt, dass das Durchlaufen des Arrays durch Zeilen die Leistung mehr als verdoppelt (durchschnittlich über jeweils 100 Runden).

Processing columns by rows*** took 4 ms (avg)
Processing rows by columns*** took 10 ms (avg) 

Dies liegt daran, dass das Array so gespeichert wird, dass aufeinanderfolgende Spalten (dh int-Werte) nebeneinander im Speicher platziert werden, während aufeinanderfolgende Zeilen dies nicht tun. Damit der Prozessor die Daten tatsächlich verwenden kann, müssen sie in seine Caches übertragen werden. Die Übertragung des Speichers erfolgt durch einen Byteblock, der als Cache-Zeile bezeichnet wird. Das Laden einer Cache-Zeile direkt aus dem Speicher führt zu Latenzen und verringert somit die Leistung eines Programms.

Für den Core i7 (Sandy Bridge) enthält eine Cache-Zeile 64 Bytes, sodass jeder Speicherzugriff 64 Bytes abruft. Da der erste Test in einer vorhersagbaren Reihenfolge auf den Speicher zugreift, ruft der Prozessor Daten vorab ab, bevor sie tatsächlich vom Programm verbraucht werden. Insgesamt führt dies zu einer geringeren Latenz bei Speicherzugriffen und verbessert somit die Leistung.

Mustercode:

  package test;

  import java.lang.*;

  public class PerfTest {
    public static void main(String[] args) {
      int[][] numbers = new int[1000][1000];
      long startTime;
      long stopTime;
      long elapsedAvg;
      int tries;
      int maxTries = 100;

      // process columns by rows 
      System.out.print("Processing columns by rows");
      for(tries = 0, elapsedAvg = 0; tries < maxTries; tries++) {
       startTime = System.currentTimeMillis();
       for(int r = 0; r < 1000; r++) {
         for(int c = 0; c < 1000; c++) {
           int v = numbers[r][c]; 
         }
       }
       stopTime = System.currentTimeMillis();
       elapsedAvg += ((stopTime - startTime) - elapsedAvg) / (tries + 1);
      }

      System.out.format("*** took %d ms (avg)\n", elapsedAvg);     

      // process rows by columns
      System.out.print("Processing rows by columns");
      for(tries = 0, elapsedAvg = 0; tries < maxTries; tries++) {
       startTime = System.currentTimeMillis();
       for(int c = 0; c < 1000; c++) {
         for(int r = 0; r < 1000; r++) {
           int v = numbers[r][c]; 
         }
       }
       stopTime = System.currentTimeMillis();
       elapsedAvg += ((stopTime - startTime) - elapsedAvg) / (tries + 1);
      }

      System.out.format("*** took %d ms (avg)\n", elapsedAvg);     
    }
  }
Miraculixx
quelle
1

Die JVM kann und wird häufig stören, und der JIT-Compiler kann sich zwischen den Versionen erheblich ändern. Einige Mikrooptimierungen sind in Java aufgrund von Sprachbeschränkungen, wie z. B. Hyper-Threading-freundlich oder der SIMD-Sammlung der neuesten Intel-Prozessoren, nicht möglich.

Es wird empfohlen, einen sehr informativen Blog zu diesem Thema von einem der Disruptor- Autoren zu lesen:

Man muss sich immer fragen, warum man sich die Mühe macht, Java zu verwenden, wenn man Mikrooptimierungen wünscht. Es gibt viele alternative Methoden zur Beschleunigung einer Funktion, beispielsweise die Verwendung von JNA oder JNI zur Weitergabe an eine native Bibliothek.

Steve-o
quelle