Kann ich den Optimierer durch Angabe des Bereichs einer Ganzzahl andeuten?

173

Ich verwende einen intTyp, um einen Wert zu speichern. Aufgrund der Semantik des Programms variiert der Wert immer in einem sehr kleinen Bereich (0 - 36) und wird int(nicht a char) nur wegen der CPU-Effizienz verwendet.

Es scheint, dass viele spezielle arithmetische Optimierungen für einen so kleinen Bereich von ganzen Zahlen durchgeführt werden können. Viele Funktionsaufrufe für diese Ganzzahlen können in kleinen "magischen" Operationen optimiert werden, und einige Funktionen können sogar in Tabellensuchen optimiert werden.

Kann man dem Compiler also mitteilen, dass dies intimmer in diesem kleinen Bereich liegt, und kann der Compiler diese Optimierungen vornehmen?

Rolevax
quelle
4
Wertebereichsoptimierungen gibt es in vielen Compilern, z. llvm, aber mir ist kein Sprachhinweis bekannt, um ihn zu deklarieren.
Remus Rusanu
2
Beachten Sie, dass Sie, wenn Sie niemals negative Zahlen haben, möglicherweise kleine Vorteile bei der Verwendung von unsignedTypen haben, da diese für den Compiler einfacher zu verstehen sind.
user694733
4
@RemusRusanu: Pascal können Sie definieren Unterbereichstypen , zum Beispiel var value: 0..36;.
Edgar Bonet
7
" int (kein Zeichen) wird nur wegen der CPU-Effizienz verwendet. " Dieses alte Stück konventioneller Weisheit ist normalerweise nicht sehr wahr. Schmale Typen müssen manchmal auf die volle Registerbreite von Null oder Vorzeichen erweitert werden, insb. Bei Verwendung als Array-Indizes geschieht dies jedoch manchmal kostenlos. Wenn Sie ein Array dieses Typs haben, überwiegt die Reduzierung des Cache-Footprints normalerweise alles andere.
Peter Cordes
1
Ich habe vergessen zu sagen: intund unsigned intmuss auf den meisten Systemen mit 64-Bit-Zeigern auch von 32 auf 64-Bit vorzeichen- oder null-erweitert werden. Beachten Sie, dass auf x86-64 Operationen an 32-Bit-Registern kostenlos auf 64-Bit null erweitert werden (keine Vorzeichenerweiterung, aber ein vorzeichenbehafteter Überlauf ist ein undefiniertes Verhalten, sodass der Compiler nur 64-Bit-vorzeichenbehaftete Mathematik verwenden kann, wenn er dies wünscht). Sie sehen also nur zusätzliche Anweisungen zum Null-Erweitern von 32-Bit-Funktionsargumenten, keine Berechnungsergebnisse. Sie würden für engere vorzeichenlose Typen.
Peter Cordes

Antworten:

230

Ja, es ist möglich. Zum Beispiel können gccSie damit __builtin_unreachableden Compiler über unmögliche Bedingungen informieren, wie zum Beispiel:

if (value < 0 || value > 36) __builtin_unreachable();

Wir können die obige Bedingung in ein Makro einschließen:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

Und benutze es so:

assume(x >= 0 && x <= 10);

Wie Sie sehen können , werden gccOptimierungen basierend auf diesen Informationen durchgeführt:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Produziert:

func(int):
    mov     eax, 17
    ret

Ein Nachteil ist jedoch, dass Sie undefiniertes Verhalten erhalten , wenn Ihr Code jemals solche Annahmen verletzt .

Es benachrichtigt Sie nicht, wenn dies geschieht, selbst bei Debug-Builds. Um Fehler mit Annahmen einfacher zu debuggen / testen / abzufangen, können Sie ein hybrides Annahme- / Assert-Makro (Credits für @David Z) wie das folgende verwenden:

#if defined(NDEBUG)
#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
#else
#include <cassert>
#define assume(cond) assert(cond)
#endif

In Debug-Builds (mit NDEBUG nicht definiert) funktioniert es wie ein gewöhnliches assertDruckfehler- und abortProgrammierprogramm, und in Release-Builds wird eine Annahme verwendet, die optimierten Code erzeugt.

Beachten Sie jedoch, dass es kein Ersatz für reguläres ist assert- condverbleibt in Release-Builds, daher sollten Sie so etwas nicht tun assume(VeryExpensiveComputation()).

Peter Mortensen
quelle
5
@Xofo, habe es nicht verstanden, in meinem Beispiel ist dies bereits geschehen, da der return 2Zweig vom Compiler aus dem Code entfernt wurde.
6
Es scheint jedoch, dass gcc Funktionen nicht wie erwartet für magische Operationen oder Tabellensuche optimieren kann .
Jingyu9575
19
@ user3528438, __builtin_expectist ein nicht strenger Hinweis. __builtin_expect(e, c)sollte lauten als " ewird am wahrscheinlichsten ausgewertet werden c" und kann nützlich sein, um die Verzweigungsvorhersage zu optimieren, aber es beschränkt sich nicht darauf e, immer zu sein c, sodass der Optimierer andere Fälle nicht wegwerfen kann. Sehen Sie, wie die Zweige in der Baugruppe organisiert sind .
6
Theoretisch könnte anstelle von Code jeder Code verwendet werden, der bedingungslos undefiniertes Verhalten verursacht __builtin_unreachable().
CodesInChaos
14
Wenn es keine Eigenart gibt, von der ich nicht weiß, dass dies eine schlechte Idee ist, kann es sinnvoll sein, dies zu kombinieren assert, z. B. zu definieren assume, assertwann NDEBUGnicht definiert ist und __builtin_unreachable()wann NDEBUGdefiniert ist. Auf diese Weise profitieren Sie von der Annahme im Produktionscode, aber in einem Debug-Build haben Sie immer noch eine explizite Prüfung. Natürlich muss man dann genug Tests durchführen , um sich zu versichern , dass die Annahme wird in der freien Natur erfüllt werden.
David Z
61

Hierfür gibt es Standardunterstützung. Was Sie tun sollten, ist, include stdint.h( cstdint) einzuschließen und dann den Typ zu verwenden uint_fast8_t.

Dies teilt dem Compiler mit, dass Sie nur Zahlen zwischen 0 und 255 verwenden, dass es jedoch kostenlos ist, einen größeren Typ zu verwenden, wenn dies schnelleren Code ergibt. Ebenso kann der Compiler davon ausgehen, dass die Variable niemals einen Wert über 255 haben wird, und dann entsprechende Optimierungen vornehmen.

Lundin
quelle
2
Diese Typen werden bei weitem nicht so oft verwendet, wie sie sein sollten (ich persönlich neige dazu zu vergessen, dass sie existieren). Sie geben Code, der sowohl schnell als auch portabel ist, ziemlich brillant. Und sie gibt es seit 1999.
Lundin
Dies ist ein guter Vorschlag für den allgemeinen Fall. Die Antwort von deniss zeigt eine formbarere Lösung für bestimmte Szenarien.
Leichtigkeitsrennen im Orbit
1
Der Compiler erhält nur die 0-255-Bereichsinformationen auf Systemen, bei denen uint_fast8_tes sich tatsächlich um einen 8-Bit-Typ handelt (z. B. unsigned char), wie dies bei x86 / ARM / MIPS / PPC ( godbolt.org/g/KNyc31 ) der Fall ist . In der frühen DEC Alpha vor 21164A wurden Byte-Ladevorgänge / -Speicher nicht unterstützt, sodass jede vernünftige Implementierung verwendet werden würde typedef uint32_t uint_fast8_t. AFAIK, es gibt keinen Mechanismus für einen Typ, der bei den meisten Compilern (wie gcc) zusätzliche Bereichsbeschränkungen hat, daher bin ich mir ziemlich sicher, uint_fast8_tdass er sich unsigned intin diesem Fall genauso oder wie auch immer verhalten würde .
Peter Cordes
( boolist etwas Besonderes und auf 0 oder 1 beschränkt, aber es ist ein eingebauter Typ, der nicht durch Header-Dateien in Bezug charauf gcc / clang definiert wird. Wie gesagt, ich glaube nicht, dass die meisten Compiler einen Mechanismus haben das würde das möglich machen.)
Peter Cordes
1
Auf jeden Fall uint_fast8_tist dies eine gute Empfehlung, da auf Plattformen, auf denen dies genauso effizient ist wie 8-Bit, ein 8-Bit-Typ verwendet wird unsigned int. (Ich bin wirklich nicht sicher , was die fastTypen sollen schnell sein für und ob der Cache - Fußabdruck tradeoff soll ein Teil davon sein.). x86 bietet umfassende Unterstützung für Byte-Operationen, selbst für das Hinzufügen von Bytes mit einer Speicherquelle, sodass Sie nicht einmal eine separate Last ohne Erweiterung ausführen müssen (was ebenfalls sehr billig ist). gcc macht uint_fast16_teinen 64-Bit-Typ auf x86, was für die meisten Anwendungen verrückt ist (im Vergleich zu 32-Bit). godbolt.org/g/Rmq5bv .
Peter Cordes
8

Die aktuelle Antwort ist gut für den Fall, dass Sie sicher wissen, um welchen Bereich es sich handelt. Wenn Sie jedoch weiterhin ein korrektes Verhalten wünschen, wenn der Wert außerhalb des erwarteten Bereichs liegt, funktioniert dies nicht.

In diesem Fall habe ich festgestellt, dass diese Technik funktionieren kann:

if (x == c)  // assume c is a constant
{
    foo(x);
}
else
{
    foo(x);
}

Die Idee ist , ein Code-Daten Kompromiss: Sie verschieben 1 Bit von Daten (ob x == c) in der Steuerlogik .
Dies deutet auf den Optimierer hin, der xtatsächlich eine bekannte Konstante ist c, und ermutigt ihn, den ersten Aufruf von foogetrennt vom Rest zu integrieren und zu optimieren , möglicherweise ziemlich stark.

Stellen Sie jedoch sicher, dass der Code tatsächlich in einer einzigen Unterroutine berücksichtigt wird foo- duplizieren Sie den Code nicht.

Beispiel:

Damit diese Technik funktioniert, müssen Sie ein wenig Glück haben - es gibt Fälle, in denen der Compiler beschließt, die Dinge nicht statisch zu bewerten, und sie sind willkürlich. Aber wenn es funktioniert, funktioniert es gut:

#include <math.h>
#include <stdio.h>

unsigned foo(unsigned x)
{
    return x * (x + 1);
}

unsigned bar(unsigned x) { return foo(x + 1) + foo(2 * x); }

int main()
{
    unsigned x;
    scanf("%u", &x);
    unsigned r;
    if (x == 1)
    {
        r = bar(bar(x));
    }
    else if (x == 0)
    {
        r = bar(bar(x));
    }
    else
    {
        r = bar(x + 1);
    }
    printf("%#x\n", r);
}

Verwenden Sie einfach -O3und beachten Sie die vorge ausgewertet Konstanten 0x20und 0x30ein Assembler ausgegeben .

user541686
quelle
Würdest du nicht wollen if (x==c) foo(c) else foo(x)? Wenn nur um constexprImplementierungen von zu fangen foo?
MSalters
@ MSalters: Ich wusste, dass jemand das fragen würde !! Ich habe mir diese Technik constexprschon einmal ausgedacht und habe mich nie darum gekümmert, sie später zu "aktualisieren" (obwohl ich mir constexprauch danach keine Sorgen gemacht habe ), aber der Grund, warum ich sie anfangs nicht gemacht habe, war, dass ich es wollte Erleichtern Sie dem Compiler das Herausfiltern als allgemeinen Code und das Entfernen des Zweigs, wenn er sie als normale Methodenaufrufe belassen und nicht optimieren möchte. Ich habe erwartet, dass ces für den Compiler wirklich schwierig ist, c (sorry, schlechter Witz) zu erkennen, dass die beiden der gleiche Code sind, obwohl ich dies nie überprüft habe.
user541686
4

Ich möchte nur sagen, dass Sie, wenn Sie eine Lösung mit mehr Standard-C ++ wünschen, das [[noreturn]]Attribut verwenden können, um Ihre eigene zu schreiben unreachable.

Also werde ich das hervorragende Beispiel von Deniss erneut verwenden , um zu demonstrieren:

namespace detail {
    [[noreturn]] void unreachable(){}
}

#define assume(cond) do { if (!(cond)) detail::unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Was, wie Sie sehen können , zu nahezu identischem Code führt:

detail::unreachable():
        rep ret
func(int):
        movl    $17, %eax
        ret

Der Nachteil ist natürlich, dass Sie eine Warnung erhalten, dass eine [[noreturn]]Funktion tatsächlich zurückkehrt.

Geschichtenerzähler - Unslander Monica
quelle
Es funktioniert mit clang, wenn meine ursprüngliche Lösung nicht funktioniert , so schöner Trick und +1. Aber das Ganze ist sehr compilerabhängig (wie Peter Cordes uns gezeigt hat, icckann es die Leistung verschlechtern ), so dass es immer noch nicht universell anwendbar ist. Außerdem ein kleiner Hinweis: Die unreachableDefinition muss für den Optimierer verfügbar und inline sein, damit dies funktioniert .