Fibonacci-Folge / Benchmarks

Pascal, Basic und andere nicht aufgelistete
Benutzeravatar
Bebu
Beiträge: 562
Registriert: Mi Okt 21, 2009 6:19 pm
Wohnort: In der Nähe von Salzburg - Bin aber kein Österreicher!

Re: Fibonacci-Folge / Benchmarks

Beitrag von Bebu » Do Mär 09, 2017 12:49 pm

Xin hat geschrieben:Vielen Dank. Werde ich am Wochenende mal ins Rennen schicken und dann das erste Posting aktualisieren.

Go sieht ja eigentlich noch recht unscheinbar aus. Hast Du damit mal tiefergehende Erfahrung gesammelt?
Leider nein. Ich habe nur ein bisschen damit rumgespielt. Das Konzept hat mir gut gefallen, weil man praktisch gezwungen wird lose gekoppelten Code zu schreiben. Auf der anderen Seite muss man sich wohl in vieler Hinsicht umgewöhnen. Vielleicht kann ich ja auf Arbeit irgendwann ein kleines Projekt damit umsetzen.
Wer immer nach dem Unerreichbaren jagt, der wird irgendwann auf die Schnauze fallen!

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8471
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Do Mär 30, 2017 11:31 pm

Nicht, dass ich mit dem AST-Interpreter konkurrenzfähig werde, dafür verbrät der doch zuviel Zeit.

Im wichtigsten Schritt habe ich jetzt mal etwas aufgeräumt und komme so von

Code: Alles auswählen

Genesys:    ~8,8sek  AST
zu

Code: Alles auswählen

Genesys:    ~6,850sek  AST
PS:
Beim Funktionsaufruf ein 'new' rausoptimiert.

Code: Alles auswählen

Genesys:    ~6,520sek  AST
Guter Hinweis, dass die Verwendung eines MemoryPools als Stack hier nochmal 0,3-0,5 Sekunden bringen dürfte.
Den müsste ich aber erstmal schreiben und das ist mir dann doch zuviel für heute. :)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8471
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » So Apr 23, 2017 11:42 pm

Bis gestern hatte ich eine Woche "Urlaub", die ich dazu genutzt habe Genesys zu beschleunigen. Mein Ziel war am Montag (also heute) mit einem Lächeln zur Arbeit zurück zu kehren. Ist knapp geworden, will ich aber gelten lassen.

Statt 6,52 Sekunden läuft das Programm nun in 0,062 Sekunden.
Damit bin ich mit einem selbstgeschrieben JIT-Compiler, der zum ersten Mal läuft mehr als doppelt so schnell wie Java, aber habe noch etwas Abstand zu den nativ laufenden Sprachen. Mal gucken, dass ich in den nächsten Wochen nochmal eine Woche Urlaub bekomme. Da kann man noch was schleifen und natürlich auch mal ein Executable erzeugen.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8471
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Di Jun 20, 2017 2:09 pm

Am Wochenende habe ich noch ein wenig gebastelt, denn interessanterweise ist die Schleife - um die 30 Fibonaccizahlen auszurechnen aufwendiger gewesen, als der Funktionsaufruf. Ich musste benannte Variablen besser unterstützen, eben die Schleife und Genesys bringt implizit Zählvariablen mit.
Die vorherige Messung ist also 30x mal manuel programmiert der Funktionsaufruf, nun gibt's mit der Schleife wirklich identischen Code.

Das führt zu zwei Ergebnissen: Mit den Änderungen wurde das ganze auch etwas schneller: 55ms. Von 62ms auf 55ms klingt wenig - ist aber satte 10%.
Und nun, wo das ganze funktioniert, wird es vermutlich auch wieder gelöscht. Ich weiß ja jetzt, wie es funktioniert, die Test-Implementation hat damit seinen Dienst getan, nun kann man statt einer Try-And-Error-Implementation vielleicht etwas mit mehr Verstand machen. ;)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8471
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » So Jul 02, 2017 6:59 pm

In meiner Freude den JIT-Compiler lauffähig zu haben habe ich gleich zwei recht blöde Dinge übersehen. ^^

The Bad News: Wir sind langsamer als gedacht.

Der User Darksider3 sprach mich vor einiger Zeit darauf an, dass wir ja relativ kleine Laufzeiten haben, die im Falle von Java ja auch auf die Anlaufzeiten von Java zurückzuführen sein könnten. Die Fibinacci-Zahlen wie beschrieben zu berechnen ist schon sehr, sehr teuer und die Reihe von 1 bis 30, das hat in der guten alten Zeit schon viele meiner Computer ins Schwitzen gebracht. Die AST-Version schwitzte dabei ja auch noch ganz gut, also hielt ich die Aussage für ausreichend und konnte mir auch sehr gut vorstellen, dass sich Genesys auch bei längeren Laufzeiten weiter absetzen kann.
Auch wenn er mich nicht sehen konnte, wie ich mir dabei gedanklich auf die Stirn schlug... das nicht getestet zu haben, nervte mich schon. Also habe ich die Werte von 1 bis 40 berechnet, was schon massiv mehr Zeit kostet:
Java braucht hier 1,35 Sekunden - und Genesys 4,85 Sekunden.
Das mit den 30 war also dumm gelaufen, bis 33 (190ms statt 205ms bei Java) ist Genesys schneller, bei 34 (303ms) liegt Java (230ms) dann vorne. Von da an vergrößert sich der Abstand zu Genesys mit jeder weiteren Iteration.
Entsprechend mache ich den Benchmark nun zusätzlich mit Fibunacci-Zahlen bis 40. Wenn ich Java hier überhole, werde ich grundsätzlich vorne liegen.

The Good News: Wir sind schneller als gedacht - aber noch nicht schnell genug.

Ich baue Debug-Informationen in den ausführbaren Code ein. Das sind einfache Texte, die mir mein Disassembler anzeigt um mir zu sagen, wo ich mich in dem Wust aus Assembler gerade befinde. Diese werden von der CPU einfach übersprungen. Sprünge sind nichts, was ein Programm schnell macht und vor allem sind Debug-Versionen nicht unbedingt optimal, um Benchmarks zu machen. Das fiel mir die Tage auch wie Schuppen von den Augen, so dass ich mir die alte Version aus dem Repository zurückholte und die Funktion, welche die Debug-Informationen schreibt, zu deaktivieren.
Ergebnis: Statt 55ms läuft das Programm nun 30ms - fast eine Verdopplung der Ausführungsgeschwindigkeit.

Nimmt man die raus, verdoppelt sich die Ausführungsgeschwindigkeit nahezu. Finde ich gut. :-)

Code: Alles auswählen

                    30           40             (Werte gemessen auf einem Xeon X5675)
Java          139ms     1350ms
Genesys      55ms     4850ms    // mit Debug-Informationen
Genesys      30ms     2200ms    // ohne
C (opt)         12ms      650ms
Python 2.7  570ms  59950ms
Die Frage nach der Startgeschwindigkeit ist damit raus. Was bedeutet das im Alltag?
Erstens: Das Programm ist extrem kurz und da gibt's noch reichlich Potential, mit überschaubaren Änderungen deutliche Fortschritte zu machen, wie man C sieht.
Zweitens: Im Alltag laufen Programme gar nicht im Bereich von hunderten Millisekunden, sofern sie keine komplexen Berechnungen machen. Das sieht man sehr schön an Python (2.7), das für viele Aufgaben bereits reicht, aber bei Berechnungen selbst komplett in die Knie geht. Genesys hat keine nennenswerte Startphase und wird später auch native Executables rausspucken - in den gemessenen Werten ist auch immernoch der komplette Kompiliervorgang enthalten, bevor das Programm starten kann.

Von daher bin ich mit der Performance doch noch ganz zufrieden. :-)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

mfro
Beiträge: 303
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Mo Jul 31, 2017 12:59 pm

Ich glaub' Tcl hatten wir noch nicht?

Code: Alles auswählen

proc fib x {
     expr {$x<2? $x : [fib [incr x -1]] + [fib [incr x -1]]}
 }

for { set value 0 } { $value <= 30 } { incr value } {
     puts "$value: [fib $value]"
 }
ist leider eher lahm. Tcl hat zwar einen Bytecode-Interpreter, der muß aber wohl die "expr"-Zeile für jede neue Rekursionsstufe neu compilieren:

real 0m1,948s
user 0m1,699s
sys 0m0,156s
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8471
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Mo Jul 31, 2017 10:16 pm

So... Arbeit ist durch, jetzt komme ich auch hierzu :)
mfro hat geschrieben:Ich glaub' Tcl hatten wir noch nicht?
Nein, hatten wir nicht. Dafür erstmal vielen Dank. :-)
Ich habe es in meine Benchmarks übernommen.
mfro hat geschrieben:ist leider eher lahm. Tcl hat zwar einen Bytecode-Interpreter, der muß aber wohl die "expr"-Zeile für jede neue Rekursionsstufe neu compilieren:
Geschwindigkeit ist nur ein Kritierium, weswegen ich auch froh bin, wenn da noch weitere Listings kommen.
TCL ist beispielsweise was die Länge des Quelltext recht kurz. Ich bin zwar kürzer, aber tcl zeigt hier eine Syntax, die ich zwar ähnlich plane, aber noch nicht behersche. Entsprechend ist der TCL Code noch nicht exakt vergleichbar (das If(<) return ...; return ...; fehlt)
Es ist interessant möglichst weitgehend vergleichen zu können.
Daher vielen Dank dafür :)
mfro hat geschrieben: real 0m1,948s
user 0m1,699s
sys 0m0,156s
Interessant ist, dass wir ganz unterschiedliche Zeiten haben: Ich brauche auf dem Xeon länger, aber deutlich weniger System-Zeit!?

real 0m2,162s
user 0m2,156s
sys 0m0,004s


Nebenher habe dabei auch mal die aktuellen Genesys-Zeiten nachgetragen, die sich von 55ms auf 29ms verbessert haben. Sehr geil ist, dass ich damit Rust überholt habe und damit die erste nativ kompilierende Sprache. Das ist schon irgendwie cool... :-D
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

mfro
Beiträge: 303
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Mo Jul 31, 2017 10:43 pm

Xin hat geschrieben: Interessant ist, dass wir ganz unterschiedliche Zeiten haben: Ich brauche auf dem Xeon länger, aber deutlich weniger System-Zeit!?

real 0m2,162s
user 0m2,156s
sys 0m0,004s
Ich denke, das liegt an der Cygwin-Umgebung, auf der ich das heute Mittag habe laufen lassen. Auf meinem Linux-Laptop (2.1 GHz i7 4600U) sieht's so aus:

real 0m1,708s
user 0m1,704s
sys 0m0,000s
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8471
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Di Aug 01, 2017 12:40 pm

mfro hat geschrieben:
Xin hat geschrieben: Ich brauche auf dem Xeon länger,
real 0m2,162s
Ich denke, das liegt an der Cygwin-Umgebung, auf der ich das heute Mittag habe laufen lassen. Auf meinem Linux-Laptop (2.1 GHz i7 4600U) sieht's so aus:

real 0m1,708s
Erstaundlicherweise bin ich mit meinem Laptop mit i5-3-irgendwas (2,6GHz) auch schneller als der Xeon. Die Single-Thread-Performance lässt da bei den 3 GHz Xeons ziemlich zu wünschen übrig (wobei die x5675 auch schon 6 oder 7 Jahre alt sind). Aber dass man davon mehrere zusammenwerken lassen kann und ich so auf 24 Threads kommt, die dann unabhängig voneinander kompilieren, das macht die Kiste dann wieder ziemlich flott. :)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

mfro
Beiträge: 303
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Mo Okt 09, 2017 1:38 pm

Ich nehme übrigens stark an, dass Du mit C/C++ lediglich die Geschwindigkeit der Konsolen-Ausgabe misst.

ich habe nämlich gerade das hier probiert (c++ 11):

Code: Alles auswählen

constexpr int fib(int f)
{
    return f <= 2 ? 1 : fib(f - 1) + fib(f - 2);
}
und das ist keinen Deut schneller. D.h. der Compiler hat bereits ganz ohne constexpr aus deinem Benchmark eine Konstante gemacht.
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Antworten