Как мне написать поддерживаемую, быструю битовую маску времени компиляции в C++?

Ответ 1

Лучшая версия - c++17:

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

затем

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

Вернувшись в c++14, мы можем сделать этот странный трюк:

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

или, если мы застряли с c++11, мы можем решить это рекурсивно:

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

Годболт со всеми 3 - вы можете переключить CPP_VERSION определить и получить идентичную сборку.

На практике я бы использовал самое современное, что мог. 14 бьет 11, потому что у нас нет рекурсии и, следовательно, O (n ^ 2) длины символа (что может взорвать время компиляции и использование памяти компилятора); 17 бьет 14, потому что компилятору не нужно ничего кодировать, исключать этот массив, и этот трюк с массивом просто ужасен.

Из этих 14 самый запутанный. Здесь мы создаем анонимный массив всех нулей, а в качестве побочного эффекта создаем наш результат, а затем отбрасываем массив. У отброшенного массива есть число 0, равное размеру нашего пакета, плюс 1 (который мы добавляем, чтобы мы могли обрабатывать пустые пакеты).

Подробное объяснение того, что делает версия c++14. Это хитрость/хитрость, и тот факт, что вы должны сделать это для расширения пакетов параметров с эффективностью в C+ +1 4, является одной из причин, почему сложенные выражения были добавлены в c++17.

Это лучше всего понять изнутри:

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

это просто обновляет r с 1<<indexes для фиксированного индекса. indexes - это пакет параметров, поэтому нам придется его расширить.

Остальная часть работы заключается в предоставлении пакета параметров для расширения indexes внутри.

Один шаг:

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

здесь мы приводим наше выражение к void, указывая, что мы не заботимся о его возвращаемом значении (мы просто хотим побочный эффект установки r - в C+ +, выражения типа a |= b также возвращают значение, для которого они устанавливают a).

Затем мы используем оператор запятой , и 0, чтобы отбросить void "значение", и возвращает значение 0. Так что это выражение, значение которого равно 0 и в качестве побочного эффекта вычисления 0 оно устанавливает бит в r.

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

На этом этапе мы расширяем indexes пакета параметров. Итак, мы получаем:

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

в {}. Это использование , не оператор запятой, а разделитель элемента массива. Это sizeof...(indexes)+1 0 с, который также устанавливает биты в r как побочный эффект. Затем мы назначаем инструкции построения массива {} для discard массива.

Затем мы приводим discard к void - большинство компиляторов предупредит вас, если вы создадите переменную и никогда ее не прочитаете. Все компиляторы не будут жаловаться, если вы приведете его к void, это своего рода способ сказать: "Да, я знаю, я не использую это", поэтому это подавляет предупреждение.

Ответ 2

Оптимизация, которую вы ищете, кажется, петлевая очистка, которая включена в -O3, или вручную с -fpeel-loops. Я не уверен, почему это относится к сфере очистки цикла, а не развертывания цикла, но, возможно, он не желает развернуть цикл с нелокальным потоком управления внутри него (как это, возможно, из проверки диапазона).

Однако по умолчанию GCC не может очистить все итерации, что, по-видимому, необходимо. Экспериментально, передача -O2 -fpeel-loops --param max-peeled-insns=200 (значение по умолчанию - 100) позволяет выполнить работу с вашим исходным кодом: https://godbolt.org/z/NNWrga

Ответ 3

если использование только C++ 11 является обязательным (&a)[N] - это способ захвата массивов. Это позволяет вам написать одну рекурсивную функцию без использования вспомогательных функций:

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

присвоение его 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;
}

Тестовое задание

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

Выход

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

действительно нужно ценить C++ способность вычислять что-либо вычисляемое во время компиляции. Это наверняка все еще поражает меня (<>).

В более поздних версиях C++ 14 и C++ 17 ответ Якка уже прекрасно охватывает это.

Ответ 4

Я бы посоветовал вам написать правильный тип EnumSet.

Написание базового EnumSet<E> в С++ 14 (далее) на основе std::uint64_t тривиально:

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

Это позволяет вам написать простой код:

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

    flags &= IMPORTANT;
}

В С++ 11 это требует некоторых сверток, но тем не менее остается возможным:

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

И вызывается с помощью:

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

Даже НКУ тривиальным генерирует and инструкцию по -O1 godbolt:

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

Ответ 5

Начиная с С++ 11 вы также можете использовать классическую технику 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;
}

Ссылка на Compiler Explorer: https://godbolt.org/z/Gk6KX1

Преимущество этого подхода перед шаблонной функцией constexpr заключается в том, что она потенциально немного быстрее компилируется из-за правила Чила.

Ответ 6

Здесь есть некоторые далеко не "умные" идеи. Вы, вероятно, не помогаете в обслуживании, следуя им.

является

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

гораздо проще написать, чем

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

?

Тогда никакой остальной код не нужен.