einen Algorithmus beschleunigen

Hallo Forum!
Mich interessiert, ob ihr irgendwelche Tricks kennt um einen Algorithmus zu beschleunigen.
Der Algorithmus arbeitet mit einer binären Matrix (Die Elemente sind nur Bits). Diese verwaltet der Algorithus blockweise im Speicher. Jeder Speicherblock ist vom Typ Int, hat also z.b. 4 Bytes reserviert. In jedem Bit dieser Bytes befindet sich auch ein Bit der Matrix, das heißt der Speicherplatz ist in diesem Sinne optimal ausgenutzt. Zusätzlich verwendet der Algorithmus deutlich viele shift Operationen. Ich habe gelesen, dass diese zu den airthmetischen gehören und dementsprechend langsamer als logische Operationen sind. Jedoch sind auch viele AND, OR oder XOR verknüpfungen zu finden.
Eine speicherung der Matrix in einer Datenbank würde wohl keine Vorteile bringen, also bleibt nur der Hauptspeicher als Speicherort.
Kennt ihr denn irgendwelche Methoden mit denen man erheblich schnelleren Code in C erzeugen kann?
Zum Beispiel statt:

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

lieber:

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

In dem Fall denke ich , dass der 2. Algorithmus etwas schneller ist.
Ich bitte euch um alles hilfreiche was euch dazu einfällt!

Mr. N

1. Arithmetische Operationen sind nicht im Allgemeinen langsamer als logische, Addition, Subtraktion, Shiften, Bit-Und und Bit-Oder sollten so ziemlich die schnellsten Operationen auf der CPU sein (weniger als ein Takt).
2. x&1 ist nur schneller als x%2, wenn du den Optimierer nicht an hast. Grundsätzlich ist Division/Restbildung natürlich wesentlich langsamer als Bit-Und, aber in dem Fall erkennt er (der Compiler/Optimierer) beides als gleichwertig an.

Ansonsten wäre es vielleicht interessant zu wissen, was du überhaupt willst.

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