Code Optimieren

[sanv]

Hallo,

ich versuche gerade den folgenden Code zu optimieren. Kann mir jemand dabei bitte weiterhelfen. Es handelt sich dabei um ein "Spiel" wo speziell dieser Bereich langsam ist und der Rest sollte nicht geandert werden.

 public int[] bearbeiteRahmen(final double x,  final double y, final double z) {
                if (sp_object==null) 
			sp_object= Frame.getSpObject();

                final Vector<Integer> erg = new Vector<Integer>();

                Thread t = new Thread(new Runnable() { 
			public void run() 	{
                        	for (int i=0 ; i<sp_object.length/2 ; ++i) {
                                	synchronized (erg) {
                                        	if (sp_object[i].schnitt(new MDaten(x,y,z))) {
                                                	erg.add(i);
                                        	}
                                	}
                        	}
                	}
		});

                t.start();

                for (int i=sp_object.length/2; i<sp_object.length ; ++i) {
                        synchronized (erg) {
                                if (sp_object[i].schnitt(new MDatenx,y,z))) {
                                        erg.add(i);
                                }
                        }
                }

                t.join();

                int[] daten = new int[erg.size()];

                for (int i=0 ; i<erg.size() ; ++i) {
                        daten [i] = erg.get(i);
                }
                Arrays.sort(daten);
                return daten;
        }

Das erste was ich zum optimieren gemacht habe ist folgendes:

Anstatt jedes mal eine neue Instanz von MDaten zu generien mache ich das hier:

MDaten object1 = new MDaten(x,y,z);

Und dieses "object1" gebes ich als parameter in die schnitt methode.

Was kann ich sonst noch machen ob den code zu optimieren/schneller zu machen.

Danke im Vorraus.

 

[bygones]

niemals code optimieren wenn man nicht stichhaltige beweise hat dass man unter performance leidet.

nie

lieber code verstaendlicher schreiben und besser

 

[objcler]

Vector ist böse.
Es mal ohne einen zweiten Thread probieren.
Rausfinden was genau in der Methode langsam ist und das dann optimieren.

 

[objcler]

niemals code optimieren wenn man nicht stichhaltige beweise hat dass man unter performance leidet.

nie

lieber code verstaendlicher schreiben und besser

Er schrieb doch: "Es handelt sich dabei um ein "Spiel" wo speziell dieser Bereich langsam ist " - ich nehme an, dass der Bereich so langsam ist, dass das Spiel keinen Sinn mehr macht. Sonst ist jeder Optimierungsversuch erstmal unnötig.

 

[bygones]

oh - standardantwort rausgehauen ;-)

 

[objcler]

oh - standardantwort rausgehauen ;-)

Ist ja auch in 99% der Threads, die was mit "Optimierung" zu tun haben die richtige.

 

[sanv]

danke fuer die schnellen antworten.

das ist der code den ich so bekommen habe, ich hab diesen nicht selber geschrieben.

wenn ich alles in einem thread mache ist es um einiges schneller. zB:

 final Vector<Integer> erg = new Vector<Integer>();
 
  for (int i=0 ; i<sp_object.length/2 ; ++i) {
          if (sp_object[i].schnitt(new MDaten(x,y,z))) {
                  erg.add(i);
          }
   }
 
               
 for (int i=sp_object.length/2; i<sp_object.length ; ++i) {
        if (sp_object[i].schnitt(new MDatenx,y,z))) {
                 erg.add(i);
        }
  }
 
  int[] daten = new int[erg.size()];
 
  for (int i=0 ; i<erg.size() ; ++i) {
           daten [i] = erg.get(i);
  }
  Arrays.sort(daten);
  return daten;

Sollte es nicht schneller sein wenn ich >2 threads hab und das Spiel zB auf einem multi-core system lauft?

Danke im Vorraus.

 

[tfa]

Sollte es nicht schneller sein wenn ich >2 threads hab und das Spiel zB auf einem multi-core system lauft?

Nicht, wenn du ständig (teilweise unnötig(?)) synchronisierst.

 

[objcler]

danke fuer die schnellen antworten.

das ist der code den ich so bekommen habe, ich hab diesen nicht selber geschrieben.

wenn ich alles in einem thread mache ist es um einiges schneller. zB:

 final Vector<Integer> erg = new Vector<Integer>();
 
  for (int i=0 ; i<sp_object.length/2 ; ++i) {
          if (sp_object[i].schnitt(new MDaten(x,y,z))) {
                  erg.add(i);
          }
   }
 
               
 for (int i=sp_object.length/2; i<sp_object.length ; ++i) {
        if (sp_object[i].schnitt(new MDatenx,y,z))) {
                 erg.add(i);
        }
  }
 
  int[] daten = new int[erg.size()];
 
  for (int i=0 ; i<erg.size() ; ++i) {
           daten [i] = erg.get(i);
  }
  Arrays.sort(daten);
  return daten;

Sollte es nicht schneller sein wenn ich >2 threads hab und das Spiel zB auf einem multi-core system lauft?

Danke im Vorraus.

Wenn du nur einen Thread hast kannst du auch gleich noch die zweite for-Schleife killen und alles in einem Durchgang machen. Dann wirds noch schneller.

Threads bedeuten nicht gleich kürzere Laufzeiten. Jeder Thread erzeugt auch erstmal einen Verwaltungsaufwand, den man nicht unterschätzen sollte. Außerdem musst du locken (synchronized), was auch alles Zeit kostet.

Grundregel: Erstmal alles synchron, ohne Threads programmieren. Das ist meist am einfachsten und am elegantesten. Wenn du dann feststellst, dass das ein Problem ist (Performancetechnisch, ...) dann kannst du immernoch auf Threads umstellen.

 

[sanv]

ich verstehe auch nicht warum der entwickler hier synchronisiert..

 

[tfa]

ich verstehe auch nicht warum der entwickler hier synchronisiert..

Das ist ja auch falsch.
Es wird Vector.add synchronisert, was es aber schon ist. Noch schlimmer allerdings, dass auch die if-Bedingung, wo gar nichts mir erg gemacht wird, synchronisiert wird. Das macht es nochmal langsamer.
Ich würde beide Threads jeweils eigene Ergebnislisten erzeugen lassen und die dann am Ende zusammenführen.

 

[objcler]

ich verstehe auch nicht warum der entwickler hier synchronisiert..

Bedenke bitte noch, dass die Grundregeln aller Grundregeln beachtet werden muss:

Probleme werden erstmal möglichst elegant und einfach gelöst.
Das Programm wird erstmal fertig gemacht.
Dann macht man Performancetests und optimiert zielgenau.

Es macht oft keinen Sinn rein mathematische Rechenoperationen zu optimieren. Jedenfalls nicht in Applikationen, die zum Beispiel irgendwas zeichnen (Spiele) oder viel IO-Erzeugen. Es kostet viel mehr Zeit ein Kreis zu zeichnen als eine extrem komplizierte Berechnung durchzuführen. Dann sollte man sich eventuell eher dauf das Zeichnen selbst konzentrieren. (Muss ich überhaupt zeichnen, kann ich den Region of Interest einschränken?, Caching?, ...).

 

[sanv]

d.h. eine loesung waere zB einen thread zu machen und die zwei for schleifen in 1 zu schreiben:

for (int i=0 ; i<sp_object.length ; ++i) {
          if (sp_object[i].schnitt(new MDaten(x,y,z))) {
                  erg.add(i);
          }
   }

 

[objcler]

d.h. eine loesung waere zB einen thread zu machen und die zwei for schleifen in 1 zu schreiben:

for (int i=0 ; i<sp_object.length ; ++i) {
          if (sp_object[i].schnitt(new MDaten(x,y,z))) {
                  erg.add(i);
          }
   }

Kein Thread.

Streiche das Wort am besten aus deinem Wortschatz

 

[FArt]

Ist ja auch in 99% der Threads, die was mit "Optimierung" zu tun haben die richtige.

.. und hier auch...

Laufzeitanalyse würden zeigen, ob die Synchronisation ausbremst, oder was anderes...

 

[objcler]

.. und hier auch...

Laufzeitanalyse würden zeigen, ob die Synchronisation ausbremst, oder was anderes...

Jo habe ich ja schon gesagt.

 

[tfa]

.. und hier auch...

Laufzeitanalyse würden zeigen, ob die Synchronisation ausbremst, oder was anderes...

Oder Hinschauen und Nachdenken.

 

[objcler]

Oder Hinschauen und Nachdenken.

Ob man durch Hinschauen und Nachdenken gut optimieren kann glaube ich nicht. Das ist doch gerade das "komische". Unser Instinkt sagt "das könnte man optimieren" - dtrace sagt uns dann aber in 99% der Fälle, dass die Optimierung nur marginal ist.

 

[sanv]

Das ist ja auch falsch.
Es wird Vector.add synchronisert, was es aber schon ist. Noch schlimmer allerdings, dass auch die if-Bedingung, wo gar nichts mir erg gemacht wird, synchronisiert wird. Das macht es nochmal langsamer.
Ich würde beide Threads jeweils eigene Ergebnislisten erzeugen lassen und die dann am Ende zusammenführen.

Hab jetzt eine 2. Verision geschrieben mit threads wo ich 2 Ergebnislisten erzeugen lasse :

 Thread thread = new Thread(new Runnable() { public void run() {
                        for (int i=0 ; i<sp_object.length/2 ; ++i)
                        {
                            if (sp_object[i].schnitt(daten))
                                    teil1.add(i);
                        }
                }});
                thread.start();

                for (int i=sp_object.length/2; i<sp_object.length ; ++i)
                {
                        if (sp_object[i].schnitt(daten))
                                teil2.add(i);
                }
                thread.join();

                erg.addAll(teil1);
                erg.addAll(teil2);

Aber die Loesung mit einer for-schleife ist noch immer am schnellsten?

Die Vorgabe ist die Laufzeit bist zu 99% zu reduzieren.

 

[objcler]

Hab jetzt eine 2. Verision geschrieben mit threads wo ich 2 Ergebnislisten erzeugen lasse :

 Thread thread = new Thread(new Runnable() { public void run() {
                        for (int i=0 ; i<sp_object.length/2 ; ++i)
                        {
                            if (sp_object[i].schnitt(daten))
                                    teil1.add(i);
                        }
                }});
                thread.start();

                for (int i=sp_object.length/2; i<sp_object.length ; ++i)
                {
                        if (sp_object[i].schnitt(daten))
                                teil2.add(i);
                }
                thread.join();

                erg.addAll(teil1);
                erg.addAll(teil2);

Aber die Loesung mit einer for-schleife ist noch immer am schnellsten?

Die Vorgabe ist die Laufzeit bist zu 99% zu reduzieren.

Wie kann man so eine Vorgabe machen? Das ist irgendwie komisch. Wie gesagt: Es gibt tools mit denen man das Laufzeitverhalten extrem detailliert beobachten und bewerten kann. Du solltest dich vielleicht erstmal auf die Analyse stürzen.

Google: dtrace

Vielleicht ist der Algorithmus selbst nicht das Problem sondern andere Dinge auf die du eher wenig Einfluss hast. Aber wir sollten hier nicht weiter Vermutungen aufstellen sondern die Werkzeuge benutzen, die uns die Antwort geben können.

 

[sanv]

Also ich habe den Code mal mit dem Profiler in NetBeans "untersucht" und folgendes Ergbnisse erhalten:

Die Klasse "SchnelleVersion" ist jene die ich "optimiert" habe in dem ich 2 Threads wie oben beschrieben verwende.

 

[Ark]

1. Was genau macht dieses [c]schnitt(daten)[/c]? (Code!)
2. Du sortierst [c]erg[/c] zum Schluss. Muss diese Sortierung zwingend vorgenommen werden? Wenn ja: Könnte eventuell ein TreeSet<Integer> angebracht sein?

Ark

 

[sanv]

1. Was genau macht dieses [c]schnitt(daten)[/c]? (Code!)
2. Du sortierst [c]erg[/c] zum Schluss. Muss diese Sortierung zwingend vorgenommen werden? Wenn ja: Könnte eventuell ein TreeSet<Integer> angebracht sein?

Ark

zu 1. die schnitt-methode macht folgendes:

public boolean schnitt (MDaten zentrum) 
{
    return zentrum.sub(wert).length() < abstand;
}

wert ist nochmals ein Objekt vom Typ MDaten.

zu 2. Der Rueckgabewert der methode ist int[].

 

[Marco13]

Ohne jetzt zu wissen, wie DAS (z.B "ab") alles implementiert ist:

private abstandSquared = abstand * abstand;
...

public boolean schnitt (MDaten zentrum) 
{
    return zentrum.ab(wert).lengthSquared() < abstandSquared;
}

DAS sind Sachen, die wirklich was bringen (können). Und das ist keine "premature optimization".

 

[tfa]

Ohne jetzt zu wissen, wie DAS (z.B "ab") alles implementiert ist:

private abstandSquared = abstand * abstand;
...

public boolean schnitt (MDaten zentrum) 
{
    return zentrum.ab(wert).lengthSquared() < abstandSquared;
}

DAS sind Sachen, die wirklich was bringen (können). Und das ist keine "premature optimization".

Warum "squared"? Wenn a²<b² gilt automatisch a<b.

@TS: Wie oft wird die Schleife denn durchlaufen?

 

[Marco13]

Warum "squared"? Wenn a²<b² gilt automatisch a<b

Genau deswegen ja - man muss (da kein Code gepostet wurde *wink*) davon ausgehen, dass bei "length()" eine Wurzel gezogen wird, was bei "lengthSquared" dann nicht notwendig wäre.

 

[tfa]

Genau deswegen ja - man muss (da kein Code gepostet wurde *wink*) davon ausgehen, dass bei "length()" eine Wurzel gezogen wird, was bei "lengthSquared" dann nicht notwendig wäre.

Achso meintest du das...

 

[Ark]

Und was macht dieses [c]sub(wert)[/c]? Was ist überhaupt [c]wert[/c]? Wo kommt es her? Welche Programmteile sind noch am zu optimierenden Code beteiligt? (Lass dir doch bitte nicht alles aus der Nase ziehen. )

Ark

 

[sanv]

also, wie gesagt ich sollte "nur" den code den ich im ersten post angeben habe optimieren und den rest nicht "anfassen".

mir wurde geraten eventl. Java's executor fuer mehrere threads zu verwenden? ist das ratsam?

 

[Der Müde Joe]

>Java's executor fuer mehrere threads zu verwenden?

Executor sind eigentlich Threads vorzuziehen. (einfach gesagt)

 

[JohannisderKaeufer]

Hast du auch daran gedacht einen Unit-Test zu schreiben?

Es wäre ja äußerst Schade wenn das ganze schneller läuft aber ein anderes, bzw. falsches Ergebnis rauskommt.

Hier könnte auch die Annotation
@Test(timeout = 1000)
von interesse sein.

 

[sanv]

also das ergebnis passt da es in einer anderen klasse verglichen wird. der inhalt des int[] (rueckgabewert der methode) wird mit der berechnung der original klasse verglichen und der inhalt passt.

 

[sanv]

Mit

  Thread t = new Thread(new Runnable() {....

werden ja mehrere Threads erzeugt (wie aus dem NetBeans Profiler ersichtlich wird). Kann man das zB mit ExecutorService "optimieren". Kann mir jemand eventl. bitte ein Bspl geben.

Danke im Vorraus.