Wie schreibe ich eine wartbare, schnelle Bitmaske zur Kompilierungszeit in C ++?

113

Ich habe einen Code, der mehr oder weniger so ist:

#include <bitset>

enum Flags { A = 1, B = 2, C = 3, D = 5,
             E = 8, F = 13, G = 21, H,
             I, J, K, L, M, N, O };

void apply_known_mask(std::bitset<64> &bits) {
    const Flags important_bits[] = { B, D, E, H, K, M, L, O };
    std::remove_reference<decltype(bits)>::type mask{};
    for (const auto& bit : important_bits) {
        mask.set(bit);
    }

    bits &= mask;
}

Clang> = 3.6 macht das andSchlaue und kompiliert dies zu einer einzigen Anweisung (die dann überall sonst eingefügt wird):

apply_known_mask(std::bitset<64ul>&):  # @apply_known_mask(std::bitset<64ul>&)
        and     qword ptr [rdi], 775946532
        ret

Aber jede Version von GCC, die ich versucht habe, kompiliert dies zu einem enormen Durcheinander, das Fehlerbehandlung beinhaltet, die statisch DCE-fähig sein sollte. In anderem Code wird sogar das important_bitsÄquivalent als Daten in Übereinstimmung mit dem Code platziert!

.LC0:
        .string "bitset::set"
.LC1:
        .string "%s: __position (which is %zu) >= _Nb (which is %zu)"
apply_known_mask(std::bitset<64ul>&):
        sub     rsp, 40
        xor     esi, esi
        mov     ecx, 2
        movabs  rax, 21474836482
        mov     QWORD PTR [rsp], rax
        mov     r8d, 1
        movabs  rax, 94489280520
        mov     QWORD PTR [rsp+8], rax
        movabs  rax, 115964117017
        mov     QWORD PTR [rsp+16], rax
        movabs  rax, 124554051610
        mov     QWORD PTR [rsp+24], rax
        mov     rax, rsp
        jmp     .L2
.L3:
        mov     edx, DWORD PTR [rax]
        mov     rcx, rdx
        cmp     edx, 63
        ja      .L7
.L2:
        mov     rdx, r8
        add     rax, 4
        sal     rdx, cl
        lea     rcx, [rsp+32]
        or      rsi, rdx
        cmp     rax, rcx
        jne     .L3
        and     QWORD PTR [rdi], rsi
        add     rsp, 40
        ret
.L7:
        mov     ecx, 64
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:.LC1
        xor     eax, eax
        call    std::__throw_out_of_range_fmt(char const*, ...)

Wie soll ich diesen Code schreiben, damit beide Compiler das Richtige tun können? Wenn dies nicht der Fall ist, wie soll ich das schreiben, damit es klar, schnell und wartbar bleibt?

Alex Reinking
quelle
4
Können Sie nicht eine Maske erstellen, anstatt eine Schleife zu verwenden B | D | E | ... | O?
HolyBlackCat
6
Die Aufzählung hat eher Bitpositionen als bereits erweiterte Bits, also könnte ich das tun(1ULL << B) | ... | (1ULL << O)
Alex Reinking
3
Der Nachteil ist, dass die tatsächlichen Namen lang und unregelmäßig sind und es bei weitem nicht so einfach ist zu erkennen, welche Flags sich in der Maske mit all dem Linienrauschen befinden.
Alex Reinking
4
@AlexReinking Du könntest es zu einem machen (1ULL << Constant)| pro Zeile und richten Sie die konstanten Namen auf den verschiedenen Zeilen aus, was für die Augen einfacher wäre.
Einpoklum
Ich denke, das Problem hier hängt mit der mangelnden Verwendung des vorzeichenlosen Typs zusammen. GCC hatte immer Probleme mit der statischen Verwerfung der Korrektur für Überlauf und Typkonvertierung in vorzeichenbehafteten / vorzeichenlosen Hybriden. Das intErgebnis der Bitverschiebung hier ist ein Ergebnis der Bitoperation, die intmöglicherweise long longvom Wert abhängt und formal enumist nicht gleichbedeutend mit einer intKonstanten. Clang fordert "als ob", gcc bleibt pedantisch
Swift - Friday Pie

Antworten:

112

Beste Version ist ::

template< unsigned char... indexes >
constexpr unsigned long long mask(){
  return ((1ull<<indexes)|...|0ull);
}

Dann

void apply_known_mask(std::bitset<64> &bits) {
  constexpr auto m = mask<B,D,E,H,K,M,L,O>();
  bits &= m;
}

zurück in können wir diesen seltsamen Trick machen:

template< unsigned char... indexes >
constexpr unsigned long long mask(){
  auto r = 0ull;
  using discard_t = int[]; // data never used
  // value never used:
  discard_t discard = {0,(void(
    r |= (1ull << indexes) // side effect, used
  ),0)...};
  (void)discard; // block unused var warnings
  return r;
}

oder, wenn wir feststecken können wir es rekursiv lösen:

constexpr unsigned long long mask(){
  return 0;
}
template<class...Tail>
constexpr unsigned long long mask(unsigned char b0, Tail...tail){
  return (1ull<<b0) | mask(tail...);
}
template< unsigned char... indexes >
constexpr unsigned long long mask(){
  return mask(indexes...);
}

Godbolt mit allen 3 - Sie können CPP_VERSION define wechseln und identische Assembly erhalten.

In der Praxis würde ich das modernste verwenden, das ich konnte. 14 schlägt 11, weil wir keine Rekursion und damit keine O (n ^ 2) -Symbollänge haben (was die Kompilierungszeit und die Verwendung des Compilerspeichers explodieren lassen kann); 17 schlägt 14, weil der Compiler dieses Array nicht mit totem Code eliminieren muss und dieser Array-Trick einfach hässlich ist.

Von diesen 14 ist die verwirrendste. Hier erstellen wir ein anonymes Array aller Nullen, während wir als Nebeneffekt unser Ergebnis konstruieren und das Array dann verwerfen. Das verworfene Array enthält eine Anzahl von Nullen, die der Größe unseres Pakets entspricht, plus 1 (die wir hinzufügen, damit wir leere Pakete verarbeiten können).


Eine ausführliche Erklärung, was die Version tut. Dies ist ein Trick / Hack, und die Tatsache, dass Sie dies tun müssen, um Parameterpakete in C ++ 14 effizient zu erweitern, ist einer der Gründe, warum Fold-Ausdrücke hinzugefügt wurden.

Es ist am besten von innen nach außen zu verstehen:

    r |= (1ull << indexes) // side effect, used

dieses Updates nur rmit 1<<indexesfür einen festen Index. indexesist ein Parameterpaket, daher müssen wir es erweitern.

Der Rest der Arbeit besteht darin, ein Parameterpaket bereitzustellen, das indexesinnerhalb von erweitert werden kann.

Ein Schritt heraus:

(void(
    r |= (1ull << indexes) // side effect, used
  ),0)

Hier setzen wir unseren Ausdruck auf void, um anzuzeigen, dass uns der Rückgabewert egal ist (wir möchten nur den Nebeneffekt der Einstellung r- in C ++ geben Ausdrücke wie a |= bauch den Wert zurück, auf den sie gesetzt asind).

Dann verwenden wir den Komma-Operator ,und 0, um den void"Wert" zu verwerfen und den Wert zurückzugeben 0. Dies ist also ein Ausdruck, dessen Wert ist, 0und als Nebeneffekt der Berechnung 0setzt er ein wenig ein r.

  int discard[] = {0,(void(
    r |= (1ull << indexes) // side effect, used
  ),0)...};

An dieser Stelle erweitern wir das Parameterpaket indexes. So bekommen wir:

 {
    0,
    (expression that sets a bit and returns 0),
    (expression that sets a bit and returns 0),
    [...]
    (expression that sets a bit and returns 0),
  }

in der {}. Diese Verwendung von ,ist nicht der Kommaoperator, sondern das Arrayelementtrennzeichen. Dies ist sizeof...(indexes)+1 0s, das rals Nebeneffekt auch Bits setzt . Anschließend weisen wir die {}Array-Konstruktionsanweisungen einem Array zu discard.

Als nächstes setzen wir discardauf void- die meisten Compiler werden Sie warnen, wenn Sie eine Variable erstellen und sie nie lesen. Alle Compiler werden sich nicht beschweren, wenn Sie es besetzen void. Es ist eine Art zu sagen "Ja, ich weiß, ich benutze das nicht", also unterdrückt es die Warnung.

Yakk - Adam Nevraumont
quelle
38
Entschuldigung, aber dieser C ++ 14-Code ist etwas. Ich weiß nicht was.
James
14
@ James Es ist ein wunderbares motivierendes Beispiel dafür, warum Fold-Ausdrücke in C ++ 17 sehr willkommen sind. Es und ähnliche Tricks erweisen sich als eine effiziente Möglichkeit, ein Paket "an Ort und Stelle" ohne Rekursion zu erweitern, und die für Komplizen leicht zu optimieren ist.
Yakk - Adam Nevraumont
4
@ruben Multi Line Constexpr ist illegal in 11
Yakk - Adam Nevraumont
6
Ich kann mir nicht vorstellen, diesen C ++ 14-Code einzuchecken. Ich werde mich an C ++ 11 halten, da ich das sowieso brauche, aber selbst wenn ich es verwenden könnte, erfordert der C ++ 14-Code so viele Erklärungen, dass ich es nicht tun würde. Diese Masken können immer mit höchstens 32 Elementen geschrieben werden, daher mache ich mir keine Sorgen um das Verhalten von O (n ^ 2). Wenn n durch eine Konstante begrenzt ist, dann ist es schließlich O (1). ;)
Alex Reinking
9
Für diejenigen, die versuchen zu verstehen ((1ull<<indexes)|...|0ull), ist es ein "Falzausdruck" . Insbesondere ist es eine "binäre rechte Falte" und es sollte analysiert werden als(pack op ... op init)
Henrik Hansen
47

Die Optimierung, nach der Sie suchen, scheint das Loop-Peeling zu sein, das bei -O3oder manuell mit aktiviert wird -fpeel-loops. Ich bin mir nicht sicher, warum dies eher in den Bereich des Schleifenschälens als des Abrollens von Schleifen fällt, aber möglicherweise ist es nicht bereit, eine Schleife mit nicht lokalem Kontrollfluss darin abzuwickeln (wie dies möglicherweise aus der Bereichsprüfung hervorgeht).

Standardmäßig kann GCC jedoch nicht alle Iterationen ablösen, was anscheinend erforderlich ist. Experimentell wird durch Übergeben -O2 -fpeel-loops --param max-peeled-insns=200(der Standardwert ist 100) die Aufgabe mit Ihrem ursprünglichen Code erledigt: https://godbolt.org/z/NNWrga

Sneftel
quelle
Du bist unglaublich, danke! Ich hatte keine Ahnung, dass dies in GCC konfigurierbar ist! Obwohl aus irgendeinem Grund -O3 -fpeel-loops --param max-peeled-insns=200scheitert ... Es liegt -ftree-slp-vectorizeanscheinend an.
Alex Reinking
Diese Lösung scheint auf das x86-64-Ziel beschränkt zu sein. Die Ausgabe für ARM und ARM64 ist immer noch nicht schön, was wiederum für OP völlig irrelevant sein könnte.
Echtzeit
@realtime - es ist eigentlich etwas relevant. Vielen Dank für den Hinweis, dass es in diesem Fall nicht funktioniert. Sehr enttäuschend, dass GCC es nicht fängt, bevor es auf eine plattformspezifische IR gesenkt wird. LLVM optimiert es vor jedem weiteren Absenken.
Alex Reinking
10

Wenn nur C ++ 11 verwendet wird, ist dies ein Muss (&a)[N], um Arrays zu erfassen. Auf diese Weise können Sie eine einzelne rekursive Funktion schreiben, ohne Hilfsfunktionen zu verwenden:

template <std::size_t N>
constexpr std::uint64_t generate_mask(Flags const (&a)[N], std::size_t i = 0u){
    return i < N ? (1ull << a[i] | generate_mask(a, i + 1u)) : 0ull;
}

Zuweisen zu einem constexpr auto:

void apply_known_mask(std::bitset<64>& bits) {
    constexpr const Flags important_bits[] = { B, D, E, H, K, M, L, O };
    constexpr auto m = generate_mask(important_bits); //< here
    bits &= m;
}

Prüfung

int main() {
    std::bitset<64> b;
    b.flip();
    apply_known_mask(b);
    std::cout << b.to_string() << '\n';
}

Ausgabe

0000000000000000000000000000000000101110010000000000000100100100
//                                ^ ^^^  ^             ^  ^  ^
//                                O MLK  H             E  D  B

Man muss wirklich die Fähigkeit von C ++ schätzen, alles zu berechnen, was zur Kompilierungszeit berechenbar ist. Es ist sicherlich immer noch umwerfend ( <> ).


Für die späteren Versionen von C ++ 14 und C ++ 17 deckt Yakks Antwort dies bereits wunderbar ab.

Stapel Danny
quelle
3
Wie zeigt dies, dass apply_known_masktatsächlich optimiert wird?
Alex Reinking
2
@ AlexReinking: Alle gruseligen Teile sind constexpr. Und obwohl dies theoretisch nicht ausreicht, wissen wir, dass GCC durchaus in der Lage ist, constexprwie beabsichtigt zu bewerten .
MSalters
8

Ich würde Sie ermutigen, einen richtigen EnumSetTyp zu schreiben .

Das Schreiben eines Basic EnumSet<E>in C ++ 14 (ab) basierend auf std::uint64_tist trivial:

template <typename E>
class EnumSet {
public:
    constexpr EnumSet() = default;

    constexpr EnumSet(std::initializer_list<E> values) {
        for (auto e : values) {
            set(e);
        }
    }

    constexpr bool has(E e) const { return mData & mask(e); }

    constexpr EnumSet& set(E e) { mData |= mask(e); return *this; }

    constexpr EnumSet& unset(E e) { mData &= ~mask(e); return *this; }

    constexpr EnumSet& operator&=(const EnumSet& other) {
        mData &= other.mData;
        return *this;
    }

    constexpr EnumSet& operator|=(const EnumSet& other) {
        mData |= other.mData;
        return *this;
    }

private:
    static constexpr std::uint64_t mask(E e) {
        return std::uint64_t(1) << e;
    }

    std::uint64_t mData = 0;
};

Auf diese Weise können Sie einfachen Code schreiben:

void apply_known_mask(EnumSet<Flags>& flags) {
    static constexpr EnumSet<Flags> IMPORTANT{ B, D, E, H, K, M, L, O };

    flags &= IMPORTANT;
}

In C ++ 11 erfordert es einige Windungen, bleibt aber dennoch möglich:

template <typename E>
class EnumSet {
public:
    template <E... Values>
    static constexpr EnumSet make() {
        return EnumSet(make_impl(Values...));
    }

    constexpr EnumSet() = default;

    constexpr bool has(E e) const { return mData & mask(e); }

    void set(E e) { mData |= mask(e); }

    void unset(E e) { mData &= ~mask(e); }

    EnumSet& operator&=(const EnumSet& other) {
        mData &= other.mData;
        return *this;
    }

    EnumSet& operator|=(const EnumSet& other) {
        mData |= other.mData;
        return *this;
    }

private:
    static constexpr std::uint64_t mask(E e) {
        return std::uint64_t(1) << e;
    }

    static constexpr std::uint64_t make_impl() { return 0; }

    template <typename... Tail>
    static constexpr std::uint64_t make_impl(E head, Tail... tail) {
        return mask(head) | make_impl(tail...);
    }

    explicit constexpr EnumSet(std::uint64_t data): mData(data) {}

    std::uint64_t mData = 0;
};

Und wird aufgerufen mit:

void apply_known_mask(EnumSet<Flags>& flags) {
    static constexpr EnumSet<Flags> IMPORTANT =
        EnumSet<Flags>::make<B, D, E, H, K, M, L, O>();

    flags &= IMPORTANT;
}

Sogar GCC generiert trivial eine andAnweisung bei -O1 Godbolt :

apply_known_mask(EnumSet<Flags>&):
        and     QWORD PTR [rdi], 775946532
        ret
Matthieu M.
quelle
2
In C ++ 11 ist ein Großteil Ihres constexprCodes nicht legal. Ich meine, einige haben 2 Aussagen! (C ++ 11 constexpr saugte)
Yakk - Adam Nevraumont
@ Yakk-AdamNevraumont: Sie haben festgestellt, dass ich zwei Versionen des Codes veröffentlicht habe, die erste für C ++ 14 und eine zweite, die speziell auf C ++ 11 zugeschnitten ist? (um seine Grenzen zu erklären)
Matthieu M.
1
Es ist möglicherweise besser, std :: zugrunde liegender Typ anstelle von std :: uint64_t zu verwenden.
James
@ James: Eigentlich nein. Beachten Sie, dass EnumSet<E>ein Wert von Enicht direkt als Wert verwendet wird, sondern stattdessen verwendet wird 1 << e. Es ist eine andere Domain zusammen, was eigentlich ist , was die Klasse so wertvoll = macht> keine Chance, aus Versehen der Indizierung durch estatt 1 << e.
Matthieu M.
@MatthieuM. Ja, du hast Recht. Ich verwechsle es mit unserer eigenen Implementierung, die Ihrer sehr ähnlich ist. Der Nachteil der Verwendung von (1 << e) besteht darin, dass es sich wahrscheinlich um UB handelt, hoffentlich um einen Compilerfehler, wenn e für die Größe des zugrunde liegenden Typs außerhalb der Grenzen liegt.
James
7

Seit C ++ 11 können Sie auch die klassische TMP-Technik verwenden:

template<std::uint64_t Flag, std::uint64_t... Flags>
struct bitmask
{
    static constexpr std::uint64_t mask = 
        bitmask<Flag>::value | bitmask<Flags...>::value;
};

template<std::uint64_t Flag>
struct bitmask<Flag>
{
    static constexpr std::uint64_t value = (uint64_t)1 << Flag;
};

void apply_known_mask(std::bitset<64> &bits) 
{
    constexpr auto mask = bitmask<B, D, E, H, K, M, L, O>::value;
    bits &= mask;
}

Link zum Compiler Explorer: https://godbolt.org/z/Gk6KX1

Der Vorteil dieses Ansatzes gegenüber der Funktion constexpr für Vorlagen besteht darin, dass das Kompilieren aufgrund der Chiel-Regel möglicherweise etwas schneller ist .

Michał Łoś
quelle
1

Hier gibt es einige weit zu "kluge" Ideen. Sie helfen wahrscheinlich nicht bei der Wartbarkeit, indem Sie ihnen folgen.

ist

{B, D, E, H, K, M, L, O};

so viel einfacher zu schreiben als

(B| D| E| H| K| M| L| O);

?

Dann wird der Rest des Codes nicht benötigt.

Einer
quelle
1
"B", "D" usw. sind selbst keine Flags.
Michał Łoś
Ja, Sie müssten diese zuerst in Flags umwandeln. Das ist in meiner Antwort überhaupt nicht klar. Es tut uns leid. Ich werde aktualisieren.
Einer