утверждение времени компиляции c ++ - PullRequest
Новая
       56

утверждение времени компиляции c ++

3 голосов
/ 03 марта 2011

Я использую макрос, который может быть опасен: 

#define REMAINDER(v, size) ((v) & (size -1))

очевидно, что предполагается, что размер является степенью 2.

Я хотел бы убедиться, что размер действительно является степенью 2, но во время компиляции. (тестирование во время выполнения легко, но это НЕ то, что я хочу).

Достаточным тестом для меня будет то, что размер всегда является константой (а не переменной).

Я бы использовал BOOST_STATIC_ASSERT, но я не могу понять, как использовать его для того, что мне нужно.

Ответы [ 5 ]

6 голосов
/ 03 марта 2011

Перво-наперво: микрооптимизация не нужна.Любой приличный компилятор с включенной оптимизацией преобразует a % b в эту конструкцию, когда b является постоянной времени компиляции, которая на самом деле является степенью 2.

Затем в конкретном утверждении вы можете использовать ту же конструкцию дляподтвердите это [*]: 

BOOST_STATIC_ASSERT( !(size & (size-1)) );

[*] Обратите внимание, что, как указывает Матье М, это работает, только если size является беззнаковым типом.И это должно быть подтверждено - меньшее требование, чтобы аргумент был неотрицательным, не может быть заявлено во время компиляции: 

BOOST_STATIC_ASSERT( (X(0)-1) > X(0) ); // where X is the type of the argument

РЕДАКТИРОВАТЬ после последнего комментария:

Вы упускаете суть здесь,Для работы макроса статического утверждения size должна быть постоянной времени компиляции.Если это постоянная времени компиляции, тогда просто укажите , когда постоянная определена , что также является лучшим местом, поскольку она будет служить документацией и будет указывать на точную точку кода, которая нуждается в модификации: 

template <typename N>
class hash_map {
public:
   const std::size_t size = N;
   BOOST_STATIC_ASSERT( !(size & (size-1) ) ); // N must be power of 2 for fast %
   //...
};

В то же время утверждение о том, что инвариант хранится во время компиляции, важно для эффективности, поэтому скрытие кода не таково: просто оставьте операцию по модулю на месте, так как компилятор оптимизирует: 

std::size_t hash_map::index_of( std::size_t hash ) const {
   return hash % size;
}

Поскольку size является постоянной времени компиляции, и это степень двух (вы утверждали, что раньше), оптимизатор переведет % в оптимизированную операцию, в то время как код все еще читается людьми, которым требуетсяподдерживать его.

5 голосов
/ 03 марта 2011

РЕДАКТИРОВАТЬ: Если у вас нет профильных доказательств того, что это узкое место в вашем коде И что ваш компилятор не оптимизирует что-то вроде (v% 8) надлежащим образом, просто напишите очевидный код.

В противном случае, так как выВы имеете дело с целыми числами здесь, вы можете использовать шаблон вместо макроса?Тогда вы сможете статически утверждать внутри шаблона, так что он будет отмечаться, когда он создается неправильно.

Например, что-то вроде: 

template <int size>
int remainder(int v)
{
    BOOST_STATIC_ASSERT(!(size & (size - 1)));

    return v & (size -1);
};
3 голосов
/ 03 марта 2011

подтвердить: 

size && (size & (size - 1) == 0)

РЕДАКТИРОВАТЬ: Объяснение.

Если размер равен степени двух, устанавливается только один бит.Вычитание 1 даст значение, в котором установлены все биты до оригинала.И это дает 0.

Если размер равен , а не , то степень двух устанавливается как минимум в два бита.Вычитание 1 даст значение, в котором установлены все биты до самого низкого установленного бита оригинала.ANDing не даст 0, так как второй и последующий (справа) биты все еще установлены. 

1000 & 0111 == 0000
1100 & 1011 == 1000
2 голосов
/ 03 марта 2011 
// Only use this if size is a power of 2
#define REMAINDER(v, size) ((v) & (size -1))

Не относитесь к своим пользователям как к идиотам. Документируйте свои функции и макросы и двигайтесь дальше.

В качестве альтернативы, если вы действительно должны общаться с людьми, используйте шаблон: 

template <size_t SIZE>
size_t remainder(size_t v) {
   // Perform whatever assertions you like on SIZE here

   return v & (SIZE - 1);
}

Обратите внимание, что я должен был сделать некоторые предположения о типе ввода и вывода.

1 голос
/ 03 марта 2011

Оптимизация глазка : Оптимизация выполняется по очень небольшому набору инструкций

Это включает в себя:

  • Сворачивание констант : например, здесь size - 1 будет оцениваться во время компиляции, если size является постоянной
  • Снижение прочности : заключающееся в замене медленных операций более быстрыми ... когда результат эквивалентен (очевидно)

Теперь давайте рассмотрим пример этого с использованием внутреннего оптимизатора LLVM : 

// C
int iremainder(int i) { return i % 4; }

unsigned uremainder(unsigned u) { return u % 4; }

// LLVM IR
define i32 @iremainder(i32 %i) nounwind readnone {
entry:
  %0 = srem i32 %i, 4                             ; <i32> [#uses=1]
  ret i32 %0
}

define i32 @uremainder(i32 %u) nounwind readnone {
entry:
  %0 = and i32 %u, 3                              ; <i32> [#uses=1]
  ret i32 %0
}

Давайте проанализируем, не так ли?

  • u / 4 дает and i32 %u, 3 (что в переводе на C дает u & 3)
  • i / 4 дает srem i32 %i, 4 (что в переводе на C дает i % 4)

Какой умный компилятор ! Он не забыл, что выполнение побитовых операций со знаковыми целыми числами не приведет к желаемому результату (всякий раз, когда целое число отрицательно, а ветви стоят дороже, чем деления).

Боевой дух: Этот вид оптимизации практически бесполезен, и вы даже ошиблись.

...