Pascalsches Dreieck in C und Java (Performance)

[ctwx]

Hey,

für die Hochschule sollten wir in Java das Pascalsche Dreieck Rekursiv berechnen lassen. Da es ab Zeile ~37 recht träge wird, haben ein Kollege und ich uns einen Spaß raus gemacht und es mit dem Additionsverfahren umgesetzt. Auch erst in Java. Später noch in C++ und ich habe es noch versucht in C umzusetzen, mittels GMP Lib.

In der Hochschule lief mein C-Programm allerdings deutlich langsamer als die Java-Version. (Man sollte annehmen ein 8-Kerner i7-Prozessor schafft mehr...). Jetzt gerade eben habe ich beide Versionen hier lokal laufen lassen. (AMD Phenom II X4 @3,4 GHz mit 8 GB RAM).
Damit der Vergleich fair ist, habe ich beide Programme hier (ebenso wie in der Hochschule) auf einem 64 bit Windows 7 System ausgeführt.

Ergebnis:

• Java: ~49 sec
  C: ~16,5 sec

Ich mache das ganze nur Just4Fun und würde euch gerne um Verbesserungsvorschläge bitten, auch gerne für C und Java.
Ich denke in der C-variante müsste man noch mpz_clear aufrufen, aber wie ich es zuvor gemacht habe, lief es schief. ^^ Könnte also sein, je nachdem wie GMP das handhabt, dass da ein paar Speicherleks sind. *grins*

Hier sind die Quellcodes:

• C: http://debianforum.de/forum/pastebin.ph ... ew&s=37457 (Kompilierzeile: gcc -std=c99 -static pascal.c -L/c/gmp/lib -I/c/gmp/include -lgmp -o pascal)
  Java: http://debianforum.de/forum/pastebin.ph ... ew&s=37458

Würde mich über Feedback freuen.


Gruß,
Ctwx

[schorsch_76]

lade doch bitte noch pascal.txt hoch

[ctwx]

Bist du dir sicher? *grins* Die sind beide über 500 MB groß mit 2000 Zeilen.

[schorsch_76]

Okok

Bei dem Programm würde ein 128 Kerner nichts bringen. Single Threaded.

Mit welchem Parameter (runs) hast du es aufgerufen? Meiner Meinung nach ist hier ein dickes dickes Speicherloch drin was immens bremst (cache hits). Ich versuch mich mal daran

[ctwx]

Mit "time ./pascal 2000". Ich hatte auch schon an eine Multithreaded-Lösung gedacht, aber recht problematisch, da die Reihenfolge eine Rolle spielt.

Ich vergaß ganz zu schreiben welche Ergebnisse ich habe:
Java: ~49 sec für 2000 Zeilen
C: ~16,5 sec für 2000 Zeilen

[schorsch_76]

Hab das ganze jetzt unter C++ implementiert. Der größte Brocken an der Geschichte ist File IO.

Code: Alles auswählen

gcc pascal.cpp -lstdc++ -lgmpxx -march=native -O3 -o pascal-cpp && time ./pascal-cpp 2000  

real	0m6.938s
user	0m4.550s
sys	0m0.750s

37459

Mit deiner Lösung hab ich auch 16.5 sec auf meinem

Code: Alles auswählen

cat /proc/cpuinfo 
processor	: 0
vendor_id	: GenuineIntel
cpu family	: 6
model		: 42
model name	: Intel(R) Core(TM) i7-2670QM CPU @ 2.20GHz

Denke das das permanente malloc dir die Performance killt.

Gruß
schorsch_76

[ctwx]

Interessante Lösung. Ich nahm an, dass das Allokieren effizienter sei, als C++-Vektoren. Ich glaub ich muss bei mir noch mal herum schrauben.


Nachtrag:
Ich habe deinen und meinen Code mal unter Linux ausgeführt. Meinen Code diesmal mit:

Code: Alles auswählen

gcc pascal.c -lgmp -std=c99 -march=native -O3 -o pascal-c

kompiliert.

Bei deinem Code kam ich auf ein ähnliches Ergebnis wie du mit 6.254s. Bei meinem Code kam ich, ohne Änderung und mit der oben genannten Befehlszeile auf 8.283s.

Wobei es in meinem Code wirklich Speicherlecks gibt. Die müsste ich mal stopfen. Desweiteren kam mir die Idee, ich könnte immer in 10er Schritten neu allokieren. Das würde die Last etwas mindern. Vielleicht auch noch bisschen größere Schritte, was man wiederum abhängig machen kann, wie viele Zeilen berechnet werden sollen.

Was mich nur gerade sehr wundert, dass meine C-Lösung unter Linux fast doppelt so schnell läuft als unter Windows. ^^ Und offenbar auch schneller als bei dir.

[schorsch_76]

malloc/free ist eine der "teuersten" Operationen. Speicherallokierung ist nicht deterministisch. Im ungünstigesn Fall gibts Pagefaults und der Swap springt an. Mit permanenten kleinen Allokierungen fragmentierst du deinen Speicher und es wird langsam. Die 2x 2k mpz_class variablen haben ja schon fast im CPU Cache Platz. Deaktivierst du FileIO, siehst du was der wirkliche Flaschenhals ist. Es ist nicht die Berechnung

Diesen Algorithmus könnte man bsp. beim berechnen der Elemente einer Zeile parallelisieren. Evtl. kann hier openmp seine Loop Paralellisierung ausspielen. Falls mehr CPUs nötig wären als ein herkömmlicher Prozessor bietet, könnte auf Zeilenebene auch openmpi eingesetzt werden. Hier wäre wieder ein sehr schnelles Netzwerk nötig.

Gruß
schorsch

Hier ein paar Links:
[1] https://rt.wiki.kernel.org/index.php/HO ... age-faults
[2] http://www.rtai.dk/cgi-bin/gratiswiki.pl?Latency_Killer
[3] http://man7.org/linux/man-pages/man2/mlock.2.html
[4] http://www.open-mpi.org/faq/
[5] http://de.wikipedia.org/wiki/OpenMP
[6] http://www.linux-mag.com/id/5759/

[wanne]

hier mal ein paar Verbesserungen bringt bei mir bei -O3 allerdings nur ein paar wenige % bei -O0 spürt man's deutlich:

Code: Alles auswählen

19c19
<     fprintf(fp, "1\n1 1\n");
---
>     fprintf(fp, "%d\n%d %d\n", 1, 1, 1);
23c23
<     mpz_t *line_before = (mpz_t *)malloc(runs*sizeof(mpz_t));
---
>     mpz_t *line_before = (mpz_t *)malloc(2*sizeof(mpz_t));
26,34d25
<     mpz_t *tmpline=(mpz_t *)malloc(runs * sizeof(mpz_t));
<     
<     unsigned int i=runs;
<     do{
<       i--;
<       mpz_init_set_d(tmpline[i], 1);
<       mpz_init_set_d(line_before[i], 1);
<       
<     }while(i!=0);
37c28
<         line = tmpline;
---
>         line = (mpz_t *)malloc((i+1) * sizeof(mpz_t));
40c31,32
<         //mpz_init_set_d(line[i], 1);
---
>         mpz_init_set_d(line[0], 1);
>         mpz_init_set_d(line[i], 1);
44a37
>             mpz_init(line[j]);
55c48
<         tmpline=line_before;
---
>         free(line_before);

[wanne]

Hier läuft die c++ version langsamer:
c++: 9s
c: 8,7
meine optimierte 8,3

[ctwx]

wanne, danke für die Vorschläge. Dein Ergebnis finde ich sehr interessant. Was hast für eine CPU und wie taktet sie?

[wanne]

Hab den rechner gerade nicht mehr zur Hand. Irgend ein amd64-Zweikerner von Intel.
Der hauptgeschwindigkeitsgewinn zu anderen Rechnern dürfte der dicke Festplattencache/ Die 4GiB RAM sein. Sodass meine IO ohne wirkliches Schreiben auf die HD auskommt.
Der haputgeschwindigkeitsgewinn, von deiner auf meine Lösung war folgender:
Du hast am Ende der Schleife immer free() ausgeführt um dann direkt danach am Anfang wieder ein malloc auszuführen. Ich habe eifach vor der Schleife einmal ein dickes alloc gemacht und habe dann nur die Pointer umgehängt. Der nichtmehrgebrauchte last_line kann direkt wieder als line verwendet werden.
Die einmalige initalisierung am anfang statt das mehrmals zu machen halt leider fast keinen Geschwindigkeitsgewinnn gebracht. (Obwohl ich mir von dem eigentlich mehr erhofft habe.)

[ctwx]

Hab den rechner gerade nicht mehr zur Hand. Irgend ein amd64-Zweikerner von Intel.
Der hauptgeschwindigkeitsgewinn zu anderen Rechnern dürfte der dicke Festplattencache/ Die 4GiB RAM sein. Sodass meine IO ohne wirkliches Schreiben auf die HD auskommt.

Hmm.. Da kommt mir spontant die Idee, einen Teil meines RAM zu mounten und das Programm dort auszuführen.

Der haputgeschwindigkeitsgewinn, von deiner auf meine Lösung war folgender:
Du hast am Ende der Schleife immer free() ausgeführt um dann direkt danach am Anfang wieder ein malloc auszuführen. Ich habe eifach vor der Schleife einmal ein dickes alloc gemacht und habe dann nur die Pointer umgehängt. Der nichtmehrgebrauchte last_line kann direkt wieder als line verwendet werden.
Die einmalige initalisierung am anfang statt das mehrmals zu machen halt leider fast keinen Geschwindigkeitsgewinnn gebracht. (Obwohl ich mir von dem eigentlich mehr erhofft habe.)

Hmm.. Macht natürlich Sinn. Hätte ich aber auch angenommen. Vielleicht optimiert GCC das ja schon raus. Wobei ich gestehen muss, dass ich ein grausiger C-Programmierer, daher war das experiment mal ganz interessant.

Mal schauen ob sich da noch mehr raus optimieren lässt. Vielleicht wäre der C++-Ansatz wirklich besser. Naja, oder zumindest einfacher.

[wanne]

Hmm.. Macht natürlich Sinn. Hätte ich aber auch angenommen. Vielleicht optimiert GCC das ja schon raus.

Ich glabe nicht. Im besten fall könnte ich mir vorstellen dass er da ein realloc macht statt einem free und alloc. (Das Programm wie ich es geschrieben habe ist ja im prinzip speicheraufwändiger. Da müsste der zuerstmal kapieren, dass sich i nie über rows hinausbewegt.) Aber auch das glaube ich nicht. Die system-Calls lässt die Optimierung glaube ich unangetastet.
Im Übrigen dürfte ein viel lustigeres experiment sein die rekusive Variante in C zu schreiben. Wenn man das sauber endrekusiv macht wird das in C genausoschnell weil der gcc das (im Gegensatz zu Java) automatisch in eine Iterative Variante umschreibt.

Edit: Ne typisch rekursive Implementirung vom Paskalschen Dreieck dürfte nicht endrekursiv sein. Trotzdem dürfte die C-Variante da um längen schneller sein als die in Java. (Und vor allem hätte sie 4GiB Stack!)

[king-crash]

Hier ein Vorschlag: 37463

Um Festplattenoperationen zu vermeiden einfach das fwrite auskommentieren.
Compiler-Optimierungen bringen nicht allzu viel, da die Hauptarbeit bei der libgmp liegt...

[ctwx]

Hier ein Vorschlag: 37463

Um Festplattenoperationen zu vermeiden einfach das fwrite auskommentieren.
Compiler-Optimierungen bringen nicht allzu viel, da die Hauptarbeit bei der libgmp liegt...

Ich musste den Quellcode erst einmal durchsehen (ich verstehe den Code lieber, als ihn stumpf zu kopieren und auszuführen) und muss sagen, dass deine Änderungen echt gut sind. An einen Textbuffer hatte ich auch schon gedacht, aber bisher nicht die Zeit gehabt ihn umzusetzen. Ein bischen Unsicherheit, noch mehr Lecks ins Programm zu packen hatte ich aber auch. ^^

Naja. Deine Lösung braucht bei mir exakt 10 Sekunden. Leider habe ich gerade den Überblick verloren. Ich muss die einzelnen Werte wie lange sie bei mir auf der CPU brauchen mal notieren.


Vielen Dank!

[wanne]

An einen Textbuffer hatte ich auch schon gedacht

Eigentlich sollten die f* Funktionen selber buffern.

[wanne]

Hier mal erste Stats.

Code: Alles auswählen

$ lscpu 
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                2
On-line CPU(s) list:   0,1
Thread(s) per core:    1
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 23
Stepping:              10
CPU MHz:               2401.000
BogoMIPS:              4788.04
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              3072K
NUMA node0 CPU(s):     0,1

ftp://wanne.t-8ch.de/stuff/ergstats.ods

Die orginalversionen bleiben am schnellsten. (Hat aber auch keine vernünftige Fehlerbehandlung wie die letzte.)
Die c++-Version ist die langsamste und ist in den ersten 3 Zeilen falsch.

[king-crash]

Die Ausgabe als String ist der limiterende Faktor. Wenn du in meinem Code die append Funktionen auskommentierst braucht das ganze bei mir nur noch 100ms.
Eigentlich auch logisch wenn man bedenkt, dass die Ausgabedatei ~500MB groß ist.

Großen Respekt an die GMP Jungs, ihre lib ist wirklich schnell und trotzdem einfach zu bedienen.

[king-crash]

Noch ein kleiner Nachtrag, mein Code hat noch 2 kleine Fehler. Zum Einen sollte das Speicherinkrement nicht 10 sein, das war zu Debug-Zwecken, und zum Anderen muss nicht immer die Ganze Reihe der Zahlen nach rechts weg durchlaufen werden, sondern nur n+3.

Code: Alles auswählen

@@ -81,8 +81,8 @@
 		}
 
 //Huge Pagesize
-//	buffer_increment = 2097152;
-	buffer_increment = 10;
+	buffer_increment = 2097152;
+//	buffer_increment = 10;
 	textlen = 0;
 	buflen = 0;
 	textbuffer_prepare(buffer_increment);
@@ -154,7 +154,7 @@
 
 	for(line=0;line<runs-1;line++)
 		{
-		for(pos=1;pos<fields-1;pos++)
+		for(pos=1;pos<line+4;pos++)
 			{
 			mpz_add(b[pos], a[pos-1], a[pos]);
 			}