Warum ist C so schnell?
-
Artchi schrieb:
keksekekse schrieb:
Ein paar interessante Links:
www.google.de c warum schnell
http://scienceblogs.com/goodmath/2006/11/the_c_is_efficient_language_fa.php
* C: 0.8 seconds.
* C++: 2.3 seconds.
* OCaml: 0.6 seconds interpreted, 0.3 seconds fully compiled.
* Java: 1 minute 20 seconds.
* Python: over 5 minutes.Völlig irrelevant, weil der Test so ca. im Jahr 2000 stattfand.
foobar schrieb:
Hast du den Artikel auch ganz gelesen? Letztendlich kommt dann heraus, dass aktueller JIT-Compiler für Java auch eine Laufzeit von 0.7 Sekunden "herausoptimieren" konnten (plus dem zusätzlichem Startup der etwa 1 Sekunde dauert).
Hem, der JIT ist besser geworden, zum Glück. Aber was ist wenn ich einen heutigen C++-Compiler nehme und alles auf optimum stelle? Siehste!
Hier mal der Kommentar von dem Typen, der den Vergleichstest machte:
Mark Chu-Carroll schrieb:
I can't give you the code I did the LCS tests on - as I said, it was six years ago!
Yo, der Kommantar ist von 2006 minus 6 Jahre... 2000 wurde der Vergleich gemacht. Ist in der heutigen Zeit natürlich voll relevant. Egal ob für C, C++, Python oder Java. Alle haben heute einen anderen (besseren) Stand.
Der JIT war aber auch schon Stand 2000 so gut, dass man auf eine Laufzeit von 0.7 Sekunden gekommen ist. Insofern ist das völlig irrelevant, wie viel sich seither getan hat. Fakt ist halt nunmal, dass C/C++ in gewissen Bereichen nicht so optimieren kann, wie Java, OCaml, ..
-
foobar`` schrieb:
Fakt ist halt nunmal, dass C/C++ in gewissen Bereichen nicht so optimieren kann, wie Java, OCaml, ..
Warum?
-
java und ocaml zwingen den programmierer in wesentlich striktere regularien. dadurch kann der compiler einfacher annahmen treffen und den code entsprechend optimieren.
ginge in c++ sicherlich auch, aber irgendwann ist auch mal schluss bei der komplexität eines parsers.
wäre bei benchmark vergleichen aber eh immer sehr sehr vorsichtig. code, der in einer sprache wahnsinnig performant ist, kann in einer anderen sprache plötzlich unglaublich ineffizient werden. wenn man wirklich vergleichen will, müsste man einen bestimmten algorithmus jeweils von absoluten spezialisten in ihren lieblingssprachen implementieren lassen. das ist aber sehr selten der fall.
-
Hydrogen_Snake schrieb:
foobar`` schrieb:
Fakt ist halt nunmal, dass C/C++ in gewissen Bereichen nicht so optimieren kann, wie Java, OCaml, ..
Warum?
Simpelstes Beispiel:
f(a(),b(),c())In C++ ist das erstmal nicht parallelisierbar. In vielen funktionalen Sprachen aber, ist es problemlos parallelisierbar und wenn du zufaelligerweise 3 CPUCores hast, kann jede Funktion auf einem eigenen Core laufen.
Generell gilt: desto mehr restriktionen die Sprache einem aufzwingt, desto staerker ist es optimierbar. Restriktionen sind nicht gleichbedeutend mit beschneiden von features - denn zB Lisp bietet sicher nicht wenig features an - man kann ja sogar seine eigenen sprachfeatures implementieren - aber dadurch das zB verboten wird, dass objekte state haben koennen, ermoeglicht man unmengen an optimierungen.
Komplette virtuelle Maschinen wie Java und .NET erlauben dann auch wieder komplett andere Optimierungsansaetze da der Code erst kompiliert werden muss wenn er ausgefuehrt wird - das simpelste hier ist zB Profile Guided Optimization - etwas das in C++ nur mit grossem Aufwand (sprich viel Zeit) realisierbar und vorallem nur fuer vordefinierte Testfaelle machbar ist, bekommt man durch die virtuelle Maschine gratis.
Das sind nur 2 Aspekte von vielen (wobei alles natuerlich seinen Vorteil und seinen Nachteil hat).
PS:
solche Benchmarks sind aber in den meisten Faellen Schrott.
-
Shade Of Mine schrieb:
Generell gilt: desto mehr restriktionen die Sprache einem aufzwingt, desto staerker ist es optimierbar. Restriktionen sind nicht gleichbedeutend mit beschneiden von features - denn zB Lisp bietet sicher nicht wenig features an - man kann ja sogar seine eigenen sprachfeatures implementieren - aber dadurch das zB verboten wird, dass objekte state haben koennen, ermoeglicht man unmengen an optimierungen.
Es ist in Lisp nicht verboten, dass Objekte State haben.
-
Bashar schrieb:
Es ist in Lisp nicht verboten, dass Objekte State haben.
Damn
Ich hab gewusst dass ich lieber nichts ueber lisp sagen sollte :pIm Prinzip wollte ich damit lediglich das fehlen von seiteneffekten in vielen Funktionalen Sprachen (wie zB Erlang, F#, Haskell,...) beschreiben - von Lisp habe ich leider zuwenig Ahnung und huete mich da wieder vermutungen daruber anzustellen.
-
Shade Of Mine schrieb:
f(a(),b(),c())In C++ ist das erstmal nicht parallelisierbar.
Warum nicht? a(), b() und c() können doch wohl parallel berechnet werden. Nur f() muss warten.
-
funky cat schrieb:
Shade Of Mine schrieb:
f(a(),b(),c())In C++ ist das erstmal nicht parallelisierbar.
Warum nicht? a(), b() und c() können doch wohl parallel berechnet werden. Nur f() muss warten.
a(), b() und c() könnten globale Variable lesen/schreiben.
-
Vermutung schrieb:
a(), b() und c() könnten globale Variable lesen/schreiben.
Hast Recht. Hmmm.. fürs parallelisieren gibts in C++ ja OpenMP
-
funky cat schrieb:
Vermutung schrieb:
a(), b() und c() könnten globale Variable lesen/schreiben.
Hast Recht. Hmmm.. fürs parallelisieren gibts in C++ ja OpenMP
Könnte man nicht dem Compiler sagen, dass das Programm keine globalen Variablen hat? Dann könnte man doch parallelisieren?
-
Gegenfrage schrieb:
funky cat schrieb:
Vermutung schrieb:
a(), b() und c() könnten globale Variable lesen/schreiben.
Hast Recht. Hmmm.. fürs parallelisieren gibts in C++ ja OpenMP
Könnte man nicht dem Compiler sagen, dass das Programm keine globalen Variablen hat? Dann könnte man doch parallelisieren?
Ne, In C++ ist alles erlaubt, was kein Syntax Error ist. Demzufolge kann ein Compiler nicht zu viel Intelligenz des Programmierers voraussetzen. Man könnte vielleicht einen super-optimierenden Compiler entwickeln, der erstmal 3 Stunden den Code analysiert. In C gibt es neuerdings das "restrict" Schlüsselwort. Damit wird ein ähnlicher Ansatz verfolgt, aber letztendlich muß der Programmierer immer mitspielen. Wenn der Scheiße baut, kann der beste Compiler nichts reißen.
-
Das ist halt oft das problem bei den benchmarks. Viele sprachen haben ihre restriktionen und machen dann, egal wie ahnungslos der programmierer ist, ihre optimierungen. Bei c/c++ haengt sehr viel optimierung von dem programmierer ab. du kannst alles richtig oder alles falsch machen. machst du alles richtig, gibt es keinen grund weshalb ein c/c++ compiler nicht das schnellste executable generiert. machst du etwas falsch, bist du 100mal langsammer als scriptsprachen.
Entsprechend sind solche benchmarks oft nur die aussage darueber wie gut jemand programmiert.
-
Gegenfrage schrieb:
funky cat schrieb:
Vermutung schrieb:
a(), b() und c() könnten globale Variable lesen/schreiben.
Hast Recht. Hmmm.. fürs parallelisieren gibts in C++ ja OpenMP
Könnte man nicht dem Compiler sagen, dass das Programm keine globalen Variablen hat? Dann könnte man doch parallelisieren?
An sich ist es auch kein Problem heraus zu finden ob a, b oder c auf globale Variablen zugreifen oder vielleicht über Pointer oder Referenzen auf die gleiche Variable. Das Problem ist nur, dass man den gesamten Programmcode braucht um diese Informationen zu generieren. Dies ist aber wegen des C++ Linkermodels nicht der Fall.
GCC kennt spezielle Schlüsselwörter mit denen einfache Versprechen auch weiter reichen kann. Dazu zählen zum Beispiel die Attribute const (!= std C++ const) und pure. Es gibt noch weitere.
-
Ben04 schrieb:
Gegenfrage schrieb:
funky cat schrieb:
Vermutung schrieb:
a(), b() und c() könnten globale Variable lesen/schreiben.
Hast Recht. Hmmm.. fürs parallelisieren gibts in C++ ja OpenMP
Könnte man nicht dem Compiler sagen, dass das Programm keine globalen Variablen hat? Dann könnte man doch parallelisieren?
An sich ist es auch kein Problem heraus zu finden ob a, b oder c auf globale Variablen zugreifen oder vielleicht über Pointer oder Referenzen auf die gleiche Variable. Das Problem ist nur, dass man den gesamten Programmcode braucht um diese Informationen zu generieren. Dies ist aber wegen des C++ Linkermodels nicht der Fall.
Gibt es nicht sowas wie "global optimisation" oder -fone-at-a-time o.ä.?
-
Ich denke, das würde nur im kleinen Rahmen was nützen. Wenn der Compiler was zu optimieren überlegt und erstmal herausfinden muss, ob eine Funktion effektfrei ist und die Funktionen, die sie aufruft, usw. ... Stell dir vor, man würde const nicht immer so weiterreichen (const-Methode darf nur const-Methoden aufrufen) sondern aus Bequemlichkeit den Compiler rausfinden lassen, ob ein Objekt bis hierhin noch nicht verändert wird. Das Problem skaliert bestimmt nicht gut auf große Programme, also wird die Tiefe, bis zu der Optimierungen überlegt werden, eingeschränkt. Als würde die Übersetzung eines C- oder C++-Programms nicht schon lange genug dauern.
IMHO brauchen C und C++ funktionale Sprachmittel. Sowas wie "diese Funktion ist effektfrei" oder noch besser, explizit "die Funktion hat Effekte". Und ein gescheites Übersetzungsmodell.
-
Optimizer schrieb:
Ich denke, das würde nur im kleinen Rahmen was nützen. Wenn der Compiler was zu optimieren überlegt und erstmal herausfinden muss, ob eine Funktion effektfrei ist und die Funktionen, die sie aufruft, usw.
Es mag dich ueberraschen, aber genau so ist es. const als c++ keyword ist nur eine restriction die programmierer an andere stellen. fuer compiler ist das unwichtig fuer die optimierung. ein compiler muss die implementierung pruefen dass sie _garantiert_ keine seiteneffekte hat.
... Stell dir vor, man würde const nicht immer so weiterreichen (const-Methode darf nur const-Methoden aufrufen) sondern aus Bequemlichkeit den Compiler rausfinden lassen, ob ein Objekt bis hierhin noch nicht verändert wird.
und stell dir vor ein compiler wuerde sich darauf verlassen und du darin eine mutable veraendert oder einen const_cast oder eine global...
Das Problem skaliert bestimmt nicht gut auf große Programme, also wird die Tiefe, bis zu der Optimierungen überlegt werden, eingeschränkt. Als würde die Übersetzung eines C- oder C++-Programms nicht schon lange genug dauern.
die tiefe wird nicht eingeschraenk afaik. entsprechend kann es ewigkeiten dauern ein paar templates zu optimieren. kann man sehr schoen im VS sehen. im Debug bekommt man manche templates in sekunden compiliert, im release kann er an einem file 20min haengen. und templates sind auch nur ein teil vom graphen.
IMHO brauchen C und C++ funktionale Sprachmittel. Sowas wie "diese Funktion ist effektfrei" oder noch besser, explizit "die Funktion hat Effekte". Und ein gescheites Übersetzungsmodell.
das uebersetzungmodel ist denk ich mir geschmackssache. und effektfreiheit dem programmierer in die hand zu druecken, wo manche nichtmal mit speichermanagement klarkommen waere echt boese. wenn man ein gut zu optimierendes c++ schreiben will ist das heute schon moeglich, man muss nur alle regeln kennen die die jeweilige optimierung verhindern. zudem sollte man auch die faehigkeiten der cpus kennen, was auf einer gut ist, muss auf einer anderen nicht gut sein und das kann ein compiler nicht optimieren.
-
Ich weiß, dass const nicht bedeutet, dass etwas effektfrei ist. Aber const zu verifizieren ist für den Compiler einfach (man darf nur const-Methoden aufrufen). Die Effektfreiheit zu verifizieren ist nicht einfach, weil es dafür nicht sowas wie const gibt, deshalb denke ich, dass viele Optimierungen die möglich sind, nicht gemacht werden.
Und ich meine, es müsste so etwas wie const mit der Bedeutung "Effektfreiheit" geben. Ich hab es wohl nicht gut beschrieben.
-
Ich sehe nicht wieso das Ewigkeiten dauern muss. Man könnte das optimierte Übersetzen in zwei Teile aufbrechen. Im ersten werden aus allen Quellcode Dateien Metainformationen extrahieren welche dann im zweiten Durchlauf genutzt werden. Zwischen beiden Läufen werden die Metainformationen dann ausgewertet.
Nehmen wir das Beispiel von Seiteneffekten. Für eine Funktion vom Typ
int f(){ return a()+b(); }wird die Information "Hat nur Nebeneffekte wenn a oder b welche hat" erstellt. Für Funktionen welche auf keinen anderen aufbauen kann man dann ein "Hat Nebeneffekte" oder "Hat keine" speichern. Bei API Grenzen muss man fertig generierte Metadaten besitzen.
Das geht in linearer Zeit zu der Anzahl der Funktionen. (Template Funktionen muss man hier per Instanzierung zählen.)
Nun lädt man alle Metadaten und man erhält einen Baum. Man läuft von allen "Hat Nebeneffekte" die Abhängigkeithierarchi mit einer Tiefensuche entlang und man findet alle Funktionen die Seiteneffekte haben.
Geht auch in linearer Zeit.
Im zweiten Teil der Übersetzung benutzt man dann die so generierten Metainformationen.
Dieses Verfahren könnte zwar bis zu zweimal so langsam sein als das jetzige aber Ewigkeiten sind das noch keine.
Ähnlich könnte man sogar genau bestimmen welche Funktion von welchen globale Variablen abhängt. So könnte man trotz Seiteneffekte in vielen Situationen parallelisieren. Auch das müsste in linearer Zeit gehen.
Problematischer als Zugriffe auf globale Variablen sind Zugriffe über Pointer. Hier sehe ich keine wirklich schnelle Methode das zu optimieren.
Der Grund warum es nicht gemacht wird ist ganz einfach. 99% der Funktionen in C++ greifen irgendwo über einen Pointer auf etwas zu. Für die restlichen 1% ist es den Aufwand nicht wert.
-
Optimizer schrieb:
Ich weiß, dass const nicht bedeutet, dass etwas effektfrei ist. Aber const zu verifizieren ist für den Compiler einfach (man darf nur const-Methoden aufrufen). Die Effektfreiheit zu verifizieren ist nicht einfach, weil es dafür nicht sowas wie const gibt, deshalb denke ich, dass viele Optimierungen die möglich sind, nicht gemacht werden.
Und ich meine, es müsste so etwas wie const mit der Bedeutung "Effektfreiheit" geben. Ich hab es wohl nicht gut beschrieben.
Effektfreiheit zu testen dauert nicht lange und ist nicht kompliziert (dafuer gibt es schliesslich klare regeln), jedoch muss es gemacht werden und wird nur sehr selten ueber die c++ keywords bestimmt.