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

113

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 andinstrucción (que luego se inserta en cualquier otro lugar):

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 probado compila esto en un lío enorme que incluye el manejo de errores que debería ser DCE estáticamente. En otro código, ¡incluso colocará el important_bitsequivalente 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? De no ser así, ¿cómo debería escribir esto para que quede claro, rápido y fácil de mantener?

Alex Reinking
fuente
4
En lugar de usar un bucle, ¿no puedes construir una máscara con B | D | E | ... | O?
HolyBlackCat
6
La enumeración tiene posiciones de bits en lugar de bits ya expandidos, por lo que podría hacerlo(1ULL << B) | ... | (1ULL << O)
Alex Reinking
3
La desventaja es que los nombres reales son largos e irregulares y no es tan fácil ver qué banderas están en la máscara con todo ese ruido de línea.
Alex Reinking
4
@AlexReinking Podrías convertirlo en uno (1ULL << Constant)| por línea, y alinee los nombres de las constantes en las diferentes líneas, eso sería más fácil para los ojos.
einpoklum
Creo que el problema aquí relacionado con la falta de uso del tipo sin firmar, GCC siempre tuvo problemas con la corrección de descarte estático por desbordamiento y conversión de tipo en híbrido firmado / no firmado El resultado del desplazamiento de bits aquí es el intresultado de la operación de bits PUEDE SER intO puede long longdepender del valor y formalmente enumno es equivalente a una intconstante. clang pide "como si", gcc sigue siendo pedante
Swift - Friday Pie

Respuestas:

112

La mejor versión es :

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

Luego

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

de nuevo en , 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 nos quedamos con , podemos resolverlo de forma recursiva:

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 la definición de CPP_VERSION y obtener un ensamblaje idéntico.

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

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


Una explicación detallada de lo que la versión está haciendo. Esto 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 se agregaron expresiones de plegado en.

Se entiende mejor de adentro hacia afuera:

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

esto solo se actualiza rcon 1<<indexespara un índice fijo. indexeses un paquete de parámetros, así que tendremos que expandirlo.

El resto del trabajo es proporcionar un paquete de parámetros para expandir el indexesinterior.

Un paso fuera:

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

aquí convertimos nuestra expresión a void, lo que indica que no nos importa su valor de retorno (solo queremos el efecto secundario de establecer r: en C ++, las expresiones como a |= btambién devuelven el valor que establecieron a).

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

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

En este punto, expandimos el paquete de parámetros indexes. Entonces 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 s, que también establece bits como efecto secundario. Luego asignamos las instrucciones de construcción de la matriz a una matriz .sizeof...(indexes)+1 0r{}discard

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

Yakk - Adam Nevraumont
fuente
38
Lo siento, pero ese código C ++ 14 es algo. No se que.
James
14
@James Es un maravilloso ejemplo motivador de por qué las expresiones de plegado en C ++ 17 son muy bienvenidas. Este, y otros trucos similares, resultan ser una forma eficaz de expandir un paquete "in situ" sin recursividad y que los cumplidores encuentran fácil de optimizar.
Yakk - Adam Nevraumont
4
@ruben multi line constexpr es ilegal en 11
Yakk - Adam Nevraumont
6
No me veo revisando ese código C ++ 14. Me quedaré con el de C ++ 11 ya que lo necesito, de todos modos, pero incluso si pudiera usarlo, el código de C ++ 14 requiere tanta explicación que no lo haría. Estas máscaras siempre se pueden escribir para tener como máximo 32 elementos, por lo que no me preocupa el comportamiento de O (n ^ 2). Después de todo, si n está acotado por una constante, entonces es realmente O (1). ;)
Alex Reinking
9
Para aquellos que intentan entenderlo ((1ull<<indexes)|...|0ull), es una "expresión de doblez" . Específicamente, es un "pliegue binario a la derecha" y debe analizarse como(pack op ... op init)
Henrik Hansen,
47

La optimización que está buscando parece ser el peeling de bucle, que está habilitado en -O3o manualmente con -fpeel-loops. No estoy seguro de por qué esto cae dentro del alcance del pelado de bucles en lugar del desenrollado de bucles, pero posiblemente no esté dispuesto a desenrollar un bucle con un flujo de control no local dentro de él (como existe, potencialmente, de la verificación 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

Sneftel
fuente
¡Eres increíble, gracias! ¡No tenía idea de que esto fuera configurable en GCC! Aunque por alguna razón -O3 -fpeel-loops --param max-peeled-insns=200falla ... Se debe -ftree-slp-vectorizeaparentemente.
Alex Reinking
Esta solución parece estar limitada al objetivo x86-64. La salida para ARM y ARM64 todavía no es bonita, lo que nuevamente podría ser completamente irrelevante para OP.
tiempo real
@realtime - es algo relevante, en realidad. Gracias por señalar que no funciona en este caso. Es muy decepcionante que GCC no lo detecte antes de bajarlo a un IR específico de la plataforma. LLVM lo optimiza antes de cualquier descenso adicional.
Alex Reinking
10

si usar solo C ++ 11 es imprescindible, (&a)[N]es una forma de capturar matrices. Esto le permite escribir una sola función recursiva sin usar funciones auxiliares 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 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 que sea computable en tiempo de compilación. Seguramente todavía me sorprende ( <> ).


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

Pila de Danny
fuente
3
¿Cómo demuestra esto que apply_known_maskrealmente optimiza?
Alex Reinking
2
@AlexReinking: Todos los bits de miedo lo son constexpr. Y aunque en teoría eso no es suficiente, sabemos que GCC es bastante capaz de evaluar constexprsegún lo previsto.
MSalters
8

Le animo a escribir un EnumSettipo adecuado .

Escribir un básico EnumSet<E>en C ++ 14 (en adelante) basado en std::uint64_tes 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 convoluciones, pero sigue siendo posible de todos modos:

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 trivialmente una andinstrucción en -O1 godbolt :

apply_known_mask(EnumSet<Flags>&):
        and     QWORD PTR [rdi], 775946532
        ret
Matthieu M.
fuente
2
En c ++ 11, gran parte de su constexprcódigo no es legal. Quiero decir, ¡algunos tienen 2 declaraciones! (C ++ 11 constexpr apesta)
Yakk - Adam Nevraumont
@ Yakk-AdamNevraumont: ¿Se dio cuenta de que publiqué 2 versiones del código, la primera para C ++ 14 en adelante y una segunda especialmente diseñada para C ++ 11? (para dar cuenta de sus limitaciones)
Matthieu M.
1
Podría ser mejor usar std :: subyacente_tipo en lugar de std :: uint64_t.
James
@James: En realidad, no. Tenga en cuenta que EnumSet<E>no utiliza un valor de Ecomo valor directamente, sino que utiliza 1 << e. Es un dominio completamente diferente, que es en realidad lo que hace que la clase sea tan valiosa => sin posibilidad de indexar accidentalmente por en elugar de 1 << e.
Matthieu M.
@MatthieuM. Sí tienes razón. Lo estoy confundiendo con nuestra propia implementación, que es muy similar a la suya. La desventaja de usar (1 << e) es que si e está fuera de los límites del tamaño del tipo_de_principal, probablemente sea UB, con suerte un error del compilador.
James
7

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

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 al Explorador del compilador: https://godbolt.org/z/Gk6KX1

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

Michał Łoś
fuente
1

Aquí hay algunas ideas demasiado "inteligentes". Probablemente no esté ayudando a la mantenibilidad siguiéndolos.

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.

Uno
fuente
1
"B", "D", etc. no son banderas en sí mismas.
Michał Łoś
Sí, primero debería transformarlos en banderas. Eso no está del todo claro en mi respuesta. lo siento. Voy a actualizar.
ANuno