Wie java programm noch schneller machen?

[java-coderrr]

Hallo,

ich hab ein Stück code, welches ich noch schneller machen muss. (weils eine Hausaufgabe ist, darf ich es leider nicht veröffentlichen!)

Der ganze Code steht in einer Klasse (also ich kann nur 1 Klasse abgeben). Welche allgemeinen Methoden zur Beschleunigung gibt es?

Meine bisherigen Gedankengänge wären:
*) Sämtliche rekuriven Funktionen auf Schleifen reduzieren (ein rekursiver Funktionsaufruf dauert länger, als eine Schleife?)
*) Bestimmte Teilberechnungen so früh wie möglich machen, damit ich mehrere "kleine Aufgaben löse" und nicht 1 extrem große.
*) Den Garbage Collector für den Zeitabschnitt deaktivieren, unter welchem die Zeit gemessen wird (?)
*) Funktionsaufrufe minimieren (obwohl dadurch der Code an schönheit verliert)
*) Eine lokale Klasse mit extends Thread implementieren und Zeitkritische Abläufe parallel abarbeiten.

Leider fallen mir nicht wirklich recht viel mehr Ideen ein. Mein Programm benötigt zur Zeit um 15 Testinstanzen abzuarbeiten ca. 8 Sekunden. Hat jemand noch weitere Ideen? (also allgemeine, ich weiß, die Aussagekraft ist ziemlich beschränkt, wenn man keinen konkreten Code vor sich hat, aber vielleicht fällt jemand anderen noch etwas gutes ein)

 

[bygones]

das ist nicht ernsthaft eine Hausaufgabe ? bekommt derjenige die 1 der es in 7,46s schafft ?

deine Punkte sind z.T. marginal und a) nicht wirklich zeitkritisch und b) verschlimmern sie eher deinen Code.

Ohne Code wird dir hier keiner helfen können. Allgemein Ratschläge sind immer schwer und nicht wirklich sinnvoll.

*immer noch Kopfschüttlend über eine solche Aufgabe*

 

[maki]

Nimm einen Profiler wie VisualVM und miss die langsamsten Stellen im Code, diese kannst du dann optimieren.
Stelle den Heap der VM Optimal ein, wenn du Xms & Xmx auf denselben Wert legst, bringt das oft etwas.
Auch solltest du die Server VM nutzen anstatt der Client VM (-server parameter, braucht aber ein JDK)

Sämtliche rekuriven Funktionen auf Schleifen reduzieren (ein rekursiver Funktionsaufruf dauert länger, als eine Schleife?)

Würde imho nix messbares bringen.

Bestimmte Teilberechnungen so früh wie möglich machen, damit ich mehrere "kleine Aufgaben löse" und nicht 1 extrem große.

Bringt auch nix.

Den Garbage Collector für den Zeitabschnitt deaktivieren, unter welchem die Zeit gemessen wird (?)

Unmöglich.

Funktionsaufrufe minimieren (obwohl dadurch der Code an schönheit verliert)

Bringt auch nix, eher im Gegenteil.

Eine lokale Klasse mit extends Thread implementieren und Zeitkritische Abläufe parallel abarbeiten.

Könnte etwas bringen, kommt aber auf das Problem an, macht den Code auf jedenfall viel komplexer.

 

[Landei]

Bevor du an solche Mikro-Optimierungen denkst, schau dir erst noch mal ganz genau deinen Algorithmus an. Da lassen sich oft Größenordnungen sparen.

Dann nimm einen Profiler, um genau die "langsamen" Stellen zu finden. Alles andere ist nur Rumgestocher im Nebel.

Und erst dann versuche Optimierungen. Threads kannst du sein lassen, wenn du nicht sicher sein kannst, ob du wirklich einen Multicore/Multiprozessor zur Verfügung hast. Mit anderen Worten: Die gleichen Threads, die den Code auf deinem Dual-Core um 30% schneller machen, können ihn auf Single-Core um 50% ausbremsen. Rumgefummel am Garbage-Collector ist normalerweise eine schlechte Idee - höchstens die gesamte GC-Strategie könnte man mal testweise umschalten.

Nach dem Profiling kannst du dann Sachen ausprobieren wie
- Objekte wiederverwenden (insbesondere Sachen wie Calendar, Date, Random, Formate, DB-Connections)
- eine andere JVM (z.B. JRockit)
- JVM mehr Speicher zuweisen
- Loop Unrolling
- Bit Hacks
- Methoden private bzw. final machen

Erwarte aber nicht zuviel, moderne JIT-Compiler optimieren die "heißen" Stellen schon wie blöd, und viele vermeintliche Optimierungen erweisen sich als langsamer als das Original.

 

[Andi_CH]

Guck mal da!


new braucht sehr lange -> alles was du brauchst ausserhalb der loops allozieren

ob eine Rekursion langsamer als ein loop ist, ist fraglich
Prozeduraufrufe sind schnell
Parallelisieren bringt nichts, wenn du nur rechnest und auf nichts warten musst. Hat es wait drin oder wird von Hardware gelesen?

15 Schritte 8 Sekunden - mein Gott wo wird da Zeit verbraten?


und last but no least -> Guck mal da!

Na ja, doppelt genäht hält besser ;-)

 

[java-coderrr]

Hm ok danke schonmal.

Naja, Aufgabe ist es nur, jeden Testcase für sich unter 15 Sekunden zu schaffen. (geht dabei um Algorithmik). Also 15 Testinstanzen in 225 Sekunden. Ich brauch daweil 8 Sekunden. U.a. gibts halt den wettbewerb, wer einen schnelleren (eleganteren + weniger Speicherplatz verbrauchenden) Algorithmus findet, kriegt zusatzpunkte. Und deshalb auch rein als interesse an java wollte ich wissen, was überhaupt möglich wäre.

Im Prinzip geht es darum, dass ich einen Binären Baum habe und diesen erstellen muss. Jetzt war mein Gedanke, dass ich das linke Kind und das rechte Kind parallel erzeuge. Dadurch würde das linke Kind auf einem kern und das rechte Kind auf dem anderen Kern erzeugt (?).

Die Teilung der großen Aufgabe in kleinere ergibt durchaus sinn (ich habs vielleicht etwas schlecht formuliert), da wenn ich für einen Knoten die berechnung mache, es einen Teil schon vorberechnet und in den beiden Kindern des Knotens, die Berechnung nicht mehr gemacht werden muss(daher mache ich die berechnung nur 1 mal anstelle von 2 mal) bzw. bei größeren bäumen nur 1 mal anstelle von x mal .

Das Größte Problem ist, dass ich für die längste Testinstanz 250 ms benötige, davon aber 180 ms Funktionsaufrufe von einem Framework sind, welches ich mitbekommen habe. (und diese Funktionsaufrufe kann ich nicht vereinfachen). Einzige möglichkeit wäre wieder, über eine lokale Klasse die Klasse des Framesworks zu extenden und die Funktion selbst umzuschreiben (aber das ist doch absolut nicht schön, wenn ich das über lokale Klassen mache....)

Aber danke für eure Antworten (falls jemand doch noch gute Ideen hat, bitte nur her damit!)

 

[java-coderrr]

Aja noch was, nur aus Interesse:
Verändere ich die Anweisung i /= 2; auf einen right shift, hat das dann geschwindigkeitsförderung? Oder ist der Compiler selbst so klug, dass er das optimiert?

@Andi_CH:
Was meinst du genau mit "alles was du brauchst ausserhalb der loops allozieren"?

 

[ARadauer]

“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.”

Das sind ja nette Hausaufgaben, anstatt den leuten zu zeigen wie sie schönen sauberen Code schreiben, werden sie darauf hingetrimmt das ganze zu vermurksen...

*) Funktionsaufrufe minimieren (obwohl dadurch der Code an schönheit verliert)

toller Lehrer bring ja seine Schüler auf gute Ideen


Also meine Meinung, ohne Code kann man echts nichts sagen. Wenn du aber schon im Sekunden bereich bist, bin ich mir sicher dass es mit Sinnvollen Erweiterungen was zu hohlen gibt. Du kannst mir ja den Code mal als PM schicken... mich würd das echt interessieren..

 

[maki]

Was meinst du genau mit "alles was du brauchst ausserhalb der loops allozieren"?

Das weis er wohl selber nicht so genau, Sinn macht es jedenfalls keinen.

 

[java-coderrr]

Achso! Er meint, nicht innerhalb einer schleife immer wieder new aufzurufen, sondern nur ein einziges mal außerhalb der schleife.... -.- Danke für den Tipp =)

 

[Painii]

Achso! Er meint, nicht innerhalb einer schleife immer wieder new aufzurufen, sondern nur ein einziges mal außerhalb der schleife.... -.- Danke für den Tipp =)

Das ist denk ich das was am schnellsten Performance bringt.
Und lange leere Schleifen (bis 100000000 zählen um beim letzten Wert einmal was zu machen) vermeiden 🙂

 

[ARadauer]

Und lange leere Schleifen (bis 100000000 zählen um beim letzten Wert einmal was zu machen) vermeiden

warum sollte man sowas tun?

 

[Sanix]

“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.”

Das sind ja nette Hausaufgaben, anstatt den leuten zu zeigen wie sie schönen sauberen Code schreiben, werden sie darauf hingetrimmt das ganze zu vermurksen...

(...)

OT:
Finde ich nicht. Ich besuche auch ein Modul Effiziente Algorithmen. Da kriegt man noch oft "vermurksten" Code, da die Dozenten halt eher in der Mathematik, Algorithmik stark sind als im Programmieren. Für das saubere Programmieren gibt es zig andere Module.

@Andi_CH
Parallellisierung bringt etwas bei Multi Core CPUs. Man kann z.B. eine Matrix-Multiplikation von mehreren Threads erledigen lassen und erhält einen enormen Zeitgewinn.

 

[maki]

warum sollte man sowas tun?

Aus demselben grund weswegen man überflüssige Objekte in Schleifen allokiert 😉

Da kriegt man noch oft "vermurksten" Code, da die Dozenten halt eher in der Mathematik, Algorithmik stark sind als im Programmieren.

Klingt nach einem Kurs den jeder Programmierer braucht...

 

[Empire Phoenix]

Du willst besser nicht wissen was wir bei uns inner uni an code bekommen:
...
Die String m2s(Integer[][] I) ist mein Favorit ganz klare sache...

 

[Andi_CH]

Das weis er wohl selber nicht so genau, Sinn macht es jedenfalls keinen.

Jetzt erzählst du aber Käse!

for(int i=0; i<10000; i++) {
   MeineKlasse kkk = new MeineKlasse();
   kkk.machWasGanzSchlaues();
}

braucht garantiert viel mehr Zeit als

MeineKlasse kkk = new MeineKlasse();
for(int i=0; i<10000; i++) {
   kkk.init();
   kkk.machWasGanzSchlaues();
}

 

[Sanix]

Klingt nach einem Kurs den jeder Programmierer braucht...

Habe ich das behauptet? Ich finds jedenfalls interessant und ist sicher nicht unnötig.

 

[Andi_CH]

@Andi_CH
Parallellisierung bringt etwas bei Multi Core CPUs. Man kann z.B. eine Matrix-Multiplikation von mehreren Threads erledigen lassen und erhält einen enormen Zeitgewinn.

Stimmt - hab ich nicht dran gedacht - aber nur so viel Threads wie Kerne

 

[bygones]

braucht garantiert viel mehr Zeit als

garantiert schon mal gar nicht.... ich würde mich mit allgeimen performanz aussagen ganz zurückhalten.

allein schon - was steht im Konstruktor, was in der init methode ?

ansonsten hätte ich natürlich den beweis dass 1. soooo langsamer ist.

Performanz ist und bleibt eins der bösesten Gewänder mit denen Code verhunzt wird....

 

[maki]

Jetzt erzählst du aber Käse!
..

Nö, du konstruierst nur ein sehr seltsames Beispiel um deinen seltsame Aussage zu rechtfertigen 😉

Wenn du sagen würdest, dass wirklich überflüssige Objektinstanziierung vermieden werden sollte, dann kann man sich darauf einigen.
Die Frage ist nur, wann ist sie wirklich überflüssig und muss man das wirklich nochmals sagen?

 

[Andi_CH]

Nö, du konstruierst nur ein sehr seltsames Beispiel um deinen seltsame Aussage zu rechtfertigen 😉

Wenn du sagen würdest, dass wirklich überflüssige Objektinstanzierung vermieden werden sollte, dann kann man sich darauf einigen.
Die Frage ist nur, wann ist sie wirklich überflüssig und muss man das wirklich nochmals sagen?

Die Aussage ist gar nicht so seltsam und das Beispiel ist nicht mal konstruiert - ich entdecke immer wieder solchen und ähnlichen Schei.... in dem Code an dem ich arbeite. Es hat so viele Zeit und Memoryfresser (gewisse Kisten kommen sogar ins Swappen) drin, dass ich nebenbei darauf achte. Das Problem ist jeweils, dass es gar nicht so klar ersichtlich ist, wie ich es dargestellt habe)

Letzte Woche gefunden und eliminiert:
3 Klassen ohne Initialisierungsmethoden wurden in einem Loop (so 10'000 - 50'000 Durchgänge - es ist eine Näherungsberechnung) jedes mal neu instanziert und das nur um initialisierte Objekte zu haben.
(Vermutlich kam der gc gar nicht mehr zum Zug, denn das belegte Memory nahm in dieser Phase deutlich zu)

Früher eliminiert:
Bildung mehrerer Instanzen einer Klasse, obwohl es ein Singleton bzw sogar eine static Klasse auch getan hätte. (in dem Fall waren die Anzahl der new aufrufe nicht so relevant, aber Memory wurde unnötig belegt)

 

[maki]

Die Aussage ist gar nicht so seltsam und das Beispiel ist nicht mal konstruiert - ich entdecke immer wieder solchen und ähnlichen Schei.... in dem Code an dem ich arbeite. Es hat so viele Zeit und Memoryfresser (gewisse Kisten kommen sogar ins Swappen) drin, dass ich nebenbei darauf achte. Das Problem ist jeweils, dass es gar nicht so klar ersichtlich ist, wie ich es dargestellt habe)

Schon klar.
Aber dass es dabei um unnötige Objektinstanziierung geht ist auch klar.
Trotzdem muss man vor und nach der Änderung messen, ob sie wirklich relevant war.

Früher eliminiert:
Bildung mehrerer Instanzen einer Klasse, obwohl es ein Singleton bzw sogar eine static Klasse auch getan hätte. (in dem Fall waren die Anzahl der new aufrufe nicht so relevant, aber Memory wurde unnötig belegt)

Braucht weder ein Singleton (würg) noch eine static Klasse (? da verwechselst du wohl wieder etwas, Klasse <-> Objekt) zu sein, es reicht doch wenn das Objekt nur einmal instanziert wird.

 

[Andi_CH]

Ich verwechsle gar nichts! Schon gar nicht Klassen und Objekte

Eines war eine typische utility-Klasse -> die hab ich statisch gemacht, weil die relativ lokal benutzt wird.

Andere werden von so vielen Orten und Teilprojekten benutzt, dass ich daran lieber nicht all zu viel ändere ;-) und weitere waren zwar utility-ähnlich, aber je nach Situation (die ist aber ziemlich grundlegend ausgewählt) doch etwas unterschiedlich - ginge zu weit das jetzt zu erklären.

Singleton == Würg? (Die Frage meine ich ehrlich, aber das währe eher einen neuen Thread wert)
Ich hör das immer, aber ein Beweis, dass das auch so ist konnte mir noch niemand zeigen. (Es muss ja nicht das Singletonpattern sein - man kann auch eine Factory bauen die das sicherstellt)
-> Einsparung war konkret ca 1MB Memory - das ist doch was (eben vielleicht auch weil der gc nicht mehr nachkam)

Lieber einige Singletons als eine Kiste die swappt 🙂

 

[Gast2]

Singleton == Würg? (Die Frage meine ich ehrlich, aber das währe eher einen neuen Thread wert)
Ich hör das immer, aber ein Beweis, dass das auch so ist konnte mir noch niemand zeigen. (Es muss ja nicht das Singletonpattern sein - man kann auch eine Factory bauen die das sicherstellt)
-> Einsparung war konkret ca 1MB Memory - das ist doch was (eben vielleicht auch weil der gc nicht mehr nachkam)

Lieber einige Singletons als eine Kiste die swappt 🙂

Viele mögen keine Singletons. Erst recht nicht seit dem sich DI weitgehend durchgesetzt hat. Gibt es einige Diskussionen hier: z.B.: http://www.java-forum.org/java-basics-anfaenger-themen/97699-statische-klassen-singleton.html

 

[bygones]

Lieber einige Singletons als eine Kiste die swappt 🙂

Du darfst keine schlafenden Hunde wecken.... 😀

 

[maki]

Singleton == Würg?

Ja.

(Die Frage meine ich ehrlich, aber das währe eher einen neuen Thread wert)

Davon gibt es hier sowieso schon viel zu viele, einfach mal suchen.

Ich hör das immer, aber ein Beweis, dass das auch so ist konnte mir noch niemand zeigen.

Ach?
Schon mal einen Unittest für eine Klasse gesehen die ein Singleton per statischer Methode referenziert?
Die Vor- und Nachteile sollten doch schon lange klar sein.

-> Einsparung war konkret ca 1MB Memory - das ist doch was (eben vielleicht auch weil der gc nicht mehr nachkam)

Lieber einige Singletons als eine Kiste die swappt

1MB macht doch für den gc keinen Unterschied...
Kann ma aber auch ohne GoF Singleton lösen, muss sich ja nicht gleich mit der Pest infizieren um einen schnupfen loszuwerden.

 

[tfa]

Juchu! Eine Singleton-Diskussion! Genau das richtige für einen Freitag nachmittag.

Davon gibt es hier sowieso schon viel zu viele, einfach mal suchen.

Ich empfehle diesen hier 🙂
http://www.java-forum.org/softwareentwicklung/80674-singletons.html

 

[bygones]

Juchu! Eine Singleton-Diskussion! Genau das richtige für einen Freitag nachmittag.

ihr sollt doch keine schlafenden Hunde wecken 😀

ach und die Einsparung von 1Mb ist ja mal unvorstellbar... lass mich das nochmal durchgehen... 1Mb... whau

 

[ThreadPool]

ach und die Einsparung von 1Mb ist ja mal unvorstellbar... lass mich das nochmal durchgehen... 1Mb... whau

Lach nicht, wenn du mal ein halbes Jahr damit zugebracht hast eine Java-Anwendung zu beschleunigen da freust du dich über jedes MB, denn das was die meisten Java-Anwendungen langsam macht ist die verschwenderische und teils merkbefreite Art wie mit dem Speicher umgegangen wird. Zur Symptombekämpfung wird dann in der JVM sowas hier verwendet -XX:+UseParallelGC -XX:+AggressiveHeap, was auch wirklich was bringt aber letztendlich nur die Symptome lindert, skalieren wir die Anwendung dadurch auch nicht besser. Des Weiteren je weniger Speicher ein Objekt benötigt desto mehr geht letztendlich auch in den Prozessorchache und das ist gut, da der Zugriff darauf wesentlich schneller ist.

 

[Marco13]

Nur mal nebenbei: Ich finde die Aufgabe schon gerechtfertigt. Genau wie man das "schöne" Entwefen mal mit unrealistischen Blümchenwelt-Extremen lernt (Software planen, Spezifieren, UML verwenden und so... :lol: ) kann und sollte man IMHO auch mal versuchen, ganz bewußt auf Schönheit und Konventionen zu sch.en, und mit allen Mitteln "das letzte rauszukitzeln" - schon allein um zu erkennen, das 98% von dem, was man sich so spontqan und naiv als erstes an möglichen Optimierungen ausdenkt, nichts bringt 🙂 Oder in bezug auf die Profiler-Andeutungen: Angenommen, das besagte Modul IST das Bottleneck, und der Profiler sagt einem eben nicht, dass Divisionen langsamer sind als shifts oder wie viel Zeit genau eine Allokation eben braucht - dann kann man ja mal schauen, was sich rausholen läßt.

 

[Gelöschtes Mitglied 6946]

Jetzt erzählst du aber Käse!

for(int i=0; i<10000; i++) {
   MeineKlasse kkk = new MeineKlasse();
   kkk.machWasGanzSchlaues();
}

braucht garantiert viel mehr Zeit als

MeineKlasse kkk = new MeineKlasse();
for(int i=0; i<10000; i++) {
   kkk.init();
   kkk.machWasGanzSchlaues();
}

Hängt auch bissl davon ab, wie sehr die Methoden init und machWasGanzSchlaues reinhauen, die Instanziierung könnte dann schon nicht mehr ins Gewicht fallen - müsste man testen. Für solche Fälle könnte -XX:+DoEscapeAnalysis was bringen, denn Objekte, die nur temporär erzeugt werden, werden dann nicht auf dem Heap erzeugt, sondern auf dem Stack, wodurch es auch den Garbage Collector nicht belastet (oder so ähnlich), die Option haut u.U. schon gut rein.