spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Grundsätzlich sollte man wissen, dass aktuelle Compiler wesentlich besser optimieren können als Menschen. Das Problem ist nur, dass Compiler sehr, sehr konservativ sind mit dem was sie optimieren. Wenn es auch nur irgendeinen Fall irgendwann geben könnte, der nicht das gleiche macht wie der unoptimierte Code macht er es nicht und da kann man als Mensch dann helfen, indem man das Wissen über den Code, den der Compiler nicht hat benutzt.

Man kann davon ausgehen, dass der Compiler alle diese Tricks und noch viele mehr kennt und wann immer möglich und sinnvoll davon Gebrauch macht...

Zumal heutzutage eine Division genauso lange durch die Prozessorpipeline braucht wie ein Bitschieben. Das Lesen und Zurückschreiben der Operanden, die Abhängigkeiten zu vorherigen und nachfolgenden Rechnungen und vieles mehr sind heutzutage ausschlaggebend für die Performance.

Nehmen wir gleich das konkrete Beispiel von SirP. Wir wollen also eine Zahl mit 320 multiplizieren:


MSVC 10 generiert für das return folgenden Code:



Der Compiler verwendet hier tatsächlich das selbe Prinzip auf dem auch die Lösung von SirP basiert (nämlich der Tatsache dass §x \cdot 320 = x \cdot 256 + x \cdot 64 = x \cdot 2^8 + x \cdot 2^6§). Anstatt aber mit Shifts und Multiplikationen zu rechnen, bedient sich der Compiler über die Instruction lea spezieller Hardware, die eigentlich für die Berechnung von Speicheradressen gedacht ist, in dem Fall aber auch für unsere Multiplikation zweckentfremdet werden kann und dabei schneller ist als eine explizite Addition gefolgt von einem Bitshift. Hätten wir von Hand "optimiert", wäre nun nicht nur der Code sehr viel schlechter lesbar, sondern der Compiler hätte möglicherweise sogar schlechteren Maschinencode erzeugt. Ein moderner Compiler wie MSVC 10 ist allerdings sogar so schlau zu erkennen, dass er (x << 8 ) + (x << 6) in (x + (x << 2)) << 6 umwandeln kann, sodass beide Lösungen hier identischen Maschinencode produzieren...

Zitat von »dot«

während (-2 >> 1) dagegen undefiniert ist.

Mal rein aus Interesse: Wieso undefiniert? Ich habe noch nie Bitshifts für etwas anderes als vorzeichenlose Integer benutzt, aber werden nicht ansich immer einfach nur die Bits geshiftet? Dann würde das Ergebnis einfach nur von der internen Darstellung der Zahl abhängen (besonders deutlich wohl bei floats), aber die ist ja nicht undefiniert sondern einfach nur plattformabhängig.

Also ich würde sagen, dass -2 standardmäßig als signed int interpretiert wird und dementsprechend hexadezimal 0x80000002 wäre (wenn angenommen wird, dass ein Integer aus vier Bytes besteht). Wenn man das shiftet oder einen Wert um diese Zahl verschiebt, ist wohl definiert, was das Ergebnis ist. Floats dagegen kann man nicht shiften (Visual C++ gibt den Fehler aus, dass float kein integraler Datentyp sei). Natürlich könnte man float in einen Integer umwandeln, diesen shiften und wieder zurückumwandeln. Das Ergebnis dürfte durchaus interessant sein

Miieeep! Negative Zahlen werden in allen mir bekannten Prozessorarchitekturen als Zweierkomplement gespeichert. -2 ist 32bit-binär also 0xfffffffe. Und ein Bitshift davon ist je nach Compiler- und Prozessorlaune entweder 0x3fffffff oder 0xffffffff, also 1073741823 oder -1. "Undefiniert" heißt ja nur, dass der C++-Standard es nicht definiert hat. Du kannst Du also nicht darauf verlassen, dass auf allen Plattformen und Compilern das selbe rauskommt.

Mehr oder weniger genau wie Schrompf sagt: Das Ergebnis eines Rechtsshift eines signed Integer von negativem Wert ist laut C++ Standard implementation defined. D.h. es gibt ein wohldefiniertes Ergebnis, wie das aussieht ist aber dem jeweiligen Compiler überlassen. "Undefiniert" war da technisch nicht ganz der korrekte Ausdruck, sorry for that. MSVC z.B. füllt von links mit dem Vorzeichenbit. D.h. (-1 >> n) liefert unter MSVC also -1 für jedes beliebige n...