C++ deutlich langsamer als Java, warum?

[minos5000]

Hi,

ich hab mich zum Zeitvertreib daran gemacht die Aufgaben von projecteuler.net zu lösen und folgendes auf die gleiche Weise einmal in C++ und dann in Java implementiert:


2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?


C++

#include <iostream>

using namespace std;

int number = 21;
bool divisible()
{
for (int i = 2; i < 21; i++)
{
if (number % i != 0)
return false;
}
return true;
}

int main()
{
while (!divisible()) {
number++;
}
cout << number;
return 0;
}


Java

package de.euler;

public class Problem5 {

static int number = 21;

public static void main(String[] args) {
while (!divisible())
number++;
System.out.println(number);
}

private static boolean divisible() {
for (int i = 2; i < 21; i++) {
if (number % i != 0)
return false;
}
return true;
}
}



Vorneweg, von C++ hab ich nicht viel Ahnung und wahrscheinlich verletzte ich irgendwelche ehernen Regeln, aber wundern tut's mich trotzdem, dass die C++ Lösung (unter V++ 2010 Express) 2 sek. braucht, während die Java Variante das ganze in 517ms schafft...
Woran liegts?


Besten Gruß
minos

[Shink]

Vorneweg, von C++ hab ich nicht viel Ahnung und wahrscheinlich verletzte ich irgendwelche ehernen Regeln, aber wundern tut's mich trotzdem, dass die C++ Lösung (unter V++ 2010 Express) 2 sek. braucht, während die Java Variante das ganze in 517ms schafft...
Woran liegts?
Was hast du denn genau gemessen?

[minos5000]

Jeweils bei Ein- und Ausgang aus der Hauptfunktion die Systemzeit genommen und dann die Differenz ausgegeben.

[#44]

Debug- oder Release-Build?

[Tiamat]

Zeig mal den Code der Zeitmessung, ich vermute einen Fehler beim C++ Part

[minos5000]

Code mit Zeitmessung


JAVA

public static void main(String[] args) {
long start = System.currentTimeMillis();
while (!divisible())
number++;
System.out.println(number);
System.out.println(System.currentTimeMillis() - start);
}


C

int main()
{
int start = time(NULL);
while (!divisible()) {
number++;
}
cout << number << endl;
cout << time(NULL) - start;
return 0;
}


Ich weiss, time() ist ungenauer, aber an der Größenordnung ändert das ja nichts.

@44 Release-Build, bei Debug hat ein Durchlauf sogar 8 sek gebraucht.

[Nighthawk13]

Hmm ein guter Compiler könnte Loop-unrolling machen.
Dann wäre x%i z.B. x%2 was zu x&2 optimiert werden kann usw.

Vielleicht macht das der Java-JIT-Compiler und der C++ Compiler nicht?

[seba86]

C++ (ohne .NET!) geht definitiv schneller als Java. Vielleicht auch einfach mal den Compiler wechseln.

[Monger]

Wahrscheinlich ist in beiden Fällen die Ausgabe die teuerste Operation, und davon hast du im C++ Beispiel ein paar mehr als bei Java. Kann eventuell auch am Laufzeitverhalten liegen: beide Programme messen ja nur die Zeit des Methodenaufrufs, nicht etwa des gesamten Programms. Vor Aufruf der Main passiert nunmal auch noch einiges. Möglicherweise macht sich auch Java standardmäßig ein paar Plattformoptimierungen zunutze, die bei C++ nicht aktiv sind.

Aber grundsätzlich ist eine Performancemessung bei so kleinen Zeitabständen ohnehin widersinnig. Performance sollte man grundsätzlich nur am lebenden Objekt (sprich: einer realen Anwendung, wo man einen Engpass vermutet) messen.

[Trap]

Poste mal die Compiler-Kommandozeile die du verwendest.

[RLZ]

Spezialfälle, bei denen ein Compiler versagt, gibt es immer wieder. Hier hast du wohl offensichtlich einen gefunden.

Davon abgesehen noch ein paar Dinge, die mir direkt ins Auge springen:
- Die Schleife sollte man von 20 ab dekrementieren
- Ein Early-Out gegen die größte 2er Potenz (16) wird wahrscheinlich Wunder wirken
- Globale Variablen verwendet man nur wenn es unbedingt sein muss. Hier also nicht.

[#44]

- Die Schleife sollte man von 20 ab dekrementieren
Wieso gerade so? (Steh' ich auf'm Schlauch?)

Allgemein könnte man nur mit den Zahlen 11-20 testen, 1-10 sind durch jeweils andere Zahlen bereits implizit geprüft.
Teilbar durch 20? Dann auch durch 10.
18? Dann natürlich auch 9.
Usw.

Mit dem Testen könnte man außerdem bei 2521 beginnen.

[Gast]

Wahrscheinlich ist in beiden Fällen die Ausgabe die teuerste Operation, und davon hast du im C++ Beispiel ein paar mehr als bei Java.

Ich seh in beiden Fällen nur eine Ausgabe, jeweils nur dann, wenn eine Zahl gefunden ist.

Versuch Inlining, also etwas wie inline bool divisible() - es sei denn der MSVC-Compiler tut das implizit. Das wird den Kohl nicht allzu fett machen, wäre hier aber keine schlechte Idee.

[Shink]

Wahrscheinlich ist in beiden Fällen die Ausgabe die teuerste Operation, und davon hast du im C++ Beispiel ein paar mehr als bei Java.
Aber hallo - 2 Sekunden für Kommandozeilen-ausgaben?:freak:

Aber grundsätzlich ist eine Performancemessung bei so kleinen Zeitabständen ohnehin widersinnig. Performance sollte man grundsätzlich nur am lebenden Objekt (sprich: einer realen Anwendung, wo man einen Engpass vermutet) messen.
Wie gesagt: 2 Sekunden - da kann eine 3GHz-CPU schon ordentlich Operationen raushauen.

Dass der MS-Compiler eine lahme Krücke ist halte ich auch für Unsinn.
Und dass man den Code optimieren könnte ist auch klar. (Ich würde z.B. fix das Ergebnis ausgeben.:cool:) Das erklärt aber keine Unterschiede zwischen Programmiersprachen.

[Monger]

Aber hallo - 2 Sekunden für Kommandozeilen-ausgaben?:freak:

Ja okay, ich gebs zu, blödes Argument ;)

Die Frage könnte man ein für allemal beantworten, wenn man beide Programme mal durch nen Profiler schieben würde. Performance ist ein furchtbar unintuitives Thema, da erlebt man oft Überraschungen.

Ob die Zeit wirklich am Kernalgorithmus liegt, kann man ja leicht feststellen: einfach mal die Laufzeit deutlich erhöhen (Schleifendurchläufe verzehnfachen), und dann mal schauen wie die Laufzeit skaliert. Ich tippe drauf, dass sich an den zwei Sekunden nichts nennenswert tun wird.

Edit: so blöd es klingt - auch die Uhr kann ein Schwachpunkt sein. Für Performance Messungen nimmt man eigentlich High Speed Counter, die normalen DateTime Klassen zählen in aller Regel nicht direkt die CPU Zyklen. Aber so falsch sollte die Uhr auch wieder nicht gehen.

[RLZ]

Wieso gerade so? (Steh' ich auf'm Schlauch?)
Weil du dann früher rausfliegst. Überleg mal wieviele Zahlen durch 20 teilbar sind im Vergleich zu Zahlen, die durch 2 Teilbar sind. ;)

Den Suchraum könnte man, wenn man sich ernsthaft drüber Gedanken macht, wohl wesentlich verkleinern. Jeder Zahl zu testen ist eher Schwachsinn.

[sth]

Aber so falsch sollte die Uhr auch wieder nicht gehen.
Unter Windows kommt man auf vielen Wegen nicht unter ~16ms Genauigkeit, aber selbst das sollte hier keinen limitierenden Faktor darstellen.

Habe das C++-Programm aus dem ersten Posting mal unter OSX mit gcc und clang getestet (auf 'nem i7-2600) und ähnliche Ergebnisse erzielt:


$ g++ test.cpp -o test -O3
$ time ./test
232792560
real 0m1.855s
user 0m1.854s
sys 0m0.001s

$ clang++ test.cpp -o test -O4
$ time ./test
232792560
real 0m1.891s
user 0m1.890s
sys 0m0.001s

[Senior Sanchez]

EDIT: Nee, war quatsch, geht nicht.

So, war doch nicht ganz so quatsch.
Schneller könnte es gehen, indem man eine Primfaktorenzerlegung der Zahlen von 1 bis 20 macht.
Ab dann multipliziert man ausgehend von der kleinsten Zahl, also ab 1 beginnend, die Primfaktoren jeder Zahl miteinander. Dabei fügt man aber nur die Primfaktoren hinzu, die noch nicht im Gesamtprodukt vertreten sind. Dabei ist auch auf die korrekte Anzahl der Primfaktoren zu achten.

Beispiel für 1 - 10:

10: 2x 5
9: 3x 3
8 : 2x2x2
7: 7
6 : 2x3
5: 5
4 : 2x2
3 : 3
2 : 2
1 : 1

1*2*3*2*5*7*2*3 = 2520

Also von der 4 wird z.B. nur eine 2 mitgenommen, da der andere Primfaktor 2 bereits durch die Zahl 2 vorhanden ist.

Das ganze sollte etwas schneller arbeiten und wenn man die Primfaktorenzerlegung geschickt anstellt, sollte das in der Praxis schneller sein als die oben beschriebene Variante.

[Marscel]

EDIT: Nein, das fiel nicht so sehr ins Gewicht wie gedacht.

[pest]

Dann wäre x%i z.B. x%2 was zu x&2 optimiert werden kann usw.


nochmal nachdenken ;)

man könnte aber tatsächlich mal probieren die modulo-operationen mit einem zusätzlichen branch zu ersetzen,
also die komplette schleife unrollen und alle zweierpotenzen von i durch "if (number&(i-1)) return false" ersetzen.

oder


if ((i && !(i & (i-1)))) && (number&(i-1)) return false;
else if (number%i) return false;


außerdem wird der Funktionsaufruf bei so einer kurzen inneren Schleife einiges Kosten, also Inlinen.

[sth]

Back to topic:
Es geht immernoch um die Frage, warum derselbe Code (egal ob der Algo für die Problemstellung optimal ist oder nicht) unter Java schneller läuft als unter C/C++.

[edit]: Die Java-Version läuft bei mir ebenfalls ca. um den Faktor 4 schneller.

[Pinoccio]

EDIT: Nee, war quatsch, geht nicht.

So, war doch nicht ganz so quatsch.
Schneller könnte es gehen, indem man eine Primfaktorenzerlegung der Zahlen von 1 bis 20 macht.
Ab dann multipliziert man ausgehend von der kleinsten Zahl, also ab 1 beginnend, die Primfaktoren jeder Zahl miteinander. Dabei fügt man aber nur die Primfaktoren hinzu, die noch nicht im Gesamtprodukt vertreten sind. Dabei ist auch auf die korrekte Anzahl der Primfaktoren zu achten.Mathematisch ist da Problem, wie du schön darlegst, nahezu trivial.
Algorithmisch kann man - neben der direkten, von dir vorgeschlagenene "Formel" - sicherlich überlegen, ob man bei Teilbarkeit durch 16 und 15 auch noch 12, 8, 6, 5, 4 und 2 mittesten muss. Oder ob man ungerade Zahlen überhaupt berücksichtigt. Aber darum geht es ja gar nicht in diesem Thread.

Vorweg: Ich habe keine Ahnung von C++!
Was mir aufällt, ist das static in der JAVA-Variante. Gibt man das auf (wie auch immer), dann wird die ganze Chose langsamer, wenn auch nur wenig. Liegt es evtl. daran?

Der Algo führt 416.181.952 Modulo-Berechnungen durch, die benötigen ohne sonstige Funktionsoverhead ca. 2/3 der Zeit. Kann mal einer testen, wie das bei C++ aussieht?

Grob kalkuliert dürften von den 2/3 (etwa 1,6 Sekunden von 2,4 Sekunden bei mir, Intel i3@3,6 GHz) die hälft wirklich für Hardware-Rechnen draufgehen. Schwer zu kalkulieren, afaik ist bei Integerdivisionen (und auch Modulo) die Rechenzeit von den Operanden abhängig. (vgl z. B. http://www.agner.org/optimize/instruction_tables.pdf was 7-17 Takte für I32 und 26-86 Takte für I64 ausm Regsiter angibt, wenn ich es richtig lese.)

/edit: Ich seh grade, das war bei euch die c++-Zeit. Warum ist mein JAVA so langsam? o.O

mfg

[pest]

Höchstwahrscheinlich wird die Schleife in Java unrolled, man sollte zusätzlich mal die gesammte Anzahl an Schleifendurchläufen mitzählen!

In 2 sec. machen meine Programme was ganz Anderes.

[Pinoccio]

Höchstwahrscheinlich wird die Schleife in Java unrolled, man sollte zusätzlich mal die gesammte Anzahl an Schleifendurchläufen mitzählen!Wenn du in der Schleife einen Counter hochzählst, müsste der doch mitunrolled werden, oder?

mfg

[pest]

ja! aber ist ja Jacke wie Hose. Ich möchte ja nur wissen ob das Java-Kompilat anders als das C-Kompilat arbeitet. Z.B. von oben nach unten zählen und daher früher abbricht.

Ohne das Java-Kompilat zu sehen sind das nur Mutmaßungen.
Schleife von oben nach unten unrollen, alle Zweierpotenzen durch & (i-1) ersetzen, wenn es dann immer noch zu langsam ist liegt es an Etwas Anderem, vielleicht extreme Cache-Misses, weil number als global deklariert ist, als Parameter könnte es in einem Register landen.

[Watson007]

Höchstwahrscheinlich wird die Schleife in Java unrolled, man sollte zusätzlich mal die gesammte Anzahl an Schleifendurchläufen mitzählen!

In 2 sec. machen meine Programme was ganz Anderes.

was meinst du mit unrolled?

[pest]

Schleife komplett entfernen. number als Parameter übergeben.

und

if (number&1) return false;
if (number%3) return false;
if (number&3) return false;
if (number%5) return false;
if (number%6) return false;
if (number%7) return false;
if (number&7) return false;
usw.


dann von hinten nach vorne...ist immer noch der selbe Algorithmus :D

[mittelding]

Könnte man dieses unrolling testweise nicht vermeiden, indem man die Zahl für die Schleifenbedingung zur Laufzeit von der Eingabe einliest und Java somit garnicht in vorhinein wissen kann, wie das unrolling aussieht?
Nur so ein Laiengedanke, habe nicht viel Ahnung von Compilern :)

[Pinoccio]

Könnte man dieses unrolling testweise nicht vermeiden, indem man die Zahl für die Schleifenbedingung zur Laufzeit von der Eingabe einliest und Java somit garnicht in vorhinein wissen kann, wie das unrolling aussieht?
Nur so ein Laiengedanke, habe nicht viel Ahnung von Compilern :)Das könnte der Compiler merken - genau das wäre ein Vorteil von JIT-Compilern.

mfg

[#44]

Spannend:
Ich habe die Methode so umgebaut, dass nur ein Aufruf nötig ist (in der Hoffnung die Laufzeit zu verbessern).
Ergebnis: Statt ~830ms braucht es jetzt satte ~6350ms für einen Durchlauf.


public class Problem5 {

public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(divisible());
System.out.println(System.currentTimeMillis() - start);
}

private static int divisible() {

int number = 21;

for (int i = 2; i < 21; ++i)
{
if (number % i != 0)
{
++number;
i=2;
}
}
return number;
}
}

Java rollt also die Schleife definitiv auf - was bei diesem Code nicht möglich ist, da die Schleifenvariable verändert werden könnte.
Das ist die einzige Erklärung warum dieser Code länger läuft. (Und zeigt sehr schön, was gut gemeinte Optimierung anrichten kann!)

Von Hand aufgerollt verbessert sich die Laufzeit wieder auf ~950ms
private static int divisible() {

int number = 21;

while (!(number % 2 == 0 && number % 3 == 0 && number % 4 == 0 && number % 5 == 0 && number % 6 == 0 && number % 7 == 0 && number % 8 == 0 && number % 9 == 0 && number % 10 == 0 && number % 11 == 0 && number % 12 == 0 && number % 13 == 0 && number % 14 == 0 && number % 15 == 0 && number % 16 == 0 && number % 17 == 0 && number % 18 == 0 && number % 19 == 0 && number % 20 == 0))
{
++number;
}

return number;
}
Wo sich die letzten 120ms verstecken, habe ich aber noch nicht herausgefunden.

€: Mache ich nun number noch static fängt die Laufzeit an zwischen ~780 und ~950 zu pendeln. Das tut sie mit dem Code des TS definitiv nicht - da sind es ziemlich konstant um die 830ms.

[Tiamat]

Hab gerade mal etwas ausprobiert :


using namespace std;
int number = 21;
bool divisible()
{
if((number % 2 != 0) || (number % 3 != 0) || (number % 4 != 0) ||
(number % 5 != 0) || (number % 6 != 0) || (number % 7 != 0) ||
(number % 7 != 0) || (number % 9 != 0) || (number % 10 != 0) ||
(number % 11 != 0) || (number % 12 != 0) || (number % 13 != 0) ||
(number % 14 != 0) || (number % 15 != 0) || (number % 16 != 0) ||
(number % 17 != 0) || (number % 18 != 0) || (number % 19 != 0) || (number % 20 != 0))
return false;

return true;
}

int main (int argc, char * const argv[]) {
srand(time(NULL));
clock_t start = clock();
while (!divisible()) {
number+=1;
}
clock_t end = clock();
cout << number << endl;
cout << (end - start);




return 0;
}



= ca. 915-930ms bei -o O2 (Core2Duo 2.4Ghz) 32bit

[hell_bird]

Macht mal jemand den selben Test mit diesem schnipsel code (übernommen von RLZ)

#include <iostream>
#include <ctime>

using namespace std;


bool divisible(int number)
{
if(number&15) return false;
for (int i = 20; i > 1; i--)
{
if (number % i != 0)
return false;
}
return true;
}

int main (int argc, char * const argv[]) {
clock_t start = clock();
int number = 21;
while (!divisible(number)) {
number++;
}
clock_t end = clock();
cout << number << endl;
cout << (end - start);


return 0;
}

Also für mingw32 v4.6.1 (-O3 -DNDEBUG) gibt das bei mir folgendes Bild:
Originalcode: 2300ms
Dieser veränderte Code: 180ms

Aber im großen und ganzen sollte es niemanden verwundern, dass der Compiler einem das Denken nicht abnehmen kann und außerdem manchmal einen ganz schönen Scheiß fabriziert. Auch nicht vergessen sollte man, dass hier massenhaft mit IDIVs (modulo) gearbeitet wird, was zu den langsamsten Instructions zählt. Deshalb ist es intelligenter die Methode von Senior Sanchez zu verwenden, mit einer geschätzten Laufzeit von 0ms.

Kurz gesagt: dass Java schneller ist, liegt an der Schwäche deines C++ Compilers. Probier mal den Intelcompiler, der hat glaube ich gerade bei Schleifen seine Stärke.

[hell_bird]

Also falls es jemand interessiert: so wäre es richtig (aber geht natürlich ein wenig am Thema vorbei). Rechenzeit vernachlässigbar...


#include <iostream>
#include <ctime>
#include <cmath>

using namespace std;


unsigned long long getNumber(unsigned int div)
{

unsigned long long number = 1;

bool visited[div+1];
for(unsigned int i=0; i<=div; i++) visited[i] = false;

for(unsigned int i=2; i<=div; i++)
{
if(!visited[i])
{
visited[i] = true;
unsigned int maxp = 1;

for(unsigned int u = 2*i; u<=div; u+=i)
{
visited[u] = true;
unsigned int p = 0, utmp = u;
while((utmp % i) == 0)
{
p++;
utmp /= i;
}
maxp = max(maxp, p);
}
number *= pow(i, maxp);
}

}

return number;
}

int main (int argc, char * const argv[]) {
clock_t start = clock();

unsigned long long number = getNumber(20);

clock_t end = clock();
cout << number << endl;
cout << (end - start);


return 0;
}

[Shink]

ja! aber ist ja Jacke wie Hose. Ich möchte ja nur wissen ob das Java-Kompilat anders als das C-Kompilat arbeitet. Z.B. von oben nach unten zählen und daher früher abbricht.

Ohne das Java-Kompilat zu sehen sind das nur Mutmaßungen.
Wenn ich mich recht erinnere macht der Java-Compiler kein unrolling - wenn dann der JITter sobald er draufkommt dass es notwendig ist.

Was der Bytecode macht lässt sich ja relativ einfach herausfinden; was der JIT-Compiler macht hingegen nicht.

[Nighthawk13]

Der ursprüngliche Code läuft bei mir schneller mit __forceinline__ als inline(2.2 vs 3.3 Sekunden) -> Der Compiler(VS2008) ignoriert das normale inline und macht stur nen CALL. Ein Gruß an das M$-Compilerteam! :uclap:

Hier mal der ASM-Code der Inline-variante:

; 75 : volatile int i=0;

mov esi, DWORD PTR ?number@@3HA ; number
mov DWORD PTR __$EHRec$[esp+88], 0
mov DWORD PTR _i$[esp+80], 0
$LL2@testy:

; 76 : while (!divisible())

mov ecx, 2
$LL9@testy:
mov eax, esi
cdq
idiv ecx
test edx, edx
jne $LN29@testy
inc ecx
cmp ecx, 21 ; 00000015H
jl SHORT $LL9@testy

; 78 : i = number;

[...]

; 77 : number++;
$LN29@testy:
inc esi
mov DWORD PTR ?number@@3HA, esi ; number
jmp $LL2@testy

Das "idiv" haut natürlich rein(17-28Cycles auf Nehalem), wie bereits festgestellt wurde.

[hell_bird]

Naja inline ist ja auch nur eine Empfehlung, die der Compiler ignorieren darf, weil er ja eh alles besser weiß.

Aber mal im Ernst: was ist denn an dem Endprodukt falsch? Oder anders gesagt, wie schafft es Java da wesentlich schneller zu sein? Wenn ich später ein wenig Zeit habe, werde ich mal versuchen wie schnell "handoptimierter" assemblercode ist.

[pest]

wurde doch schon festgestellt das Java die Schleife unrolled. Du sparst dir dir Speicherzugriff auf [esi] und [inc ecx,cmp ecx, 21,jl SHORT $LL9@testy] fällt weg.

[hell_bird]

Stimmt... der Speicherzugriff ist total überflüssig, das hatte ich übersehen. Aber ich glaube nicht, dass das aufrollen einen so großen Einfluss hat, vor allem weil der Sprung ja praktisch immer richtig vorhergesagt wird.

[#44]

Stimmt... der Speicherzugriff ist total überflüssig, das hatte ich übersehen. Aber ich glaube nicht, dass das aufrollen einen so großen Einfluss hat, vor allem weil der Sprung ja praktisch immer richtig vorhergesagt wird.
Durch Aufrollen fallen bei jedem Durchlauf der äußeren Schleife 20 19 Sprünge, 20 19 Inkremet-Operationen und 20 19 Vergleiche weg.

In der Summe je 4,7 4,4 MRD Sprünge, Inkrements und Vergleiche.

Und: Wie erklärst du sonst den Geschwindigkeitsfaktor 7-8 beim Beispiel aus meinem letzten Post?

[hell_bird]

Durch Aufrollen fallen bei jedem Durchlauf der äußeren Schleife 20 19 Sprünge, 20 19 Inkremet-Operationen und 20 19 Vergleiche weg.

In der Summe je 4,7 4,4 MRD Sprünge, Inkrements und Vergleiche.

Und: Wie erklärst du sonst den Geschwindigkeitsfaktor 7-8 beim Beispiel aus meinem letzten Post?
1. Die Inkrements fallen nicht weg, da es keine Instruction gibt, die durch eine Konstante Zahl teilt, ich muss den Teiler als Register oder Speicheradresse mitgeben

2. 4,4 Mrd wäre richtig wenn die Schleife jedes mal alle 19 Zahlen duchprobieren würde. Das ist aber nicht der Fall. In der hälfte der Fälle wiederholt sich die schleife beispielsweise gar nicht.

Aber: Ich wollte das ganze natürlich nicht so stehen lassen und habe einen Test gemacht. Code und Windowsexecutables sind im Anhang. Im einzelnen habe ich folgendes gemacht:

standard.asm:
Zuerst einmal wollte ich genau das, was im ersten Post geschrieben steht in Assembler umsetzen undzwar ohne unnütze Instructions und ohne Speicherzugriffe. Es gibt auch keinen Funktionsaufruf, ist also inline (was mein Compiler mingw 4.6.1 in der Optiumierungsstufe -O3 ganz von alleine erkannt hat)

standardx.asm:
Der Unterschied zu standard.asm ist, dass der erst Schleifendurchlauf (Teilbar durch 2?) durch eine Bitoperation ersetzt wird. Das hat mingw 4.6.1 komischerweise mit -O1 gemacht, mit -O3 nicht, was dazu geführt hat, dass -O1 die schnellste Optimierungsstufe für den Code von minos war.

unrolled.asm
standard.asm aufgerollt

unrolledx.asm
Aufgerollt und alle zweierpotenzen durch Bitoperationen überprüft. Ich denke das ist noch eine Operation, die man von einem Compiler erwarten könnte.

Das ganze habe ich auf einem Pentium E5200@2.5Ghz getestet (in meinem vorigen Post hatte ich eine andere CPU, ist also nicht vergleichbar) mit den folgenden Ergebnissen:


standard: 4203ms
standardx: 1406ms
unrolled: 2203ms
unrolledx: 766ms


Somit komme ich auch auf einen Faktor 5.5 zwischen stur hingeklatscht und ordentlich optimiert. Hätte ich nicht erwartet.

Mich würden noch Ergebnisse von anderen CPUs interessieren. Falls jemand Zeit hat lasst doch einfach mal die Programme aus dem Anhang laufen:

Aufruf mit:

time.exe standard.exe
etc...


Ansonsten besteht natürlich immer die Möglichkeit, dass ich selbst einen Fehler gemacht habe... Ich lasse mich gerne korrigieren.

// edit:
mingw-runtime Dateien habe ich noch angehängt

[#44]

1. Die Inkrements fallen nicht weg, da es keine Instruction gibt, die durch eine Konstante Zahl teilt, ich muss den Teiler als Register oder Speicheradresse mitgeben

2. 4,4 Mrd wäre richtig wenn die Schleife jedes mal alle 19 Zahlen duchprobieren würde. Das ist aber nicht der Fall. In der hälfte der Fälle wiederholt sich die schleife beispielsweise gar nicht.

Aber: Ich wollte das ganze natürlich nicht so stehen lassen und habe einen Test gemacht. Code und Windowsexecutables sind im Anhang. Im einzelnen habe ich folgendes gemacht:

Zu 2.: Wie sagt man so schön? Denken ist Glückssache :redface:

1. Verstehe ich aber nicht ganz, wenn die Schleifenvariable wegfällt, fällt doch natürlich auch das Hochzählen dieser weg :confused:

Zu deinem Assembler-Programm:

Stock Phenom II X4 940 (3GHz)


Standard: 6053ms
Standardx: 2855ms
Unrolled: 5975ms
Unrolledx: 2078ms


Musste vorher aber noch zwei DLLs laden:
libstdc++-6.dll
libgcc_s_dw2-1.dll

[Pinoccio]

2. 4,4 Mrd wäre richtig wenn die Schleife jedes mal alle 19 Zahlen duchprobieren würde. Das ist aber nicht der Fall. In der hälfte der Fälle wiederholt sich die schleife beispielsweise gar nicht.Es sind 416.181.952 Modulo-Berechnungen beim hier implkementierten udn diskutierten Ansatz. Macht 1,75 Durchläufe pro Zahl.

Auf anderen PCs testen ist so eine Sache, ich bekomme eine Fehlermeldung, dass die libgcc_s_dw2-1.dll fehlt.
/edit: da war #44 schneller. Ich ahbe die beiden DLLs nicht runtergeladen, daher keine Werte von mir.

Und die Zeitnahme time zu nenen ist auch ungünstig, da das bereits ein Befehl in der Command-line (http://technet.microsoft.com/de-de/library/cc770579%28WS.10%29.aspx) ist.

mfg

[hell_bird]

oops... habe dem vorigen Post noch die Runtimedateien angehängt... hoffe dass es so funktioniert. Warum hat eingentlich jeder Compiler seine eigene Runtime... können die das nicht linken?

@#44: Interessante Werte. Da scheinen sich Unterschiede in der Architektur zu zeigen. Vor allem da du ja bei nicht gerade langsamen 3Ghz taktest. Ich tippe einfach mal auf die Art der Sprungvorhersage und/oder die länge der Pipline.
sagmal ist das die selbe maschine mit der du in einem vorigen post ~800ms hattest?

und zu dem Inkrementieren: Entweder man muss inkrementieren oder jedes mal das Register mit einem mov befehl füllen. Da ist inkrementieren die bessere Lösung

[pest]

1. Verstehe ich aber nicht ganz, wenn die Schleifenvariable wegfällt, fällt doch natürlich auch das Hochzählen dieser weg :confused:


x86 suckt derbe

Eine Division teilt immer den Inhalt von EDX:EAX mit einem anderen Rechenregister und speichert den Quotienten in EAX und den Rest in EDX.
Der Divisor muss dabei ein reg32-Register sein, kann also keine Konstante sein.

die Übersetzung für (number%i) ist dann

mov ecx,[i] // lade zähler
mov eax,[number] // lade eax mit number
xor edx,edx // lösche edx
div ecx // division von edx:eax mit ecx
test edx,edx // rest testen

[#44]

sagmal ist das die selbe maschine mit der du in einem vorigen post ~800ms hattest?
Ja. Diesmal sogar ohne zwei Minecraft Clients und VLC im Hintergrund...
Das Javaprogramm verbessert sich unter dieses Vorraussetzungen noch mal um 20ms (auf 810ms)

Und danke für die Erklärung!

[pest]

hier noch meine Zeiten C2D@45nm mit 3.6GHz


standard: 2917ms
standardx: 967ms
unrolled: 1513ms
unrolledx: 530ms

[hell_bird]

hier noch meine Zeiten C2D@45nm mit 3.6GHz
Zu meinen Messwerten genau Taktskaliert. Danke.

Ja. Diesmal sogar ohne zwei Minecraft Clients und VLC im Hintergrund...
Ich hab hier auch einen Phenom herumstehen und konnte deine Katastrophalen Werte reproduzieren. Java hab ich nicht drauf, aber ich werde in den nächsten Tagen mal versuchen das ganze mit Java laufen zu lassen und hiermit zu analysieren:
http://stackoverflow.com/questions/6911603/disassemble-java-jit-compiled-native-bytecode (hat das jemand schonmal benutzt?)

[pest]

Vielleicht kann der JIT das Problem auf alle Cores verteilen :D - kann mir schlecht vorstellen wie man das noch 2x schneller machen soll ohne Grundlegend etwas zu ändern.
Von 20 zu 2 zählen wird halt auch nochmal ne Menge bringen.

[hell_bird]

Kann es leider in Java nicht nachvollziehen. Bei mir ist Java zwischen 2,5 und 4 Sekunden auf E5200@2.5GHz und zwischen 5.5 (schnipsel von #44) und 7.7 (Threadstarter) Sekunden auf X3 720 @ 3.4 GHz. Jeweils wird nur ein Kern benutzt. Ich habe einfach in Eclipse ein jar gemacht auf den Rechner verschoben und mit "java -jar test1.jar" gestartet. Muss ich da noch etwas besonderes beachten?

@alle die so gute Ergebnisse mit Java haben: könnt ihr nochmal nachmessen ob das nicht ein Bug in der Zeitmessung ist? Entweder per Augenmaß oder mit System.nanoTime().

long start = System.nanoTime();
[...]
System.out.println((System.nanoTime() - start)/1e9);

[Nighthawk13]

i5-750@3.3Ghz
standard.exe : 3463ms
standardx.exe: 952ms
unrolled.exe 1919ms
unrolledx.exe: 687ms
Die Messwert schwanken z.T. ziemlich: Letzter Test 670-780ms z.B.

[#44]

Ausgabe des Codes vom TS mit Nanotime: 0.805569127
Egal ob aus Eclipse oder als JAR.

Hab das 64bit SDK installiert, falls das etwas ausmachen sollte...

[hell_bird]

Hab das 64bit SDK installiert, falls das etwas ausmachen sollte...
Oha tatsache... habe 64bit jre7 installiert und die Zeiten haben sich deutlich verbessert. Ich hoffe ich kann das demnächst analysieren. Hat jemand eine Idee wie mit x86-64 das Problem leichter gelöst werden kann? Mir scheint, dass immer noch nur ein Kern genutzt wird. Geht da was mit SIMD? Aber eigentlich gibt es keinen Grund warum das nicht mit der 32bit jre klappt...

[Nighthawk13]

32->64bit verdoppelt die Anzahl Register(8->16), d.h. weniger Load/Store-Instruktionen werden fürs Register Spilling verschwendet. Ansonsten hat x64 (imo) kein Performance-Vorteil.

[Coda]

Wenn man wirklich 64-Bit-Integer-Arithmetik benötigt ist es auch schneller als 32 Bit. Das ist allerdings ziemlich selten der Fall.

Vielleicht kann der JIT das Problem auf alle Cores verteilen :D
Sehr unwahrscheinlich, das funktioniert selbst mit einem Offline-Compiler nichtmal bei simplen Schleifen ordentlich.


Btw:
#include <iostream>
#include <unordered_map>
#include <algorithm>

void factorize(unsigned int number, std::unordered_map<unsigned int, unsigned int> &primes)
{
for(unsigned int i = 2; i <= number; ++i)
{
unsigned int factor_count = 0;

while(number % i == 0 && number != 1) {
number /= i;
++factor_count;
}

if(factor_count > 0) {
auto find_iter = primes.find(i);

if(find_iter != primes.end()) {
find_iter->second = std::max(factor_count, find_iter->second);
}
else {
primes[i] = factor_count;
}
}
}
}

int main()
{
std::unordered_map<unsigned int, unsigned int> primes;

for(unsigned int i = 1; i<= 20; ++i) {
factorize(i, primes);
}

unsigned int result = 1;
for(auto iter = primes.begin(); iter != primes.end(); ++iter) {
for(unsigned int i = 0; i < iter->second; ++i) {
result *= iter->first;
}
}

std::cout << result << std::endl;
}

time ./test
232792560

real 0m0.002s
user 0m0.000s
sys 0m0.001s

[#44]

Wer bencht jetzt noch x64 Binaries vom C++ Code um die Eingangsfrage zu beantworten? *g*

[Coda]

Macht auf meinem Server (Intel Xeon E5620 2.40GHz) keinen Unterschied:

time ./test2-x64
232792560
real 0m2.540s
user 0m2.534s
sys 0m0.002s


time ./test2-x86
232792560
real 0m2.540s
user 0m2.535s
sys 0m0.001s


Ist alles GCC 4.4 mit -O3

x86 suckt derbe

Eine Division teilt immer den Inhalt von EDX:EAX mit einem anderen Rechenregister und speichert den Quotienten in EAX und den Rest in EDX.
Der Divisor muss dabei ein reg32-Register sein, kann also keine Konstante sein.

die Übersetzung für (number%i) ist dann

mov ecx,[i] // lade zähler
mov eax,[number] // lade eax mit number
xor edx,edx // lösche edx
div ecx // division von edx:eax mit ecx
test edx,edx // rest testen

Du glaubst gar nicht, was mit register renaming alles aufgefangen wird ;)

[hell_bird]

Ich bräuchte mal ein wenig Hilfe.

Was ich weiß:
- Die beste Lösung für das Problem ist es die Schleife aufzurollen und die Modulooperationen mit zweierpotenzen durch Bitoperationen zu ersetzen
- Phenom II Prozessoren haben ein Problem mit der Art wie ich in meinem obigen Post die Schleife aufgerollt habe. Die Zeit verbessert sich nicht gegenüber der unaufgerollten Version
- Die üblichen C++ Compiler sind eher noch schlechter als meine Version
- Die Java x64 Version erzeugt einen ziemlich gut optimierten Code, die x86 Version ist sehr viel langsamer
- Java x64 ist auch auf Phenom II Prozessoren sehr performant
- Das Geheimnis von Java x64 ist auch das Aufrollen von Schleifen zu erkennen daran, dass wenn man den Parameter "-XX:LoopUnrollLimit=0" mitgibt, die Performance um den Faktor 7-8 langsamer wird

Zusammengefasst:
- Java ist in diesem Fall schneller als die meisten C++ Compiler :mad:
- Phenoms haben irgendeine Architekturschwäche
- Sie können das Ergebnis aber fast so schnell wie Intelprozessoren berechnen wenn sie mit dem richtigen Code gefüttert werden

Wofür ich Hilfe bräuchte:
An irgendetwas müssen die Phenom II Prozessoren ja schwer zu kauen haben und ich kann mir gerade einfach gar nichts vorstellen an dem es liegen könnte. Es gibt die Möglichkeit mit "-XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly" den Code des jit compilers auszugeben, allerdings benötigt man dazu eine Bibliothek, die es ausgerechnet für windows 64 bit nicht als binary gibt. Könnte jemand einfach den Code vom Originalpost nehmen und unter linux und der 64bit Java VM (idealerweise auf einem Phenom II) rauslassen und posten?

https://wikis.oracle.com/display/HotSpotInternals/PrintAssembly

[Tiamat]

bool divisible()
{
if(number & 1 != 0)
return false;
for(int i = 20; i >= 3; i-=1) {
if(number % i != 0)
return false;

}

return true;
}


Diese kaum modifizierte Variante kommt bei mir (2.4Ghz Core2Duo, GCC 4.2) auf
660 ms. Die entsprechende Java Variante benötigt bei mir 1100ms.

[hell_bird]

if((number & 15 != 0) || (number & 1 != 0))

Das wird wahrscheinlich nochmal deutlich besser sein... trotzdem fänd ich gerade am interessantesten wie Java den "schlecht" programmierten Code besser optimieren kann als verschiedenste C++ compiler

[Tiamat]

Stimmt, mit nem kleinen Trick und deiner Erweiterung konnte ich es auf 160ms reduzieren. Der unmodifizierte Code hat am Anfang bei mir 4,7 Sekunden benötigt ^^.

Soweit ich weiß berechnete Java den Restwert mit rest = x - (x/y) * y. Ob das immer noch so ist weiß ich nicht.

[Gast]

Hier mal mein Programm:

static void Main(string[] args)
{
int begin, end;
int number = 20;
begin = Environment.TickCount;
do
{
number+=20;
} while (number % 19 != 0 || number % 18 != 0 || number % 17 != 0 || number % 16 != 0 || number % 15 != 0 || number % 14 != 0 || number % 13 != 0 || number % 12 != 0 || number % 11 != 0);

end = Environment.TickCount;
Console.WriteLine("Messung mit TickCount: Vergangene Zeit = {0} Millisekunden", end - begin);
Console.WriteLine("Zahl: {0} ", number);
while (true) ;
}


Es ist in C# geschrieben und benötigt 47ms auf einem i7-2620M
als native Code also einmal mit ngen übersetzt sind es nur noch 16ms.

Bei gleicher Betrachtung in Visual C++ benötigt es 21ms

Die idee dahinter ist ganz einfach, da 20 die größte zu prüfende zahl ist, muss die gesuchte definitiv immer durch 20 teilbar sein, also ist nur jede 20te zu prüfen. Dazu kommt bei genauer betrachtung, dass alle zahlen unter 11 bereits über vielfache in den zahlen von 11-20 stecken und da wir nur vielfache von 20 prüfen braucht man für diese auch kein modulo mehr machen.

[hell_bird]

Hier mal mein Programm:

static void Main(string[] args)
{
int begin, end;
int number = 20;
begin = Environment.TickCount;
do
{
number+=20;
} while (number % 19 != 0 || number % 18 != 0 || number % 17 != 0 || number % 16 != 0 || number % 15 != 0 || number % 14 != 0 || number % 13 != 0 || number % 12 != 0 || number % 11 != 0);

end = Environment.TickCount;
Console.WriteLine("Messung mit TickCount: Vergangene Zeit = {0} Millisekunden", end - begin);
Console.WriteLine("Zahl: {0} ", number);
while (true) ;
}


Es ist in C# geschrieben und benötigt 47ms auf einem i7-2620M
als native Code also einmal mit ngen übersetzt sind es nur noch 16ms.

Bei gleicher Betrachtung in Visual C++ benötigt es 21ms

Die idee dahinter ist ganz einfach, da 20 die größte zu prüfende zahl ist, muss die gesuchte definitiv immer durch 20 teilbar sein, also ist nur jede 20te zu prüfen. Dazu kommt bei genauer betrachtung, dass alle zahlen unter 11 bereits über vielfache in den zahlen von 11-20 stecken und da wir nur vielfache von 20 prüfen braucht man für diese auch kein modulo mehr machen.
Die Idee ist gut, die Umsetzung mangelhaft. Wenn du schon mit Primfaktoren anfängst mach es gleich ohne die große Schleife. Das Konzept wurde hier schon von Senior Sanchez vorgestellt (http://www.forum-3dcenter.org/vbulletin/showpost.php?p=9139005&postcount=18) und von mir umgesetzt (http://www.forum-3dcenter.org/vbulletin/showpost.php?p=9139424&postcount=33).

Habe auch mal C# angeworfen, das ist aber lahm und uninteressant:

using System;
using System.Diagnostics;


namespace _3dctest
{
class Program
{

unsafe static int number = 21;

unsafe static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();

while (!divisible())
number++;

sw.Stop();

Console.WriteLine(number);
Console.WriteLine(sw.ElapsedMilliseconds);
Console.ReadKey();
}

unsafe private static bool divisible()
{
for (int i = 2; i < 21; i++)
{
if (number % i != 0)
return false;
}
return true;
}

}
}


Jemand noch Interesse an Java Assembly analyse (http://www.forum-3dcenter.org/vbulletin/showpost.php?p=9144217&postcount=57)? Ansonsten werde ich in mittelfristiger Zukunft das ganze in einer VM rauslassen.

[Yavion]

Ohne es getestet zu haben, mutmaße ich mal, dass "unsafe" im o.g. Beispiel in etwa so viel bringt, wie ausgeschaltetes ESP in der Autowaschanlage. :D

[PatkIllA]

Ohne es getestet zu haben, mutmaße ich mal, dass "unsafe" im o.g. Beispiel in etwa so viel bringt, wie ausgeschaltetes ESP in der Autowaschanlage. :D
Bei mir wird es durch unsafe sogar noch 5 bis 10% langsamer

[Gast]

Die Idee ist gut, die Umsetzung mangelhaft. Wenn du schon mit Primfaktoren anfängst mach es gleich ohne die große Schleife. Das Konzept wurde hier schon von Senior Sanchez vorgestellt (http://www.forum-3dcenter.org/vbulletin/showpost.php?p=9139005&postcount=18) und von mir umgesetzt (http://www.forum-3dcenter.org/vbulletin/showpost.php?p=9139424&postcount=33).


Ok da das vorherige mit zuviel denken war:

int begin, end;
int number = 0;
int index = 21;
begin = Environment.TickCount;
do
{
number += 20;
index = 21;
while (--index > 0)
{
if ((number % index) == 0)
{
continue;
}
break;
}
} while (index > 0);
end = Environment.TickCount;
Console.WriteLine("Messung mit TickCount: Vergangene Zeit = {0} Millisekunden", end - begin);
Console.WriteLine("Zahl: {0} ", number);


benötigt 94ms in C# die Originalfassung brauchte bei mir fast 5s
und nach ngen 78ms

die die Änderungen sind, dass die Funktion manuell "geinlined" wurde, da .net diese keinesfalls machen wird, generell nur durch 20 teilbare zahlen geprüft werden und die Prüfreihenfolge des Modulos getauscht wurde, da es wahrscheinlicher ist, dass eine Zahl durch einen großen Teiler nicht teilbar ist, hat auch gleich zur folge, dass die von mir vorher weggelassenen Modulos nur beim finalen Durchlauf einmal ausgeführt werden. Alle Werte die für die Berechnungen verwendet werden könnten nun also Automatisiert berechnet werden, somit ist das ganze von der genau gefragten zahl unabhängig.