Zum Spaß habe ich versucht, die Stack-Performance einiger Programmiersprachen zu vergleichen, die die Fibonacci-Serie mit dem naiven rekursiven Algorithmus berechnen. Der Code ist in allen Sprachen der gleiche, ich poste eine Java-Version:
%Vor%Ok, der Punkt ist, dass ich mit diesem Algorithmus mit Eingabe 40 diese Zeiten habe:
%Vor%Sie werden in einer Ubuntu 10.04-Box mit den Versionen jeder Sprache in den offiziellen Repositories auf einer Dual-Core-Intel-Maschine gespeichert.
Ich weiß, dass funktionale Sprachen wie ocaml die Verlangsamung haben, die von der Behandlung von Funktionen als Bürger erster Ordnung herrührt, und haben kein Problem, die Laufzeit von CPython zu erklären, weil es die einzige interpretierte Sprache in diesem Test ist, aber ich war beeindruckt die Java-Laufzeit, die die Hälfte der c für den gleichen Algorithmus ist! Würden Sie dies der JIT-Kompilierung zuordnen?
Wie erklären Sie diese Ergebnisse?
EDIT: Danke für die interessanten Antworten! Ich erkenne, dass dies kein richtiger Maßstab ist (ich habe nie gesagt, dass es war: P) und vielleicht kann ich ein besseres machen und es Ihnen nächstes Mal posten, im Lichte dessen, was wir besprochen haben:)
EDIT 2: Ich habe die Laufzeit der ocaml-Implementierung mit dem optimierenden Compiler ocamlopt aktualisiert. Außerdem habe ich das Testbed bei Ссылка veröffentlicht. Fühlen Sie sich frei, Ergänzungen zu machen, wenn Sie wollen:)
Vielleicht möchten Sie die Optimierungsstufe Ihres C-Compilers erhöhen. Mit gcc -O3 macht das einen großen Unterschied, einen Rückgang von 2.015 Sekunden auf 0.766 Sekunden, eine Reduktion von etwa 62%.
Darüber hinaus müssen Sie sicherstellen, dass Sie richtig getestet haben. Sie sollten jedes Programm zehn Mal ausführen, entfernen Sie die Ausreißer (am schnellsten und am langsamsten), dann die anderen acht.
Stellen Sie außerdem sicher, dass Sie die CPU-Zeit und nicht die Uhrzeit messen.
Alles andere als das, ich würde keine vernünftige statistische Analyse in Betracht ziehen und es könnte durchaus zu Lärm kommen, was Ihre Ergebnisse nutzlos macht.
Für das, was es wert ist, waren diese obigen C-Zeiten für sieben Läufe, wobei die Ausreißer vor der Mittelung herausgenommen wurden.
Tatsächlich zeigt diese Frage, wie wichtig die Auswahl des Algorithmus ist, wenn eine hohe Leistung angestrebt wird. Obwohl rekursive Lösungen in der Regel elegant sind, leidet dieser unter dem Fehler, dass Sie eine Menge von Berechnungen duplizieren. Die iterative Version:
%Vor%senkt außerdem die benötigte Zeit von 0,766 Sekunden auf 0,078 Sekunden, eine weitere Reduzierung von 89% und eine satte Reduzierung von 96% gegenüber dem ursprünglichen Code.
Und als letzten Versuch sollten Sie Folgendes ausprobieren, das eine Nachschlagetabelle mit Berechnungen jenseits eines bestimmten Punktes kombiniert:
%Vor%Das verkürzt die Zeit noch einmal, aber ich vermute, dass wir hier den Punkt der abnehmenden Rendite erreichen.
Sie sagen sehr wenig über Ihre Konfiguration aus (beim Benchmarking sind Details alles: Befehlszeilen, verwendeter Computer, ...)
Wenn ich versuche, für OCaml zu reproduzieren, bekomme ich:
%Vor% Dies ist auf einem Intel Xeon 5150 (Core 2) bei 2,66 GHz. Wenn ich den Bytecode OCaml Compiler ocamlc andererseits verwende, bekomme ich eine Zeit ähnlich Ihrem Ergebnis (11s). Aber natürlich, um einen Geschwindigkeitsvergleich durchzuführen, gibt es keinen Grund, den Bytecode-Compiler zu verwenden, es sei denn, Sie möchten die Geschwindigkeit der Kompilierung selbst vergleichen ( ocamlc ist erstaunlich für die Geschwindigkeit der Kompilierung).
Eine Möglichkeit ist, dass der C-Compiler auf der Annahme optimiert, dass der erste Zweig ( n < 2 ) der häufigste ist. Es muss das nur zur Kompilierzeit tun: Vermutungen machen und dabei bleiben.
Hotspot wird den Code ausführen, sehen, was tatsächlich passiert häufiger und neu optimieren basierend auf diesen Daten.
Sie können einen Unterschied erkennen, indem Sie die Logik von if :
Es ist trotzdem einen Versuch wert:)
Überprüfen Sie wie immer auch die Optimierungseinstellungen für alle Plattformen. Offensichtlich die Compiler-Einstellungen für C - und auf Java, versuchen Sie, die Client-Version von Hotspot vs der Server-Version zu verwenden. (Beachten Sie, dass Sie länger als eine Sekunde laufen müssen, um den vollen Nutzen von Hotspot zu erhalten ... es könnte interessant sein, den äußeren Anruf in eine Schleife zu setzen, um Läufe von einer Minute oder so zu erhalten.)
Ich kann die Python-Leistung erklären. Pythons Leistung für Rekursion ist bestenfalls miserabel und sollte wie die Pest vermieden werden, wenn man darin kodiert. Zumal der Stapelüberlauf standardmäßig bei einer Rekursionstiefe von nur 1000 ...
auftrittWas die Leistung von Java angeht, ist das erstaunlich. Es ist selten, dass Java C (sogar mit sehr wenig Compiler-Optimierung auf der C-Seite) schlägt ... was die JIT tun könnte, ist Memo oder Tail-Rekursion ...
Beachten Sie, dass die Java-Hotspot-VM intelligent genug ist, um fib () - Aufrufe zu memotieren. Dadurch können die exponentiellen Kosten des Algorithmus auf etwas reduziert werden, das näher an den linearen Kosten liegt.
Ich schrieb eine C-Version der naiven Fibonacci-Funktion und kompilierte sie zu Assembler in gcc (4.3.2 Linux). Ich habe es dann mit gcc -O3 kompiliert.
Die nicht optimierte Version war 34 Zeilen lang und sah wie eine direkte Übersetzung des C-Codes aus.
Die optimierte Version war 190 Zeilen lang und (es war schwer zu sagen, aber) schien zumindest die Aufrufe für Werte bis etwa 5 zu inline.
Mit C sollten Sie entweder die Fibonacci-Funktion "inline" deklarieren oder mit gcc das Argument -finline-functions zu den Kompilierungsoptionen hinzufügen. Dadurch kann der Compiler rekursives Inlining ausführen. Das ist auch der Grund, warum mit -O3 eine bessere Leistung erreicht wird, aktiviert -finline-functions .
Bearbeiten Sie müssen mindestens -O / -O1 angeben, um rekursives Inlining zu erhalten, auch wenn die Funktion inline deklariert ist. Eigentlich habe ich selbst festgestellt, dass ich die Funktion inline deklariere und -O als Kompilierungsflag benutze oder einfach -O -finline-functions benutze, mein rekursiver fibonacci Code war schneller als mit -O2 oder -O2 -finline-functions .
Ein C-Trick, den Sie ausprobieren können, besteht darin, die Stapelprüfung zu deaktivieren (dh den eingebauten Code, der dafür sorgt, dass der Stapel groß genug ist, um die zusätzlichen lokalen Variablen der aktuellen Funktion zuzuweisen). Dies könnte für eine rekursive Funktion heikel sein und könnte tatsächlich der Grund für die langsamen C-Zeiten sein: Das ausführende Programm könnte keinen Stapelspeicherplatz mehr haben, was die Stapelprüfung zwingt, den gesamten Stapel während des tatsächlichen Durchlaufs mehrmals neu zuzuweisen / p>
Versuchen Sie, die benötigte Stapelgröße zu approximieren, und zwingen Sie den Linker, so viel Stapelspeicherplatz zuzuweisen. Deaktivieren Sie dann die Stapelprüfung und erstellen Sie das Programm erneut.
Tags und Links python java c performance ocaml