Wie programmiere ich performant? Literaturtipps?

Gregor

Ich finde, Du solltest TAOCP lesen.

soerenP

Ich kenn nur TAFKAP
Nein, habs gegooglet, ich schaus mir mal an.
Vielen Dank an alle!
Sören

Hi,

versuchs mal mit

Scott Meyers Effektiv C++ programmieren"

Scott Meyers "Mehr Effektiv C++ programmieren"

oder ich sag mal so: Kreative Faulheit. Nichts machen was nicht muß und immer nur das machen was muß und nichts doppelt.
Keine Objekte mit Standardargumenten erstellen und dann ändern, sondern gleich mit aktuellen Argumenten erstellen.
Nur das berechnen, was auch wirklich weiter verwendet wird.
Mit Exceptions sparsam umgehen, nicht als Steuerstrukturen verwenden...
Niedrige Operationen verwenden, also besser Shift als Multiplikation wenn das möglich ist, Addition vor Multiplikation, zur Compilezeit berechenbare Werte auch dort berechnen, tief geschachtelte Felder vermeiden...
Und letztlich gilt immer noch, daß kleinere Programme nicht so viel Code durchschleusen müssen und daher schon von Hause aus eine Chance haben effizienter zu sein. (natürlich bei sonst gleicher Programmqualität.)

Gruß Mümmel

Jester

soerenP schrieb:

Hört sich auf den ersten Blick nicht so allgemein an (Algorithmen), wie ichs gerne hätte, aber ich schau auf jeden Fall mal nach, danke!

Du suchst was allgemeineres als das?

muemmel schrieb:

Niedrige Operationen verwenden, also besser Shift als Multiplikation wenn das möglich ist,

Ein klassisches Beispiel für premature Optimizing... Auf modernen Prozessoren können Multiplikationen sogar schneller sein als bit-shifting.

hustbaer

skals schrieb:

Auf modernen Prozessoren können Multiplikationen sogar schneller sein als bit-shifting.

Achja? Nenne bitte ein Beispiel!

Tyrdal

Egal was von beiden schneller ist, von einem zeitgemäßen Compiler kann man erwarten, daß er vernünftig optimiert. Und die Entscheidung ob Shift oder Multiplikation schneller ist, dürfte eine der einfachsten sein.

rapso

hustbaer schrieb:

skals schrieb:

Auf modernen Prozessoren können Multiplikationen sogar schneller sein als bit-shifting.

Achja? Nenne bitte ein Beispiel!

jede cpu mit SSE.

Vielleicht suchst du sowas:
Efficient C++ | ISBN: 0201379503

rapso schrieb:

Kilo Byte = 1000, 1 Kilobyte = 1024, da Eigenbegriff

falsch, 1 kilobyte = 1000 bytes. 1024 bytes = 1 kibibyte.

Du solltest besonders auf minmalen Speicherverbrauch achten! Speicherzugriffe sind im Vergleich zu der Rechengeschwindigkeit moderne CPUs teuer!

muemmel schrieb:

Und letztlich gilt immer noch, daß kleinere Programme nicht so viel Code durchschleusen müssen und daher schon von Hause aus eine Chance haben effizienter zu sein. (natürlich bei sonst gleicher Programmqualität.)

Nicht wirklich.

hustbaer

rapso schrieb:

hustbaer schrieb:

skals schrieb:

Auf modernen Prozessoren können Multiplikationen sogar schneller sein als bit-shifting.

Achja? Nenne bitte ein Beispiel!

jede cpu mit SSE.

Hihi, ok, wenn was parallel geht dann stimmt das
Die muss man halt im Moment selbst mit intrinsics/inline asm schreiben da es noch keinen wirklich guten SSE Vectorizer gibt (oder bin ich nur nichtmehr am Laufenden?).

-----

z.T. Programmgrösse: es kommt eigentlich nur drauf an wie gross der oft durchlaufene Code im Vergleich zum Cache ist. Wenn ein Programm komplett in den Cache passt, ein anderes (welches das gleiche tut) dagegen nicht, dann macht das schon meist einen Unterschied.

Wenn beide komplett in den L1 Cache passen ist es natürlich egal.

Das kommt drauf an. Der Algorithmus ist entscheidender.

Besser nen Quicksort der nicht in den L1 Cache passt als ein Bubbe sort der reinpasst.

thordk

bevor man performant programmiert, sollte man lernen, effizient zu programmieren. das erste ziel sollte immer ein solider entwurf sein. fragen die man dabei bewegen sollte sind:
- was genau ist das problem
- lässt sich das problem durch ein standard pattern abbilden (ist in 95% der fälle wahr)
- welche teilaufgaben gibt es und welche algorithmen werden benötigt

wenn man das alles weiss, hat man schon die halbe miete. optimierung von performanz ist dann eine detailaufgabe.
zur frage effizienz ist das buch "der pragmatische programmierer" relativ empfehlenswert.

hustbaer

MisterX schrieb:

Das kommt drauf an. Der Algorithmus ist entscheidender.

Besser nen Quicksort der nicht in den L1 Cache passt als ein Bubbe sort der reinpasst.

Richtig. Ich bin davon ausgegangen dass beide Programme die gleichen Algorithmen verwenden, obwohl das aus meinem Posting nicht klar hervorgeht wie ich jetzt sehe.

Und man könnte das wahrscheinlich noch unendlich lange fortsetzen mit anderen Dingen (Quicksort ist z.B. nicht optimal für jeden Input was Grösse angeht oder ob die Elemente schon grossteils "vorsortiert" sind uswusf).

Ich wollte eigentlich nur feststellen dass Codegrösse sehr wohl einen Einfluss haben kann. Wie gross der ist und ob nicht andere Faktoren überwiegen ist wieder eine andere Sache, am Besten man probiert es einfach aus.

Genauso (was aber schon erwähnt wurde) kann es einen Unterschied machen wieviel Byte/KB/MB an Daten man angreifen muss, und in welcher Reihenfolge man die Zugriffe macht.

hustbaer schrieb:

Ich wollte eigentlich nur feststellen dass Codegrösse sehr wohl einen Einfluss haben kann. Wie gross der ist und ob nicht andere Faktoren überwiegen ist wieder eine andere Sache, am Besten man probiert es einfach aus.

Es ist aber wohl eines der unwichtigsten Dinge wenn es um Performance geht. Bevor man krampfhaft versuch kleinen Code zu schreiben gibt es 1000 andere Dinge die wichtiger sind. Das ist einfach das Problem bei solchen Threads, dass hier immer wieder solche "tollen Tricks" aufgezählt werden und einige Leute dann versuchen so ihren Code schnell zu bekommen, anstatt die passenden Algorithmen und Datenstrukturen zu verwenden.

rapso

hustbaer schrieb:

rapso schrieb:

hustbaer schrieb:

skals schrieb:

Auf modernen Prozessoren können Multiplikationen sogar schneller sein als bit-shifting.

Achja? Nenne bitte ein Beispiel!

jede cpu mit SSE.

Hihi, ok, wenn was parallel geht dann stimmt das
Die muss man halt im Moment selbst mit intrinsics/inline asm schreiben da es noch keinen wirklich guten SSE Vectorizer gibt (oder bin ich nur nichtmehr am Laufenden?).

wenn man den code fuer den compiler freundlich schreibt, dann kann er das mitlerweile zu nem gewissen grad vektorisieren. besonders bei speicherverschiebung laeuft das recht gut, ob das auf mul zutrifft kann ich jedoch nicht sagen. jedoch bezog sich meine antwort rein darauf, dass bit-shift in SSE immer noch nicht geht

rapso

Byty schrieb:

rapso schrieb:

Kilo Byte = 1000, 1 Kilobyte = 1024, da Eigenbegriff

falsch, 1 kilobyte = 1000 bytes. 1024 bytes = 1 kibibyte.

als das kilobyte erfunden wurde vor jahrzehnten, gab es sicher kein kiwibyte.

rapso

och nö schrieb:

hustbaer schrieb:

Ich wollte eigentlich nur feststellen dass Codegrösse sehr wohl einen Einfluss haben kann. Wie gross der ist und ob nicht andere Faktoren überwiegen ist wieder eine andere Sache, am Besten man probiert es einfach aus.

Es ist aber wohl eines der unwichtigsten Dinge wenn es um Performance geht. Bevor man krampfhaft versuch kleinen Code zu schreiben gibt es 1000 andere Dinge die wichtiger sind. Das ist einfach das Problem bei solchen Threads, dass hier immer wieder solche "tollen Tricks" aufgezählt werden und einige Leute dann versuchen so ihren Code schnell zu bekommen, anstatt die passenden Algorithmen und Datenstrukturen zu verwenden.

da stimm ich zu. die ganzen tips sind oft kontraproduktiv, da sie stumpf befolgt werden. wenn man schnellen code schreiben moechte, muss man nachdenken und keine stumpfen abfolgen abarbeiten, denn was in einem fall gut ist, kann im anderen kontraproduktiv sein.
Das beste ist, einen Profiler laufen zu lassen und rauszufinden wie es geht.