Телеграмм чат группы ProCxx страница 15629

Я имел в виду ситуацию, когда у тебя 64*N бит - цикл, на каждой итерации которого строго 64 бита обрабатывается. Если округлять хранилище бит до кратного 64, то цикла всегда достаточно. Если же не округлять, после цикла будет иф с проверкой, не осталось ли "хвоста"

источник

19:05пожаловаться #10

AT

Anatoly Tomilov in pro.cxx

я бы сделал через этот же while и для остатка байт доп цикл. Всё это нормально оптимизируется в popcnt

godbolt.org

Compiler Explorer - C++ (x86-64 gcc 9.2)

inline
size_t count(size_t x)
{
size_t n = 0;
while ((x &= (x - 1))) ++n;
return n;
}

int main(int argc, char * argv[])
{
return count(size_t(argc));
}

источник

19:06пожаловаться #11

AT

Anatoly Tomilov in pro.cxx

развёртывание цикла с константным количеством итераций — это наверное с 60-х годов умеют компиляторы

источник

19:07пожаловаться #12

m

magras in pro.cxx

Anatoly Tomilov

я бы сделал через этот же while и для остатка байт доп цикл. Всё это нормально оптимизируется в popcnt

godbolt.org

Compiler Explorer - C++ (x86-64 gcc 9.2)

inline
size_t count(size_t x)
{
size_t n = 0;
while ((x &= (x - 1))) ++n;
return n;
}

int main(int argc, char * argv[])
{
return count(size_t(argc));
}

Замени size_t на char и посмотри что выйдет: https://godbolt.org/z/GP78jv

@smertig об этом и говорит - если оперировать блоками по 64 бита это легко оптимизируется. Если блоки по 8 бит, нужно будет хвост обрабатывать отдельно, так как компилятор не справляется.

godbolt.org

Compiler Explorer - C++ (x86-64 gcc 9.2)

template <class T, std::size_t N>
size_t count(const std::array<T, N>& bits)
{
size_t n = 0;
for (auto x : bits) {
while ((x &= (x - 1))) ++n;
}
return n;
}

int main(int argc, char * argv[])
{
std::array<std::size_t, 8> x;
x.fill(argc);
return count(x);
}

источник

19:39пожаловаться #13

m

magras in pro.cxx

magras

Замени size_t на char и посмотри что выйдет: https://godbolt.org/z/GP78jv

@smertig об этом и говорит - если оперировать блоками по 64 бита это легко оптимизируется. Если блоки по 8 бит, нужно будет хвост обрабатывать отдельно, так как компилятор не справляется.

godbolt.org

Compiler Explorer - C++ (x86-64 gcc 9.2)

template <class T, std::size_t N>
size_t count(const std::array<T, N>& bits)
{
size_t n = 0;
for (auto x : bits) {
while ((x &= (x - 1))) ++n;
}
return n;
}

int main(int argc, char * argv[])
{
std::array<std::size_t, 8> x;
x.fill(argc);
return count(x);
}

Да собственно и не важно, справится компилятор или нет. Важно что обработка этого хвоста не бесплатна.

источник

19:46пожаловаться #14

AT

Anatoly Tomilov in pro.cxx

magras

Замени size_t на char и посмотри что выйдет: https://godbolt.org/z/GP78jv

@smertig об этом и говорит - если оперировать блоками по 64 бита это легко оптимизируется. Если блоки по 8 бит, нужно будет хвост обрабатывать отдельно, так как компилятор не справляется.

godbolt.org

Compiler Explorer - C++ (x86-64 gcc 9.2)

template <class T, std::size_t N>
size_t count(const std::array<T, N>& bits)
{
size_t n = 0;
for (auto x : bits) {
while ((x &= (x - 1))) ++n;
}
return n;
}

int main(int argc, char * argv[])
{
std::array<std::size_t, 8> x;
x.fill(argc);
return count(x);
}

там два прыжка вперёд получаются https://godbolt.org/z/oYsMex

godbolt.org

Compiler Explorer - C++ (x86-64 gcc 9.2)

template<int m>
size_t count(const void * x)
{
size_t n = 0;
int i = 0;
auto x64 = reinterpret_cast<const uint64_t * &>(x);
while (i + std::numeric_limits<uint64_t>::digits <= m) {
auto v = *x64;
while ((v &= (v - 1)) != 0) {
++n;
}
++x64;
i += std::numeric_limits<uint64_t>::digits;
}
auto x32 = reinterpret_cast<const uint32_t * &>(x);
while (i + std::numeric_limits<uint32_t>::digits <= m) {
auto v = *x32;
while ((v &= (v - 1)) != 0) {
++n;
}
++x32;
i += std::numeric_limits<uint32_t>::digits;
}
if (i != m) {
auto x8 = reinterpret_cast<const uint8_t * &>(x);
uint32_t v = *x8;
if (++i != m) {
v <<= 8;
v |= *++x8;
if (++i != m) {
v <<= 8;
v |= *++x8;
}
}
while ((v &= (v - 1)) != 0) {
++n;
}
}
return n;
}

int main(int argc, char…

источник

20:17пожаловаться #15

AT

Anatoly Tomilov in pro.cxx

больше нет оверхеда

источник

20:18пожаловаться #16

AT

Anatoly Tomilov in pro.cxx

не перестаю удивляться, до чего же умные компиляторы

источник

20:19пожаловаться #17

AT

Anatoly Tomilov in pro.cxx

ошибся — вот ещё круче оптимизация со стороны компилятора https://godbolt.org/z/edYaqc (upd: для 117 бит всё намного печальнее)

godbolt.org

Compiler Explorer - C++ (x86-64 gcc 9.2)

источник

20:27пожаловаться #18

m

magras in pro.cxx

Anatoly Tomilov

больше нет оверхеда

In my book два дополнительных цикла - это оверхед, который устраняется паддингом. Это увеличивает размер реально исполняемого кода, что например влияет на кеширование.

Согласен что такое решение может быть полезно. Но оно дороже в поддержке и дает спорное преимущество.

источник

20:28пожаловаться #19

AT

Anatoly Tomilov in pro.cxx

magras

In my book два дополнительных цикла - это оверхед, который устраняется паддингом. Это увеличивает размер реально исполняемого кода, что например влияет на кеширование.

Согласен что такое решение может быть полезно. Но оно дороже в поддержке и дает спорное преимущество.

там нет циклов

источник

20:29пожаловаться #20