Hallo Leute, ich hatte heute eine kleine Diskussion mit jemandem über die Sprache C. Ich war der Meinung, daß es für die Laufzeit eines C-Programms sehr wohl einen Unterschied macht, ob ich die selbe Funktion mit 20 Schleifen programmiere oder ob ich das mit vielleicht nur 4 Schleifen hinkriege. Mein Gegenüber war der Meinung, daß das keine Rolle spielt, weil der Compiler sowieso den Quellcode optimiert. Speziell geht es hierbei um die C auf SPS-Steuerungen (ja, sowas gibt es)...sollte aber eigentlich egal sein. Ich bin halt der Meinung, daß der Compiler, wenn er auch optimieren kann kein Hellseher ist und somit bei 20 Schleifen nicht einfach mal 4 draus machen kann. Vielleicht kann mich ja jemand aufklären. Ist es wirklich so, daß Umständlicher Code nach der Compilierung die gleich Laufzeit hat wie kompakter Code ? (Für mich würde das keinen Sinn ergeben) Danke Meininger
> Ist es wirklich so, daß Umständlicher Code nach der Compilierung > die gleich Laufzeit hat wie kompakter Code ? im Allgmeinen nicht. Allerdings: > Ich war der Meinung, daß es für die Laufzeit eines C-Programms sehr > wohl einen Unterschied macht, ob ich die selbe Funktion mit 20 > Schleifen programmiere oder ob ich das mit vielleicht nur 4 > Schleifen hinkriege. Das kommt auf den Schleifeninhalt an. Wenn die Transformation von 20 auf 4 Schleifen naheliegend ist, dann kriegt der Compiler das meistens auch alleine hin. Steckt da aber etwas algorithmisch ausgefeilteres dahinter, dann kriegt der Compiler das meistens nicht hin. Es hängt halt dacon ab, ob er die Vereinigung von 20 Schleifen zu 4 in der Datenflussanalyse erkennen kann oder nicht. Aber generell kann man da nicht viel sagen ausser: Das muss man ausprobieren. Jeder Fall ist anders gelagert.
Meininger schrieb: > Ich bin halt der Meinung, daß der Compiler, wenn er auch optimieren kann > kein Hellseher ist und somit bei 20 Schleifen nicht einfach mal 4 draus > machen kann. Mach mal einfach die Gegenprobe: wenn man dem Compiler sagt, er soll möglichst aggressiv auf Geschwindigkeit optimieren, dann kann er im Extremfall alle Schleifen "entrollen", d. h. linear hintereinander in den Code schreiben. Spätestens an dieser Stelle sollte dir klar werden, dass es dann egal ist, ob es 20 kleine oder 4 große Schleifen waren. Ja, Compiler optimieren auf einer Ebene, an die man oft als Assembler- programmierer nicht rangehen würde, weil der entstehende Code völlig unübersichtlich und schlecht zu warten ist. Aber das ist dem Compiler natürlich egal. ;-)
Das war ja nur eine grundsätzliche Frage ohne konkrets Codebeispiel. Wenn jemand 20 Schleifen braucht um das selbe zu machen wie jemand der dazu nur 4 braucht, kann doch das Kompilat niemals gleich groß sein oder ? Da würde der Begriff "Codeoptimierung" doch ad absurdum geführt werden.
Meininger schrieb: > Das war ja nur eine grundsätzliche Frage ohne konkrets Codebeispiel. > Wenn jemand 20 Schleifen braucht um das selbe zu machen wie jemand der > dazu nur 4 braucht, kann doch das Kompilat niemals gleich groß sein oder > ? Da würde der Begriff "Codeoptimierung" doch ad absurdum geführt > werden. Das kannst du so nicht sagen. Es hängt immer vom Einzelfall ab. Ich würde mal so sagen: Die meisten 'Optimierungen' auf dieser Codeebene, die von einem C-Programmierer mit 2, 3, 4 Monaten Erfahrungen gemacht werden, kriegt der Compiler auch hin. Konzentrier dich als Programmierer auf die algorithmische Ebene. Das bringt viel mehr, als derartie Low-Level Code Pfriemeleien. Ein Compiler wird keinen Bubble-Sort erkennen und durch einen Quicksort ersetzen. Das ist aber die Ebene, auf der du dir massiv Zeit holen kannst. Ob du jetzt
1 | for ( i = 0; i < 5; i++ ) |
2 | a[i] = 5; |
3 | for ( i = 0; i < 5; i++ ) |
4 | b[i] = 8; |
schreibst, oder
1 | for ( i = 0; i < 5; i++ ) |
2 | {
|
3 | a[i] = 5; |
4 | b[i] = 8; |
5 | }
|
spielt kaum eine Rolle. Das schafft der Compiler auch locker ohne dich.
Meininger schrieb: > Das war ja nur eine grundsätzliche Frage ohne konkrets Codebeispiel. > Wenn jemand 20 Schleifen braucht um das selbe zu machen wie jemand der > dazu nur 4 braucht, kann doch das Kompilat niemals gleich groß sein oder > ? Da würde der Begriff "Codeoptimierung" doch ad absurdum geführt > werden. > dann würde der Compiler in seine Glaskugel schauen müssen und zum Hellseher mutieren! ...irgendwie macht deine Fragerei keinen Sinn!
Fefe hat das mal schön zusammengefasst: http://media.ccc.de/browse/conferences/camp2007/cccamp07-en-1952-Know_your_compiler.html Grob gesagt, nimm den geeignetsten Algorithmus, und implementiere den möglichst lesbar und kurz. Den Rest macht der Compiler. Anmerkung: Der geeignetste Algorithmus ist der, der bei minimalem Aufwand akzeptabel lange Zeit braucht. Viele sehr schnelle Algorithmen sind bei kleinen Elementzahlen langsamer als einfache Algorithmen. Und je weniger "schräges Zeug" Du machst, um so mehr Chancen hat der Compiler das zu optimieren. Wenn Du in C so schreibst wie man in Pascal schreibt, dann hat der Compiler große Freiheiten für die Optimierung.
@Karl Heinz Buchegger Diese Antwort war mal richtig erleuchtend! Es spielt also keine Rolle, ob ich einen Ringspeicher mit einer vergewaltigten Schleife indiziere oder dafür Modulo nehme ?
@Compiler Den Antworten der anderen Leser zu folgern, macht die Frage schon Sinn. Es macht nur keinen Sinn solche Antworten zu schreiben wie du, das kostet nur Speicherplatz.
Meininger schrieb: > @Karl Heinz Buchegger > > Diese Antwort war mal richtig erleuchtend! > > Es spielt also keine Rolle, ob ich einen Ringspeicher mit einer > vergewaltigten Schleife indiziere oder dafür Modulo nehme ? Es bringt nichts, wenn du immer allgmeine Dinge erfragen möchtest. Optimierungen sind etwas spezielles. Da gibt es wenige allgemeine Regeln. DIe wichtigste lautet: Don't do it! Die zweit wichtigste lautet: Don't do it, yet! Damit ist jetzt nicht gemeint, dss man absichtlich blödsinnigen Code schreiben soll. Du sollst den Algorithmus benutzen, der dem Problem angemessen ist. Du sollst normale Programmierrichtlinien beachten. Und du sollst die Regeln deiner "Handwerkskunst" beherrschen und sicher anwenden können. Und dann .... sollst du erst mal feststellen ob dein Code schnell genug ist. Ist er es, dann ist es ok. Erst wenn er nicht schnell genug ist, gehts an die Feinarbeit in der Optimierung. Und da wiederrum lautet die oberste Devise: Messen, messen, messen. Ehe es ans Optimieren geht, musst du erst mal feststellen, wo überhaupt Optimierungspotential besteht. Premature optimization is the root of all evil. Vorzeitige Optimierung ist die Wurzel allen Übels.
Meininger schrieb: > Es macht nur keinen Sinn solche Antworten zu schreiben wie du, das > kostet nur Speicherplatz. Falsch. Das ist die einzig sinnvolle Frage zu diesem Thema: Wie sieht der Code aus?
Jetzt muß ich eingestehen, daß ich nicht gesehen habe, daß "Compiler" derjenige war, der nach dem Code gefragt hat. Nach all den Antworten hier muß ich eingestehen, daß die Frage nun für mich berechtigt ist und nehme mienne Angriff in Richtung "Compiler" zurück. Allerdings wurde mir das jetzt erst durch die Dikussion mit "Karl Heinz Buchegger" klar. Danke für eure Beiträge, die Frage ist damit für mich beantwortet.
Karl Heinz Buchegger schrieb: > Falsch. > Das ist die einzig sinnvolle Frage zu diesem Thema: Wie sieht der Code > aus? > danke, ich hatte schon an mir gezweifelt...;-)
Wobei ich schon noch eines einwerfen möchte (komme übrignes aus e-technik, nicht aus Informatik) ...Bubble-sort und Quick-Sort unterscheiden sich ja im Endeffekt genau darin um was es geht. Das eine hat mehr Schleifen usw. als das andere. Ein Algorithmus ist ja auch nichts anderes als eine Aneinanderreihung von verschiedenen Konstrukten. Also könnte man ja doch sagen, daß eine kompliziertere Programmierung zu schlechterer Laufzeit führt, wenngleich natürlich die Größe des Algorithmus eine wesentliche Rolle spielt. Ich möchte jetzt eben das Wort Algorithmus nicht so stheen lassen, da im Prinzip ja jede Lösung für ein Problem ein Algorithmus ist.
Meininger schrieb: > Es spielt also keine Rolle, ob ich einen Ringspeicher mit einer > vergewaltigten Schleife indiziere oder dafür Modulo nehme ? Jain. Ersteinmal kommt es auf den Compiler an (und die Parameter an) und zum anderen kann ein Compiler zwar viele aber nicht alle Optimierungen vornehmen, die man sich überlegen kann. Nehmen wir mal folgenden Beispielquellcode: #define max 10 int arr[max]; function add(int start) { int index = start; for(int i=0; i<max; ++i) { arr[index] += i; index = (index+1); if (index >= max) index = 0; } } dieser ließe sich optimieren, indem statt index = (index+1); if (index >= max) index = 0; ein Modulo benutzt wird: index = (index+1) % max; Der Grund ist, dass aktuelle Prozessoren mit Pipelining arbeiten und bedingte Sprünge möglichst vermieden werden sollten. Hier konnte der bedingte Sprung (if-Abfrage) durch eine Rechenoperation ersetzt werden. Es ist durchaus möglich, dass der Compiler so ein "Muster" erkennen kann und auch entsprechend optimiert. Aber es ist eben vom Compiler (und dessen Optimierungsoptionen) abhängig und nicht sicher ob das passiert. Fazit ist aber mal eines: Es ist völlig unsinnig unnötig überall auf Geschwindigkeit zu optimieren. Erste Priorität sollte immer sein, dass der Quellcode gut lesbar bleibt. Nur dann kann man komplexe Software vernünftig weiterentwickeln. Es gibt genau 2 zwingende Gründe für Geschwindigkeits-Optimierung: 1. Es gibt eine Spezifikation (Vorgabe), wie schnell etwas ablaufen muss; Wenn die Spezifikation nicht erfüllt ist, muss optimiert werden. Beispiel: Der Wettervorhersage für morgen muss heute vor Sendebeginn fertig werden. Wenn die Vorhersage erst übermorgen berechnet ist, ist sie nicht mehr brauchbar. 2. Wenn man eine Software-Bibliothek entwickelt, welche von vielen anderen Entwicklern in zeitkritischen Stellen eingesetzt werden soll, muss verstärkt auf Optimierung geachtet werden. Ansonsten gilt: Man sollte keine unnötig "lahme" Software programmieren, aber in keinem Fall darf die Lesbarkeit und Verständlichkeit der Software grundlos leiden. Für Optimierungen gilt: Immer vorher definieren, was man erreichen will. Denn optimieren kann man immer weiter. Man wird bei komplexer Software immer noch irgendwo etwas finden, das ein wenig schneller programmiert werden kann. Aber der Gewinn an Geschwindigkeit ist dann einfach nicht mehr lohnenswert. Man sollte auch nicht wild drauf los optimieren, sondern zuerst die Stellen finden, die wirklich Rechenzeit verbraten bzw. Latenzprobleme verursachen. Dafür gibt es Profiler (externe Software, Bibliotheken oder Compiler/Entwicklungsumgebungs-Werkzeug) oder man misst einfach verstrichene Zeit in bestimmten Routinen von Hand... Man kann sagen, dass oft 90% der Rechenzeit in 10% des Quellcodes verbraucht wird. Und das beutet, dass man die anderen 90% des Quellcodes eigentlich nicht optimieren braucht. Die wirklich lohnenswerten Optimierungen sind aber heutzutage selten die Berechnungen, sondern oft bei der Speicherverwaltung zu finden. Neue Speicherbereiche anfordern und wieder freigeben, ist sehr zeitaufwändig. Ebenso spielt eine große Rolle, wie man Speicherbereiche Abarbeitet (Zeilen oder Spaltenweises durchlaufen von 2-dimensionalen Arrays). Das können viele Compiler aber optimieren. Bei großen Arrays kann hier schnell Faktor 10 an Geschwindigkeit heraus kommen. Worauf ich hinaus will: Man verschätzt sich (selbst wenn man Ahnung hat) schnell, wenn es darum geht zu sagen: "Wo wird denn die meiste Rechenzeit verbraucht?"; Fazit: Messen! Profiling-Werkzeuge verwenden! Und... nur optimieren wenn's auch Sinn macht! Lieber eine Software die nicht "ab und an" mal abstürzt oder sonstwie fehlerhaft arbeitet und dafür 5% mehr Zeit für eine Berechnung investieren...
Stefan K. schrieb: > will: Man verschätzt sich (selbst wenn man Ahnung hat) schnell, Oh, ja. Ist mir mal so gegangen. Kompliziertere Berechnung und mir ist aufgefallen, dass gewisse Werte mehrmals berechnet werden. Die Idee war, da einen Cache-Mechanismus einzubauen. 3 Tage Arbeit und im Endeffekt war die 'optimierte' Version langsamer als die ursprüngliche. Im Profiler hab ich dann gesehen, dass die ursprüngliche 'Mehrmalsberechnung' keine 10% der Laufzeit ausgemacht hat.
Meininger schrieb: > ...Bubble-sort und Quick-Sort unterscheiden sich ja im Endeffekt genau > darin um was es geht. Das eine hat mehr Schleifen usw. als das andere. Nö. Das geht viel weiter. Die komplette Grundidee, auf der die Sortierung basiert, ist eine völlig andere. Die 'Schleifen' sind nur Werkzeug um die Idee zu implementieren. Die Idee hinter Bubble Sort lautet: Vergleiche 2 nebeneinanderliegende Einträge und wenn sie in der verkehrten Reihenfolge liegen, dann vertausche sie. Das ganze mach entsprechend oft oder aber (in der verkürzten Version) solange, bis keine Vertauschungen mehr notwendig sind. Die Idee hinter Quick-Sort ist Nimm deine Einträge her und eine Stich-Element (zb Stichzahl). Teile die Einträge auf in 2 Haufen: die einen größer als das Stich-Element, die anderen kleiner. Dann geh her und sortiere die Teilhaufen zb nach dem gleichen Schema. Völlig andere Sortieridee.
Meininger schrieb: > ...Bubble-sort und Quick-Sort unterscheiden sich ja im Endeffekt genau > darin um was es geht. Das eine hat mehr Schleifen usw. als das andere. > nein, dass sind zwei grundverschiedene Ansätze! > Ein Algorithmus ist ja auch nichts anderes als eine Aneinanderreihung > von verschiedenen Konstrukten. > wenn es so wäre, würde es den Beruf des Informatikers/Programmierers nicht mehr geben, weil jemand Schlaues den Universal-Compiler geschaffen hätte und sich selbst arbeitslos gemacht hätte (krass ausgedrückt!). > Ich möchte jetzt eben das Wort Algorithmus nicht so stheen lassen, da im > Prinzip ja jede Lösung für ein Problem ein Algorithmus ist. > falsch, es ist ein Unterschied, ob es ein Bubble-, ein Quick- oder sonstwas-Sort ist. Ein Algorithmus unterscheidet sich nicht in der "Anordnung" der Befehle, sondern in der Herangehensweise(!) an ein Problem. Ich kann eine Menge wie ein kleines Kind sortieren oder etwas schlauer an das Problem herangehen, weil ich ein paar algorithmische Grundkenntnisse besitze und diese auch anwenden/transformieren/abstrahieren kann. Zeige mir den Compiler, der sich ein Problem "herein versetzen" kann und selbstständig Entscheidungen treffen kann, was im spezialen Fall am optimalsten ist!
Compiler schrieb: > Zeige mir den Compiler, der > sich ein Problem "herein versetzen" kann und selbstständig > Entscheidungen treffen kann, was im spezialen Fall am optimalsten ist! > KI war/ist so ein Zauberwort, an dass ich schon während meines Studiums gezweifelt hatte... Dafür ist mir die Antwort "42" zu profan!
Compiler schrieb: > Zeige mir den Compiler, der > sich ein Problem "herein versetzen" kann und selbstständig > Entscheidungen treffen kann, was im spezialen Fall am optimalsten ist! Ein Programmierer hat meist auch zusätzliche Informationen, die er nicht in den Quellcode schreibt, aber für Optimierungen nutzen kann. Zum Beispiel könnte der Programmierer wissen, dass eine Liste von Werten, in die er genau einen Wert einfügt, schon sortiert ist. Dann muss der Wert nur an der richtigen Stelle eingefügt werden. Das ginge mit einem viel geringeren Aufwand, als den Wert am Ende anzuhängen und dann die gesamte Liste zu sortieren. Ebenso funktioniert Bubble-Sort nicht gut mit bereits recht gut vorsortierten Listen. Da macht es sogar Sinn, diese vorher zu durchmischen. Insbesondere wenn Daten von Außerhalb in einem bestimmten Format oder nach einer bestimmten Vorgabe in das Programm gelangen, kann der Compiler dieses Vorwissen nicht aus dem Quellcode ableiten.
Stefan K. schrieb: > dieser ließe sich optimieren, indem statt > > index = (index+1); > if (index >= max) index = 0; > > ein Modulo benutzt wird: > > index = (index+1) % max; Schlechtes Beispiel, Division sind selbst auf modernen CPU teuer. (Jedenfalls solange der Divisor nicht konstant und aus der Menge 2 hoch n ist). Dafür kennen moderne CPUs sowas wie CMOV was Sprünge vermeiden hilft. Möglicherweise ist auch die OOO und Sprungvorhersage der Ziel-CPU so gut, das die Version mit dem if schneller ist.
Stefan K. schrieb: > dieser ließe sich optimieren, indem statt > > index = (index+1); > if (index >= max) index = 0; > > ein Modulo benutzt wird: > > index = (index+1) % max; Die "optimierte" Version ist bei mir (gcc) um den Faktor 3 langsamer.
Der Compiler tut auch einen cmovge in den compilierten Code: code] add: .LFB0: .cfi_startproc xorl %eax, %eax xorl %ecx, %ecx .p2align 4,,10 .p2align 3 .L3: movslq %edi,%rdx addl $1, %edi addl %eax, arr(,%rdx,4) cmpl $1000000, %edi cmovge %ecx, %edi addl $1, %eax cmpl $1000000, %eax jne .L3 rep ret .cfi_endproc [/code]
Meininger schrieb: > Vielleicht kann mich ja jemand aufklären. Ist es wirklich so, daß > Umständlicher Code nach der Compilierung die gleich Laufzeit hat wie > kompakter Code ? Vielleicht sollte man das hier mal deutlicher schreiben: "Umständlicher Code" ist Code, der umständlich gedacht ist oder nach einer Idee arbeitet, die unklug ist. Also etwas, wo ein schlecht durchdachter Algorithmus dahinter steckt. Beispiel: if ((a>512)||(a==512) a = a - 512; mag sein, daß der Compiler das reduziert kriegt, aber a = a & 511 ist weniger umständlich - nur als triviales Beispiel. Das ist was ganz anderes als "Kompakter Code", den ich hier mal als Zusammenziehung auf Quellcodeniveau definiere, die zwar sprachlich erlaubt ist, aber einfach bloß aus Schreibfaulheit dasteht. Beispiel: A *= B; //"kompakt" A = A*B; // "ausführlich" Ich halte nix von solchem "kompakten" Code, sondern sehe die Lesbarkeit und Deutlichkeit als viel wichtiger an. Selbst der Compiler kommt mit einfacheren und dafür deutlicheren Anweisungen meist besser zurecht als mit komplizierten Zusammenziehungen, von denen eben nur der Programmierer glaubt, daß er damit sein Programm optimiert hätte. In obigem Beispiel kommt bei beiden Schreibweisen der gleiche Maschinencode heraus... Ein anderes blödes Beispiel ist die Abneigung einiger C-Programmierer gegen Pascal, weil man bei C { und } schreibt und bei Pascal eben begin und end schreiben muß. Welch verschwenderische Fingerabnutzung! Ein gutes Beispiel für sauschlechten weil umständlichen Code findet man bei ST bei deren Standardbibliothek für die STM32er. Dort wird massiv aller möglicher Krempel an selbst definierten Konstanten zusammengeschrieben, um dann als Parameterblock irgendwo im RAM hinterlegt zu werden, wo dann ein Zeiger im Funktionsaufruf drauf zeigt - und in der Funktion wird dann aus dem ganzen Wust eine simple Zahl gemacht, die in das betreffende Register geschrieben wird. Viel Lärm um nichts und ein Beispiel, wie man es NICHT machen sollte. W.S.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.