WTF?! Algorithmus-Geschwindigkeitstest

[SuperSeppel13]

Hallo Leute,
ich bin vorhin im Internet über den "fast inverse square root"-Algorithmus gestolpert. Da ich womöglich einen Nutzen dafür hätte wollte ich ihn dann erst mal auf Leistung testen.

Dazu habe ich eine Testmethode geschrieben, die zuerst ein Array mit einer anzahl n an zufälligen floats von 0 bis 10000 anlegt.
Danach lasse ich mir von jedem dieser Werte die inverse Quadratwurzel berechnen, und zwar im ersten Durchlauf einfach mit

1f/(float)Math.sqrt(x)

und im zweiten mit dem invSqrt-Algorithmus (siehe unten).
Zwischen beiden Durchläufen habe ich mir jeweils die

System.nanoTime()

geben lassen und habe dann im Nachhinein die Dauer beider durchläufe berechnet.

Das erstaunliche hierbei war, dass der "schnelle" Algorithmus auch bei wiederholtem Test bis zu vier mal so lang gebraucht hat.
Als ich dann die Methode dahingehend änderte, dass bei jedem Programmdurchlauf gleich hundert Testdurchläufe gemacht werden, stellte ich fest, dass bei einem Test mit n<1000 Werten pro Durchlauf immer so bei den ersten zwei oder drei tests die invSqrt methode langsamer ist und bei allen danach aber ca 5 mal so schnell! (bei kleineren n sind auch mehr langsame Durchläufe am Anfang.)

Kann mir das irgendwer erklären?! Ich dachte dass die JVM vielleicht noch irgendwas laden muss, aber wieso verlangsamt dass dann die einem Methode aber nicht die andere (oder zumindest unterschiedlich stark)?!

Hier ist nochmal der Algorithmus:

    public static float invSqrt(float x){
        float xhalf = 0.5f * x;
        int i = Float.floatToRawIntBits(x); // store floating-point bits in integer
        i = 0x5f3759df - (i >> 1); // initial guess for Newton's method
        x = Float.intBitsToFloat(i); // convert new bits into float
        x = x*(1.5f - xhalf*x*x); // One round of Newton's method
        //x = x*(1.5f - xhalf*x*x); // optional second round, slower/more accurate
        return x;
    }

und hier mein ganzer code, falls ihr das auch mal testen wollt:

public class Test {

    public static void main (String[] args){
        int l = 100;
        double sum = 0;

        for(int i=0; i<100; i++){
            sum += test();
        }

        System.out.println();
        System.out.println("average: " + sum/l);//durchschnitt prozentuale zeitersparnis

    }

    static double test(){
        final int l = 10000;//test-länge
        float[] f = new float[l];
        long start, half, end;
        float sol;

        for(int i = 1; i<l; i++){
            f[i] = (float)Math.random()*10000f;//zufallszahlen generieren
        }

        start = System.nanoTime();

        //durchlauf mit standart methode
        for(int i=0; i<l; i++){
            sol = 1f/(float)Math.sqrt(f[i]);
        }

        half = System.nanoTime();

        //durchlauf mit invSqrt
        for(int i=0; i<l; i++){
            sol = invSqrt(f[i]);
        }

        end = System.nanoTime();

        long t1 = half-start;//länge erster durchlauf
        long t2 = end-half;//länge zweiter durchlauf
        double d = (1d-(double)t2/t1)*100;//geschw.-zunahme in prozent
        
        System.out.println(t1/1000000d);//in millisec
        System.out.println(t2/1000000d);
        System.out.println(d);
        System.out.println();

        return d;
    }

    public static float invSqrt(float x){
        float xhalf = 0.5f * x;
        int i = Float.floatToRawIntBits(x); // store floating-point bits in integer
        i = 0x5f3759df - (i >> 1); // initial guess for Newton's method
        x = Float.intBitsToFloat(i); // convert new bits into float
        x = x*(1.5f - xhalf*x*x); // One round of Newton's method
        //x = x*(1.5f - xhalf*x*x); // One round of Newton's method
        return x;
    }
}

Ich werd den algorithmus auf jeden fall verwenden, aber interessieren tuts mich doch... =)

Grüße,
SuperSeppel13

 

[Marco13]

Als ich dann die Methode dahingehend änderte, dass bei jedem Programmdurchlauf gleich hundert Testdurchläufe gemacht werden, stellte ich fest, dass bei einem Test mit n<1000 Werten pro Durchlauf immer so bei den ersten zwei oder drei tests die invSqrt methode langsamer ist und bei allen danach aber ca 5 mal so schnell! (bei kleineren n sind auch mehr langsame Durchläufe am Anfang.)

Ohne das ganze im Detail nachvollzogen zu haben, aber MIT dem Hinweis, dass solche selbsgebastelten "Micro-Benchkarks" immer sehr heikel sind (und speziell bei sol "elementaren" Operationen wie 1/sqrt nur sehr bedingt überhaupt eine Aussagekraft haben) : Der beschriebene Effekt könnte (!) durch den JIT (Just-In-Time-Compiler) kommen. (Websuche). Der optimiert den Code noch, "während" er läuft, und konzentriert sich dabei auf Dinge, die "oft" ausgeführt werden.

 

[SuperSeppel13]

Hm, ja, dass das mein Test n bischen improvisiert ist ist mir schon klar, aber die Ergebnisse waren halt bis auf diese Ungereimtheit am Anfang sehr konsistent, weshalb ich drchaus bereit bin, ihnen ein gewisses Vertrauen zu schenken.
Ich habe das ganze jetzt nochmal auf einem anderen Rechner getestet, mit exakt dem gleichen Ergebnis.

Die Erklärung mit dem JIT-Compiler leuchtet mir ein - Danke dafür!
Ich werd mich dazu mal ein wenig näher informieren...