einen Algorithmus beschleunigen

Stimmt, den Optimizer habe ich jetzt ganz außer Acht gelassen.
Dann wäre es für mich wichtig zu wissen inwieweit man einen Algorithmus von der Programmierweise mit Operationen trotz Optimizer beschleunigen kann. Wo kann ich herausfinden welche Operationen wie genau schnell sind?

Undertaker

Mr. N schrieb:

...die schnellsten Operationen auf der CPU sein (weniger als ein Takt).

was verstehst du unter 'takt'?
oder sollte das ein taktloser scherz sein?

Mr. N

Undertaker schrieb:

Mr. N schrieb:

...die schnellsten Operationen auf der CPU sein (weniger als ein Takt).

was verstehst du unter 'takt'?
oder sollte das ein taktloser scherz sein?

Das war so ein Begriff aus dem AMD Manual, das ich vor ein paar Jahren gelesen habe. Bei ner 2 GHz CPU wäre ein Takt wohl 0,5 Nanosekunden lang. Mit "weniger als ein Takt" meine ich, dass die Instruktion zwar einen Takt benötigt, die CPU aber üblicherweise mehrere solche Instruktionen gleichzeitig ausführt, wenn eben noch genug ALUs etc. übrig sind.

Undertaker

Mr. N schrieb:

Mit "weniger als ein Takt" meine ich, dass die Instruktion zwar einen Takt benötigt, die CPU aber üblicherweise mehrere solche Instruktionen gleichzeitig ausführt, wenn eben noch genug ALUs etc. übrig sind.

ach so, aber damit das wirkung zeigt muss man wohl den code entsprechend gestalten, damit die CPU das gut parallelisieren kann.
@OP: guck dir den asm-code an, den der compiler ausspuckt. eventuell kannst du's von hand besser machen. bei guten compilern ist die chance aber nicht besonders hoch.

Undertaker schrieb:

ach so, aber damit das wirkung zeigt muss man wohl den code entsprechend gestalten, damit die CPU das gut parallelisieren kann.
@OP: guck dir den asm-code an, den der compiler ausspuckt. eventuell kannst du's von hand besser machen. bei guten compilern ist die chance aber nicht besonders hoch.

Wie meinst du das "entsprechend gestalten"? Das könnte also zu einer Beschleunigung beitragen?
Leider habe ich keinen guten Compiler, der mir ASM Code ausspuckt. Gibt es da einen kostenlosen im internet der das kann?

Blubberblase schrieb:

Leider habe ich keinen guten Compiler, der mir ASM Code ausspuckt.

Ich dachte immer C wird zuerst in Assembler umgewandelt. Du weißt wahrscheinlich bloß nicht wie mans einstellt

Gibt es da einen kostenlosen im internet der das kann?

Visual Studio

Ja, ich weiß nicht genau wie man das einstellt... Ich lade mit mal diesen Compiler runter!

BorisDieKlinge

vll. statt "i++" prefix "++i" verwenden!

BorisDieKlinge schrieb:

vll. statt "i++" prefix "++i" verwenden!

Total sinnlos bei int

Undertaker

Blubberblase schrieb:

Undertaker schrieb:

ach so, aber damit das wirkung zeigt muss man wohl den code entsprechend gestalten, damit die CPU das gut parallelisieren kann.
@OP: guck dir den asm-code an, den der compiler ausspuckt. eventuell kannst du's von hand besser machen. bei guten compilern ist die chance aber nicht besonders hoch.

Wie meinst du das "entsprechend gestalten"? Das könnte also zu einer Beschleunigung beitragen?

naja, irgendwelche abhängigkeiten beseitigen, schleife weg, cout rausschmeissen, z.b. statt:

for(int i = 0; i < 8; i++) 
{
   if((byte >> i) & 1) 
     cout << "Bit gefunden";
}

sowas:

if(byte & 0x80) 
   bit[7] = 1;
if(byte & 0x40) 
   bit[6] = 1;
if(byte & 0x20) 
   bit[5] = 1;
...
...

und danach das bit[] array in einem rutsch ausgeben.
das ist vielleicht verträglicher für 'nen instruction cache und mehrere ALUs

Blue-Tiger

hmm.... bist du sicher, dass du den Algorithmus selber nicht noch optimieren kannst? Damit holst du in der Regel wesentlich mehr raus als mit low-level-Optimierungen!

hustbaer

Was ist wie langsam...?

Schnell:
* Addition, Subtraktion, And, Or, Xor, Not, Shift, Rotate, Compare

Langsam:
* Multiplikation, Sprünge

Langsamer:
* Division, Modulo, "falsch geratene" Sprünge

Für float/double gilt im Prinzip dasselbe. Ob float/double oder integer schneller ist kommt auf die Hardware an, im PC Bereich ist AFAIK meist integer schneller.

Ganz ganz langsam:
* sin, cos, log, exp, sqrt, ...

Grundsätzlich sollte man allerdings erstmal gucken ob man überhaupt einen optimalen Algorithmus verwendet, also ob es nicht etwas gäbe was eine geringere Komplexität hat (z.B. O(n log n) statt O(n²)).

Ein weiterer wichtiger Punkt ist dann noch dass man "Cache Aware" programmiert -- Cache Misses sind halt nicht gerade "billig".

Vielen Dank für die vielen guten Antworten!
Das hilft mir schon viel mehr weiter.
Ich habe neulich bemerkt, dass im Algorithmus erst eine Konstante Variable definiert wird:
const VAR;
und später wird oft die Variable in folgendem Zusammenhang verwendet:
(VAR - 1)
Ist es in diesem Fall besser eine neue Konstante (VAR -1 ) einzurichten statt immer eine Operation mit dieser Constanten zu machen, oder kriegt das der Optimizer selbst mit und richtet sich selbst soetwas ein, statt jedes mal -1 zu rechnen?

hustbaer

Blubberblase schrieb:

...

Ist es in diesem Fall besser eine neue Konstante (VAR -1 ) einzurichten statt immer eine Operation mit dieser Constanten zu machen, oder kriegt das der Optimizer selbst mit und richtet sich selbst soetwas ein, statt jedes mal -1 zu rechnen?

Das bekommt jeder mir bekannte Optimizer hin (solange VAR kein Klassentyp mit überladenem Operator "-" ist).