Инструкция Find First Set (ffs) для повышения точности uint512_t

Я разрабатываю алгоритм, который использует __builtin_ffsll() с типом uint64_t.

Я хочу переключиться на 512-битное поле с помощью библиотеки повышения точности (я работаю на машине с поддержкой avx512).

Есть ли функция, аналогичная упомянутой встроенной? В качестве альтернативы, как я могу эффективно реализовать такую ​​​​функциональность для 512-битных целых чисел?


c++ boost bit-manipulation avx512 boost-multiprecision
person Purple    schedule 02.10.2019    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Из документация:

unsigned lsb(const number-or-expression-template-type& x);

Возвращает (отсчитываемый от нуля) индекс младшего значащего бита, для которого установлено значение 1.

Выдает std::range_error, если аргумент равен <= 0.

ffs() основан на единице, поэтому добавление 1 к возвращаемому значению lsb() сделает его эквивалентным. Редактировать: И, как уже отмечалось, принимая во внимание случай передачи 0.

Может быть, что-то вроде

unsigned ffs512(const boost::multiprecision::uint512_t &n) {
  if (n.is_zero()) {
    return 0;
  } else {
    return boost::multiprecision::lsb(n) + 1;
  }
}
person Shawn    schedule 02.10.2019
comment
Также обратите внимание на другое поведение для ввода == 0. Похоже, что lsb предназначен для переноса таких вещей, как инструкция bsf x86, которая устанавливает флаг только тогда, когда ввод равен нулю; он не записывает полезное значение в выходной регистр. Но ffs обрабатывает случай input==0, возвращая 0. - person Peter Cordes; 03.10.2019
comment
Действительно ли lsb для 512-битного целого числа компилируется в последовательность AVX512, которая использует vptestmd/vpcompressd или подобное для поиска первого ненулевого двойного слова, а затем vmovd для извлечения его в целочисленный регистр для tzcnt? (Или используя 2x 256-битные векторы, чтобы не переводить ЦП в 512-битный режим SIMD.) ОП хочет, чтобы это было эффективно на x86, предположительно с gcc и/или clang с -O3 -march=skylake-avx512 - person Peter Cordes; 03.10.2019
comment
@PeterCordes Я предполагаю, что серверная часть GMP вызывает mpz_scan1(). Ни малейшего понятия об остальных. - person Shawn; 03.10.2019
comment
В Godbolt не установлена ​​серверная часть GMP :/ С переносимой серверной частью CPP gcc и clang используют циклы qword для проверки ненулевого фрагмента, а затем tzcnt его. godbolt.org/z/qEq_QE. GCC по-прежнему выдает функции, создающие исключения, но ffs512 оптимизирует любые потенциальные вызовы к ним. AVX2, чтобы просто найти правильный индекс dword или qword для скалярной нагрузки, также был бы хорош, по сравнению с идеей AVX512, которую я предложил ранее. mpz_scan1() просто написан на C (gmplib.org/repo/gmp/file /tip/mpz/scan1.c), который использует тот же поиск конечностей (в short_cut:), что и битовое сканирование с нулевым концом. - person Peter Cordes; 03.10.2019
comment
@PeterCordes Я думаю, что GMP имеет только общую версию mp[nz]_scan1, потому что она никогда не была ограничивающим фактором по сравнению с умножениями или худшими делениями и gcd. Если вы считаете, что это полезно, и вы можете предоставить более быструю версию для больших сканирований, которая существенно не замедляет распространенный случай, когда сканирование почти сразу находит 1 бит, вы можете попробовать внести его в GMP. Но на самом деле у OP более простой случай, когда он всегда сканирует с самого начала. И текущий lsb, вероятно, достаточно быстр для них. - person Marc Glisse; 03.10.2019
comment
@MarcGlisse: да, версия GMP должна быть гораздо более гибкой, а размер не является константой времени компиляции. Я думаю, что мы могли бы обнаружить большое количество конечностей с помощью одной дополнительной проверки, которая может быть незначительной для небольшого количества. Но если первый 1 находится в первой конечности, то да, чистый скаляр все же намного лучше (также позволяет избежать любого риска остановки переадресации хранилища из-за широкой нагрузки). Так что, возможно, вы захотите начать с этого и смотреть только на размер, возможно, для поиска SIMD, если он не найден в первой конечности. Если он не найден в первых 64 битах, его, вероятно, нет и в следующих 64 битах для больших n. - person Peter Cordes; 03.10.2019
comment
Похоже, что этот uint512_t определен только для бэкэнда cpp_int, поэтому для этого вопроса не имеет большого значения, как его реализует бэкэнд gmp. - person Shawn; 03.10.2019