Rechnen mit kleinen Zahlen langsamer!?

[Marco13]

Hi

Eigentlich dachte ich ja, dass ich mir für die meisten Gründe scheinbar unerklärlichen Verhaltens zumindest irgendwas mit JIT, caching & Co zusammenreimen könnte, aber das hier kann ich mir im Moment nicht erklären - und es scheint etwas so ... "elementares" zu sein, dass mich das jetzt schon ein bißchen wurmt :autsch: :

Das Rechnen mit kleinen Zahlen scheint deutlich (!) langsamer zu sein, als das Rechnen mit "normalen" Zahlen. Gemerkt habe ich das eben in einem größeren Programm eher zufällig, konnte es aber nicht recht glauben, und habe deswegen nochmal einen Microbenchmark gemacht (und natürlich auf die übliche Weise versucht, diesem so viel Aussagekraft wie möglich zu geben: Mehrere Durchläufe mir größer werdenen Eingaben und abwechselndem Aufruf der beiden Fälle).

import java.util.*;

class SmallNumbers
{
    public static void main(String args[])
    {
        for (int n=1000; n<=10000000; n*=10)
        {
            float a[] = new float[n];
            float b[] = new float[n];
            float dot = 0;
            long before = 0;
            long after = 0;
            int runs = 5;

            fill(a, 1e-20f);
            fill(b, 1e-20f);
            before = System.nanoTime();
            dot = 0;
            for (int i=0; i<runs; i++)
            {
                dot += dot(a,b);
            }
            after = System.nanoTime();
            System.out.println("Small  for "+n+" time "+(after-before)/1e6+" ms result "+dot);

            fill(a, 1);
            fill(b, 1);
            before = System.nanoTime();
            dot = 0;
            for (int i=0; i<runs; i++)
            {
                dot += dot(a,b);
            }
            after = System.nanoTime();
            System.out.println("Normal for "+n+" time "+(after-before)/1e6+" ms result "+dot);
        }
    }

    private static void fill(float a[], float factor)
    {
        Random r = new Random(0);
        for (int i=0; i<a.length; i++)
        {
            a[i] = r.nextFloat() * factor;
        }
    }


    private static float dot(float a[], float b[])
    {
        float sum = 0;
        for (int i=0; i<a.length; i++)
        {
            sum += a[i] * b[i];
        }
        return sum;
    }
}

Das ganze getestet mit Java6/29 (-server) auf Win7/64, Core i7@3Ghz... das Ergebnis:

Small  for 1000 time 0.619448 ms result 1.605676E-37
Normal for 1000 time 0.140942 ms result 1605.6758
Small  for 10000 time 6.114442 ms result 1.6553897E-36
Normal for 10000 time 0.049765 ms result 16553.873
Small  for 100000 time 53.807083 ms result 1.6730621E-35
Normal for 100000 time 0.511914 ms result 167305.3
Small  for 1000000 time 531.612915 ms result 1.6681287E-34
Normal for 1000000 time 4.534153 ms result 1668135.5
Small  for 10000000 time 5312.714176 ms result 1.6468518E-33
Normal for 10000000 time 54.758528 ms result 1.650076E7

Ja, gut, man könnte da jetzt zwar auch spekulieren, dass die Normalisierung für die Mutliplikation tief im Prozessor seine Zeit braucht oder was weiß ich, und ein kleiner Unterschied wäre ja OK, aber es kann doch nicht sein, dass das Multiplizieren von ein paar "kleinen" Zahlen durchgängig hundert mal so lange dauert wie das von ein paar "normalen" Zahlen!? :autsch: Soll man in solchen Fällen wirklich alle Zahlen von Hand "normalisieren", damit der arme Herr Prozessor das nicht machen muss? :noe:

Oder ist einfach nur mein Computer kaputt? ;(

 

[bERt0r]

Ich schätze mal, dass diese Normalisierung eben bei jeder Rechenoperation neu durchgeführt werden muss, dadurch entsteht ein exponentiell größerer Aufwand. Es muss schließlich auch jedes Zwischenergebnis dann nochmal umgerechnet werden.

 

[planetenkiller]

Wenn ich double anstatt float nehme, ist die Performance bei mir wieder ok.

Das einzige was ich finden konnte: Denormal number - Wikipedia, the free encyclopedia

 

[Marco13]

Tatsächlich, das scheint es zu sein ... Dort steht auch explizit

in extreme cases, instructions involving denormal operands may run as much as 100 times slower.

Ich hatte erst nicht gedacht, dass das hier zutrifft, weil 1e-20 ja noch nicht "denormal" wäre, aber die Zahlen werden ja miteinander multipliziert. Dann kommt man in die Größenordnung von 1e-40, und das IST dann kleiner als 2^-126. Mit 1e-16 bleiben fast alle Produkte über 1e-37 (bzw über 2^-126), und man merkt keinen Unterschied mehr.

Danke für den Schubser in die richtige Richtung!

Fragt sich nur, wie ich das Problem in der echten Anwendung umgehe... Alles dumpf Größermultiplizieren wäre ja ein Krampf...

 

[SlaterB]

würde das Normalisieren nicht auch schon Zeit kosten?
hab jetzt nicht so genau geschaut was du da machst, falls jede Zahl sogar mehrfach gerechnet wird und 10 Mio. Durchläufe nur 5 sec dauern,
dann kann man das nun wahrlich als nebensächlich betrachten,
sei froh dass du nicht mit BigDecimal für Genauigkeit rechnen musst, wer weiß um wieviel Zehnerpotenzen das dann noch langsamer ist,

aber wo immer die Zahlen herkommen falls nicht gerade Zufall, das sollte 99% der Zeit verbrauchen,
die 1% Java-Zahlen-Rechnung muss man normalerweise nicht optimieren..

 

[Marco13]

würde das Normalisieren nicht auch schon Zeit kosten?
...
das sollte 99% der Zeit verbrauchen,
die 1% Java-Zahlen-Rechnung muss man normalerweise nicht optimieren..

Es geht in diesem Fall tatsächlich um sowas wie "Numbercrunching": Viele Dot-Products und Matrix-Vektor-Multiplikationen hintereinander. Man wartet eben teilweise mehrere Minuten auf das Ergebnis - und wenn man das auf wenige Sekunden drücken könnte, wäre das nicht schlecht. Später werde ich das vermutlich nochmal mit JCublas laufen lassen und schauen, was man da noch rausholen kann (dürfte noch einiges sein) aber ich würde schon gerne auch eine in vertretbarer Zeit laufende pure-Java-Implementierung haben...

Ich hab' da echt an meinem Verstand gezweifelt: Eine Iteration, die ~50 mal durchläuft, und IMMER genau das gleiche macht - und die erste Iteration hat ~30ms gedauert, die folgenden wurden immer langsamer, und die letzte brauchte >300ms (weil eben immer mehr Zahlen immer kleiner wurden) :autsch:

Tatsächlich ist sowas hier (in das Beispiel eingebaut) schon wieder 30 mal schneller:

    private static float hackDot(float a[], float b[])
    {
        float sum = 0;
        for (int i=0; i<a.length; i++)
        {
            sum += (a[i] * 1e20) * (b[i] * 1e20);
        }
        sum /= 1e40;
        return sum;
    }

Aber... :autsch: ... das kann man ja nicht bringen :noe: Und natürlich ist es für die echte Anwendung ohnehin ungeeignet, weil es mega-:autsch: ist, und man es nicht für alle Zahlen machen dürfte. Gar nicht mal so sehr weil da viel Genauigkeit flöten geht: Wenn die Zahlen erstmal so klein sind, ist das eigentlich auch egal. Es geht grob gesagt am Ende ohnehin nur um die Zahlen, die eben NICHT so klein geworden sind, und ob eine dieser kleinen dann 1.123e-30 oder 2.987e-31 ist, spielt eigentlich keine Rolle - deswegen war auch mein erster Ansatz im "echten" Programm eine art "cutoff": [c]if (value < 1e-20) value = 0;[/c]. Aber befremdlich fand ich das ganze schon... ???:L

 

[bERt0r]

Hast du dir schon mal die Ergebnisse deiner Multiplikationen angeschaut? Wenn ich die dot Funktion ein wenig ändere:

  private static float dot(float a[], float b[])
    {
    	int count=0;
        float sum = 0;
        for (int i=0; i<a.length; i++)
        {
        	float f=a[i]*b[i];
        	if(f==0f)
        	{
        		count++;
        	}
        	sum+=f;
        }
        System.out.println("Count= "+count);
        return sum;
    }

Bekomm ich beim letzten durchlauf insgesamt 26458 Underflows, das könnte auch eine Ursache für die schlechte Performance sein.

 

[Marco13]

Hm. Schwer zu sagen. Die Zahlen werden "zu klein", und es wird langsamer - ich vermute, dass die vielen Millionen kleinen Zahlen eher die Verlangsamung bringen als die wenigen Prozent Unterflows - müßte man mal versuchen, isoliert voneinander zu testen...

 

[schalentier]

Mh interessant.

Ich kenn deinen Usecase ja nicht, aber vielleicht is das tatsaechlich ein Fall, wo man auf die guten alten Fixed-Length-"Floats" zurueckgreifen koennte? Also quasi dass du anstatt mit Floats/Doubles, komplett mit Ints/Longs rechnest. Das geht natuerlich nur, wenn dein Wertebereich eingrenzbar ist - und du z.B. 4 Bits fuer vor dem Punkt nimmst und die restlichen 60 Bit fuer Nachkommastellen. So wie frueher halt, als der Coprozessor fuer die Fliesskommarechnung noch verdammt lahm war ;-)

 

[Marco13]

Hmnee... im konkreten Fall geht das nicht, und ... es wäre ja auch schwer als allgemeine Lösung anzusehen. Ich denke, das mit dem "cutoff" wird im vorliegenden Fall das beste sein, aber bin mir nicht sicher, ob und inwieweit das die Ergebnisse verfälscht (ist dort schwer einzuschätzen...)

 

[ThreadPool]

Wenn ich double anstatt float nehme, ist die Performance bei mir wieder ok.

Ich habe das auch mal versucht und interessanterweise hat sich die Zeit extrem verkürzt. Man sieht zwar immernoch einen Unterschied aber der Faktor liegt da bei Weitem nicht mehr im zwei- bis dreistelligen Bereich. Für den double-Bereich sind die Zahlen wohl "normaler", da der Bereich größer ist oder intepretiere dich das falsch?

 

[Marco13]

Das stimmt. Insgesamt (also bei den Zahlen um 1.0 rum) wäre double etwas langsamer, aber dieser Einbuch um Faktor 100 würde erst viel, viel später stattfinden.