Ausführungsgeschwindigkeit

Code-Stücke können hier veröffentlicht werden.
Antworten
Tredory
User
Beiträge: 7
Registriert: Mittwoch 26. Februar 2014, 10:34

Hallo zusammen,

Ich bin derzeit unter anderem meine C und C++ Kenntnisse mal wieder am auffrischen (Hobby). Nun habe ich ein kleines Programm erstellt, welches ich vor längerer Zeit schon mal in Python erstellt habe, und hab das mal verglichen.

Es ist ein Programm, dass die Kreiszahl Pi empirisch ermitteln soll.
Mir ist klar das Python "langsamer" ist als ein Compiliertes C++ Programm, aber das der Unterschied so gewaltig ist, damit habe ich nicht gerechnet.

Hier die Beiden Programmcodes:

Python:

Code: Alles auswählen

r = 3000
treffer = 0
quadtreffer = r**2

for i in range(r):
    x2 = (i+0.5)**2
    for j in range(r):
        y2 = (j+0.5)**2
        #print("x2: ", x2, " y2: ", y2, '\n')
        if (x2 + y2 <= quadtreffer):
            treffer += 1

print("%.5f" %(4*treffer/quadtreffer))
C++:

Code: Alles auswählen

#include <iostream>
#include <math.h>
using namespace std;

int main(int argc, char **argv)
{
	int r = 3000, treffer = 0;
	double quadtreffer = pow(r,2);
	double x2 = 0.0, y2 = 0.0;

	for(int i=0; i<r; i++) {
		x2 = pow((i+0.5),2);
		for(int j=0; j<r; j++) {
			y2 = pow((j+0.5),2);
			//cout << "x2: " << x2 << " y2: " << y2 << endl;
			if((x2+y2) <= quadtreffer) {
				treffer++;
			}
		}
	}
	cout << (4*treffer/quadtreffer);
	return 0;
}
zu den Laufzeiten:
Beide Programme habe ich auf dem RaspberryPi ausgeführt, dabei habe ich noch das Programm time verwendet um die Laufzeit zu vergleichen.

Ergebnis:
"time python ./pi.py3"
Python Laufzeit = 3 Min 31,201 Sek

"time ./pi"
C++ Laufzeit = 4,151 Sek

Das C++ Programm hat also gerade einmal 1,25% der Zeit des Python Skriptes gebraucht. Hab ich hier irgendwo einen grob fahrlässigen Fehler gemacht, oder ist dieser Extreme Unterschied normal ?
Wenn ich die auskommentierten Ausgabezeilen in der inneren For-Schleife auch noch ausgeben lasse brauchen beide deutlich länger, aber auch dann ist das c++ Programm bei weitem schneller.

EDIT:
Ich habe im übrigen auch versucht die beiden Variablen im Python Skript "global" am anfang mit x2 = 0.0 und y2 = 0.0 zu deklarieren, da ich dachte das es eventuell daran liegt das er bei jeden schleifendurchlauf den Speicher dafür neu "einkaufen" muss. Dies hat die Laufzeit aber noch auf 3 Min 57 Sek angehoben.

Grüße Jens
BlackJack

@Tredory: Ich sehe jetzt nichts auffälliges. Ausser das ich das nicht auf Modulebene geschrieben hätte sondern in einer Funktion. Das zwar nicht aus Geschwindigkeitsgründen, es hätte aber den Nebeneffekt das es etwas schneller wird, weil lokale Namen schneller aufgelöst werden können als welche auf Modulebene.

Das Programm ist für Python untypisch. So etwas macht man nicht mit Python-Schleifen, jedenfalls nicht wenn es schnell sein soll. Schau Dir mal das `numpy`-Modul an.

Und PyPy als alternative Python-Implementierung mit einem JIT-Compiler ist vielleicht auch schneller als CPython.
Tredory
User
Beiträge: 7
Registriert: Mittwoch 26. Februar 2014, 10:34

@ BlackJack: Danke für die schnelle Antwort. Ich habe da nur keine Funktion draus gemacht, da dies ja nur ein kleines Experiment war und ich den Code eh nicht weiter verwenden wollte. Daher hab ich da gar nicht dran gedacht eine Funktion zu erstellen.
Habe gerade einmal einen groben blick auf numpy.org geworfen, meinst du im speziellen die Tools um C++ bzw. Fortran Code in Python zu verwenden ? oder hattest du eher einen anderen lösungsansatz mit den numpy arrays im Kopf ? Werde mir das auf jedenfall mal genauer ansehen.
BlackJack

@Tredory: Wenn man das in C++ oder Fortran schreibt nur um es dann von Python aus zu verwenden, braucht man Python ja kaum. Nein, ich meinte schon es mit Arrays zu lösen. Braucht natürlich ein bisschen mehr Speicher als die Schleifenlösung.
Tredory
User
Beiträge: 7
Registriert: Mittwoch 26. Februar 2014, 10:34

@ BlackJack: Das hab ich mir auch gedacht. Dann hab ich ja jetzt wieder einen Grund wieder was mit Python zu basteln. Werde da mal gucken ob ich mit numpy was auf die Reihe bekomme.
Die einfachste Variante wäre zwar es einfach sein zu lassen, da man Pi ja auch einfach "Fertig" benutzen könnte, aber das wäre ja langweilig :P
BlackJack

@Tredory: Warum ist Dein Raspi denn so langsam? Sowohl in Python als auch in C ist bei mir der ”naive” Ansatz schon deutlich schneller als bei Dir. Auf einem Raspi mit Raspbian (Debian Wheezy) und nicht über- oder untertaktet, also bei 700 Mhz.

Dein erster Ansatz in eine Funktion verpackt braucht knapp über zwei Minuten (124.69 s):

Code: Alles auswählen

def calculate_pi_a(radius=RADIUS):
    hit_zone = radius**2
    hit_count = 0
    for i in xrange(radius):
        x = (i + 0.5)**2
        for j in xrange(radius):
            y = (j + 0.5)**2
            if x + y <= hit_zone:
                hit_count += 1
    return 4.0 * hit_count / hit_zone
Meine C-Funktion sieht so ähnlich aus wie Deine C++-Version, nur das ich ohne `pow()` ausgekommen bin:

Code: Alles auswählen

#define RADIUS  3000
#define HIT_ZONE  ((double) RADIUS * RADIUS)

double calculate_pi_a(void)
{
    uint16_t i, j;
    double x, y;
    uint32_t hit_count = 0;

    for (i = 0; i < RADIUS; ++i) {
        x = i + 0.5;
        x *= x;
        for (j = 0; j < RADIUS; ++j) {
            y = j + 0.5;
            y *= y;
            if (x + y <= HIT_ZONE) {
                ++hit_count;
            }
        }
    }
    return 4 * hit_count / HIT_ZONE;
}
Das ist mehr als vier mal schneller als Deins: 0.709s

Und der Unterschied ist bei mir grösser. Waren es bei Dir noch knapp 2% die das C++-Programm von der Laufzeit des Python-Programms gebraucht hat, sind es bei mir nur cirka 0.6%.

Eine offensichtliche Verbesserungsmöglichkeit ist mir dann doch noch aufgefallen: Die Werte in den Schleifen sind ja grundsätzlich gleich, und trotzdem werden sie immer und immer wieder auf's neue berechnet. Man könnte das einmal *vor* den Schleifen erledigen und damit die Laufzeit halbieren (51.85 s):

Code: Alles auswählen

def calculate_pi_b(radius=RADIUS):
    hit_zone = radius**2
    values = [(i + 0.5)**2 for i in xrange(radius)]
    hit_count = 0
    for x in values:
        for y in values:
            if x + y <= hit_zone:
                hit_count += 1
    return 4.0 * hit_count / hit_zone
Und in C, wo der Geschwindigkeitsgewinn dadurch nicht ganz so gross ist (0.529s):

Code: Alles auswählen

double calculate_pi_b(void)
{
    uint16_t i, j;
    double x, *values;
    uint32_t hit_count = 0;

    values = malloc(RADIUS * sizeof(*values));
    for (i = 0; i < RADIUS; ++i) {
        x = i + 0.5;
        values[i] = x * x;
    }

    for (i = 0; i < RADIUS; ++i) {
        for (j = 0; j < RADIUS; ++j) {
            if (values[i] + values[j] <= HIT_ZONE) {
                ++hit_count;
            }
        }
    }

    free(values);
    return 4 * hit_count / HIT_ZONE;
}
Wenn man in Python einen Sprung machen möchte ohne viel Arbeit rein zu stecken, dann kann man mit Numpy in 6.85 s fertig werden, allerdings auf Kosten von Speicherverbrauch:

Code: Alles auswählen

def calculate_pi_numpy(radius=RADIUS):
    hit_zone = radius**2
    A = ((np.arange(radius) + 0.5)**2).reshape((1, -1)).repeat(radius, 0)
    A += A.copy().transpose()
    hit_count = (A <= hit_zone).sum()
    return 4.0 * hit_count / hit_zone
Tredory
User
Beiträge: 7
Registriert: Mittwoch 26. Februar 2014, 10:34

Hi BlackJack,
Erst einmal Herzlichen Dank, das du dir mein Problem noch genauer angesehen hast und dort Zeit investiert hast.
Ich werde mal 1:1 deine Code Schnipsel übernehmen und Testen und die Zeiten Posten. Das wundert mich jetzt ja doch etwas das es bei dir so viel schneller läuft (Ich verwende ebenfalls Raspbian aus dem aktuellen noobs Image Version 1.3.4 und habe den Raspberry auf 700mHz laufen).
Womit hast du Das C-Prog compiliert ? GCC, clang vielleicht macht das ja auch einen unterschied, oder hast du irgendwelche Optimierungen eingeschaltet ? warst du über ssh drauf oder im Terminal oder im LXDE ? Ich war bei den Tests im LXDE angemeldet und hab dort Geany, IDLE3, sowie 2 Terminal Fenster geöffnet.
Ich muss leider gestehen das ich bisher noch nicht dazu gekommen bin mich damit weiter zu befassen. Bin gerade noch dabei meine Bachelor arbeit zu schreiben, welche ich am Montag einreichen muss.Daher werde ich erst danach dazu kommen dieses Thema weiter zu verfolgen.

Gruß Tredory
BlackJack

@Tredory: Den C-Quelltext habe ich mit `clang` und ``-O3`` übersetzt. Ich gehe per SSH auf den Rechner, den benutze ich sonst als Interner-Radio-Wecker. Da ist eine vierstellige 7-Segment-LCD-Anzeige per I2C an den GPIOs angeschlossen, welche die Uhrzeit anzeigt. Ausser USB-WiFi hängt da sonst nichts weiter dran.

Dann wird bei Dir wahrscheinlich die laufende grafische Umgebung den Unterschied machen.

Ich habe die C-Variante noch mal überarbeitet. Die (gedachte) 3000×3000 Matrix die in den Schleifen ausgerechnet wird, ist ja symmetrisch, also braucht man nur die Hälfte auf einer Seite der diagonalen Werte ausrechnen und kann die verdoppeln und dann die Diagonale noch dazurechnen (0.261 s):

Code: Alles auswählen

double calculate_pi_c(void)
{
    uint16_t i, j;
    double x, *values;
    uint32_t hit_count = 0;

    values = malloc(RADIUS * sizeof(*values));
    for (i = 0; i < RADIUS; ++i) {
        x = i + 0.5;
        values[i] = x * x;
    }

    for (i = 0; i < RADIUS; ++i) {
        for (j = i + 1; j < RADIUS; ++j) {
            if (values[i] + values[j] <= HIT_ZONE) {
                ++hit_count;
            }
        }
    }
    hit_count *= 2;

    for (i = 0; i < RADIUS; ++i) {
        if (values[i] * 2 <= HIT_ZONE) {
            ++hit_count;
        }
    }

    free(values);
    return 4 * hit_count / HIT_ZONE;
}
Viel Glück bei der Arbeit. :-)
BlackJack

Zwei neue Ergebnisse welche die Grenze(n) der Laufzeit weiter verschieben. In beide Richtungen. Erst die schnellere Variante: Auf ARM-Prozessoren lohnt es sich deutlich mehr Gleitkommaoperationen zu vermeiden. Zum einen weil nicht alle Prozessoren überhaupt Gleitkommaoperationen direkt in Hardware unterstützen und zum anderen, weil selbst wenn sie das tun, wie beim Raspi, dann gibt es trotzdem noch deutliche Laufzeitunterschiede zu reiner Ganzzahlarithmetik. Also nun das ganze mit „fixed point”-Arithmetik (Laufzeit 0.082s):

Code: Alles auswählen

#define HIT_ZONE_FIXPOINT  ((RADIUS * RADIUS) << 2)

double calculate_pi_d(void)
{
    uint16_t i, j;
    uint32_t *values;   /* Fixed point values with two bits fractional part. */
    uint32_t hit_count = 0;

    values = malloc(RADIUS * sizeof(*values));
    /* 
     * `j` is a fixed point value with one bit fractional part here.
     * So it starts at 0.5 and is incremented by 1.0 each loop iteration.
     */
    for (i = 0, j = 1; i < RADIUS; ++i, j += 2) {
        values[i] = j * j;
    }

    for (i = 0; i < RADIUS; ++i) {
        for (j = i + 1; j < RADIUS; ++j) {
            if (values[i] + values[j] <= HIT_ZONE_FIXPOINT) {
                ++hit_count;
            }
        }
    }
    hit_count *= 2;

    for (i = 0; i < RADIUS; ++i) {
        if (values[i] * 2 <= HIT_ZONE_FIXPOINT) {
            ++hit_count;
        }
    }

    free(values);
    return 4.0 * hit_count / (HIT_ZONE_FIXPOINT >> 2);
}
Alle Varianten mit einer `main()` um sie einfach ausprobieren zu können, sind hier zu finden: http://pastebin.com/uBePbQ2w

Und nun die andere Richtung — die längste Laufzeit bisher mit 3 Stunden 37 Minuten und 28 Sekunden. Auf einem C64 mit folgenden BASIC-Programm, das mit BASIC-Boss kompiliert wurde:

Code: Alles auswählen

   10 REM@ £PROTOCOL
   20 REM@ £CONSTANT R,HZ
   30 REM@ £WORD I=FAST,J=FAST
   40 REM@ £FASTFOR
   50 TI$="000000":R=2999:HZ=(R+1)*(R+1):HC=0:DIM X(R)
   60 FOR I=0 TO R:X=I+0.5:X(I)=X*X:NEXT
   70 FOR I=0 TO R-1:FOR J=I+1 TO R:IF X(I)+X(J)<=HZ THEN HC=HC+1
   80 NEXT:NEXT:HC=HC*2
   90 FOR I=0 TO R:IF X(I)*2<=HZ THEN HC=HC+1
  100 NEXT
  110 PRINT 4*HC/HZ,TI$
Tredory
User
Beiträge: 7
Registriert: Mittwoch 26. Februar 2014, 10:34

Hi, das lässt dir wohl keine Ruhe oder ;-)

Finde das Genial. Hast du nur dafür jetzt ernsthaft einen C64 ausgegraben ?
Das das auf dem Brotkasten mit seinem ~1 MHZ ewig dauern wird war ja abzusehen :P

Ich bin leider immernoch nicht dazu gekommen, Hab die Arbeit abgegeben nu kommt noch das Kolloquium und irgendwie kommen ständig andere Sachen dazwischen :-(

Kann das ja auch nochmal auf nem Arduino Mega Testen mit seinen 16 Mhz.
BlackJack

@Tredory: Nee, den C64 habe ich nicht dafür extra ausgegraben, mit dem spiele ich auch sonst noch gerne ein wenig herum. Dieses Programm hatte ich allerdings auf einem Chameleon64 laufen lassen, ein C64 in einem FPGA-Chip. :-)

Mal sehn was ich als nächstes mache, Amiga 500, oder das für den C64 in Assembler schreiben. :-)
Tredory
User
Beiträge: 7
Registriert: Mittwoch 26. Februar 2014, 10:34

Oha Amiga, Quantensprung zum C64 mit ~7MHZ :P
Assembler, Freiwillig ?? Na viel Spass :P
BlackJack

@Tredory: Klar freiwillig Assembler. Die Frage stellt sich beim C64 doch eher beim BASIC. Das ist deutlich schrecklicher. :-)

Und es würde mich schon interessieren wie schnell man das auf dem C64 bekommt, denn BASIC-Gleitkommazahlen sind ziemlich langsam, auch kompiliert, und da das BASIC nur 16-Bit-Ganzzahlen kennt, musste ich einiges als Gleitkommazahlen belassen was man in Assembler dann mit 24-Bit und 32-Bit Ganzzahlen beziehungsweise Festkommazahlen machen kann.
BlackJack

Und hier ist eine 6510-Assembler-Version die auf dem C64 in 7 Minuten und 42 Sekunden durchläuft: http://pastebin.com/0ufNWVG9
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

BlackJack hat geschrieben:Und hier ist eine 6510-Assembler-Version die auf dem C64 in 7 Minuten und 42 Sekunden durchläuft: http://pastebin.com/0ufNWVG9
Also genau die Version habe ich jetzt gerade gesucht :lol:
Das Leben ist wie ein Tennisball.
Francesco
User
Beiträge: 824
Registriert: Mittwoch 1. Dezember 2004, 12:35
Wohnort: Upper Austria

Hallo, ich habe das (die Originalversion) auch gerade probiert

die letzte Zeile habe ich durch

Code: Alles auswählen

print("%.5f" %(4*float(treffer)/quadtreffer))
ausgetauscht (sonst gibt das Programm 3.0000 statt 3.14159 aus).
Bei mir sind das 4.40 Sekunden auf Acer Aspire 7741. Gut, ist kein Raspberry, aber das ist ein Faktor 30 bis 40 mal schneller.
Python 2.7, Ubuntu 14.04 LTS

Das C++ Programm 0.39 Sekunden, also ist bei mir das C++ Programm ohne Optimierung (g++ pi_test.cpp -o pi_test) etwas über 11 mal schneller.

Nachtrag: Jetzt habe ich noch pypy probiert. Ich glaube es fast nicht: 0.201 Sekunden, ds ist etwa doppelt so schnell als die C++ Version (bei mir zumindest)!
Antworten