[C++] right-shift vs division

[Krishty]

Ich bin ein Bisschen übermüdet und stehe auf dem Schlauch. Bisher habe ich 17 Bits von einer Variable weggeschmissen:

  (a * b + 65536) >> 17

Weil a * b möglicherweise negativ wird ist das Verhalten implementation-defined. Ich hätte an der Stelle gern garantiert arithmetisches Schubsen, darum habe ich es ersetzt durch:

  (a * b + 65536) / 131072

Und jetzt hat alles zu funktionieren aufgehört. Öh was mache ich falsch?

Edit: Okay; das Runden durch +2^16 ist schonmal falsch für negative Zahlen. Aber weiter: Wo ist der Unterschied?

[Krishty]

Aaaah; jetzt komme ich langsam dahinter:

  x = a * b;
  (x + 65536) >> 17 // richtig
  (x + (x > 0 ? 65536 : -65536)) >> 17 // falsch
  (x + (x > 0 ? 65536 : -65536)) / 131072 // richtig

[Krishty]

Ach du mächtiger Ochsenhoden … ich sehe gerade, dass in C die Division negativer Zahlen implementation-defined ist.

Bei

  x = -5 / 2;

kann entweder -2 oder -3 rauskommen; je nachdem, ob

  x = -5 % 2

nun -1 oder 1 ergibt. Dementsprechend rundet mein / 131072 auch entweder auf oder ab; je nach Compiler. Arithmetik gibt mir hier also null Vorteile gegenüber Shift. Fuck fuck fuck

Bleibt jetzt nur ein

  #if __clang__
  #elif _MSVC_VER
  #elif …

?

[Krishty]

Okayokay. Der Compiler muss beim Optimieren die as-if-Regel beachten. Das bedeutet, ich kann den Quelltext folgendermaßen aufbauen:

  if(-1 / 2 == 0) { // Implementierung rundet auf
    if(x < 0) {
      result = (x - 65536) / 131072;
    } else {
      result = (x + 65536) / 131072;
    }
  } else { // -1: Implementierung rundet ab
    result = (x + 65536) / 131072;
  }

Dann ist Compiler / Zielarchitektur egal, sofern richtig optimiert wird.

So … jetzt funktioniert es zwar, aber es ist saulangsam, weil Visual C++ sich für

  if(x < 0) {
    result = (x - 65536) / 131072;
  } else {
    result = (x + 65536) / 131072;
  }

entschieden hat. Statt einer Addition und einem Shift habe ich jetzt eine Verzweigung. JA DA FICKEN JA DIE DUMMEN HÜHNER SCHLAUER

[Spiele Programmierer]

Scheinbar implementiert nahezu jeder Compiler einen vorzeichenbehafteten Shift als arithmetischen Shift, wie ich auf Stackoverflow entnehmen konnte.
Um ganz sicher zu sein, könnte man doch auch soetwas machen?
static_assert((-2 >> 1) == -1, "Arithmetic shift does not work");

Dann strapaziert man nicht den Optimierer.
Außerdem ist höchst wahrscheinlich folgender Ausdruck schneller, der ohne Sprünge oder Conditional Move arbeitet... (Int kann natürlich durch Architekturunabhänige oder sonstige Typen ersetzt werden.)

Code: Alles auswählen

int result = a * b;
result += (((int)(result & INT_MIN)) >> (sizeof(result) * CHAR_BIT - 18)) | 65536; //x >= 0 ? 65536 : -65536
result  >>= 17;

Das sollte im kompletten Werteraum auf das gleiche Ergebnis kommen.

Allerdings solltest du beachten, dass die Shift-Optimierung nicht identisch mit der Division ist.
Beispiel: -65536 >> 17 == -1 aber -65536 / 131072 == 0
Wenn das eine Rolle spielt müsste der letzte Shift auf jeden Fall eine Division sein, der allerdings leicht weniger effizient wäre.

[Krishty]

Das Theater x >= 0 ? 65536 : -65536 ist aber sinnlos weil der arithmetische Shift im Fall von negativen Zahlen sowieso gegen -INF rundet. Wenn ich einen arithmetischen Shift (und Zweierkomplement) garantieren kann, ist

  result = a * b + 65536 >> 17;

sowohl die richtige als auch die schnellste Lösung. Existiert jedoch kein arithmetischer Shift, muss ich auf das if-Konstrukt oben ausweichen und prüfen, ob die Division auf- oder abrundet, und falls sie aufrundet, den ? 65536 : -65536-Tanz aufführen.

Ich würde das gern via Präprozessor auflösen (#if -3 >> 1 == -2), aber als ich es zuletzt kontrolliert habe, hat C++ nicht garantiert, dass der Präprozessor dieselbe Arithmetik benutzt wie die Zielplattform. Hat sich das mit C++11 geändert?

[BeRsErKeR]

Kannst du nicht einfach den Absolutwert runden/shiften und im Anschluss wahlweise das Minus wieder hinzufügen? Dann hast du in jedem Fall definiertes Verhalten unabhängig vom Compiler.

[Krishty]

abs(): 3 Anweisungen
Prüfen / Speichern des Vorzeichens: 2 Anweisungen + 1 Register
Minus wieder anfügen: 3 Anweisungen

Acht Anweisungen auf zwei Registern statt zwei Anweisungen auf einem Register? Für etwas, das x86 quasi eingebaut mitbringt? Nur über meine Leiche!

Also ist meine Sorge jetzt:

Ich würde das gern via Präprozessor auflösen (#if -3 >> 1 == -2), aber als ich es zuletzt kontrolliert habe, hat C++ nicht garantiert, dass der Präprozessor dieselbe Arithmetik benutzt wie die Zielplattform. Hat sich das mit C++11 geändert?

[Sternmull]

Das sollte aber als Argument für eine Template-Spezialisierung verwendbar sein. Ich denke mal das dort garantiert ist das das Verhalten von Compilezeit und Laufzeit identisch ist.

[Krishty]

Wieder drei Mal so viele Zeilen wie ein if oder #if …

[Spiele Programmierer]

Was spricht gegen das "static_assert"?
Wieviele Zeilen ist doch eigentlich relativ egal.
Dein "if" braucht auf jeden Fall mehr Zeilen und wenn es darum ginge Zeilen zu sparen, könnte man es so oder so in eine Zeile schreiben oder noch drastisch verkürzen.

[Krishty]

Dass ein static_assert nicht verzweigt und ich, sobald es fehlschlängt, erstmal wieder herausfinden muss, warum zur Hölle dieser Code nicht funktionieren soll. Aber ja – ich kann es benutzen um den Präprozessor zu verifizieren. Und Templates … neee danke.

Code: Alles auswählen

SignedInt8B roundedFixedPoint(
  SignedInt8B const   number,
  UnsignedInt1B const numberOfFractionBits
) {
  // TODO: Assumes the preprocessor uses the same arithmetic as the implementation. Is this guaranteed?
# if -3 >> 1 == -2 // Arithmetic shift rounding down?
    return (number + (SignedInt8B(1) << numberOfFractionBits) / 2) >> numberOfFractionBits;
# else // Logical shift; need to use division?
    auto const divisor = SignedInt8B(1) << numberOfFractionBits;
#   if -3 / 2 == -2 // Division rounds down?
      return (number + divisor / 2) / divisor;
#   else // Division rounds up?
      if(number < 0) {
        return (number - divisor / 2) / divisor;
      } else {
        return (number + divisor / 2) / divisor;
      }
#   endif
# endif
}

[Spiele Programmierer]

Es wird auf allen Compilern funktionieren.
Außer du hast etwas extrem ganz Exotisches vor(und das fällt eigentlich aus, so wie du programmierst). Und selbst theoretisch gibt es, um nicht erst irgendetwas herausfinden zu müssen, eine Aussagekräftige Fehlermeldung.

[Krishty]

Ja gut; vielleicht übertreibe ich es wirklich. Also weg mit allen Verzweigungen! Vielen Dank :)

[BeRsErKeR]

abs(): 3 Anweisungen
Prüfen / Speichern des Vorzeichens: 2 Anweisungen + 1 Register
Minus wieder anfügen: 3 Anweisungen

Acht Anweisungen auf zwei Registern statt zwei Anweisungen auf einem Register? Für etwas, das x86 quasi eingebaut mitbringt? Nur über meine Leiche!

Seit wann braucht man für Integer-Absolutwerte mehr als 1 Anweisung? Das ist doch eine simple Verundung mit einer Konstanten oder hab ich was verpasst?

Naja wenns dir um Geschwindigkeit geht, dann solltest du einen anderen Weg gehen. Ich dachte dein Sorge wäre die Unsicherheit, dass das kompatibel ist.

[Krishty]

Seit wann braucht man für Integer-Absolutwerte mehr als 1 Anweisung? Das ist doch eine simple Verundung mit einer Konstanten oder hab ich was verpasst?

Ja; das Zweierkomplement ;) Siehe Bit Twiddling Hacks – Compute the integer absolute value (abs) without branching.

Für Gleitkommazahlen wäre es eine Verundung; aber wegen globalem Speicherzugriff wäre die auch nicht mehr simpel.

[BeRsErKeR]

Jaja der gute alte Brainfart. :D Ich bin das mittlerweile gewöhnt mit dem Bit, weil ich in letzter Zeit viel mit Komprimierung rumgespielt habe und dort exzessiv das MSB missbraucht habe und fürs Delta-Encoding die Werte so kodiere, dass sie bis auf das Vorzeichenbit gleich kodiert werden.