Ответ 1
Запрашивая, как инициализировать вектор, в основном запрашивается учебник. Google использует некоторые из руководств Intel для использования встроенных функций. Я собираюсь притвориться, что вопрос не является тривиальным, и ответьте на попытку эффективно реализовать эту функцию. Это определенно не та функция, которую вы бы попытались векторизовать как общий новичок.
См. x86 теги wiki для ссылки на документы, особенно. Интеллектуальное руководство Intel. См. sse теги wiki для ссылки на a очень приятное введение в SIMD-программирование с использованием встроенных SSE и, как эффективно использовать SIMD, среди других ссылок.
Сводка содержания:
- Развертывание/векторизация бесплатно
v % salt_length. - Как вы могли бы векторизовать
v++; v %= loop_invariant;, если это не была сила 2 или константа времени компиляции. Включает ответ на вопрос заголовка об использовании_mm_set_epi8или других способов инициализации вектора для этой цели. - Как начать векторизацию сложного цикла следующим образом: начните с разворачивания, чтобы найти последовательные зависимости.
-
непроверенная версия полной функции, которая векторизовывает все, кроме
% iи swap. (т.е. векторизация всех операций, которые были дешевы в любом случае, как вы просили).-
(v + salt[v] + p)(и все, что ведет к нему) векторизовывает две инструкцииvpaddw. Установка префикс-суммы вне цикла для векторизацииpбыла сложной, но в конце концов она тоже была пронумерована. -
Подавляющее большинство времени выполнения функции будет находиться в скалярном внутреннем цикле над вектором элементов
j, узкое место наdiv(или что-то, что может сделать SVML), и/или промахи в кеше с очень большие строки.
-
Весь цикл не может легко векторизовать, потому что свопы с псевдослучайными индексами создают непредсказуемую последовательную зависимость. Использование AVX512 собирать + перетасовку + разброс, с AVX512CD для поиска битмаксов конфликта, возможно, будет, но это должен быть отдельный вопрос. Я не уверен, как трудно было бы это сделать эффективно, или если бы вы часто повторяли векторный перетасовки много раз, делали только прогресс в одном не конфликтующем элементе.
Так как salt_length = sizeof(size_t) - это константа времени компиляции и мощность 2 меньше длины вашего вектора, v++ и v%=salt_length не требуют никакого кода внутри цикла на всех и происходит бесплатно как побочный эффект эффективного разворачивания цикла для выполнения нескольких v значений параллельно.
(Использование зависимого от платформы размера соли означает, что 32-битная сборка не сможет обрабатывать данные, созданные с помощью 64-битной соли. Даже x32 ABI имеет 32-разрядный size_t, поэтому переход на uint64_t будет кажется, имеет смысл, если вам не нужно делиться солеными хешами между машинами.)
В скалярном цикле v следует повторяющийся шаблон 0 1 2 3 0 1 2 3... (или 0..7 для 64-битного). В векторном коде мы делаем, возможно, 8 v значений сразу с элементами 4B в 32-байтовом векторе или 16 итераций одновременно с элементами 2B.
Итак, v становится вектором константы цикла. Интересно, что так же salt[v], поэтому нам не нужно делать никаких поисков соляных таблиц внутри цикла. Фактически, v+salt[v] может быть предварительно вычислен для скалярного и векторного.
Скалярная версия должна предварительно вычислить v+salt[v] и развернуть на 4 или 8, также удалив поиск LUT, чтобы вся пропускная способность памяти/кеша была доступна для фактических свопов. Компилятор, вероятно, не сделает этого для вас, поэтому вам, вероятно, потребуется развернуть вручную и написать дополнительный код для обработки последнего нечетного числа строковых байтов. (Без разворачивания вы все равно можете предварительно вычислить таблицу поиска v+salt[v] с типом, достаточно широким, чтобы не обернуться).
Даже убедившись, что salt_length известно во время компиляции, также позволит значительно улучшить код. v %= compile_time_constant дешевле, чем a div insn, и чрезвычайно дешево, когда он имеет силу 2. (Он просто превращается в v &= 7). Возможно, компилятор сделает это для вас, если скалярная версия может быть встроена или если вы использовали salt_length = sizeof(size_t) вместо того, чтобы передавать ее как функцию arg вообще.
Если вы еще не знаете salt_length:, то есть, что @harold предлагал, прежде чем вы раскрыли критическую информацию о salt_length:
Поскольку мы знаем v < salt_length для начала, нам понадобится не более одного v -= salt_length, чтобы вернуть его обратно в правый диапазон и сохранить этот инвариант. Это называется "сокращением силы", поскольку вычитание является более слабой (и более дешевой) операцией, чем деление.
// The scalar loop would benefit from this transformation, too.
// or better, unroll the scalar loop by 8 so everything becomes constant
v++;
if( v >= salt_length)
v-= salt_length;
Чтобы векторизовать только это: допустим, что все, что мы знаем, salt_length <= 16, поэтому мы можем использовать вектор из 32 значений uint8_t. (И мы можем использовать pshufb для векторизации поиска salt[v] LUT).
// untested // Vectorizing v++; v %= unknown_loop_invariant_value;
if (!salt_length) return;
assert(salt_length <= 16); // so we can use pshufb for the salt[v] step
__m256i vvec = _mm256_setr_epi8( // setr: lowest element first, unlike set
0%salt_length, 1%salt_length, 2%salt_length, 3%salt_length,
4%salt_length, 5%salt_length, 6%salt_length, 7%salt_length,
8%salt_length, 9%salt_length, 10%salt_length, 11%salt_length,
12%salt_length, 13%salt_length, 14%salt_length, 15%salt_length,
16%salt_length, 17%salt_length, 18%salt_length, 19%salt_length,
20%salt_length, 21%salt_length, 22%salt_length, 23%salt_length,
24%salt_length, 25%salt_length, 26%salt_length, 27%salt_length,
28%salt_length, 29%salt_length, 30%salt_length, 31%salt_length);
__m256i v_increment = _mm256_set1_epi8(32 % salt_length);
__m256i vmodulus = _mm256_set1_epi8(salt_length);
// salt_lut = _mm256_set1_epi64x(salt_byval); // for known salt length. (pass it by val in a size_t arg, instead of by char*).
// duplicate the salt into both lanes of a vector. Garbage beyond salt_length isn't looked at.
__m256i salt_lut = _mm256_broadcastsi128_si256(_mm_loadu_si128(salt)); // nevermind that this could segfault if salt is short and at the end of a page.
//__m256i v_plus_salt_lut = _mm256_add_epi8(vvec, salt_lut); // not safe with 8-bit elements: could wrap
// We could use 16-bit elements and AVX512 vpermw (or vpermi2w to support longer salts)
for (...) {
vvec = _mm256_add_epi8(vvec, v_increment); // ++v;
// if(!(salt_length > v)) { v-= salt_length; }
__m256i notlessequal = _mm256_cmpgt_epi8(vmodulus, vvec); // all-ones where salt_length > v.
// all-zero where salt_length <= v, where we need to subtract salt_length
__m256i conditional_sub = _mm256_and_si256(notlessequal, vmodulus)
vvec = _mm256_sub_epi8(vvec, conditional_sub); // subtract 0 or salt_length
// salt[v] lookup:
__m256i saltv = _mm256_shuffle_epi8(salt_lut, vvec); // salt[v]
// then maybe pmovzx and vextracti128+pmovzx to zero-extend to 16-bit elements? Maybe vvec should only be a 16-bit vector?
// or unpack lo/hi with zeros (but that behaves differently from pmovzx at the lane boundary)
// or have vvec already holding 16-bit elements with the upper half of each one always zero. mask after the pshufb to re-zero,
// or do something clever with `vvec`, `v_increment` and `vmodulus` so `vvec` can have `0xff` in the odd bytes, so pshufb zeros those elements.
}
Конечно, если бы мы знали, что salt_length имеет мощность 2, мы должны были просто замаскировать все, кроме соответствующих младших бит в каждом элементе:
vvec = _mm256_add_epi8(vvec, _mm256_set1_epi8(salt_length)); // ++v;
vvec = _mm256_and_si256(vvec, _mm256_set1_epi8(salt_length - 1)); // v &= salt_length - 1; // aka v%=salt_length;
Заметив, что мы начали с неправильного размера элемента, мы понимаем, что только векторизация одной строки за раз была плохой идеей, потому что теперь нам нужно изменить весь код, который мы уже писали, чтобы использовать более широкие элементы, иногда требуя другая стратегия, чтобы сделать то же самое.
Конечно, вам нужно начать с грубого наброска, умственного или записанного, поскольку вы можете делать каждый шаг отдельно. В процессе размышления об этом вы видите, как разные части могут соответствовать друг другу.
Для сложных циклов полезным первым шагом может быть попытка вручную развернуть скалярный цикл. Это поможет найти последовательные зависимости и все, что упрощается при разворачивании.
(stuff) % i: жесткая часть
Нам нужны элементы, достаточно широкие, чтобы удерживать максимальное значение i, потому что i не является степенью 2, а не константой, так что по модулю операция выполняется. Все шире - это отходы и сокращает нашу пропускную способность. Если бы мы могли векторизовать весь остаток цикла, возможно, стоило бы специализировать функцию с разными версиями для разных диапазонов str_length. (Или, может быть, цикл с элементами 64b до я <= UINT32_MAX, затем цикл до я <= UINT16_MAX и т.д.). Если вы знаете, что вам не нужно обрабатывать строки > 4GiB, вы можете ускорить общий случай, используя только 32-битную математику. (64-разрядное деление медленнее, чем 32-битное деление, даже если верхние биты равны нулю).
На самом деле, я думаю, что нам нужны такие элементы, как максимум p, так как он продолжает накапливаться навсегда (пока он не обернется на 2 ^ 64 в исходном скалярном коде). В отличие от постоянного модуля, мы не можем просто использовать p%=i, чтобы держать его под контролем, хотя modulo является дистрибутивным. (123 % 33) % (33-16) != 123 % (33-16). Даже выравнивание до 16 не помогает: 12345% 32!= 12345% 48% 32
Это приведет к тому, что p будет слишком большим для повторного условного вычитания i (пока маска условия не будет ложной) даже при довольно больших значениях i.
Есть трюки для modulo по известным целочисленным константам (см. http://libdivide.com/), но AFAIK разрабатывает мультипликативный модульный обратный для соседнего делитель (даже с силовым шагом, равным 16), не легче, чем для совершенно отдельного номера. Таким образом, мы не могли бы недорого просто настроить константы для следующего вектора значений i.
Закон малых чисел, возможно, стоит того, чтобы очистить последнюю пару
векторных итераций с предварительно вычисленными векторами мультипликативных модулярных инверсий
поэтому % i можно сделать с помощью векторов. Как только мы приблизимся к концу строки, он, вероятно, будет горячим в кеше L1, поэтому мы полностью ограничены в div, а не подкачки/хранилища. Для этого мы могли бы использовать пролог, чтобы достичь значения i, которое было кратно 16, поэтому последние несколько векторов при приближении к я = 0 всегда имеют одинаковое выравнивание значений i. Или иначе у нас будет LUT констант для диапазона значений i, и просто сделайте от него неуравновешенные нагрузки. Это означает, что нам не нужно вращать salt_v и p.
Возможно, преобразование в FP было бы полезно, поскольку последние процессоры Intel (особенно Skylake) имеют очень мощное аппаратное обеспечение FP с существенной конвейерной обработкой (пропускная способность: коэффициент латентности). Если мы сможем получить точные результаты с правильным выбором округления, это было бы здорово. (float и double могут точно представлять любое целое число до размера их мантиссы.)
Я думаю, стоит попробовать Intel _mm_rem_epu16 (с вектором i значений, которые вы уменьшаете с помощью вектора set1(16)). Если они используют FP для получения точных результатов, это здорово. Если он просто распаковывается в скалярный и выполняет целочисленное деление, он будет тратить время на получение значений обратно в векторе.
Во всяком случае, самым легким решением является итерация векторных элементов со скалярным циклом. Пока вы не придумаете что-то необычное, использующее AVX512CD для свопов, это кажется разумным, но, вероятно, примерно на порядок медленнее, чем просто свопы, если они все горячие в кэше L1.
(untest) частично-векторный вариант функции:
Здесь код в проводнике компилятора Godbolt с полными комментариями к проектам, включая диаграммы, которые я сделал при вычислении префикса SIMD -sum algo. В конце концов я вспомнил, что видел более узкую версию этого как строительный блок в @ZBoson с плавающей запятой SSE Prefix sum answer, но только после того,.
// See the godbolt link for full design-notes comments
// comments about what makes nice ASM or not.
#include <stdint.h>
#include <stdlib.h>
#include <immintrin.h>
#include <assert.h>
static inline
__m256i init_p_and_increment(size_t salt_length, __m256i *p_increment, __m256i saltv_u16, __m128i saltv_u8)
{ // return initial p vector (for first 16 i values).
// return increment vector by reference.
if (salt_length == 4) {
assert(0); // unimplemented
// should be about the same as length == 8. Can maybe factor out some common parts, like up to psum2
} else {
assert(salt_length == 8);
// SIMD prefix sum for n elements in a vector in O(log2(n)) steps.
__m128i sv = _mm256_castsi256_si128(saltv_u16);
__m128i pshift1 = _mm_bslli_si128(sv, 2); // 1 elem (uint16_t)
__m128i psum1 = _mm_add_epi16(pshift1, sv);
__m128i pshift2 = _mm_bslli_si128(psum1, 4); // 2 elem
__m128i psum2 = _mm_add_epi16(pshift2, psum1);
__m128i pshift3 = _mm_bslli_si128(psum2, 8); // 4 elem
__m128i psum3 = _mm_add_epi16(pshift3, psum2); // p_initial low 128. 2^3 = 8 elements = salt_length
// psum3 = the repeating pattern of p values. Later values just add sum(salt[0..7]) to every element
__m128i p_init_low = psum3;
__m128i sum8_low = _mm_sad_epu8(saltv_u8, _mm_setzero_si128()); // sum(s0..s7) in each 64-bit half
// alternative:
// sum8_low = _mm_bsrli_si128(p_init_low, 14); // has to wait for psum3 to be ready: lower ILP than doing psadbw separately
__m256i sum8 = _mm256_broadcastw_epi16(sum8_low);
*p_increment = _mm256_slli_epi16(sum8, 1); // set1_epi16(2*sum(salt[0..7]))
__m128i p_init_high = _mm_add_epi16(p_init_low, _mm256_castsi256_si128(sum8));
__m256i p_init = _mm256_castsi128_si256(p_init_low);
p_init = _mm256_inserti128_si256(p_init, p_init_high, 1);
// not supported by gcc _mm256_set_m128i(p_init_high, psum3);
return p_init;
}
}
void
hashids_shuffle_simd(char *restrict str, size_t str_length, size_t salt_byval)
{
//assert(salt_length <= 16); // so we can use pshufb for the salt[v] step for non-constant salt length.
// platform-dependent salt size seems weird. Why not uint64_t?
size_t salt_length = sizeof(size_t);
assert(str_length-1 < UINT16_MAX); // we do p + v + salt[v] in 16-bit elements
// TODO: assert((str_length-1)/salt_length * p_increment < UINT16_MAX);
__m128i saltv_u8;
__m256i v, saltv;
if(salt_length == 4) {
v = _mm256_set1_epi64x(0x0003000200010000); // `v%salt_length` is 0 1 2 3 repeating
saltv_u8 = _mm_set1_epi32( salt_byval );
saltv = _mm256_cvtepu8_epi16( saltv_u8 ); // salt[v] repeats with the same pattern: expand it to 16b elements with pmovzx
} else {
assert(salt_length == 8);
v = _mm256_cvtepu8_epi16( _mm_set1_epi64x(0x0706050403020100) );
saltv_u8 = _mm_set1_epi64x( salt_byval );
saltv = _mm256_cvtepu8_epi16( saltv_u8 );
}
__m256i v_saltv = _mm256_add_epi16(v, saltv);
__m256i p_increment;
__m256i p = init_p_and_increment(salt_length, &p_increment, saltv, saltv_u8);
for (unsigned i=str_length-1; i>0 ; /*i-=16 */){
// 16 uint16_t j values per iteration. i-- happens inside the scalar shuffle loop.
p = _mm256_add_epi16(p, p_increment); // p += salt[v]; with serial dependencies accounted for, prefix-sum style
__m256i j_unmodded = _mm256_add_epi16(v_saltv, p);
// size_t j = (v + saltv[v] + p) % i;
//////// scalar loop over 16 j elements, doing the modulo and swap
// alignas(32) uint16_t jbuf[16]; // portable C++11 syntax
uint16_t jbuf[16] __attribute__((aligned(32))); // GNU C syntax
_mm256_store_si256((__m256i*)jbuf, j_unmodded);
const int jcount = sizeof(jbuf)/sizeof(jbuf[0]);
for (int elem = 0 ; elem < jcount ; elem++) {
if (--i == 0) break; // in fact returns from the whole function.
// 32-bit division is significantly faster than 64-bit division
unsigned j = jbuf[elem] % (uint32_t)i;
// doubtful that vectorizing this with Intel SVML _mm_rem_epu16 would be a win
// since there no hardware support for it. Until AVX512CD, we need each element in a gp reg as an array index anyway.
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
}
Это компилируется в asm, который выглядит правильно, но я его не запускал.
Кланг делает довольно разумный внутренний цикл. Это для -fno-unroll-loops для удобства чтения. Оставьте это для производительности, хотя это не будет иметь значения здесь, поскольку накладные расходы на петлях не являются узким местом.
# The loop part of clang3.8.1 output. -march=haswell -fno-unroll-loops (only for human readability. Normally it unrolls by 2).
.LBB0_6: # outer loop # in Loop: Header=BB0_3 Depth=1
add esi, 1
.LBB0_3: # first iteration entry point # =>This Loop Header: Depth=1
vpaddw ymm2, ymm2, ymm1 # p += p_increment
vpaddw ymm3, ymm0, ymm2 # v+salt[v] + p
vmovdqa ymmword ptr [rsp], ymm3 # store jbuf
add esi, -1
lea r8, [rdi + rsi]
mov ecx, 1
.LBB0_4: # inner loop # Parent Loop BB0_3 Depth=1
# gcc version fully unrolls the inner loop, leading to code bloat
test esi, esi # if(i==0) return
je .LBB0_8
movzx eax, word ptr [rsp + 2*rcx - 2] # load jbuf
xor edx, edx
div esi
mov r9b, byte ptr [r8] # swap
mov al, byte ptr [rdi + rdx]
mov byte ptr [r8], al
mov byte ptr [rdi + rdx], r9b
add esi, -1
add r8, -1
cmp rcx, 16 # silly clang, not macro-fusing cmp/jl because it wants to use a weird way to increment.
lea rcx, [rcx + 1]
jl .LBB0_4 # inner loop
jmp .LBB0_6 # outer loop
# The loop part of clang3.8.1 output. -march=haswell -fno-unroll-loops (only for human readability. Normally it unrolls by 2).
.LBB0_6: # outer loop # in Loop: Header=BB0_3 Depth=1
add esi, 1
.LBB0_3: # first iteration entry point # =>This Loop Header: Depth=1
vpaddw ymm2, ymm2, ymm1 # p += p_increment
vpaddw ymm3, ymm0, ymm2 # v+salt[v] + p
vmovdqa ymmword ptr [rsp], ymm3 # store jbuf
add esi, -1
lea r8, [rdi + rsi]
mov ecx, 1
.LBB0_4: # inner loop # Parent Loop BB0_3 Depth=1
# gcc version fully unrolls the inner loop, leading to code bloat
test esi, esi # if(i==0) return
je .LBB0_8
movzx eax, word ptr [rsp + 2*rcx - 2] # load jbuf
xor edx, edx
div esi
mov r9b, byte ptr [r8] # swap
mov al, byte ptr [rdi + rdx]
mov byte ptr [r8], al
mov byte ptr [rdi + rdx], r9b
add esi, -1
add r8, -1
cmp rcx, 16 # silly clang, not macro-fusing cmp/jl because it wants to use a weird way to increment.
lea rcx, [rcx + 1]
jl .LBB0_4 # inner loop
jmp .LBB0_6 # outer loop