Optimieren von Multiplikation mit Potenz von 2 ?

[Dirty Oerti]

Tag!

Mal eine kurze, schnelle Frage:

Macht es einen Unterschied, ob man

Code: Alles auswählen

count*=32

oder

Code: Alles auswählen

count<<=5

schreibt?

Ergebnis ist ja beidesmal das selbe.

Nur habe ich gelesen, letztere Methode soll schneller sein.
Stimmt das?

MfG
Daniel

[fat-lobyte]

Tag!

Mal eine kurze, schnelle Frage:

Macht es einen Unterschied, ob man

Code: Alles auswählen

count*=32

oder

Code: Alles auswählen

count<<=5

schreibt?

Ergebnis ist ja beidesmal das selbe.

Nur habe ich gelesen, letztere Methode soll schneller sein.
Stimmt das?

MfG
Daniel

Ja, das ist richtig. Bei der Multiplikation mit 2 werden im Binärsystem nämlich nur ein paar Nullen angehängt - genau das, was bei dem Left Shift passiert.
Die multiplikation ( operator *=() ) ist aber allgemein und braucht mehr anweisungen als ein einfacher left shift.

[Dirty Oerti]

Ja, das ist richtig. Bei der Multiplikation mit 2 werden im Binärsystem nämlich nur ein paar Nullen angehängt - genau das, was bei dem Left Shift passiert.
Die multiplikation ( operator *=() ) ist aber allgemein und braucht mehr anweisungen als ein einfacher left shift.

Danke schön
Damit hätte sich meine Frage schon geklärt.

MfG
Daniel

[Xin]

Macht es einen Unterschied, ob man

Code: Alles auswählen

count*=32

oder

Code: Alles auswählen

count<<=5

schreibt?

Bei einem guten Compiler: nein.
Bei einem ungeübten Programmierer: ja.

Hier wäre ein Konstrukt wie

Code: Alles auswählen

count <<= x;

eher interessant.

Nur habe ich gelesen, letztere Methode soll schneller sein.
Stimmt das?

Bei einem modernen Prozessor: nein.
Bei einem alten Prozessor: ja.

[Dirty Oerti]

Bei einem guten Compiler: nein.
Bei einem ungeübten Programmierer: ja.

Hier wäre ein Konstrukt wie

Code: Alles auswählen

count <<= x;

eher interessant.

Hm...ein guter Compiler sagst du.
Ich verwende den gcc, allerdings ohne jegliche Optimierungsflags.
Wie sieht es dann aus?

Wie meinst du das? Wäre eher interessant?
Ich benötige keine Variable. Die Zahl ist konstant und nicht abhängig, sie ist 32.
Oder wie ist das zu verstehen?

Nur habe ich gelesen, letztere Methode soll schneller sein.
Stimmt das?

Bei einem modernen Prozessor: nein.
Bei einem alten Prozessor: ja.

Hängt das vom Prozessor ab, oder von der "Optimierungsstufe", mit der man compiliert?
Mit schneller meine ich keine Sekunden schneller.
Ich denke da eher in Zeitabschnitten wie "Anweisungen" oder "Takte".

[Xin]

Hm...ein guter Compiler sagst du.

"The Greenhills compiler may have optimized this benchmark to nothing."

Ich verwende den gcc, allerdings ohne jegliche Optimierungsflags.
Wie sieht es dann aus?

"The '#pragma' command is specified in the ANSI standard to have an arbitrary implementation-defined effect. In the GNU C preprocessor, '#pragma' first attempts to run the game 'rogue'; if that fails, it tries to run the game 'hack'; if that fails, it tries to run GNU Emacs displaying the Towers of Hanoi; if that fails, it reports a fatal error. In any case, preprocessing does not continue." (Richard M. Stallman, The GNU C Preprocessor, Version 1.34).

Beantwortet das Deine Frage?

Wie meinst du das? Wäre eher interessant?
Ich benötige keine Variable. Die Zahl ist konstant und nicht abhängig, sie ist 32.

Dann mach die Bitschieberei und behaupte wie ich, dass die meisten Leute, die das nicht lesen können, auch nicht programmieren können.

Nur habe ich gelesen, letztere Methode soll schneller sein.
Stimmt das?

Bei einem modernen Prozessor: nein.
Bei einem alten Prozessor: ja.

Hängt das vom Prozessor ab, oder von der "Optimierungsstufe", mit der man compiliert?

In dem Fall vom Prozessor. Moderne CPUs sind nicht nur schneller getaktet, sie leisten auch viel mehr pro Takt als alte CPUs.

Mit schneller meine ich keine Sekunden schneller.
Ich denke da eher in Zeitabschnitten wie "Anweisungen" oder "Takte".

Eine Multiplikation auf einem 68k Prozessor waren afair 9 Takte, wohingegen das Bitschieben in ein bis 2 Takten erledigt ist.
Ein P4 schafft das afair bereits in 1 Takt. Hier ist Bitschieben also nicht schneller. Ggfs. kann die Bitschieberei aber leichter mit der nachfolgenden Anweisung parallelisiert werden. Dann wäre sie wieder schneller.

[Dirty Oerti]

Beantwortet das Deine Frage?

Fast wie der Nürnberger Bahnhof

Eine Multiplikation auf einem 68k Prozessor waren afair 9 Takte, wohingegen das Bitschieben in ein bis 2 Takten erledigt ist.
Ein P4 schafft das afair bereits in 1 Takt. Hier ist Bitschieben also nicht schneller. Ggfs. kann die Bitschieberei aber leichter mit der nachfolgenden Anweisung parallelisiert werden. Dann wäre sie wieder schneller.

Hm...mein Problem ist, dass ich das schwer einschätzen kann.
Es geht aber um zeitkritische Funktionen...

Code: Alles auswählen

// (...)
    countb<<=5;
    countb+=countc;
    counta*=KONSTANTE;
    counta+=countb;
    return counta;
}

Sonst noch was optimierbar?

[Xin]

Eine Multiplikation auf einem 68k Prozessor waren afair 9 Takte, wohingegen das Bitschieben in ein bis 2 Takten erledigt ist.
Ein P4 schafft das afair bereits in 1 Takt. Hier ist Bitschieben also nicht schneller. Ggfs. kann die Bitschieberei aber leichter mit der nachfolgenden Anweisung parallelisiert werden. Dann wäre sie wieder schneller.

Hm...mein Problem ist, dass ich das schwer einschätzen kann.
Es geht aber um zeitkritische Funktionen...

Dann shifte definitiv.

Code: Alles auswählen

// (...)
    countb<<=5;
    countb+=countc;
    counta*=KONSTANTE;
    counta+=countb;
    return counta;
}

Sonst noch was optimierbar?

Sieht gut aus. Warum <<5?

[Dirty Oerti]

Dann shifte definitiv.

Ok. Mal sehen, ob ich im Code noch weitere solche Punkte finde.

Code: Alles auswählen

// (...)
    countb<<=5;
    countb+=countc;
    counta*=KONSTANTE;
    counta+=countb;
    return counta;
}

Sonst noch was optimierbar?

Sieht gut aus. Warum <<5?

Wie "Warum <<5?" ? *Die Frage irgendwie nicht verstehe*

<<5 bewirkt eine Linksverschiebung um 5 Bit.
Das entspricht einer Multiplikation mit 2 hoch 5.
2 hoch 5 wiederrum entspricht 32.

Oder wie?

[Xin]

Warum <<5?

Wie "Warum <<5?" ? *Die Frage irgendwie nicht verstehe*

<<5 bewirkt eine Linksverschiebung um 5 Bit.
Das entspricht einer Multiplikation mit 2 hoch 5.
2 hoch 5 wiederrum entspricht 32.

Oder wie?

Alles richtig - aber warum musst Du mit 32 multiplizieren, was hat das für einen Sinn?