¿Cómo escribo una máscara de bits de tiempo de compilación rápida y fácil de mantener en C++?

c++11 bit-manipulation

Question

Tengo un código que es más o menos así:

#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 hace lo inteligente y lo compila en una sola instrucción and instrucción (que luego se inserta en cualquier otra parte):

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

Pero cada versión de GCC que he intentado compila esto en un enorme desorden que incluye el manejo de errores que debería ser estáticamente DCE. En otro código, ¡incluso colocará los equivalentes important_bits como datos en línea con el código!

.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*, ...)

¿Cómo debo escribir este código para que ambos compiladores puedan hacer lo correcto? En su defecto, ¿cómo debo escribir esto para que quede claro, rápido y fácil de mantener?

Answer 1

Aquí hay algunas ideas "inteligentes" que están muy lejos. Probablemente no estés ayudando a la mantenibilidad al seguirlos

es

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

mucho más fácil de escribir que

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

?

Entonces no se necesita nada del resto del código.

Answer 2

Desde C ++ 11 también puedes usar la técnica TMP clásica:

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;
}

Enlace a Compiler Explorer: https://godbolt.org/z/Gk6KX1

La ventaja de este enfoque sobre la función constexpr de la plantilla es que es potencialmente un poco más rápido de compilar debido a la regla de Chiel .

Answer 3

La mejor versión es c ++ 17 :

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

Entonces

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

De vuelta en c ++ 14 , podemos hacer este extraño truco:

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;
}

o, si estamos atascados con c ++ 11 , podemos resolverlo recursivamente:

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 con los 3 : puede cambiar CPP_VERSION define y obtener el ensamblaje idéntico.

En la práctica usaría lo más moderno que pude. 14 tiempos 11 porque no tenemos recursión y, por lo tanto, la longitud del símbolo O (n ^ 2) (que puede explotar el tiempo de compilación y el uso de la memoria del compilador); 17 beats 14 porque el compilador no tiene que eliminar el array de código muerto, y ese truco de array es feo.

De estos 14 es el más confuso. Aquí creamos una matriz anónima de todos los 0, mientras que como efecto secundario construimos nuestro resultado y luego descartamos la matriz. La matriz descartada tiene un número de 0s igual al tamaño de nuestro paquete, más 1 (que agregamos para que podamos manejar paquetes vacíos).

Una explicación detallada de lo que está haciendo la versión c ++ 14 . Este es un truco / truco, y el hecho de que tenga que hacer esto para expandir los paquetes de parámetros con eficiencia en C ++ 14 es una de las razones por las que las expresiones de plegado se agregaron en c ++ 17 .

Se entiende mejor desde adentro hacia afuera:

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

esto solo actualiza r con 1<<indexes para un índice fijo. indexes son un paquete de parámetros, así que tendremos que expandirlo.

El resto del trabajo es proporcionar un paquete de parámetros para expandir los indexes dentro de.

Un paso hacia fuera:

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

aquí dejamos nuestra expresión en void , lo que indica que no nos importa su valor de retorno (solo queremos el efecto secundario de configurar r - en C ++, las expresiones como a |= b también devuelven el valor al que establecen a).

Luego usamos el operador de coma , y 0 para descartar el "valor" y devolver el valor 0 . Así que esta es una expresión cuyo valor es 0 y como efecto secundario del cálculo de 0 establece un bit en r .

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

En este punto, expandimos los indexes paquete de parámetros. Así obtenemos:

 {
    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),
  }

en el {} . Este uso de , no es el operador de coma, sino el separador de elementos de matriz. Esto es sizeof...(indexes)+1 0 s, que también establece bits en r como efecto secundario. Luego, asignamos las instrucciones de construcción de la matriz {} a un discard matriz.

A continuación, emitimos discard a void : la mayoría de los compiladores le avisarán si crea una variable y nunca la lee. Todos los compiladores no se quejarán si lo void , es una forma de decir "Sí, lo sé, no uso esto", por lo que suprime la advertencia.

Answer 4

La optimización que está buscando parece ser el peeling de bucle, que se habilita en -O3 , o manualmente con -fpeel-loops . No estoy seguro de por qué esto está incluido en el ámbito del peeling de bucle en lugar del desenrollado del bucle, pero posiblemente no esté dispuesto a desenrollar un bucle con un flujo de control no local dentro de él (ya que, potencialmente, hay un control de rango).

Sin embargo, de forma predeterminada, GCC no llega a poder pelar todas las iteraciones, lo que aparentemente es necesario. Experimentalmente, pasar -O2 -fpeel-loops --param max-peeled-insns=200 (el valor predeterminado es 100) hace el trabajo con su código original: https://godbolt.org/z/NNWrga

Answer 5

Le animo a escribir un tipo de EnumSet adecuado.

Escribir un EnumSet<E> básico EnumSet<E> en C ++ 14 (en adelante) basado en std::uint64_t es 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;
};

Esto le permite escribir código simple:

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

    flags &= IMPORTANT;
}

En C ++ 11, requiere algunas circunvoluciones, pero sigue siendo posible:

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;
};

Y se invoca con:

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;
}

Incluso GCC genera de forma trivial and una instrucción en -O1 godbolt :

apply_known_mask(EnumSet<Flags>&):
        and     QWORD PTR [rdi], 775946532
        ret

Answer 6

si usar solo C ++ 11 es una necesidad (&a)[N] es una forma de capturar arreglos. Esto le permite escribir una sola función recursiva sin utilizar las funciones de ayuda en absoluto:

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;
}

asignándolo a un 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;
}

Prueba

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

Salida

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

Uno realmente tiene que apreciar la capacidad de C ++ para calcular cualquier cosa computable en el momento de la compilación. Seguramente todavía sopla mi mente ( <> ).

Para las versiones posteriores, yakk''s respuesta de yakk''s C ++ 14 y C ++ 17 ya cubre eso maravillosamente.