Forum: PC-Programmierung C schneller machen


von Sebastian (Gast)


Lesenswert?

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

von Nachdenklicher .. (dms)


Lesenswert?

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
}

von Mighty (Gast)


Lesenswert?

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

von Thomas B. (yahp) Benutzerseite


Lesenswert?

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

von Johnny (Gast)


Lesenswert?

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

von Bartli (Gast)


Lesenswert?

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

von Karl heinz B. (kbucheg)


Lesenswert?

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

von Bartli (Gast)


Lesenswert?

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

von Mighty (Gast)


Lesenswert?

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

von Μαtthias W. (matthias) Benutzerseite


Lesenswert?

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

von Nis (Gast)


Lesenswert?

Was willste denn dann nehmen?

von Bartli (Gast)


Lesenswert?

Binäre Suche (wenn das Dingens sortiert ist...)

von Bartli (Gast)


Lesenswert?

...äääh...reden wir von ner Linked List ? Naja, auch egal.

von Mighty (Gast)


Lesenswert?

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

von Karl heinz B. (kbucheg)


Lesenswert?

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

von Mighty (Gast)


Lesenswert?

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

von Karl heinz B. (kbucheg)


Lesenswert?

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

von Mighty (Gast)


Lesenswert?

> 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);

von Karl heinz B. (kbucheg)


Lesenswert?

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

von Sebastian (Gast)


Lesenswert?

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

von Mighty (Gast)


Lesenswert?

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

von Stefan (Gast)


Lesenswert?

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 ;-)

von Karl heinz B. (kbucheg)


Lesenswert?

> 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
Noch kein Account? Hier anmelden.