Programme beschleunigen in C

[erichpop]

Hallo Leute ich habe eine Frage im Bezug auf die Geschwindigkeit von Programmen, bzw. meiner konkreten Anwendung.
Es geht mir darum herauszufinden was so generelle Verhaltensregeln sind um in c die Laufzeit der Programme klein zu halten. Die theoretischen Ideen über Laufzeiten kenne ich (d.h. Laufzeit Analyse usw. im Informatikgrundstudium).
Ich suche nach einer guten Beschreibung die mir kurz und knapp einige generelle Verhaltensregeln bzgl. des codes, nicht bzgl. der Struktur meines Algorithmus nennt. Alles was ich bisher entdeckt habe bleibt da absolut wage. Es heißt immer, dies oder das ist schnell aber ich suche nach konkreten Beispielen wann was wirklich zu erheblichen Unterschieden führt. Dabei interessieren mich zurzeit speziell folgende Fragen:
1. Wann benutze ich Zeigen wann Variablen, wie groß ist der Geschwindigkeitsunterschied?
2. Macht es einen Unterschied ob ich mein Programm in viele Unterfunktionen aufteile oder nicht?
3. Hat die Anzahl der an Unterfunktionen gegeben Paramter Einfluss auf die Laufzeit?
4. Variablen lieber lokal oder global deklarieren?
5. Welche Geschwindigkeitsunterschiede machen die Einzelnen typen (float double usw.)?
6. Wie benutze ich fprintf innerhalb einer sehr lang laufenden for schleife geschwindigkeitseffizient?
7. Parallelisierung mittels MPI einer for schleife deren Durchläufe unabhängig voneinander sind.
8. Böse if Abfragen sind die wirklich so langsam und wenn ja wie kann ich die verbessern?
9. usw.
Konkret geht es darum, dass ich eine forschleife habe, die mind. 1 Mio mal durchläuft und wie sich jeder ausrechen kann braucht das ganze Programm ca. 11 Tage wenn jeder Durchlauf auch nur 1 sec dauert. Parallelisierung ist übrigens kein Problem ich kann auf große Cluster zugreifen.

Vielen Dank

[panzi]

Ließ das:
http://events.ccc.de/camp/2007/Fahrp...s/1952.en.html

Sind nur Folien. Den Vortrag dazu bekommst du als Video da:
http://dewy.fem.tu-ilmenau.de/CCC/CC...r_compiler.m4v
bzw. http://events.ccc.de/camp/2007/Streams

1. Wann benutze ich Zeigen wann Variablen, wie groß ist der Geschwindigkeitsunterschied?

"Normale" Variablen sind sicher oft schneller, weil keine Indirektion da ist. Verwende Zeiger wo es Sinn macht. Wenn durch eine normale Variable der Code schlechter zu maintainen ist, ist es eine schlechte Wahl. i.d.R. stellt sich die Frage eh nicht, weil es klar ist das man nur das eine oder Andere verwenden kann. Und der Kompiler optimiert eh sau viel (deswegen muss man bei multithreaded Sachen oft volatile verwenden, damits noch so läuft wie man erwarten würde).

2. Macht es einen Unterschied ob ich mein Programm in viele Unterfunktionen aufteile oder nicht?

Nicht bei einen guten Kompiler

3. Hat die Anzahl der an Unterfunktionen gegeben Paramter Einfluss auf die Laufzeit?

Nicht bei einen guten Kompiler.

4. Variablen lieber lokal oder global deklarieren?

Würd sagen egal.

5. Welche Geschwindigkeitsunterschiede machen die Einzelnen typen (float double usw.)?

kA

6. Wie benutze ich fprintf innerhalb einer sehr lang laufenden for schleife geschwindigkeitseffizient?

Gibts unterschiedliche Möglichkeiten printf zu verwenden?

7. Parallelisierung mittels MPI einer for schleife deren Durchläufe unabhängig voneinander sind.

Sicher eine gute Idee, wenn es sich um viele Durchläufe handelt.

8. Böse if Abfragen sind die wirklich so langsam und wenn ja wie kann ich die verbessern?

Naja. Das hat mit der breiten Pipeline zu tun. Also conditional Branches haun dir die breite Pipeline zam, denn auch ansonsten unabhängige Befehle können nicht Parallel ausgeführt werden, es muss auf den Ausgang des Branches gewartet werden. Apple macht da was krankes ihn deren 3D API (soweit ich weiß): Gewisse Settings werden nicht mit ifs in jedem Schleifendurchgang abgefragt. Stattdessen wird mit Hilfe von LLVM der Code der Schleife entsprechend neu kompeliert und somit gibts kein einziges if im Code, aber es wird trotzdem genau das gemacht was bei der Version mit den ifs gemacht werden würde (also semantisch ident) nur erspart man sich die vielen Branches.

[jan61]

Moin,

noch 2 kleine Ergänzungen zu panzi:

1. Wann benutze ich Zeigen wann Variablen, wie groß ist der Geschwindigkeitsunterschied?

Pointer sind u. a. dann sinnvoll, wenn Du dadurch große oder häufige Umkopieraktionen im Speicher (z. B. immer wiederkehrende Variablenzuweisungen) einsparen kannst, beim Iterieren durch Arrays o. ä.

6. Wie benutze ich fprintf innerhalb einer sehr lang laufenden for schleife geschwindigkeitseffizient?

Beim Schreiben in Dateien könnte es sinnvoll sein, statt fprintf() lieber fwrite() mit einer größeren Blocksize zu nutzen und die Blöcke durch z. B. sprintf() zusammenzusetzen. Eine andere Möglichkeit, Dateioperationen zu beschleunigen, ist mmap(), also das Einblenden von Dateien in den RAM.

Jan

[Berufspenner]

2. Macht es einen Unterschied ob ich mein Programm in viele Unterfunktionen aufteile oder nicht?

Du hast hals höchstens häufige Sprünge im Programm selber. Halt immer vom Aufruf der Funktion hin zur Definition und wieder zurück. Einen Geschwindigkeitsvorteil kannst du dir evtl. durch Inline-Funktionen verschaffen. Dies geht aber nur auf Kosten der Speicherbelegung. Dein Programm wird dadurch halt größer, aber messbar schneller. Die Frage ist bloß, zu welchem Preis. Das ist dann eben von deinem Programm abhängig.

Edit:

5. Welche Geschwindigkeitsunterschiede machen die Einzelnen typen (float double usw.)?

Wenn du kleine Typen wie int, short und char benutzt, dann kannst du, wenn du variablen mit dem Schlüssel "register" deklarierst, also z.B.

register short i;

diese direkt im CPU Register verarbeiten, was natürlich ein Optimum an Geschwindigkeit ist. Das geht wie gesagt aber nur mit kleinen Datentypen

[unita02]

2. Macht es einen Unterschied ob ich mein Programm in viele Unterfunktionen aufteile oder nicht?

Natürlich. Jeder Funktionsaufruf und Rücksprung muß (je nach "Calling type" - in Win z.B. cdecl oder pascal) den Stack belegen/bereinigen. (also oft gerufene Funktionen als inline: die fügt der Compiler an die Stelle des Aufrufes ein -> dafür aber mehr Code)

3. Hat die Anzahl der an Unterfunktionen gegeben Paramter Einfluss auf die Laufzeit?

Ja. Siehe 2.

4. Variablen lieber lokal oder global deklarieren?

Hängt von deinem Speichermodell ab (Stichwort "short pointer") - im allgemeinen aber nicht.

5. Welche Geschwindigkeitsunterschiede machen die Einzelnen typen (float double usw.)?

Das hängt von deiner CPU ab. Ein sizeof(int) sollte in der Regel die CPU-Datenwort-Breite wiederspiegeln und am effizientesten verarbeitet werden. Viele Rechner haben auch Zusatzmodule zum effizienteren Rechnen (ala 8087:-) Beispiel: die x86 CPU's haben sogenannte SSE-Erweiterungen, die mit Float/Double wesentlich effizienter rechnen können (z.B. Vektorberechnungen). Natürlich muß Du dann auch eine lib haben, die selbige anspricht. Auch Grafikkarten können für Vektorrechnungen effektiv "misbraucht" werden.

6. Wie benutze ich fprintf innerhalb einer sehr lang laufenden for schleife geschwindigkeitseffizient?

Benutze es garnicht :-) !!!
Besser ist kumulierendes sprintf in einen großeren Speicher-Block, und ab und an ein write, wenn dieser voll ist (die f... Funktionen sind auf die Systemfunktionen open/close/read/write aufgesetzt und z.T. wesentlich langsamer und nicht threadsafe)

7. Parallelisierung mittels MPI einer for schleife deren Durchläufe unabhängig voneinander sind.

Erstmal solltest Du mit dem fprintf aufpassen - das ist (in den meisten Implementierungen) nicht thread-safe. Generell ist häufige Ausgabe auf die Konsole grottenlangsam und da hierzu Systemfunktionen gerufen werden, auch serialisierend. Dann sollte die Anzahl der Threads an der realen Anzahl CPUs angepaßt sein - zuviele Threads bewirken einen Performance-Einbruch!

8. Böse if Abfragen sind die wirklich so langsam und wenn ja wie kann ich die verbessern?

Das ist sehr unspezifisch gefragt... Manchmal kann ein case schneller sein.

[Boron]

8. Böse if Abfragen sind die wirklich so langsam und wenn ja wie kann ich die verbessern?

Das ist sehr unspezifisch gefragt... Manchmal kann ein case schneller sein.

Falls es möglich ist auf die if zu verzichten und durch eine switch/case-Anweisung zu ersetzen, dann kann man sich überlegen ob den einzelnen cases eine "Auswahlwahrscheinlichkeit" zugeordnet werden kann (z.B. case 'x' häufiger als case 'q').
Wenn das so ist, dann empfiehlt es sich die cases in absteigender Wahrscheinlichkeit zu schreiben. Also wahrscheinliche cases oben und unwahrscheinliche cases unten. Jeder mir bekannte Compiler erzeugt nämlich auch den Assemblercode in der Reihenfolge, was zur Folge hat, dass wahrscheinlichere cases schneller gefunden werden.

Aber das ist wirklich nur "Feintuning". Die wahren Flaschenhälse liegen meist an ganz anderer Stelle. Wenn es klemmt würde ich zuerst mit einem Profiler prüfen, wo am meisten Zeit verblasen wird.