wake-up-neo.net

Vergleich von vorzeichenlosen Ganzzahlen ohne Vorzeichen

Wir kennen also alle die C/C++ - Vergleichsregeln mit/ohne Vorzeichen, und -1 > 2u == true. Ich habe eine Situation, in der ich "korrekte" Vergleiche effizient implementieren möchte.

Meine Frage ist, was effizienter ist, wenn man auf so viele Architekturen Rücksicht nimmt, wie man kennt. Offensichtlich haben Intel und ARM ein höheres Gewicht.

Gegeben:

int x;
unsigned int y;
if (x < y) {}

Ist es besser zu fördern:

x < y  =>  (int64)x < (int64)y

oder ist es besser, 2 Vergleiche durchzuführen, dh:

x < y  =>  (x < 0 || x < y)

Ersteres impliziert eine Nullerweiterung, Vorzeichenerweiterung und einen Vergleichszweig +, und letzteres erfordert keine Vorzeichenerweiterungsoperationen, sondern zwei aufeinanderfolgende cmp + -Zweige.
Traditionelle Weisheit legt nahe, dass Verzweigungen teurer sind als Vorzeichenverlängerungen, was beide Pipelines ist, aber im ersten Fall gibt es einen Stillstand zwischen dem Erweiterungs- und dem Einzelvergleich, wohingegen ich mir im zweiten Fall vorstellen kann, dass einige Architekturen Pipeline könnten die 2 Vergleiche, aber dann von 2 bedingten Zweigen gefolgt? 

Es gibt einen weiteren Fall, bei dem der vorzeichenlose Wert ein kleinerer Typ als der vorzeichenbehaftete Typ ist, was bedeutet, dass eine einzige Null-Erweiterung auf die Länge des vorzeichenbehafteten Typs erfolgen kann und dann ein einzelner Vergleich ... in diesem Fall ist es vorzuziehen Verwenden Sie die extend + cmp-Version, oder wird die 2-Vergleichsmethode immer noch bevorzugt?

Intel? ARM? Andere? Ich bin mir nicht sicher, ob es hier eine richtige Antwort gibt, aber ich würde gerne hören, wie die Leute es nehmen. Leistungseinbußen auf niedrigem Niveau sind heutzutage schwer vorherzusagen, insbesondere bei Intel und zunehmend auch bei ARM.

Bearbeiten:

Ich sollte hinzufügen, es gibt eine offensichtliche Auflösung, bei der die Typen gleich der Breite der Architektur sind. In diesem Fall ist es offensichtlich, dass die 2-Vergleichslösung bevorzugt wird, da die Promotion selbst nicht effizient durchgeführt werden kann. Natürlich erfüllt mein int-Beispiel diese Bedingung für 32-Bit-Architekturen, und Sie können das Gedankenexperiment für die auf 32-Bit-Plattformen angewendete Übung auf short übertragen.

Edit 2:

Entschuldigung, ich habe die u in -1 > 2u vergessen! > _ <

Bearbeiten Sie 3:

Ich möchte die Situation ändern, um anzunehmen, dass das Ergebnis des Vergleichs ein tatsächlicher Zweig ist und das Ergebnis NICHT als boolesches Ergebnis zurückgegeben wird. So würde ich die Struktur bevorzugen; Dies wirft jedoch einen interessanten Punkt auf, dass es eine andere Gruppe von Permutationen gibt, wenn das Ergebnis ein Bool-Wert gegenüber einem Zweig ist.

int g;
void fun(int x, unsigned in y) { if((long long)x < (long long)y) g = 10; }
void gun(int x, unsigned in y) { if(x < 0 || x < y) g = 10; }

Dies erzeugt den beabsichtigten Zweig, der normalerweise impliziert wird, wenn Sie eine if;

29
Manu Evans

Nun, Sie haben die Situation richtig typisiert: C/C++ kann keinen vollständig vorzeichenbehafteten int/unsigned int-Vergleich mit einem einzigen Vergleich durchführen.

Ich wäre überrascht, wenn der Aufstieg zu int64 schneller wäre als zwei Vergleiche. Meiner Erfahrung nach können Compiler recht gut erkennen, dass ein solcher Unterausdruck rein ist (keine Nebenwirkungen hat) und somit kein zweiter Zweig benötigt wird. (Sie können den Kurzschluss auch explizit mit bitwise-or: (x < 0) | (x < y) deaktivieren.) Im Gegensatz dazu bin ich der Ansicht, dass Compiler KEINE Spezialfalloptimierung für Ganzzahlen durchführen, die größer als die native Word-Größe sind. Daher ist (int64)x < (int64)y wahrscheinlich um tatsächlich einen vollständigen Vergleich zu machen.

Unterm Strich gibt es keine Beschwörung, die garantiert den bestmöglichen Maschinencode auf jedem Prozessor liefert, aber für die gängigsten Compiler auf den gängigsten Prozessoren würde ich vermuten, dass das Zwei-Vergleich-Formular nicht langsamer ist als die Beförderung -int64 Formular.

BEARBEITEN: Ein paar Fehler bei Godbolt bestätigen, dass der GCC auf ARM32 viel zu viele Maschinen in den Int64-Ansatz steckt. VC macht dasselbe auf x86. Mit x64 ist der Int64-Ansatz jedoch tatsächlich um einen Befehl kürzer (da die Heraufstufung und der 64-Bit-Vergleich trivial sind). Das Pipelining kann jedoch dazu führen, dass die tatsächliche Leistung in beide Richtungen geht. https://godbolt.org/g/wyG4yC

11
Sneftel

Sie müssen dies von Fall zu Fall beurteilen. Es gibt mehrere Gründe, warum signierte Typen in einem Programm verwendet werden:

  1. Weil Sie tatsächlich negative Zahlen in Berechnungen oder Ausgaben haben müssen.
  2. "Sloppy tippen" bedeutet, dass der Programmierer einfach int in sein gesamtes Programm eintippt, ohne sich darüber Gedanken zu machen.
  3. Versehentlich unterschrieben. Das Programm wollte eigentlich keine vorzeichenbehafteten Zahlen, sondern endete versehentlich mit ihnen, entweder durch implizite Typ-Promotions oder durch die Verwendung von Ganzzahlkonstanten wie 0, die vom Typ int ist.

Im Falle von 1) sollte die Arithmetik mit signierter Arithmetik ausgeführt werden. Sie sollten dann in den kleinstmöglichen Typ konvertieren, der für die maximal erwarteten Werte erforderlich ist. 

Angenommen, ein Wert kann beispielsweise einen Bereich von -10000 bis 10000 haben. Sie müssen dann einen 16-Bit-Typ mit Vorzeichen verwenden, um ihn darzustellen. Der richtige Typ, der dann plattformunabhängig verwendet werden kann, ist int_fast16_t

Die Typen int_fastn_t und uint_fastn_t setzen voraus, dass der Typ mindestens so groß wie n ist. Der Compiler darf jedoch einen größeren Typ auswählen, wenn er einen schnelleren Code/eine bessere Ausrichtung bietet.


2) wird geheilt, indem stdint.h studiert und aufgehört wird, faul zu sein. Als Programmierer muss man immer die Größe und Vorzeichen von jeder einzelnen im Programm deklarierten Variablen berücksichtigen. Dies muss zum Zeitpunkt der Erklärung erfolgen. Wenn Sie später eine Art Offenbarung erhalten, gehen Sie zurück und ändern Sie den Typ.

Wenn Sie die Typen nicht sorgfältig betrachten, werden Sie mit absoluter Sicherheit zahlreiche, oft subtile Fehler schreiben. Dies ist besonders in C++ wichtig, da hier die Typkorrektheit wählerischer ist als in C.

Wenn "schlampiges Tippen" verwendet wird, ist der tatsächlich beabsichtigte Typ meistens nicht signiert. Betrachten Sie dieses schlampige Tippbeispiel:

for(int i=0; i<n; i++)

Es macht überhaupt keinen Sinn, signiertes int hier zu verwenden, warum also? Wahrscheinlich durchlaufen Sie ein Array oder einen Container, und der richtige Typ ist size_t

Wenn Sie jedoch die maximale Größe kennen, die n enthalten kann, beispielsweise 100, können Sie den am besten geeigneten Typ dafür verwenden:

for(uint_fast8_t i=0; i<100; i++)

3) wird auch durch Studium geheilt. Insbesondere die verschiedenen Regeln für implizite Beförderungen, die in diesen Sprachen existieren, wie die üblichen arithmetischen Konvertierungen und Integer-Beförderung .

6
Lundin

In Anbetracht des von Ihnen präsentierten spezifischen Setups:

int x;
unsigned int y;

und Ihre offensichtliche Absicht, zu bewerten, ob der Wert von x numerisch kleiner ist als der von y, und das Zeichen von x zu respektieren, würde ich gerne dazu schreiben

if ((x < 0) || (x < y)) {}

das ist deine zweite Alternative. Sie drückt die Absicht klar aus und ist für breitere Typen erweiterbar, solange der maximal darstellbare Wert des Typs y mindestens so groß ist wie der maximal darstellbare Wert des Typs x. Wenn Sie also bereit sind, festzulegen, dass die Argumente diese Form haben, können Sie sie sogar als "Abwenden Ihrer Augen, C++ - Anhänger" - ein Makro schreiben.

Das Konvertieren beider Argumente in einen 64-Bit-Ganzzahlentyp mit Vorzeichen ist keine tragbare Lösung, da nicht garantiert werden kann, dass es sich tatsächlich um eine promotion von int oder unsigned int handelt. Es ist auch nicht für breitere Typen erweiterbar.

Was die relative Leistung Ihrer beiden Alternativen angeht, bezweifle ich, dass es große Unterschiede gibt, aber wenn es Ihnen wichtig ist, möchten Sie einen vorsichtigen Benchmark schreiben. Ich könnte mir vorstellen, dass die tragbare Alternative eine mehr Maschinenanweisung als die andere erfordert, und ich kann mir auch vorstellen, dass eine weniger benötigt wird. Nur wenn solche Vergleiche die Leistung Ihrer Anwendung bestimmen, kann eine einzelne Anweisung auf die eine oder andere Weise einen spürbaren Unterschied ausmachen.

Das ist natürlich spezifisch für die Situation, die Sie vorgestellt haben. Wenn Sie gemischte vorzeichenbehaftete/vorzeichenlose Vergleiche in beliebiger Reihenfolge für viele verschiedene Typen ausführen möchten, die zur Kompilierzeit aussortiert werden, kann ein vorlagenbasierter Wrapper dabei helfen (und dies würde die Frage der Verwendung eines Makros in Frage stellen) Aber ich nehme an, Sie fragen genau nach Details des Vergleichs.

6
John Bollinger

Die Version mit zwei Zweigen wäre sicherlich langsamer, aber in Wirklichkeit ist nichts davon zwei Zweige ... oder einzelne Zweige ... auf x86.

Zum Beispiel wird x86 gcc 7.1 für C++ source:

bool compare(int x, unsigned int y) {
    return (x < y); // "wrong" (will emit warning)
}

bool compare2(int x, unsigned int y) {
    return (x < 0 || static_cast<unsigned int>(x) < y);
}

bool compare3(int x, unsigned int y) {
    return static_cast<long long>(x) < static_cast<long long>(y);
}

Produziere diese Versammlung ( godbolt live demo ):

compare(int, unsigned int):
        cmp     edi, esi
        setb    al
        ret

compare2(int, unsigned int):
        mov     edx, edi
        shr     edx, 31
        cmp     edi, esi
        setb    al
        or      eax, edx
        ret

compare3(int, unsigned int):
        movsx   rdi, edi
        mov     esi, esi
        cmp     rdi, rsi
        setl    al
        ret

Wenn Sie versuchen würden, diese in komplexerem Code zu verwenden, würden sie in 99% der Fälle inline dargestellt. Ohne Profiling ist es nur Vermutung, aber "aus gutem Grund" würde ich compare3 als "schneller" bezeichnen, vor allem, wenn es in einem Code außerhalb der Reihenfolge ausgeführt wird (irgendwie komisch, es macht die richtige 32-> 64-Promotion selbst für uint-Argumente, während) Es würde einige Anstrengungen erfordern, um Code-Aufrufe zu erzeugen, die mit etwas Durcheinander in oberen 32b von esi verglichen werden, aber es würde sich wahrscheinlich davon lösen, wenn es in komplexeren Berechnungen inline angegeben wird, wobei das Argument bereits erwähnt wird. so ist der compare3 dann noch einfacher + kürzer).

... wie gesagt, ich treffe keine Aufgaben, bei denen ich das brauchen würde. Ich kann mir zum Beispiel nicht vorstellen, an etwas zu arbeiten, an dem ein gültiger Datenbereich unbekannt ist, also arbeite ich an der C/C++ passt perfekt und ich schätze genau die Art und Weise, wie es funktioniert (der < für vorzeichenbehaftete und nicht vorzeichenbehaftete Typen ist gut definiert und führt zu kürzestem/schnellstem Code. Außerdem wird eine Warnung ausgegeben, die mich als Programmierer dazu veranlasst, ihn zu validieren, und im Fall von müssen die Quelle entsprechend ändern).

5
Ped7g

Ein tragbarer Trick, den Sie tun können, ist zu prüfen, ob Sie beide Argumente von intmax_t auf <stdint.h> erweitern können. Dies ist der breiteste integrale Typ, den eine Implementierung unterstützt. Sie können (sizeof(intmax_t) > sizeof(x) && sizeof(intmax_t) >= sizeof(y)) überprüfen und in diesem Fall eine erweiterte Konvertierung durchführen. Dies funktioniert in dem sehr häufigen Fall, in dem int 32 Bit breit ist und long long int 64 Bit breit ist.

In C++ können Sie clevere Dinge tun, bei denen Sie über eine Vorlage für einen sicheren Vergleich verfügen, die std::numeric_limits<T> auf ihre Argumente überprüft. Hier ist eine Version. (Kompilieren Sie mit -Wno-sign-compare auf gcc oder clang!)

#include <cassert>
#include <cstdint>
#include <limits>

using std::intmax_t;
using std::uintmax_t;

template<typename T, typename U>
  inline bool safe_gt( T x, U y ) {
    constexpr auto tinfo = std::numeric_limits<T>();
    constexpr auto uinfo = std::numeric_limits<U>();
    constexpr auto maxinfo = std::numeric_limits<intmax_t>();

    static_assert(tinfo.is_integer, "");
    static_assert(uinfo.is_integer, "");

    if ( tinfo.is_signed == uinfo.is_signed )
      return x > y;
    else if ( maxinfo.max() >= tinfo.max() &&
              maxinfo.max() >= uinfo.max() )
      return static_cast<intmax_t>(x) > static_cast<intmax_t>(y);
    else if (tinfo.is_signed) // x is signed, y unsigned.
      return x > 0 && x > y;
    else // y is signed, x unsigned.
      return y < 0 || x > y;      
  }

int main()
{
  assert(-2 > 1U);
  assert(!safe_gt(-2, 1U));
  assert(safe_gt(1U, -2));
  assert(safe_gt(1UL, -2L));
  assert(safe_gt(1ULL, -2LL));
  assert(safe_gt(1ULL, -2));
}

Es könnte auf Fließkomma aufmerksam gemacht werden, indem zwei Linien geändert werden.

4
Davislor

Mit einem kleinen Template-Jiggery-Pokery denke ich, dass wir in allen Szenarien automatisch das optimale Ergebnis erzielen können:

#include<iostream>
#include<cassert>


template<class T> auto make_unsigned(T i) -> T { return i; }

auto make_unsigned(int i) -> unsigned int {
    assert(i >= 0);
    return static_cast<unsigned int>(i);
}

auto make_unsigned(short i) -> unsigned short {
    assert(i >= 0);
    return static_cast<unsigned short>(i);
}

auto make_unsigned(long long i) -> unsigned long long {
    assert(i >= 0);
    return static_cast<unsigned long long>(i);
}

template<
        class I1,
        class I2,
        std::enable_if_t<(std::is_signed<I1>::value and std::is_signed<I2>::value)
                         or (not std::is_signed<I1>::value and not std::is_signed<I2>::value)>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return i1 < i2;
};

template<
        class I1,
        class I2,
        std::enable_if_t<std::is_signed<I1>::value and not std::is_signed<I2>::value>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return (i1 < 0) or make_unsigned(i1) < i2;
};

template<
        class I1,
        class I2,
        std::enable_if_t<not std::is_signed<I1>::value and std::is_signed<I2>::value>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return not (i2 < 0) and i1 < make_unsigned(i2);
};



int main() {

    short a = 1;
    unsigned int b = 2;

    std::cout << unsigned_less(a, b) << std::endl;

    using uint = unsigned int;
    using ushort = unsigned short;
    std::cout << unsigned_less(ushort(1), int(3)) << std::endl;

    std::cout << unsigned_less(int(-1), uint(0)) << std::endl;
    std::cout << unsigned_less(int(1), uint(0)) << std::endl;

    return 0;
}
0
Richard Hodges

Schauen Sie sich Andrei Alexandrescus Keynote auf der letzten D-Konferenz über Design by Introspection in Berlin an.

Darin zeigt er, wie eine geprüfte int-Klasse zur DESIGN-Zeit entworfen wird, und eines der Features, die er dazu bringt, ist genau das - wie man signierte und unsignierte vergleicht.

Grundsätzlich müssen Sie 2 Vergleiche durchführen

Wenn (signed_var <0), dann unsigned_var zurückgeben Else promoted/cast signs_var an unsigned_var und dann vergleichen

0
PMcK