3. Signum-Funktionen effizient implementieren

Signum-Funktionen effizient implementieren

  • ?

    Ich möchte die Signum-Funktion
    \operatorname{sgn}(x) := \begin{cases} -1 & \text{if } x < 0, \\ 0 & \text{if } x = 0, \\ 1 & \text{if } x > 0. \end{cases}
    in C++ möglichst effizient implementieren.

    Ich habe einmal folgende Implementierungen geschrieben:

    #include <cassert>
#include <algorithm>

int signumA(int x) {
  if (x > 0)
     return 1;
  if (x < 0)
     return -1;
  if (x == 0)
     return 0;
  assert(false);
}
int signumB(int x) {
  return (x>0) - (x<0);
}
int signumC(int x) {
  return std::min(std::max(-1, x), 1);
}
int signumD(int x) {
  int y = 0;
  if (x > 0) y = 1;
  if (x < 0) y = -1;
  return y;
}
int signumE(int x) {
  return x ? x/std::abs(x) : 0;
}

    Lustigerweise gibt der Compiler für jede dieser äquivalenten Funktionen einen anderen Assemblercode aus.

    Welche Implementierung ist jetzt die schnellste?

    0
  • Mod

    sugnitar schrieb:

    Welche Implementierung ist jetzt die schnellste?

    Miss es!

    Meine Vermutung (ohne zu schummeln!) wäre B > A = D > C > E.

    0
  • ?

    assert?
    Mit eingeschaltetem Optimizer?

    Klar: messen!

    0
  • F

    Wenn du ziemlich viele Signums am Stück berechnen willst und nicht nur vereinzelte brauchst,
    könnte es sich auch lohnen die Dinger gleich im 4er-Pack zu berechnen (benötigt allerdings CPU mit SSSE3):

    #include <cstdint>
#include <iostream>
#include <emmintrin.h>
#include <tmmintrin.h>

inline void signum4(std::int32_t (&result)[4], const std::int32_t (&values)[4])
{
	_mm_store_si128(
		reinterpret_cast<__m128i*>(&result),
		_mm_sign_epi32(_mm_set1_epi32(1), _mm_load_si128(reinterpret_cast<const __m128i*>(&values))));
}

int main()
{
	alignas(alignof(__m128i)) std::int32_t values[4] = { -123, 0, 321, 1 };
	alignas(alignof(__m128i)) std::int32_t result[4];

	signum4(result, values);

	for (auto v : result)
		std::cout << v << std::endl;
}

    siehe: _mm_sign_epi32

    Und auch hier gilt: messen!

    Finnegan

    0

  • Die reinterpret_cast in deinem Code sind falsch. Strict Aliasing und so.

    0
  • F

    hustbaer schrieb:

    Die reinterpret_cast in deinem Code sind falsch. Strict Aliasing und so.

    Prinzipiell ja, aber die Datentypen für SIMD-Intrinsics sind in gängigen Compilern im Allgemeinen speziell für solche Operationen ausgelegt,
    da es ansonsten ziemlich umständlich wäre, die Daten standardkonform und ohne Kopie in den richtigen Typen zu bekommen
    (__m128i repräsentiert ja unter der Haube ein 128-Bit-Register).

    Aus der GCC-Implementierung:

    typedef long long __m128i __attribute__ ((__vector_size__ (16), __may_alias__));

    Andere Compiler berücksichtigen diese Typen entsprechend auf ihre Weise. Hier darf man - auch wenn es richtig ist, dass erstmal die Alarmglocken losgehen -
    ruhig etwas liberaler reinterpretieren und den Code somit lesbar halten.

    Gruss,
    Finnegan

    P.S.: Erhellende SO-Antwort zu diesem Thema: http://stackoverflow.com/questions/24787268/how-to-implement-mm-storeu-epi64-without-aliasing-problems/24788226#24788226
    P.P.S: GCC und Clang schlucken obigen Code übrigens mit -Wall ohne murren.

    0

  • Finde die Argumente nicht überzeugend.

    0
  • ?

    Ist das assert in signumA überhaupt erreichbar?

    0
  • Mod

    foonil schrieb:

    Ist das assert in signumA überhaupt erreichbar?

    Derzeit nicht. Aber wenn irgendwann ein Template draus gemacht wird, das dann mit Fließkommazahlen instanziert wird, schon. Dazu ist ein assert dann durchaus gut, weil es darauf aufmerksam macht, dass da etwas gemacht wurde, das so nicht vorgesehen war.

    0

  • Nur zur Sicherheit nachgefragt: das kann bei Fliesskommazahlen auch nur bei NaNs passieren, oder?

    0
  • Mod

    hustbaer schrieb:

    Nur zur Sicherheit nachgefragt: das kann bei Fliesskommazahlen auch nur bei NaNs passieren, oder?

    So ist es. +/- 0, an die du jetzt wahrscheinlich denkst, sind beide gleich 0 (egal welche 0 gemeint ist) und +/- Unendlich ist größer bzw. kleiner 0. Vorausgesetzt natürlich eine der üblichen Fließkommaimplementierungen, vorgeschrieben sind diese Dinge nicht.

    0

  • Ja, so hab' ich mir das auch gedacht. Wäre komisch wenns anders wäre. Wollte nur zur Sicherheit nochmal nachfragen.

    Vorausgesetzt natürlich eine der üblichen Fließkommaimplementierungen, vorgeschrieben sind diese Dinge nicht.

    Achja, ja, der Standard schreibt ja nicht IEEE-floats vor. Ist nur fast überall so. Wobei es sicher exoten gibt wo andere Regeln gelten (vielleicht DSPs oder so?).

    0
  • ?

    SeppJ schrieb:

    sugnitar schrieb:

    Welche Implementierung ist jetzt die schnellste?

    Miss es!

    Resultat:

    clang++ -O3 -march=native -std=c++11:
./sA 50000 100000  0.53s user 0.00s system 99% cpu 0.529 total
./sB 50000 100000  0.40s user 0.00s system 99% cpu 0.405 total
./sC 50000 100000  0.34s user 0.00s system 99% cpu 0.344 total
./sD 50000 100000  0.43s user 0.00s system 99% cpu 0.435 total
./sE 50000 100000  13.59s user 0.00s system 99% cpu 13.593 total

g++ -O3 -march=native -std=c++11:
./sA 50000 100000  0.59s user 0.00s system 99% cpu 0.593 total
./sB 50000 100000  0.51s user 0.00s system 99% cpu 0.507 total
./sC 50000 100000  16.97s user 0.00s system 99% cpu 16.973 total
./sD 50000 100000  0.52s user 0.00s system 99% cpu 0.526 total
./sE 50000 100000  14.85s user 0.00s system 99% cpu 14.859 total

g++ -O3 -march=native -std=c++11:
./sA 100000 1000000  12.21s user 0.00s system 99% cpu 12.217 total
./sB 100000 1000000  10.89s user 0.00s system 99% cpu 10.890 total
./sD 100000 1000000  11.14s user 0.00s system 99% cpu 11.143 total

clang++ -O3 -march=native -std=c++11:
./sA 100000 1000000  10.36s user 0.00s system 99% cpu 10.357 total
./sB 100000 1000000  9.33s user 0.00s system 99% cpu 9.330 total
./sC 100000 1000000  8.73s user 0.00s system 99% cpu 8.729 total
./sD 100000 1000000  9.25s user 0.00s system 99% cpu 9.252 total

    ( Code: https://ideone.com/e0zTTE )

    SeppJ schrieb:

    Meine Vermutung (ohne zu schummeln!) wäre B > A = D > C > E.

    C > B > D > A > E. Im g++ wäre C ganz hinten.

    Stellt sich die Frage, wieso? Geht es besser? Was läuft im gcc (Version 5.3.0) schief im Vergleich zu clang++ (Version 3.7.1)?

    Der Code von Finnegan braucht bei mir 17.61s, sehr wahrscheinlich benutze ich ihn falsch.

    Es geht mir hier nur um Integer, mit Floats würde ich lieber noch Epsilon-Vergleiche anstellen.

    0
  • C
    Mod

    sugnitar schrieb:

    Was läuft im gcc (Version 5.3.0) schief im Vergleich zu clang++ (Version 3.7.1)?

    Scheint eine Regression zu sein. Beim mir mit Vers. 4.9.3 erzeugt Variante C vernünftigen Code der auch schneller als alle anderen Varianten ist.

    0
  • F

    sugnitar schrieb:

    Stellt sich die Frage, wieso? Geht es besser? Was läuft im gcc (Version 5.3.0) schief im Vergleich zu clang++ (Version 3.7.1)?

    Der Code von Finnegan braucht bei mir 17.61s, sehr wahrscheinlich benutze ich ihn falsch.

    Hi! ... ich habe das ich nochmal mit GCC 5.2 und einem 3.8er Clang unter Windows gestestet und auch bei mir erzeugt GCC diesen extremen Ausreisser bei Variante C.
    Interessant ist, dass GCC 5.3 im Vergleich zu Clang und seiner 4.9er Reihe die Schleife in main() scheinbar nicht vektorisiert: siehe hier (GCC 5.3) und hier (GCC 4.9) (xmm-Register vs Standardregister).
    Ob das alleine der Grund für die extremen Laufzeitunterschiede ist, kann ich auf die Schnelle nicht sagen. Immerhin scheint signumC() ordentlich ge-inlined worden zu sein.

    Was meine vorgeschlagene signum4() -Funtion angeht, so könnte der Grund für deren schlechte Laufzeit sein, dass sie mit _mm_store_si128() eine explizite Anweisung enthält,
    das Ergebnis der Berechnung in den Speicher zu zurückzuschreiben, während der Compiler bei den anderen Varianten die Möglichkeit hat, die gesamte Berechnung sowie das
    abschließende XOR in Registern auszuführen. Da die Speicherzugriffe wahrscheinlich ohnehin einen sehr grossen Anteil an der gemessenen Laufzeit haben werden, ist es nicht
    verwunderlich, dass signum4() in diesem Fall schlechter abschneidet.

    Ich habe den Testcode mal auf die Schnelle modifiziert, so dass auch die anderen Funktionen das Ergebnis in den Speicher schreiben und signum4() mit in den Test aufgenommen: http://ideone.com/UyZyrF.
    (man möge mir das plumpe "malloc" nachsehen, leider benötigen SIMD-Operationen ein spezielles Speicher-Alignment, und das einem std::vector beizubringen hätte mehr Arbeit gemacht und den Code nur unnötig aufgebläht).

    Mit dieser Variante erziele ich auf meinem Rechner folgende Ergebnisse:

    g++ 5.2.0, clang 3.8.0 (based on LLVM 3.8.0svn)
compiler-flags: -O3 -march=native -std=c++11

      [ args: 50000 100000 ]    [ args: 100000 1000000 ]
               g++     clang          g++      clang
A:          1.833s    2.903s      38.267s    57.430s
B:          1.715s    1.503s      37.051s    33.353s
C:         22.447s    1.482s            -    29.394s
D:          1.742s    1.491s      37.458s    33.368s
E:         23.319s   23.360s            -          -
signum4:    1.399s    1.391s      28.274s    28.138s

    Obwohl die Compiler anscheinend in der Lage sind, die Schleifen zu Vektorisieren, scheinen die expliziten SIMD-Instruktionen von signum4() hier dennoch minimal besser abzuschneiden
    (Allerdings finden hier mit der lesen-schreiben-Kombination auch mehr Speicherzugriffe statt, welche die Performance der reinen Rechnenoperation überschatten dürften).
    Ob sich das allerdings lohnt ist eine andere Frage, da solche manuellen SIMD-Implementierungen meistens erst dann glänzen, wenn man viele Operationen auf einem zusammenhängenden
    Speicherbereich durchführt. Wenn noch ein bisschen mehr als nur das Signum auf den Daten gemacht werden muss, das man gut vektorisieren kann, würde ich es mir allerdings überlegen.

    Gruss,
    Finnegan

    0
Anmelden zum Antworten