Conteo de bits: preprocesador magic vs C++moderno
Supongamos que quiero crear una tabla de búsqueda de conteo de bits construida en tiempo de compilación para enteros de 64 bits en trozos de 16 bits. La única manera que conozco de hacer esto es el siguiente código:
#define B4(n) n, n + 1, n + 1, n + 2
#define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
#define B8(n) B6(n), B6(n + 1), B6(n + 1), B6(n + 2)
#define B10(n) B8(n), B8(n + 1), B8(n + 1), B8(n + 2)
#define B12(n) B10(n), B10(n + 1), B10(n + 1), B10(n + 2)
#define B14(n) B12(n), B12(n + 1), B12(n + 1), B12(n + 2)
#define B16(n) B14(n), B14(n + 1), B14(n + 1), B14(n + 2)
#define COUNT_BITS B16(0), B16(1), B16(1), B16(2)
unsigned int lookup[65536] = { COUNT_BITS };
¿Existe una forma moderna (C++11/14) de obtener el mismo resultado?
5 answers
¿Por qué no usar la biblioteca estándar?
#include <bitset>
int bits_in(std::uint64_t u)
{
auto bs = std::bitset<64>(u);
return bs.count();
}
Ensamblador resultante (Compilado con -O2 -march=native):
bits_in(unsigned long):
xor eax, eax
popcnt rax, rdi
ret
Vale la pena mencionar en este punto que no todos los procesadores x86 tienen esta instrucción, por lo que (al menos con gcc) necesitará hacerle saber para qué arquitectura compilar.
@tambre mencionó que en realidad, cuando puede, el optimizador irá más allá:
volatile int results[3];
int main()
{
results[0] = bits_in(255);
results[1] = bits_in(1023);
results[2] = bits_in(0x8000800080008000);
}
Ensamblador resultante:
main:
mov DWORD PTR results[rip], 8
xor eax, eax
mov DWORD PTR results[rip+4], 10
mov DWORD PTR results[rip+8], 4
ret
Los niños de la vieja escuela como yo necesitan encontrar nuevos problemas a resolver :)
Actualización
No todos estaban contentos de que la solución dependiera de la ayuda de la cpu para calcular el bitcount. Entonces, ¿qué pasa si usamos una tabla autogenerada pero permitimos al desarrollador configurar el tamaño de la misma? (advertencia - largo tiempo de compilación para la versión de tabla de 16 bits)
#include <utility>
#include <cstdint>
#include <array>
#include <numeric>
#include <bitset>
template<std::size_t word_size, std::size_t...Is>
constexpr auto generate(std::integral_constant<std::size_t, word_size>, std::index_sequence<Is...>) {
struct popcount_type {
constexpr auto operator()(int i) const {
int bits = 0;
while (i) {
i &= i - 1;
++bits;
}
return bits;
}
};
constexpr auto popcnt = popcount_type();
return std::array<int, sizeof...(Is)>
{
{popcnt(Is)...}
};
}
template<class T>
constexpr auto power2(T x) {
T result = 1;
for (T i = 0; i < x; ++i)
result *= 2;
return result;
}
template<class TableWord>
struct table {
static constexpr auto word_size = std::numeric_limits<TableWord>::digits;
static constexpr auto table_length = power2(word_size);
using array_type = std::array<int, table_length>;
static const array_type& get_data() {
static const array_type data = generate(std::integral_constant<std::size_t, word_size>(),
std::make_index_sequence<table_length>());
return data;
};
};
template<class Word>
struct use_table_word {
};
template<class Word, class TableWord = std::uint8_t>
int bits_in(Word val, use_table_word<TableWord> = use_table_word<TableWord>()) {
constexpr auto table_word_size = std::numeric_limits<TableWord>::digits;
constexpr auto word_size = std::numeric_limits<Word>::digits;
constexpr auto times = word_size / table_word_size;
static_assert(times > 0, "incompatible");
auto reduce = [val](auto times) {
return (val >> (table_word_size * times)) & (power2(table_word_size) - 1);
};
auto const& data = table<TableWord>::get_data();
auto result = 0;
for (int i = 0; i < times; ++i) {
result += data[reduce(i)];
}
return result;
}
volatile int results[3];
#include <iostream>
int main() {
auto input = std::uint64_t(1023);
results[0] = bits_in(input);
results[0] = bits_in(input, use_table_word<std::uint16_t>());
results[1] = bits_in(0x8000800080008000);
results[2] = bits_in(34567890);
for (int i = 0; i < 3; ++i) {
std::cout << results[i] << std::endl;
}
return 0;
}
Actualización final
Esta versión permite el uso de cualquier número de bits en la tabla de búsqueda y admite cualquier tipo de entrada, incluso si es menor que el número de bits en el tabla de búsqueda.
También cortocircuita si los bits altos son cero.
#include <utility>
#include <cstdint>
#include <array>
#include <numeric>
#include <algorithm>
namespace detail {
template<std::size_t bits, typename = void>
struct smallest_word;
template<std::size_t bits>
struct smallest_word<bits, std::enable_if_t<(bits <= 8)>>
{
using type = std::uint8_t;
};
template<std::size_t bits>
struct smallest_word<bits, std::enable_if_t<(bits > 8 and bits <= 16)>>
{
using type = std::uint16_t;
};
template<std::size_t bits>
struct smallest_word<bits, std::enable_if_t<(bits > 16 and bits <= 32)>>
{
using type = std::uint32_t;
};
template<std::size_t bits>
struct smallest_word<bits, std::enable_if_t<(bits > 32 and bits <= 64)>>
{
using type = std::uint64_t;
};
}
template<std::size_t bits> using smallest_word = typename detail::smallest_word<bits>::type;
template<class WordType, std::size_t bits, std::size_t...Is>
constexpr auto generate(std::index_sequence<Is...>) {
using word_type = WordType;
struct popcount_type {
constexpr auto operator()(word_type i) const {
int result = 0;
while (i) {
i &= i - 1;
++result;
}
return result;
}
};
constexpr auto popcnt = popcount_type();
return std::array<word_type, sizeof...(Is)>
{
{popcnt(Is)...}
};
}
template<class T>
constexpr auto power2(T x) {
return T(1) << x;
}
template<std::size_t word_size>
struct table {
static constexpr auto table_length = power2(word_size);
using word_type = smallest_word<word_size>;
using array_type = std::array<word_type, table_length>;
static const array_type& get_data() {
static const array_type data = generate<word_type, word_size>(std::make_index_sequence<table_length>());
return data;
};
template<class Type, std::size_t bits>
static constexpr auto n_bits() {
auto result = Type();
auto b = bits;
while(b--) {
result = (result << 1) | Type(1);
}
return result;
};
template<class Uint>
int operator()(Uint i) const {
constexpr auto mask = n_bits<Uint, word_size>();
return get_data()[i & mask];
}
};
template<int bits>
struct use_bits {
static constexpr auto digits = bits;
};
template<class T>
constexpr auto minimum(T x, T y) { return x < y ? x : y; }
template<class Word, class UseBits = use_bits<8>>
int bits_in(Word val, UseBits = UseBits()) {
using word_type = std::make_unsigned_t<Word>;
auto uval = static_cast<word_type>(val);
constexpr auto table_word_size = UseBits::digits;
constexpr auto word_size = std::numeric_limits<word_type>::digits;
auto const& mytable = table<table_word_size>();
int result = 0;
while (uval)
{
result += mytable(uval);
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wshift-count-overflow"
uval >>= minimum(table_word_size, word_size);
#pragma clang diagnostic pop
}
return result;
}
volatile int results[4];
#include <iostream>
int main() {
auto input = std::uint8_t(127);
results[0] = bits_in(input);
results[1] = bits_in(input, use_bits<4>());
results[2] = bits_in(input, use_bits<11>());
results[3] = bits_in(input, use_bits<15>());
for (auto&& i : results) {
std::cout << i << std::endl;
}
auto input2 = 0xabcdef;
results[0] = bits_in(input2);
results[1] = bits_in(input2, use_bits<4>());
results[2] = bits_in(input2, use_bits<11>());
results[3] = bits_in(input2, use_bits<15>());
for (auto&& i : results) {
std::cout << i << std::endl;
}
auto input3 = -1;
results[0] = bits_in(input3);
results[1] = bits_in(input3, use_bits<4>());
results[2] = bits_in(input3, use_bits<11>());
results[3] = bits_in(input3, use_bits<15>());
for (auto&& i : results) {
std::cout << i << std::endl;
}
return 0;
}
Ejemplo de salida:
7
7
7
7
17
17
17
17
32
32
32
32
La salida de ensamblado resultante para una llamada a bits_in(int, use_bits<11>()), por ejemplo, se convierte en:
.L16:
mov edx, edi
and edx, 2047
movzx edx, WORD PTR table<11ul>::get_data()::data[rdx+rdx]
add eax, edx
shr edi, 11
jne .L16
Lo cual me parece razonable.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-12-15 07:18:06
Esta es una solución de C++14, construida básicamente alrededor del uso de constexpr:
// this struct is a primitive replacement of the std::array that
// has no 'constexpr reference operator[]' in C++14
template<int N>
struct lookup_table {
int table[N];
constexpr int& operator[](size_t i) { return table[i]; }
constexpr const int& operator[](size_t i) const { return table[i]; }
};
constexpr int bit_count(int i) {
int bits = 0;
while (i) { i &= i-1; ++bits; }
return bits;
}
template<int N>
constexpr lookup_table<N> generate() {
lookup_table<N> table = {};
for (int i = 0; i < N; ++i)
table[i] = bit_count(i);
return table;
}
template<int I> struct Check {
Check() { std::cout << I << "\n"; }
};
constexpr auto table = generate<65536>();
int main() {
// checks that they are evaluated at compile-time
Check<table[5]>();
Check<table[65535]>();
return 0;
}
Versión ejecutable: http://ideone.com/zQB86O
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-07-20 12:59:08
Con c++17 puede usar constexpr para construir la tabla de búsqueda en tiempo de compilación. Con el cálculo de population count la tabla de búsqueda se puede construir de la siguiente manera:
#include <array>
#include <cstdint>
template<std::size_t N>
constexpr std::array<std::uint16_t, N> make_lookup() {
std::array<std::uint16_t, N> table {};
for(std::size_t i = 0; i < N; ++i) {
std::uint16_t popcnt = i;
popcnt = popcnt - ((popcnt >> 1) & 0x5555);
popcnt = (popcnt & 0x3333) + ((popcnt >> 2) & 0x3333);
popcnt = ((popcnt + (popcnt >> 4)) & 0x0F0F) * 0x0101;
table[i] = popcnt >> 8;
}
return table;
}
Uso de la muestra:
auto lookup = make_lookup<65536>();
El std::array::operator[] es constexpr ya que c++17, con c++14 el ejemplo anterior compila pero no será un verdadero constexpr.
Si desea castigar a su compilador, también puede inicializar el std::array resultante con plantillas variádicas. Este la versión también funcionará con c++14 e incluso con c++11 usando el truco de índices .
#include <array>
#include <cstdint>
#include <utility>
namespace detail {
constexpr std::uint8_t popcnt_8(std::uint8_t i) {
i = i - ((i >> 1) & 0x55);
i = (i & 0x33) + ((i >> 2) & 0x33);
return ((i + (i >> 4)) & 0x0F);
}
template<std::size_t... I>
constexpr std::array<std::uint8_t, sizeof...(I)>
make_lookup_impl(std::index_sequence<I...>) {
return { popcnt_8(I)... };
}
} /* detail */
template<std::size_t N>
constexpr decltype(auto) make_lookup() {
return detail::make_lookup_impl(std::make_index_sequence<N>{});
}
Nota: En el ejemplo anterior cambié a los enteros de 8 bits de los enteros de 16 bits.
La versión de 8 bits hará solo 256 argumentos de plantilla para la función detail::make_lookup_impl en lugar de 65536. Este último es demasiado y excederá el máximo de profundidad de instanciación de plantilla. Si tiene más de suficiente memoria virtual, puede aumentar este máximo con la bandera del compilador -ftemplate-depth=65536 en GCC y volver a los enteros de 16 bits.
De todos modos, eche un vistazo a la siguiente demostración y pruebe cómo la versión de 8 bits cuenta los bits establecidos de un entero de 64 bits.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-07-20 09:40:00
Uno más para la posteridad, creando una tabla de búsqueda usando una solución recursiva (de profundidad log(N)). Hace uso de constexpr-if y constexpr-array-operator [], por lo que es mucho C++17.
#include <array>
template<size_t Target, size_t I = 1>
constexpr auto make_table (std::array<int, I> in = {{ 0 }})
{
if constexpr (I >= Target)
{
return in;
}
else
{
std::array<int, I * 2> out {{}};
for (size_t i = 0; i != I; ++i)
{
out[i] = in[i];
out[I + i] = in[i] + 1;
}
return make_table<Target> (out);
}
}
constexpr auto population = make_table<65536> ();
Véalo compilar aquí: https://godbolt.org/g/RJG1JA
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-07-30 07:19:46
for (int x = 0; x < 65536; x++)
{
int mask = 1;
int bitCount = 0;
for (int y = 0; y < 16; y++)
{
if ((mask << y) & x)
bitCount++;
}
lookup_1[x] = bitCount;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-07-27 09:40:47