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.
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.
