Programm unter Win schneller als unter Lin ?!
-
Hallo!
Ich habe einen kleinen Algorithmus geschrieben, der die Goldbach-Vermutung (jede gerade Zahl größer als 2 lässt sich aus der Summe zweier Primzahlen bilden) in einem anzugebenden Intervall überprüft.
Nun habe ich dies in Form eines C-Programmes umgesetzt, welches mit clock() die Zeit berechnet, die es für die Berechnung benötigt. Dies habe ich zunächst unter Linux umgesetzt, einmal unter SuSE 8.1 mit Kernel 2.4.19-4GB und einmal unter debian 3.0r1 mit Kernel 2.4.18. Zum Spass habe ich es dann mit dem Borland C-Compiler auch einmal unter Windows XP Professional compiliert und die Zeiten unter den diversen Betriebssystemen gemessen.
Hier das Ergebnis im Intervall [4...100000]:
SuSE 8.1 (unter X): 147 Sek
debian 3.0 (Konsole): 140 Sek
Win XP: 107 Sek !!!Das Programm lief auf einem Athlon XP 2400+. Da es nur Vergleiche, Inkrementoperationen und ein paar Wertzuweisungen durchführt, stellt sich für mich natürlich die Frage, wie dieser große Geschwindigkeitsunterschied zustande kommt? Ich bin eigentlich ein großer Linux-Anhänger, aber dieses Ergebnis verwundert mich sehr! Unter Lin liefen auch fast keine Prozesse - nur die notwendigen, also nichts Prozessorraubendes. Weiß sich das jemand zu erklären?!
Hier noch der Code:
#include <stdio.h> #include <stdbool.h> #include <time.h> int main(void){ long int von, bis, i, j, k, teiler; bool ist_prim=1; clock_t start, ende; printf("Goldbach-Vermutung\n" "==================\n\n" "-> Jede gerade Zahl groeßer als 2 ergibt sich aus der Summe\n" " zweier Primzahlen... - dies ueberprueft das Programm\n\n"); printf("Zu pruefenden Bereich eingeben:\n"); do { printf("1. Untere Grenze: "); scanf("%ld", &von); } while(von<0 && printf("Zahl muss positiv sein!\n")); printf("2. Obere Grenze: "); scanf("%ld", &bis); start = clock(); if(von<=2) von=4; // 4 ist die erste gerade Zahl > 2 else if(von%2 !=0) // wenn "von" ungerade... ++von; // ... dann mache sie gerade! /* pruefe alle Zahlen im Bereich [von...bis] */ for(i=von; i<=bis; i+=2){ printf("\r%6.3f%% bearbeitet...", i/(float)bis*100); /* pruefe die jeweilige Zahl j auf die Goldbach-Vermutung */ for(j=2; j<i; ++j){ ist_prim=1; /* pruefe, ob erste Zahl j eine Primzahl ist */ for(teiler=2; teiler<=j/2; ++teiler) /* wenn Ausdruck wahr, dann keine Primzahl */ if(j%teiler==0){ ist_prim=0; break; } /* wenn keine Primzahl, dann pruefe naechste Zahl */ if(!ist_prim) continue; /* pruefe die zweite Zahl k, die die Differenz zwischen i und j darstellt */ k=i-j; for(teiler=2; teiler<=k/2; ++teiler) /* wenn Ausdruck wahr, dann keine Primzahl */ if(k%teiler==0){ ist_prim=0; break; } /* wenn Goldbach-Zahl gefunden, dann fahre mit naechstem i fort */ if(ist_prim) break; } if(!ist_prim){ printf("\nVerstoß gegen die Goldbach-Vermutung!\n"); return 0; } } ende = clock(); printf("\nAlle Zahlen im Bereich [%ld...%ld] entsprechen " "der Goldbach-Vermutung!\n\n", von, bis); printf("Benoetigte Zeit: %10.3f Sek\n\n", (ende-start)/(double)CLOCKS_PER_SEC); return 0; }
-
hast du vielleicht die Optimierung vergessen beim kompilieren?
-
Original erstellt von <Mellon>:
**Hallo!...snipp...
Nun habe ich dies in Form eines C-Programmes umgesetzt, welches mit clock() die Zeit berechnet, die es für die Berechnung benötigt. Dies habe ich zunächst unter Linux umgesetzt, einmal unter SuSE 8.1 mit Kernel 2.4.19-4GB und einmal unter debian 3.0r1 mit Kernel 2.4.18. Zum Spass habe ich es dann mit dem Borland C-Compiler auch einmal unter Windows XP Professional compiliert und die Zeiten unter den diversen Betriebssystemen gemessen.
**Auf unterschiedlichen Betriebssystemen auch noch unterschiedliche Compiler zu verwenden, ist schon einmal ganz schlecht. Laufzeitunterschiede können dann allein schon darin begründet liegen, wie z.B. Borland deinen Quellcode optimiert und in Maschinencode umsetzt. Wenn schon, solltest du für solche Zwecke auch auf Windows den GCC einsetzen sollen.
Original erstellt von <Mellon>:
**
Hier das Ergebnis im Intervall [4...100000]:SuSE 8.1 (unter X): 147 Sek
debian 3.0 (Konsole): 140 Sek
Win XP: 107 Sek !!!Das Programm lief auf einem Athlon XP 2400+.
...snipp...
**PowerPC G4 867MHz (Typ 7450) mit MacOS X 10.2.5: 57.550 Sek
(Kompiliert mit GCC v3.1 und den Compiler-Flags: -Wall -ansi -s -O2)
-
Also ich habe "gcc -Wall -O2 goldbach.c" genommen. Mit dem -O2-Flag hat sich die Zeit unter debian schonmal auf 127 Sek drücken lassen.
Übrigens mein Versehen: Die Sekundenanzahl gilt für das Intervall [4...200000] und nicht bis 100000, wäre ja auch ein wenig langsam in dem Fall
Trotzdem noch 20 Sekunden und das, wo gerade mal die k-Tools, init, die gettys und die bash laufen. Schon komisch, oder?!
-
Schonmal dran gedacht das deine Sekundenzahl nicht stimmt.
Es vergehen bei 4 - 200000 Intel 2.5 GHZ 135 Sekunden obwohl nur 60 angezeigt werden.
Weiters darfst du auch nicht die Ausgabe dazurechnen.[ Dieser Beitrag wurde am 22.04.2003 um 06:46 Uhr von Unix-Tom editiert. ]
-
Hi,
also ohne fuer den Athlon optimiert zu haben, sind es bei mir 125sec, wenn man
den Anzeigen trauen darf. Werde heute mal noch fuer den Athlon optimieren lassen.Mein System:
AMD Athlon XP 2200+ M
512MB DDR
OS: FreeBSD 5.0-RELEASE Customer Kernelmfg
v R
-
nice -20 ./code
?
-
wollt nochmal was zu den optimierungen sagen:
(system: PI 200, 96 Räm, 2.4.19 kernel, intervall 4 - 25000, bei 200000 hats 1250 sec gedauert [bei O3])ohne optimierung: 26.650 sec
O2: 21.320 sec
O3: 21.320 sec (komisch, was? habs aber mehrfach ausprobiert)
O4: 21.350 secirgendwie lohnt also nur die O2, bei den anderen steigt nur noch die programmgröße, hatte alerdings keine großen zahlen (mache den test grad noch)
-
Original erstellt von Unix-Tom:
**Schonmal dran gedacht das deine Sekundenzahl nicht stimmt.
Es vergehen bei 4 - 200000 Intel 2.5 GHZ 135 Sekunden obwohl nur 60 angezeigt werden.
Weiters darfst du auch nicht die Ausgabe dazurechnen.[ Dieser Beitrag wurde am 22.04.2003 um 06:46 Uhr von [qb]Unix-Tom** editiert. ][/QB]
??? Bei mir vergehen genauso viel Sekunden wie angezeigt werden, also ist da alles in bester Ordnung. Außerdem rechne ich keine Ausgabe dazu, die eine "Verstoß gegen die Goldbach-Vermutung" tritt nie auf, da die Vermutung für alle geraden Zahlen größer 2 zutreffen müsste. Und die anderen Ausgaben folgen erst nach dem Stoppen der CPU-Zeit mit ende=clock()!
-
Original erstellt von HAR:
nice -20 ./code
?Hab ich ausprobiert, da aber keine weiteren rechenintensiven Prozesse laufen, hat das nicht wirklich etwas gebracht...
-
Die richtigen Compiler Einstellungen sind schon mal ganz wichtig.
Lediglich mit -O1 oder -O2 (-O3 bringt nichts bis nicht mehr viel) ist die Laufzeit schon einmal kürzer. Wenn ich dann noch weitere Compiler Optionen angebe, steigert sich die Performance auf Faktor 3:O0: 538.030 Sek (ohne Optimierung)
O1: 462.100 Sek
O2: 462.620 Sek
O2: 185.470 Sek (mit zusätzlichen Compiler Optionen)$ gcc --version
gcc (GCC) 3.1
Copyright (C) 2002 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.$ uname -a
SunOS 5.8 sun4us sparc FJSV,GPUS$ gcc -o main_goldbach_opti -Wall -Wmain -std=c99 -O2 -fsigned-char -fno-asm -fno-builtin -finline-functions -fomit-frame-pointer -m64 -mptr64 -mhard-float -mfpu -mcpu=v9 main_goldbach.c
Die Laufzeit deines Programms skaliert quadratisch zur Anzahl der zu testenden Zahlen. Vielleicht solltest du da mal was dran drehen.
In nachfolgendem Quellcode habe ich deine Goldbach Testroutine durch Funktionen von Armand Turpel ersetzt. Im Interval [4...200000] erhalte ich eine Laufzeit von 2.270 Sek wenn ich die Ausgabe in eine Datei umleite. Allerdings ist noch irgendwo ein Bug -- die 4 wird als Fehler aufgezeigt.
am_* Funktionen der "C-lib of math routines" von Armand Turpel entnommen
http://www.2357.a-tu.net/index.php?link=Software#include <stdio.h> #include <math.h> #include <time.h> int p_pt(int t) { int a=5; while (a*a<=t) { if (t%a==0) return -1; if (t%(a+2)==0) return -1; a=a+6; } return 1; } /* do we have a prime number ? */ int am_primetest(int t) { int a=5; if (t<4) { if (t==2) return 1; if (t==3) return 1; return -1; } if (t%2==0) return -1; if (t%3==0) return -1; while (a*a<=t) { if (t%a==0) return -1; if (t%(a+2)==0) return -1; a=a+6; } return 1; } /* Goldbach's Conjecture */ int am_goldbach(int a,int *p) { int e=5,k; if (am_primetest(a-3)==1) { p[0]=3; p[1]=a-3; return 1; } k=a/2+1; while(e<k) { if (p_pt(e)==1) { if(am_primetest(a-e)==1) { p[0]=e; p[1]=a-e; return 1; } } e=e+2; if (p_pt(e)==1) { if(am_primetest(a-e)==1) { p[0]=e; p[1]=a-e; return 1; } } e=e+4; } return -1; } int main(void) { int von, bis, i; clock_t start, ende; int buffer[2]; printf("Goldbach-Vermutung\n" "==================\n\n" "-> Jede gerade Zahl groeßer als 2 ergibt sich aus der Summe\n" " zweier Primzahlen... - dies ueberprueft das Programm\n\n"); printf("Zu pruefenden Bereich eingeben:\n"); do { printf("1. Untere Grenze: "); scanf("%ld", &von); } while(von<0 && printf("Zahl muss positiv sein!\n")); printf("2. Obere Grenze: "); scanf("%ld", &bis); start = clock(); /* pruefe alle Zahlen im Bereich [von...bis] */ for(i=von; i<=bis; i+=2) { if ( am_goldbach(i,buffer) == -1) { printf("Goldbach's conjecture is wrong. ( %i )\n", i); } else { printf("Goldbach is right: %i = %i + %i\n", i, buffer[0], buffer[1]); } } ende = clock(); printf("\nAlle Zahlen im Bereich [%ld...%ld] entsprechen " "der Goldbach-Vermutung!\n\n", von, bis); printf("Benoetigte Zeit: %10.3f Sek\n\n", (ende-start)/(double)CLOCKS_PER_SEC); return 0; }
-
Nicht schlecht, Descartes, der neue Algorithmus, allerdings geht es mir nicht um eine Verbesserung dessen sondern doch nur um eine Verbesserung der Geschwindigkeit unter Linux, welche im Vergleich zu Windows bei gcc -Wall -O2 ja nicht wirklich gut abschneidet. Trotzdem danke für diesen neuen Weg...
-
Mal ein paar "Kontrollwerte" , die gleichzeitig auch Fragen aufwerfen:
Athlon XP 1600+ (1400MHz), Code aus Mellons erstem Beispiel, Bereich von 4 bis 100000 (Einhunderttausend).
Borland C++ Builder 6, WinXP, Debug-Modus, keine Optimierungen: ~45 sec
Borland Kylix3, SuSE 8.1, Debug-Modus, keine Optimierungen, KDE-Konsole: ~48 secDie angezeigten Zeiten decken sich mit Handmessungen.
Fragen wirft das Ganze deshalb auf, weil der Rechner doch deutlich langsamer ist, aber nur rund die Hälfte der besten Zeit von Mellon benötigt. Welchen "Borland C-Compiler" genau hast du denn da benutzt?
Nachtrag:
SuSE 8.1, gcc -Wall -O2, KDE-Konsole: ~42 sec[ Dieser Beitrag wurde am 22.04.2003 um 14:50 Uhr von Jansen editiert. ]
-
Original erstellt von Jansen:
**
Fragen wirft das Ganze deshalb auf, weil der Rechner doch deutlich langsamer ist, aber nur rund die Hälfte der besten Zeit von Mellon benötigt. Welchen "Borland C-Compiler" genau hast du denn da benutzt?
**Hatte oben geschrieben, dass ich mich erst vertippt hatte. Es gilt das Intervall [4...200000] für die gemessenen Zeiten.
Tw: Kann mir einer sagen, welche gcc-Optionen für meinen XP 2400+ am besten wären?! Auch mit "gcc -O2 -Wall -Wmain -fsigned-char -fno-asm -fno-builtin -finline-functions -fomit-frame-pointer -o goldbach goldbach.c" komme ich nicht unter 127 Sekunden und da ist Win ja immernoch 20 Sekunden schneller!
-
gcc -Wall -W -pipe -O3 -fomit-frame-pointer -malign-double -fschedule-insns2 -march=athlon -mcpu=athlon -malign-functions=4
beim gcc 3.2.1 > solltest du auch mal die Option -mfpmath=sse,387 ausprobieren
(und du solltest vielleicht lieber einen Profiler benutzen, anstelle intern die Geschwindigkeit zu messen)
[ Dieser Beitrag wurde am 22.04.2003 um 16:30 Uhr von kingruedi editiert. ]
-
Original erstellt von kingruedi:
**gcc -Wall -W -pipe -O3 -fomit-frame-pointer -malign-double -fschedule-insns2 -march=athlon -mcpu=athlon -malign-functions=4beim gcc 3.2.1 > solltest du auch mal die Option -mfpmath=sse,387 ausprobieren
**Tja, selbst damit komme ich nur auf 119 Sekunden. Das sind immernoch 12 Sekunden zu langsam im Gegensatz zu Windows. Und: bei Windows läuft das GUI, bei Linux nur die Konsole. Ich bin aber Linux-Anhänger und will nun endlich mal wissen, wie sich diese Differenz erklären lässt. Compiler unter Windows war übrigens der "Borland C 5.0"...
-
mess die Geschwindigkeit am besten mal mit einem Profiler nach, anstelle interner Zeitanalyse.
-
Sorry: Profiler?!
-
Siehe z.B. Manpage gprof(1)
1.) Programm kompilieren mit der GCC Option "-pg"
2.) Kompilierte Programm einmal ausführen (es wird eine Datei "gprof.mon" erzeugt)
3.) den Profiler aufrufen: gprof goldbach.exe gprof.mon"
Steht aber alles auch in der Manpage gprof(1)
Profiling, Linker-Mapdateien und obskure gcc-Optionen unter Linux
http://www.fefe.de/devel/profiling.txt
-
Hat etwas länger gedauert.
Also: ich habe das mit gprof mal gemacht, funzt auch gut. Habe den Code zwischen den beiden clock()-Aufrufen in eine eigene Funktion gepackt, so dass ich deren Zeit abrufen kann. Unter debian sowie suse braucht das Programm 113 Sekunden. Habe es auch nochmal ohne Profiling in Windows XP gemacht. Dort braucht es jetzt 115 Sekunden (obwohl ich nichts geändert habe 8 Sekunden langsamer?! naja...), das bezieht sich aber auf die clock()-Aufrufe und die Zeitberechnung damit. Gibt es auch einen Profiler unter Windows, der ähnlich gprof ist? Und was ist der Unterschied zwischen Abrufen mit clock() oder mit gprof? Mit den clock()-Abrufen komme ich auf ca. 119 Sekunden, also 6 Sekunden langsamer, obwohl es derselbe Codeteil ist. Auch im Vergleich zu Windows ist es hier wieder langsamer. Sind Lin und Win bei clock() eigentlich äquivalent anzusehen?
Unter tomsrtbt habe ich es auch mal ohne gprof probiert: 113 Sekunden! Soll heißen, mit gprof wäre es noch weniger geworden - kein Wunder auch, wenn fast kein Prozess am Laufen ist...
Hätte jetzt aber mal gern eine Aufklärung zu o.a. Fragen, das Ganze wurmt mich immernoch recht doll.