Perfomance: Arraylist absichtlich zum Nullpointer schicken...

[osion]

Das Durchlaufen von Arrays ist ebenfalls eine häufig auftretende Verwendung. Gerade bei großen Datenmengen und somit großen Arrays macht sich jedoch der Schleifenoverhead bemerkbar. Der Schleifenoverhead entsteht dabei u.a. durch die Gültigkeitsprüfungen (siehe auch Schleifen). Sie haben jedoch eine Alternative. Anstatt bei jedem Schleifendurchlauf zu prüfen, ob das Ende des Arrays erreicht wurde lassen Sie Ihre Anwendung bewusst auf einen Fehler laufen. Die erzeugte ArrayIndexOutOfBoundsException fangen Sie dann gekonnt ab. Gerade bei Bytecode Interpretern können Sie hier nicht zu unterschätzende Geschwindigkeitsvorteile erringen .

Das Performance-Handbuch: Implementierung mit Java

Fragen:
1. Denken die an while(true) und int wert immer steigern
2. Ab wann ist es gross?
3. Was denkt ihr darüber?

 

[arilou]

Beispiel:

int idx = 0;
while( idx < myArray.length() )
{
  // mach was simples, schnelles mit myArray[idx]
  idx++ ;
}

Wenn der Schleifenrumpf nur wenig Rechenzeit benötigt, wird die "idx < myArray.length()" -Prüfung zu einem erheblichen Faktor der Gesamtrechenzeit. Der Autor meint, man sollte stattdessen

int idx = 0;
try{
  while( true )
  {
    // mach was simples, schnelles, das auf myArray[idx] zugreift
    idx++ ;
  }
} catch( ArrayIndexOutOfBoundsException aioobE ) {
  ;
}

verwenden, das sei ggf. schneller.
Ich würde das aber wirklich nur machen, wenn's in dem Programmabschnitt total auf die Performance ankommt.
Außerdem sind Exceptions "teuer" (Rechenzeit), das lohnt sich also erst ab wirklich großen Arrays (ich schätz' mal ab vielleicht 100.000 Elementen), und sollte bestens dokumentiert werden, warum man hier so seltsam vorgeht.

Speziell für Java-Anfänger lautet meine Empfehlung: Lasst die Finger von solchen Spezialitäten - 6 Wochen nach dem Programmieren versteht man selbst kaum mehr, warum die Schleife funktioniert X-)
Den letzten Satz bzgl. "Bytecode-Interpreter" - au wei, wer benützt denn noch sowas?
Vielleicht bei embedded-Mikrokontrollern, aber ansonsten hat man doch heutzutage JIT/HotSpot-Kompiler.

 

[nvidia]

Deine Überschrift ist nicht richtig. Es geht um eine ArrayIndexOutOfBoundsException und nicht um eine NullpointerException.
Zum Thema selbst, da musst du nachmessen. Die Grundidee der Beschreibung ist anstelle explizit über die Laufvariable zu prüfen sich auf die interne Prüfung zu verlassen um so die explizite Prüfung zu sparen. Die Annahme des Textes beruht dann aber darauf das beide Prüfungen ausgeführt werden und somit eine irgendwie redundant ist.
Bei Java kann man das so aber pauschal nicht beantworten da während der Ausführung des Programmes einiges passiert. Z.B. kann der JIT, Code innerhalb der for-Schleife inlinen und auswerten ob die Laufvariable jemals über einen Index hinausgehen wird, ist das nicht der Fall kann er das interne Bounds-Checking wegfallen lassen.

Bei einfachen for-Schleifen wird das, so nehme ich an, so gut wie immer der Fall sein. Der "schnellste" for-Loop, meiner Erfahrung nach, sieht übrigens wie folgt aus (Pseudocode):

int[] array = ... //irgendein array
for(int i = array.length; --i >=0; ){
    array[i] ...
        }

Solche Geschichten kann man aber nur empirisch durch messen überprüfen, d.h. man schnappt sich ein Tool wie z.B. den JMH und schreibt sich einen Microbenchmark und schaut sich den Trend bei verschiedenen Versionen an. Microbenchmarks sind aber keine triviale Sache, da muss schon genau aufgepasst werden sonst sind die Ergebnisse nicht aussagekräftig.

Falls du derzeit Probleme mit der Geschwindigkeit deines Programmes hast solltest du dir vll. andere Algorithmen und Datenstrukturen ansehen. Die Konstrukte wie For-Schleifen etc. sind vom Optimierungspotenzial eher niedriger anzusiedeln als der Code der in der For-Schleife ausgeführt wird.

 

[LepraHorst]

Guten Abend,

da ich den Denkansatz dieses Autors sehr interessant fand, hab ich mal ein kleines Programm geschrieben. Es vergleicht die Zeit, die bei den unterschiedlichen Methoden vergeht.

package schleifenoverhead;

import java.util.*;

public class Schleifenoverhead {

    public static void main(String[] args) {
        
        Random random = new Random();
        
        long currentMillis;
        long newMillis;
        long a = 1;
        int n = 0;
        int[] array = new int[100000000];
        
        //füllen des Arrays mit Zufallszahlen
        for(int i = 0; i < array.length; i++){
            array[i] = random.nextInt() % 100;
        }
        
        
        //Variante 1: for-Schleife
        currentMillis = System.currentTimeMillis();
        for(int i = 0; i < array.length; i++){
            a += array[i]; 
        }
        newMillis = System.currentTimeMillis();
        System.out.println("Die for-Schleife benötigte: " + (newMillis - currentMillis));
        
        
        //Variante 2: While-Schleife mit Zählbedingung
        a = 1;
        currentMillis = System.currentTimeMillis();
        while(n < array.length){
            a += array[n];
            n++;
        }
        newMillis = System.currentTimeMillis();
        System.out.println("Die While-Abfrage benötigte: " + (newMillis - currentMillis));
        
        
        //Variante 3: While(true)-Schleife mit abgefangener Exception
        a = 1;
        n = 0;
        currentMillis = System.currentTimeMillis();
        try{
            while(true){
                a += array[n];
                n++;
            }                                   
        }
        catch(IndexOutOfBoundsException e){
            newMillis = System.currentTimeMillis();
            System.out.println("Die While-Schleife mit Exception benötigte: " + (newMillis - currentMillis));
        }
    }
    
}

Dabei schneidet die Schleife, die durch die Exception unterbrochen wird, am besten ab. Jetzt stellt sich mir nur noch die Frage, ob System.currentTimeMillis() genau genug für so einen Test ist, oder ob ich so Messabweichungen bekomme.

LG

 

[osion]

Eine Exception erzeugt jeweils ein Standbild des Javastack zum Auslösungszeitpunkt und ist daher synchronisiert.

Das Performance-Handbuch: Implementierung mit Java

Es sollte nicht ausser betracht gezogen werden, dass eine Exception syncronsiert abläuft, d .h. würden immer 5 Threads laufen und einen eigenen String bearbeiten, das in einem Exception part, so würde man das gut merken.

Es sollte versucht werden, dass Exception gar nicht auftretten, d. h. evtl. durch if abgefangen wird...nicht wahr?

 

[arilou]

@LepraHorst: RTFM: "the granularity of the value depends on the underlying operating system and may be larger [than 1 ms]."
Auf Windoof-Rechnern mit Oracles JVM muss man damit rechnen, dass .currentTimeMillis() Sprünge von 10 oder 16 ms macht.

System.nanoTime() wäre besser geeignet für kurze Zeitspannen - aber auch hier wird nur garantiert, dass es zumindest nicht schlechter misst als .currentTimeMillis() .

@osion: Gerade um den Vergleich von "mit if abfangen" gegenüber "Zeitdauer Exception" geht's ja - also: nein, hier kann ggf. explixit des Exceptionhandling besser sein.


Bei sehr kurzen Schleifenrümpfen gewinnt man aber ggf. mehr mittels Loop-unrolling. Leider geht in Java wohl nicht "Duffs Device", man muss es etwas händischer angehen. (Außerdem macht das ein JIT ggf. sowieso automatisch, sofern sich die Schleifengrenze nicht ändern kann.)

 

[LepraHorst]

Ich hab mein programm auf OpenSuse laufen lassen. Welche Zeitauflösung bietet mir das?

Und worin besteht genau der Unterschied zwischen currentTimeMillis() und System.nanoTime(), im Bezug auf die genauigkeit?
Sind diese Methoden nicht beide an die Systemzeit gebunden?

 

[arilou]

@LepraHorst: RTFM, Java APIs, java.lang.System

.currentTimeMillis() liefert die vergangenen Millisekunden seit 01.01.1970, 00:00 Uhr GMT. Somit also "an die Systemzeit gebunden".

.nanoTime() liefert die Nanosekunden seit irgendeinem bestimmten Zeitpunkt A; dieser ist nur für das aktuell laufende Java-Programm/seine JVM festgelegt, und kann auch negativ sein.

Bei guten JVMs verwendet .nanoTime() einen tatsächlich im Nanosekundenbereich arbeitenden Hardware-Timer; .currentTimeMillis() verwendet ggf. einen anderen Timer.

 

[LepraHorst]

@arilou:

Vielen Dank für die Erklärung. Ich hab schon in der Java-Doku nachgelesen, aber die genaue Funktionsweise von System.nanoTime() nicht verstanden.
Ich hab mein kleines Programm jetzt umgeschrieben. Aber das Ergebnis verwundert mich noch.

Wenn ich die Ausgabe so gestalte, dann bekomme ich ein eindeutiges Ergebnis:

Die for-Schleife benötigte: 70
Die While-Abfrage benötigte: 83
Die While-Schleife mit Exception benötigte: 59

Dann ist mir allerdings aufgefallen, die Zeiteinheit vergessen habe. Also hab ich als einzige Änderung das "ms" an den Ausgabestring des System.out.println() gehängt. Dies erfolgt jedoch erst nach der Speicherung des Endzeitpunkts.
Dadurch wird das Ergebnis jedoch deutlich verändert:

Die for-Schleife benötigte: 63ms
Die While-Abfrage benötigte: 69ms
Die While-Schleife mit Exception benötigte: 61ms

Ich habe beide Programmvarianten mehrmals ausgeführt und komme immer wieder auf die gleichen Ergebnisse.
Woran kann dies liegen?

 

[nvidia]

Woran kann es liegen, hm.... In erster Linie daran das derart konstruierte Microbenchmarks nicht wirklich aussagekräftig sind. Das liegt zum einen daran, das die VM komplexe Dinge im Hintergrund zusammenfummelt. Das wäre z.B. inlining, dead code elimination, constant folding, reordering von Operationen etc. pp. und zum Anderen kommt noch die ganze Hardwareschiene dazu, passen die Daten in den Cache und hat der Nachfolger dadurch eine bessere Laufzeit usw. Deshalb nimmt man heute Benchmark-Frameworks, die versuchen den Nutzer vor einigen dieser Fallen zu bewahren wie z.B. das die "Warmup"-Phase nicht ausgeführt wurde etc. pp. Ein ganz guter aktueller Vertreter ist z.B. JMH. Ein MB-Beispiel findet sich unter Using JMH for Java Microbenchmarking Dennoch muss man auch bei der Verwendung von MBB aufpassen, das man tatsächlich das benchmarkt was man möchte.

 

[osion]

Was sehr cool wäre, wäre wenn man bei Eclipse ein Übersichtsfenster über alle Methoden hat welcher Synchronisiert laufen und alle Locks usw.

So könnte an der Warteliste gesehen werden, welche Stellen zum Deadlock führen könnte und wo Flaschenhälse entstehen, was zu einer Perfomance steigerung führen würde.

 

[Thallius]

Solche Tests sind unter einem Multi-Tasking-OS vollkommen sinnfrei. Am besten ist der Rechner noch mit dem Internet verbunden und hat einen Multi-Core. Was da dann alles passiert während Deine App abläuft ist nicht mehr nachzuvollziehen.

Gruß

Claus

 

[osion]

Solche Tests sind unter einem Multi-Tasking-OS vollkommen sinnfrei. Am besten ist der Rechner noch mit dem Internet verbunden und hat einen Multi-Core. Was da dann alles passiert während Deine App abläuft ist nicht mehr nachzuvollziehen.

Gruß

Claus

Natürlich nicht so ausführlich, aber es wäre sicherlich sehr gut brauchbar, würden man bei allen Synchronisierten Punkte sehen, wie dort der Status wäre, was ja nicht die Welt wäre, weil Java sowieso das Intern schon händelt nicht wahr?


Beispiel


Name Synchronisiert |||| Status |||| Warteschlange

---

Methode XY |||| Use |||||20

 

[arilou]

@osion: Auf jeden Fall zeigen deine "Ergebnisse", dass man deutlich mehr Aufwand betreiben muss, um den Unterschied herauszuarbeiten.

Z.B. muss man bedenken, dass eine moderne CPU bei 3 GHz dann 3 Milliarden(!) Befehle pro Sekunde rechnet (nur 1 CPU-Kern!). Da sind 100 Mio. Integer-ADDs, 100 Mio. INC und 100 Mio. JNZ in zusammen 1/10 s abgefrühstückt. Auch musst du beachten, dass du die Rechenperformance testen möchtest, und nicht die Speicherbandbreite - 100 Mio int's brauchen 400 MB Ram, d.h. der Programmlauf würde evtl. erheblich durch die Cacheumladerei beeinflusst.

Ich schließe mich den Vorrednern an - Mikrobenchmarks sind nicht einfach.

 

[osion]

@osion: Auf jeden Fall zeigen deine "Ergebnisse", dass man deutlich mehr Aufwand betreiben muss, um den Unterschied herauszuarbeiten.

Z.B. muss man bedenken, dass eine moderne CPU bei 3 GHz dann 3 Milliarden(!) Befehle pro Sekunde rechnet (nur 1 CPU-Kern!). Da sind 100 Mio. Integer-ADDs, 100 Mio. INC und 100 Mio. JNZ in zusammen 1/10 s abgefrühstückt. Auch musst du beachten, dass du die Rechenperformance testen möchtest, und nicht die Speicherbandbreite - 100 Mio int's brauchen 400 MB Ram, d.h. der Programmlauf würde evtl. erheblich durch die Cacheumladerei beeinflusst.

Ich schließe mich den Vorrednern an - Mikrobenchmarks sind nicht einfach.

Leider muss ich sagen, dass ich denke du sprichst von LepraHorst. Jedenfalls konzentriere ich mich auf die Grosse Fische im Programm, z. B. Flaschenhälse.

 

[Natac]

Auch wenn ich die Diskussion interessant finde... In Produktivcode würde ich so eine Schleife nie verbauen. Der damit evtl. verbundene Performance-Gewinn stehen für mich in keinem Verhältnis zur dadurch verlorenen Lesbarkeit und Einfachheit.

Und wie meine Vorposter schon schrieben: Wenn das Programm zu langsam ist, liegt es wohl nur im speziellen Sonderfall an der Art der Schleife. Von daher würde ich so eine Schleife beruhigt ins Kuriositäten-Kabinett verbannen und weiter mit normalen for und while-Schleifen arbeiten.

 

[arilou]

Leider muss ich sagen, dass ich denke du sprichst von LepraHorst. Jedenfalls konzentriere ich mich auf die Grosse Fische im Programm, z. B. Flaschenhälse.

Richtig - Entschuldigung. Die "Ergebnisse" waren von LepraHorst, ja.