Kleiner Vergleich der Geschwindigkeit von R vs julia

[jogo]

Die "Wort für Wort"-Übersetzung ist wahrlich eine Krux, wenn es Algorithmen betrifft, die mit Vektoroperationen geschrieben werden können und in der Ausgangssprache elementweise umgesetzt wurden.
Wenn man in R vektorbasiert arbeitet, dann ist dieser Teil so schnell wie kompilierter C-Code, denn dieser Teil ist kompilierter Code (C oder FORTRAN). Nur das Drumherum ist R - und damit interpretierter Code. Interpreter sind langsam, weil sie Zeile für Zeile abarbeiten müssen - das liegt also in der Natur der Sache.
Nun bilden oftmals aber gerade die Vektoroperationen den Kern dessen ab, was an Arbeit zu erledigen ist. Wenn man diesen Teil elementweise ausführt, gerät man in die Interpreterfalle (siehe oben - jede einzelne Zeile muss interpretiert werden).
Wenn man Vektoroperationen nutzt, dann kann der Unterschied zu C oder FORTRAN oder was auch immer nur im function-call-Overhead bzw. normalen Interpretationsoverhead bestehen - diese Overheads sollten nicht der Grund sein, weshalb man von einer zu einer anderen Programmiersprache wechseln sollte.

Es gibt sehr verschiedenen Programmiersprachen; und jede hat ihre Stärken und Schwächen. Z.B. kann man den Gaußschen Algorithmus für die Lösung eines linearen Gleichungssystems auch in PROLOG zu programmieren (das habe ich mit einem Freund zusammen in der Studienzeit wirklich gemacht - der Code sieht auch elegant aus), aber die Geschwindigkeit ist total grottig. Wenn man dagegen ein wissensbasiertes System mit vielen logischen Regeln in C (oder einer an deren 3G-Programmiersprache oder bei z.B. C++ einer 3,5-G-Sprache) implementieren wollte, hätte man sicher arge Probleme, um die Grundstruktur der Problematik zu implementieren (vielleicht gibt es dafür inzwischen Bibliotheken in C oder spezielle Klassen in C++).

Deswegen ist es bei dem Geschwindigkeitvergleich zwischen R und anderen Programmiersprachen wichtig, dass bei der Imprementation in R die R-eigenen Mittel gut ausgenutzt werden. Klar ist dann aber auch, dass nicht viel Spielraum für andere ähnliche Sprachen übrig bleibt (nur Interpretations- und function-call-Overhead).

Klar ist aber auch, dass bei Nichtnutzung der Vektoroperation der Geschwindigkeitsvergleich klar zugunsten von fast jeder kompilierenden Sprache ausfällt.
(zusätzliche Anmerkung: Ob eine Sprache interpretierend oder kompilierend ist, hängt weitestgehend nicht von der Sprache ab, sondern von den üblichen Umgebungen, die diese Sprachen bereitstellen - während des Studiums hatte ich es auch einmal mit einem C-Interpreter zu tun.)

Gruß, Jörg

[Athomas]

während des Studiums hatte ich es auch einmal mit einem C-Interpreter zu tun.

Das war aber noch beim Kaiser, oder ?

[jogo]

ja, Kaiser Zuse III.
Bei unserem Abiturgebäude (Villa, gebaut um 1900) hatten wir uns gewundert wie modern es war, dass man schon einen Pool im Garten angelegt hat. Später erfuhren wir, dass dies die Kühlung war (im Sinne von Wärmetauscher) für den ZR1, der damals die gesamte Villa ausfüllte.

Gruß, Jörg

[schubbiaschwilli]

Gude!

Trotz allen Diskussionen, wie der Code optimiert werden könnte (es waren ja einige interessante Ansätze dabei - Auch Sachen, die ich übersehen habe weil es bei ähnlichen Problemen nicht ging) möchte ich doch noch einmal erwähnen, was ich gemacht habe: Nämlich 2 Programme möglichst ähnlich zu bauen, um dann zu schauen, was schneller ist bzw. wie viel. Es war kein Wettbewerb, wer eine Programmiersprache wie gut tunen kann.

Ich möchte aber noch einmal auf einen wesentlichen Punkt eingehen: Nämlich die verwendeten eingebauten Funktionen. Verwendet man diese, dann ist die unterschiedliche Laufzeit nämlich m.E. vernachlässigbar. Erst der Algorithmus von Ding macht julia wirklich bzw. deutlich schneller - Vektorisierung hin oder her.

Dank&Gruß
schubbiaschwilli

[jogo]

Ich möchte aber noch einmal auf einen wesentlichen Punkt eingehen: Nämlich die verwendeten eingebauten Funktionen. Verwendet man diese, dann ist die unterschiedliche Laufzeit nämlich m.E. vernachlässigbar. Erst der Algorithmus von Ding macht julia wirklich bzw. deutlich schneller - Vektorisierung hin oder her.

Danke, dass Du diese Erfahrung nochmal heraushebst.
Es wäre wirklich interessant, worin der Unterschied in den Implementierungen bei dem Algorithmus von Ding besteht.
Folgende Ursachen könnte es geben (Liste sicher nicht vollständig):
- Der Algorithmus ist für elementweises Rechnen aufgeschrieben, aber Arbeiten mit Vektoren wäre möglich und würde dann die entsprechende Geschwindigkeit in den R-Code bringen
- Der Algorithmus lässt sich nicht gut durch Nutzung von Vektoroperationen ausdrücken (manchmal kann das im Laufe eines Algorithmus auch zu Platzproblem führen - typisch für Algorithmen der Kombinatorik und der Graphentheorie)

Gruß, Jörg

[Athomas]

Anbei ein interessanter Artikel zum Thema "Non-central Chi-Squared Probabilities – Algorithms in R":

https://cran.r-project.org/web/packages ... -Chisq.pdf

und der Originalartikel von Cherng G. Ding (super Spaghetti-Fortran 66, was für Feinschmecker wie jogo ):

https://pdfs.semanticscholar.org/d373/6 ... 478462.pdf

[jogo]

Der Code in dem Artikel von Ding ist FORTRAN 77 (ich sehe jetzt aber auch keinen großen Unterschied zu F66).
Der Algorithmus ist laut Autor des Artikels ein rekursiver Algorithmus. Auch bei iterativen und rekursiven Algorithmen gibt oft keine Darstellung in Form von Vektoroperationen.

Wenn - wie von schubbiaschwilli beschrieben für die zweite Runde der der gleiche Ablauf in R (ohne Vektoroperationen) bzw. in julia implementiert wurde, dann ist der Unterschied in der Geschwindigkeit wirklich der zwischen Interpreter und Compiler.

Was mich jetzt im Vergleich mit dem Artikel https://cran.r-project.org/web/packages ... -Chisq.pdf wundert, ist, dass dort steht, dass zunächst pnchisq() in C implementiert wurde - später auch nach dem Algorithmus von Ding und dann noch später diese Funktion mit der klassischen pchisq() zusammengefasst wurde - Also müsste doch in aktuellen R-Versionen ein C-Kompilat des Algorithmus von Ding werkeln. Dann muss es aber noch einige Unterschiede (vielleicht in Anzahl der Iterationen oder Abbruchkriterium) geben zwischen der Variante in pchisq() und der Variante in der zweiten Runde (dort die Implementierung für julia).

Gruß, Jörg

[Athomas]

Der Code in dem Artikel von Ding ist FORTRAN 77

Oho! Nenne mir bitte ein Argument dafür, dass sich das Ding vom Ding nicht innerhalb des Sprachstandarts von Fortran 66 bewegt!
Umgekehrt ist das "Block IF" mit else-Zweigen in Fortran 77 eingeführt worden - und das hätte man hier doch ganz fein verwenden können !?

Der Algorithmus ist laut Autor des Artikels ein rekursiver Algorithmus.

Ich glaube, da hat er sich verhaspelt - er schreibt ja auch von "recursive iterations" - was immer das sein soll!

[jogo]

Der Code in dem Artikel von Ding ist FORTRAN 77

Oho! Nenne mir bitte ein Argument dafür, dass sich das Ding vom Ding nicht innerhalb des Sprachstandarts von Fortran 66 bewegt!
Umgekehrt ist das "Block IF" mit else-Zweigen in Fortran 77 eingeführt worden - und das hätte man hier doch ganz fein verwenden können !?

Bei der Angabe FORTRAN 77 habe ich nur aus dem Kopf des Artikels zitiert. Da ich mit den feinen Unterschieden nicht ganz so gut auskenne wie Du (das sollte ja eigentlich das sein, was einen Feinschmecker ausmacht ), ist mir gleich gar kein Unterschied aufgefallen zu den FORTRAN-Varianten, die mir geläufig sind.

Gruß, Jörg

[EDi]

Hier komm R's copy-on-modify zu trage.
Bei jedem schreiben der Sys.time() wird eine Kopie von data erstellt, das kostet natürlich...

Durch den Vorschlag von Athomas (Vektorize + Sys.time() ausgliedern) kann man das recht "billig" ~6.5x schneller machen.

Ein weiterer "billiger speed-up ist, wenn man auf den (unnötigen) "factor" verzichtet:

Code: Alles auswählen

  data$PutCallFlag <- as.character(data$PutCallFlag)

Das macht den code dann schon insg. ~11x schneller.

Danach (=2. Iteration durch den profiler) ist "nur" noch die pchisq_ding() zeit am verbrauchen...