Rechnen mit kleinen Zahlen langsamer!?

Marco13

Top Contributor
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).

Java:
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:
Code:
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

Top Contributor
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.
 

Marco13

Top Contributor
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... :(
 
S

SlaterB

Gast
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

Top Contributor
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:
Java:
    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

Top Contributor
Hast du dir schon mal die Ergebnisse deiner Multiplikationen angeschaut? Wenn ich die dot Funktion ein wenig ändere:
Java:
  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

Top Contributor
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

Gesperrter Benutzer
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

Top Contributor
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

Bekanntes Mitglied
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

Top Contributor
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
P Rechnen mit sehr kleinen Zahlen Allgemeine Java-Themen 5
M Rechnen mit sehr kleinen Zahlen Allgemeine Java-Themen 8
JAnruVA Datentypen Berechneten String-Wert in Double umwandeln um weiter zu rechnen Allgemeine Java-Themen 7
Mikejr Recursion mit Zinseszins rechnen Allgemeine Java-Themen 20
B Parameter Konstruktor plus rechnen Allgemeine Java-Themen 6
KeexZDeveoper Schnelleres Rechnen Allgemeine Java-Themen 8
J-Gallus Erste Schritte Wahrscheinlich Anfänger Fehler beim rechnen. Falsches Ergebnis. Allgemeine Java-Themen 9
A Mit dem letzten bis zum ersten Wert aus Array rechnen Allgemeine Java-Themen 15
M Probleme beim rechnen, bei Zahlen mit führenden Nullen. Allgemeine Java-Themen 7
J zu blöd zum rechnen Allgemeine Java-Themen 7
F Taschenrechner Term rechnen Allgemeine Java-Themen 4
S Java rechnen mit unbekannten Allgemeine Java-Themen 11
B Fehler beim Rechnen mit Floats Allgemeine Java-Themen 3
B Rechnen mit mehreren Variablen Allgemeine Java-Themen 2
M In einer Tabelle rechnen Allgemeine Java-Themen 12
H Mit String rechnen Allgemeine Java-Themen 14
hdi Probleme beim Rechnen mit BigDecimal Allgemeine Java-Themen 5
E Konstante Zahl Threads parallel rechnen lassen Allgemeine Java-Themen 6
O "Rechnen" mit Farben Allgemeine Java-Themen 12
T Mit Datum und Zeit rechnen Allgemeine Java-Themen 8
G Probleme mir Rechnen Allgemeine Java-Themen 5
P rechnen mit extrem grossen zahlen Allgemeine Java-Themen 2
H Komplexes Rechnen mit Java Allgemeine Java-Themen 6
S Rechnen mit float Zahlen Allgemeine Java-Themen 2
O Java zu blöde um 1-1 zu rechnen?? Allgemeine Java-Themen 20
turmaline OOP zwei gleiche Methoden mit kleinen Unterschieden Allgemeine Java-Themen 15
Developer_X Brauche Hilfe bei meinem kleinen hilfsprogramm Allgemeine Java-Themen 4
E verstehe fehler bei meinem (kleinen) programm nicht Allgemeine Java-Themen 5
berserkerdq2 Versteht jemand, was diese beiden Zahlen bei dem IJVM Code zu bedeuten haben? Allgemeine Java-Themen 10
L die 3 größten Zahlen im Array Allgemeine Java-Themen 1
A Potenzmenge der Zahlen von 1 bis n Allgemeine Java-Themen 20
Monokuma String List nach Zahlen und Worten sortieren Allgemeine Java-Themen 9
G Java Editor Löschen doppelter Zahlen einer Liste Allgemeine Java-Themen 2
A String auf Zahlen überprüfen Allgemeine Java-Themen 5
J Zahlen Abstand zur Null bestimmen Allgemeine Java-Themen 11
R Methoden Was fehlt mir bzw. muss ich bei der Methode countHarshabNumbers ändern damit ich die Harshad Zahlen im Intervall [51, 79] zählen kann? Allgemeine Java-Themen 19
O Variablen Addition von Double-Werten ergibt seltsame 0.9999999 Zahlen Allgemeine Java-Themen 2
B Zufällig zwischen vorgegebenen Zahlen auswählen Allgemeine Java-Themen 6
M Zahlen in Array anordnen Allgemeine Java-Themen 8
D Erste Schritte Arrays vergleichen und die zahlen die nur einmal vorkommen ausgeben Allgemeine Java-Themen 5
D Erste Schritte Fehler mit negativen und 0 Zahlen im String Allgemeine Java-Themen 6
T Tesseract OCR mit Zahlen Allgemeine Java-Themen 1
D Integer-Array variabler Größe mit Zahlen befüllen (Schleifen) Allgemeine Java-Themen 0
F Zahlen zu Bits Allgemeine Java-Themen 3
S Überprüfen, ob 5 Zahlen nebeneinander liegen Allgemeine Java-Themen 5
R Große Zahlen in Worten abkürzen Allgemeine Java-Themen 10
B Arrays mit Text und Zahlen füllen Allgemeine Java-Themen 3
G Aus JTextField Zahlen auslesen und random generieren Allgemeine Java-Themen 10
D Operatoren Logischer Rightshift von negativen Zahlen auf Bit-Ebene Allgemeine Java-Themen 7
L 2-Dimensionaler String: Zahlen verschieben Allgemeine Java-Themen 10
M Algorithmus zum Zahlen einteilen Allgemeine Java-Themen 8
H Fibonacci-Zahlen Allgemeine Java-Themen 5
B Zahlen manuell eingeben und in Array Speichern Allgemeine Java-Themen 2
E mit extrem langen Zahlen (als Zeichneketten) arbeiten Allgemeine Java-Themen 4
L Filewriter schreibt Zahlen in Textdatei Allgemeine Java-Themen 2
T Methoden Zahlen austauschen Allgemeine Java-Themen 8
Z Zahlen aus Bild auslesen Allgemeine Java-Themen 1
M ungerade zahlen auf 4 zahlen aufteilen Allgemeine Java-Themen 2
F Funktionsplotter komplexe Zahlen: geeignetes 3D-Koordinatensystem Allgemeine Java-Themen 16
B Zahlen ausgeben hilfe! Allgemeine Java-Themen 8
S Zahlen aus (String mit zahlen) immer wieder neu auslesen Allgemeine Java-Themen 5
N Bin to Dez und umgekehrt mit sehr großen Zahlen Allgemeine Java-Themen 2
T Modulo-Operator versagt bei zu großen Zahlen? Allgemeine Java-Themen 14
AssELAss String mit Zahlen mit Tausendertrennzeichen versehen Allgemeine Java-Themen 14
D Code bitte mit 19 stelligen Zahlen kompatibel machen Allgemeine Java-Themen 5
U (Java) Happy Numbers in Anlehnung an den Sieb des Eratosthenes (Glueckliche Zahlen) Allgemeine Java-Themen 1
J Array ohne vorher festgelegte Länge oder Wie wandle ich Zahlen in Zahlen mit anderen Basen um? Allgemeine Java-Themen 6
Cayton Bruchrechner stürzt bei eingabe negativer Zahlen ab Allgemeine Java-Themen 4
N Zahl mit bestimmter Länge und nur bestimmten Zahlen generieren lassen Allgemeine Java-Themen 7
P Datentypen String-Daten zu Byte-Zahlen konvertieren - Komme nicht weiter nach vielem versuchen :-/ Allgemeine Java-Themen 7
I Java-Programm: Zahlen in Worte Allgemeine Java-Themen 22
H String auf Zahlen prüfen Allgemeine Java-Themen 4
V iText Textfelder mit Zahlen! Allgemeine Java-Themen 2
R Modulo mit negativen Zahlen Allgemeine Java-Themen 8
Luk10 Römische Zahlen in Java Allgemeine Java-Themen 7
R Codehinweise: Algorithmus Größenvergleich von n Zahlen Allgemeine Java-Themen 5
GianaSisters ArrayList mit Zahlen Allgemeine Java-Themen 10
B User-Input aus Zahlen und Operatoren - beste Umsetzung? Allgemeine Java-Themen 8
S Fixe Zahlen vergleichen Allgemeine Java-Themen 4
D JTable -> 1Spalte nur zahlen Allgemeine Java-Themen 2
N Zahlen in Strings einer ArrayList sortieren Allgemeine Java-Themen 14
T Apache POI Export EXCEL - [Zahlen-Werte] Allgemeine Java-Themen 1
ModellbahnerTT Button mit Zahlen beschriften Allgemeine Java-Themen 1
J Zahlenkombination aus int-array, mit absteigenden Zahlen Allgemeine Java-Themen 6
P große double Zahlen und modulo Allgemeine Java-Themen 8
R Runden von Zahlen Allgemeine Java-Themen 3
J Zahlen Rechtsbuendig in File schreiben Allgemeine Java-Themen 3
W POI - Formatierung für Zahlen Allgemeine Java-Themen 4
MQue Zahlen mit Border Allgemeine Java-Themen 2
T ungerade zahlen berechnen Allgemeine Java-Themen 3
N Zahlen mit Nachkommastellen aus Textfeldern einlesen Allgemeine Java-Themen 6
P Algoritmus für 3er-Paare von n Zahlen Allgemeine Java-Themen 12
A Fibonacci-Zahlen & kopfgesteuerte Schleifen & Strukt Allgemeine Java-Themen 8
J Suche regex-Pattern fuer Liste von Zahlen zwischen 0-100 Allgemeine Java-Themen 6
G die mittlere von 5 Zahlen nur mit if und else finden Allgemeine Java-Themen 48
MQue Zahlen an alysieren Allgemeine Java-Themen 6
ARadauer Random keine Zahlen doppelt Allgemeine Java-Themen 4
V FileWriter und Zahlen (Kein Problem, nur Verständnisfrage) Allgemeine Java-Themen 4
G Strings die Zahlen enthalten sinnvoll sortieren (A2 < A10 Allgemeine Java-Themen 4
F 3 Zahlen "vereinfachen" Allgemeine Java-Themen 5

Ähnliche Java Themen

Neue Themen


Oben