Hallo Ich sucher Literatur (Web Tutorials, Bücher,...) wie man schnellen C Code schreibt, bzw. wie man die Geschwindigkeit von C Code misst. Ihr wisst ja das ++i schneller als i++ ist,... Also ich suche schnelle Codekonstrukte, Tips, Tricks,... Danke schon mal im Vorraus fürs Lesen und vielleicht könnt Ihr ja helfen. Sebastian
es sind verschiedenen Dinge ... i++ Postkrement ++i Prekrement
1 | #include <stdio.h> |
2 | |
3 | int main (int argc, char **argv) { |
4 | int a, b, i; |
5 | |
6 | i = 0; |
7 | a = ++i; |
8 | b = i++; |
9 | |
10 | printf ("%d %d %d\n", i, a, b); |
11 | |
12 | return 0; |
13 | } |
++i bedeutet dass der Schleifenkörper erst ausgeführt, dann inkrementiert wird. i++ ... genau umgekehrt. Schneller is da nix. Bei gutem, soliden Entwurf von Algorithmen und Software-Design sollte man anfangen. Literatur empfehlungen: Code Complete - Steve McConnell Design Patterns - Gamma et all Algorithims in C - Robert Sedwick Geg. auch mal eine Vorlesung Theoretische Informatik / Logik besuchen. Da kannste viel brauchbares mitnehmen. z.B. Minimierung von logischen Ausdrücken, sortieren nach Wahrscheinlichkeit (bei verknüpften Bedingungen sehr hilfreich) uvm. Wenn du dann noch schnelleren Code willst, gehts in richtig system spezifischer Optimierungen. z.B. effektives ausnutzen der "multimedia erweiterungen" der CPU. Die sind eigentlich für die berechnung von Matrizen gedacht aus integralen Koordinaten (MMX) oder Fließkommakoordinaten (SSE). Aber der Zugewinn an Geschwindigkeit ist irrelevant gering gegenüber Verlusten bei schlechtem Software-Design und Algorithmen. Also fang da an.
Naja, es gibt angeblich schon einen Unterschied zwischen der Post- und der Prefixform dieses Operators und der liegt darin, dass eine Form ne temporäre Variable erzeugt (-en muss)... Ansonste lautet die Antwort: Genau nachschauen, Profiler benutzen und nicht wie blöde losoptimieren. 10 % des Codes laufen 90 % der Zeit. Finde diese, optimiere diese...
Dies ist jetzt nur meine Meinung; denn diesbezüglich gehen die Meinungen sehr auseinander! Ich würde auf keinen Fall Optimierungen vornehmen die der Leserlichkeit/Verständnis des Codes schaden um ihn ein wenig schneller hin zu bekommen. Das Optimieren sollte dem Compiler überlassen werden. Mit einigen Einstellungen am Compiler kann meistens festgelegt werden, ob man eher schnellen Code oder möglichst kleinen Code haben will. Das Problem ist sonst, dass Du manuell irgendwelche Optimierungen vornimmst, die dann vielleicht den Code ein wenig schneller machen. Dann kann es sein, dass Du mal eine neue Version des Compilers installierst, welcher ein wenig anders mit Deinem Code umgeht. Dann beginnt Deine ganze Arbeit von vorne. Wie bereits gesagt, am besten nur den zu implementierenden Algorhythmus optimieren / vereinfachen, so dass nichts unnötiges berechnet wird. Oder vielleicht kannst Du den Algorhythmus vo vereinfachen, dass er z.B. mit 16-Bit statt 32-Bit auskommt. Das sind Dinge wo man ansetzen kann. Aber wie gesagt, ist nur meine Meinung....
> Naja, es gibt angeblich schon einen Unterschied zwischen der Post- und > der Prefixform dieses Operators und der liegt darin, dass eine Form ne > temporäre Variable erzeugt (-en muss)... Das ist komplett abhängig vom Compiler, genauer, ob dieser schlau genug ist um zu erkennen ob er den temporären Wert überhaupt benötigt oder nicht. Im cc65 Manual steht z.B. irgendwo, dass der Compiler das nicht kann, und man deshalb ++i gegenüber i++ bevorzugen soll, wenn es von der Logik her keine Rolle spielt, welche Variante verwendet wird. Man würde dann also bevorzugt for (i=0; i<10; ++i) { /*...*/ } anstatt for (i=0; i<10; i++) { /*...*/ } schreiben. > ++i bedeutet dass der Schleifenkörper erst ausgeführt, > dann inkrementiert wird. i++ ... genau umgekehrt. > Schneller is da nix. Du weisst schon dass a) Die Inkrementoperatoren mehr oder weniger nichts speziell mit Schleifen zu tun haben (ausser dass man sie selbstverständlich z.B. in einer for-Schleife verwenden kann) b) Wie eine for-Schleife in C/C++/Java/C#/... funktioniert ?
> Im cc65 Manual steht z.B. irgendwo
Ehrlich? Sowas gibts?
Dabei ist das doch eine eigentlich leichte Übung für den
Compiler.
Ansonsten:
Überlasse low-level Optimierungen dem Compiler. Der kann das
meistens besser als der Programmierer. Der Programmierer macht
Optimierungen auf der algorithmischen Ebene.
Bevor du anfängst zu optimieren: Profiler benutzen.
Alles andere ist sinnlos. Wie oben schon angesprochen, gilt
die 90/10 Regeln: Bei den meisten Programmen verursachen lediglich
10% vom Code mehr als 90% der Laufzeit. Optimierungen in den
restlichen 90% vom Code wirken sich daher nur in der Brieftasche
des Auftraggebers aus. Die Kunst besteht darin, die 10% vom Code
zu finden, bei denen sich eine Optimierung überhaupt lohnt.
Menschen sind notorisch schlecht beim Aufspüren dieser 10%.
Ein Profiler hingegen misst, wieviel Zeit in welchem Code-
Abschnitt verbraucht wird und sucht dir quasi die 10% raus.
Bsp. Ist mir selber passiert.
Ein Programmteil in einem grösserem System brauchte relativ lange.
Es ging um möglichst optimales Triangulieren von Polygonen, wobei
'optimal' hier eher subjektiv definiert wurde (keine spitze Innen-
winkel, möglichst gleich grosse Flächen der einzelnen Dreiecke)
Nach Durchsicht des Codes stellte ich fest, dass manchmal komplexe
Berechnungen mehrfach erfolgten, weil das das Pgm vereinfacht
hat. Nichts desto trotz hatte das natürlich O(n^2) [oder wars
gar O(n^3)] Komplexität. Ich beschloss, dagegen was zu tun
und auf Tricks wie Lazy-Evaluation bzw. Caching von Zwischen-
resultaten auszuweichen. Im Endeffekt funktionierte das auch,
allerdings war es so, dass diese Version noch langsamer war.
Was war geschehen?
Ich hatte keinen Profiler eingesetzt, der mir gesagt hätte, dass
die Neuberechnung von Zwischenresultaten bei weitem nicht so häufig
erfolgte, wie ich dachte. Der Zeitgewinn, den ich durch die Vermeidung
dieser Berechnungen ereichte, wurde durch die Cache-verwaltung bei
weitem wieder aufgefressen.
> Ehrlich? Sowas gibts?
Ja. Kommt bei "kleineren" Compilern an denen nicht so viele Leute
arbeiten (wie cc65, der ist für den 6502, hab ich mal spasseshalber
damit gearbeitet) ab und zu vor. Ich habe keine Ahnung von Compilerbau,
könnte mir aber vorstellen dass der Optimizer einer der schwierigeren
Bereiche ist.
@Bartli Peephole optimisation: http://en.wikipedia.org/wiki/Peephole_optimization Damt sollte man das in den Griff bekommen. Rahmenbedingungen sollten natürlich immer überprüft werden. Aber im grossen und ganzen ist dieses spezielle Problem einfach zu lösen.
Hi Erstmal sollte man sich Gedanken über den eigentlichen Algorithmus machen. Schönes Beispiel ist da immer wieder das Suchen eines bestimmten Werts in einer sortierten Liste. Leider viel zu oft sieht man da:
1 | for(i = 0; i < list.length(); i++) |
2 | {
|
3 | if(list[i] == match) return i; |
4 | }
|
schauder Matthias
Hi, wollte nochmal ein kleines Beispiel reinklatschen für Pre- und Postincrement, der Vollständigkeit halber.
1 | int i; |
2 | for(i = 0; i < 10;) { |
3 | printf("%i ", i++); /* postincrement */ |
4 | }
|
liefert: 0 1 2 3 4 5 6 7 8 9
1 | int i; |
2 | for(i = 0; i < 10;) { |
3 | printf("%i ", ++i); /* preincrement */ |
4 | }
|
hingegen liefert: 1 2 3 4 5 6 7 8 9 10 Kleiner aber feiner Unterschied. Am bessten man vermeidet also solche Schreibweisen um sich Selbst und Anderen einen gefallen zu tun. ;D
@Mighty
Ich kapiers nicht.
Was willst du uns zeigen?
Das Prä- und Postinkrement verschiedene Ergebnisse haben?
Gähn. Ja das ist genau so definiert, wenn man das Ergebnis
des Inkrement weiterverwendet. Und sei es nur für die
Ausgabe.
> Am bessten man vermeidet also solche Schreibweisen
Am besten man lernt die Sprache und passt bei dem was
man tut etwas auf. Prä und Postinkrement sind nun wirklich
kein Thema um in C bei Optimierungen anzufangen. (Mit Ausnahme
des cc6502 Kompilers, der aber anscheinend auch schon etwas in
die Jahre gekommen ist).
> Das Prä- und Postinkrement verschiedene Ergebnisse haben? Genau. Scheinbar ist das aber nicht allen klar. Und du hast scheinbar die vorigen Beiträge nicht gelesen. Erst denken, dann sprechen.. > Prä und Postinkrement sind nun wirklich > kein Thema um in C bei Optimierungen anzufangen. Lies weiter oben...
> Und du hast scheinbar die vorigen Beiträge nicht gelesen. Doch, hab ich. Und allen ist klar, dass, solange das Ergebnis der Inkrement Expression nicht benutzt wird, es also nur auf den Nebeneffekt der Erhöhung ankommt, alle Compiler die neuer als 20 Jahre sind, in beiden Fällen den gleichen Code generieren. Das zu optimieren ist für einen Compilerbauer eine absolut simple Übung und ist in C nichts, worüber sich ein Programmierer Gedanken machen sollte oder müsste. Auch das steht schon weiter oben. Mir ist aber immer noch nicht klar, was du mit: > Am bessten man vermeidet also solche Schreibweisen meinst. Welche Schreibweisen?
> Und allen ist klar, ... Schließ nicht von Dir auf Andere. Ich weiß z.B. nicht ob das für Sebastian gilt. Also hab ich ein Beispiel zur Verdeutlichung gepostet. > solange das Ergebnis der > Inkrement Expression nicht benutzt wird Jop, sonst macht es schon einen Unterschied. > Auch das steht schon weiter oben. Das hab ich auch selbst geschrieben. > Welche Schreibweisen? Ich beziehe mich dabei offensichtlich auf das sehr einfache Beispiel. printf("%i ", i++) oder printf("%i ", ++i);
> > Und allen ist klar, ... > > Schließ nicht von Dir auf Andere. Ich weiß z.B. nicht ob > das für Sebastian gilt. Also hab ich ein Beispiel > zur Verdeutlichung gepostet. Ist zwar egal. Ich versteh immer noch nicht inwiefern jettzt dein letztes Codebeispiel, das den Unterschied zwischen ++i und i++ in einer Expression mit Nebeneffekt zeigt, relevant für das Thema das Threads ist, das da lautet: Optimierungen. >> Welche Schreibweisen? > Ich beziehe mich dabei > offensichtlich auf das sehr einfache Beispiel. > printf("%i ", i++) oder printf("%i ", ++i); Erklär mal. Warum soll man das nicht verwenden? Das was da passiert ist so klar wie Klossbrühe. Oder sollte es zumindest nach der 3. Unterrichtseinheit in C sein. Selbst der grindigste C-Neuling hat das in Nullkomma-Nix kapiert was da abgeht. Ist interessant, weil sie sich andere, trivialere Dinge nicht merken können, ist aber so.
Hallo Also bei einem einfachen Programm ist es wahrscheinlich Banane ob man ++i oder i++ schreibt. Aber wenns schnell sein soll, also mathematische Operationen die kontinuierlich ausgeführt werden sollen und man schon mal gehört hat macht man sich eben seine Gedanken. Keiner kann sagen warum es gleich schnell sein soll, keiner warum es langsamer/schneller sein soll. Bisher habe ich keine Literatur darüber gefunden, weder Uralte noch neue. Hat jemand nen Tipp was es für Bücher gibt, oder irgendwas in der Art? Also es geht um C Code auf Windows. Auch wenn die Compiler mittlerweile gut sind, denke das der Compiler immer noch nicht alles macht(denken kann bisher kein Computer, auch wenn er zeitweilig ein Eigenleben zu entwickeln scheint). Und C ist ja eine knifflige Sprache, einfach zu lernen, fordernd im Detail. Sebastian
@Karl heinz Buchegger Es ist ein einfaches Beispiel! Ich müll jetzt nicht das Forum zu mit komplexen Beispielen (die du sicher auch nicht auf Anhieb verstehst) wie man es nicht machen soll. Solche die von Klugscheissern geschrieben wurden die am Ende selbst nichtmehr durchgesehen haben weil der Code weder Verständlich noch Wartbar war (*wozu soll ich das kommentieren, is doch klar warum blablabla*). Zu Optimierungen habe ich mich in Form von Literaturempfehlungen schon geäußert.
Vielleicht wurden auch nur C und C++ in einen Topf geworfen und von einem aufs andere geschlossen. Dann wäre die Diskussion sinnlos. Zu C++: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050516/026527.html "Hard fast rule: Preincrement (++X) may be no slower than postincrement (X++) and could very well be a lot faster than it. Use preincrementation whenever possible. The semantics of postincrement include making a copy of the value being incremented, returning it, and then preincrementing the "work value". For primitive types, this isn't a big deal... but for iterators, it can be a huge issue (for example, some iterators contains stack and set objects in them... copying an iterator could invoke the copy ctor's of these as well). In general, get in the habit of always using preincrement, and you won't have a problem." Bücher zum Thema gibt es sicher wie Sand am Meer. Entweder in Richtung Theorie zum Compilerbau oder in Richtung Praxis Effizientes Programmieren. Aber im Zweifelsfall kann man ja auch nachsehen, was der eigene Compiler produziert. Wenn man per ++a/a++ Performance-Probleme ausmerzen muss, hat man eh andere Probleme ;-)
> die du sicher auch nicht auf Anhieb verstehst Mach dir mal keine Sorgen darüber was ich auf Anhieb verstehe oder nicht. Mich hat nur die Aussage gestört, dass > Am bessten man vermeidet also solche Schreibweisen im Zusammenhang mit einem nicht besonders zum Thema gehörenden Beispiel gekommen ist. Ansonsten: Können wir das abschliessen. Die Diskussion um ++i oder i++ bringt einen in C nicht weiter (wohl aber in C++, wie bereits angemerkt wurde, aber darum geht es hier nicht), wenn es um das Thema Laufzeitoptimierung geht.
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.