Самый быстрый способ вычисления абсолютного значения с помощью SSE

Ответ 1

TL; DR: почти во всех случаях используйте pcmpeq/shift для создания маски и/или использовать его. У него самый короткий критический путь (привязанный к константе из памяти ) и не может пропустить кеш-код.

Как сделать это с помощью встроенных функций

Получение компилятора для emit pcmpeqd в неинициализированном регистре может быть сложным. (godbolt). Лучший способ для gcc/icc -

__m128 abs_mask(void){
  // with clang, this turns into a 16B load,
  // with every calling function getting its own copy of the mask
  __m128i minus1 = _mm_set1_epi32(-1);
  return _mm_castsi128_ps(_mm_srli_epi32(minus1, 1));
}
// MSVC is BAD when inlining this into loops
__m128 vecabs_and(__m128 v) {
  return _mm_and_ps(abs_mask(), v);
}


__m128 sumabs(const __m128 *a) { // quick and dirty no alignment checks
  __m128 sum = vecabs_and(*a);
  for (int i=1 ; i < 10000 ; i++) {
      // gcc, clang, and icc hoist the mask setup out of the loop after inlining
      // MSVC doesn't!
      sum = _mm_add_ps(sum, vecabs_and(a[i])); // one accumulator makes addps latency the bottleneck, not throughput
  }
  return sum;
}

clang 3.5 и более поздние версии "оптимизирует" set1/shift для загрузки константы из памяти. Однако он будет использовать pcmpeqd для реализации set1_epi32(-1). TODO: найдите последовательность свойств, которая создает желаемый машинный код с clang. Загрузка константы из памяти не является катастрофой производительности, но наличие каждой функции с использованием другой копии маски довольно ужасно.

MSVC: VS2013:

• _mm_uninitialized_si128() не определен.

• _mm_cmpeq_epi32(self,self) в неинициализированной переменной выдает movdqa xmm, [ebp-10h] в этом тестовом случае (т.е. загружает некоторые неинициализированные данные из стека. Это меньше рискует пропустить кеш, чем просто загружать конечную константу из памяти. Тем не менее, Kumputer говорит, что MSVC не удалось вытащить pcmpeqd/psrld из цикла (я предполагаю, что при встраивании vecabs), поэтому это неприменимо, если вы вручную не встраиваете и не выталкиваете константу из цикла самостоятельно.

• Использование _mm_srli_epi32(_mm_set1_epi32(-1), 1) приводит к тому, что movdqa загружает вектор всех -1 (поднятых вне цикла) и a psrld внутри цикла. Так что совершенно ужасно. Если вы собираетесь загрузить константу 16B, это должен быть конечный вектор. Имея целые инструкции, генерирующие маску, каждая итерация цикла также ужасна.

Предложения для MSVC: отказаться от генерации маски "на лету" и просто написать

const __m128 absmask = _mm_castsi128_ps(_mm_set1_epi32(~(1<<31));

Вероятно, вы просто получите маску, сохраненную в памяти, как константу 16B. Надеемся, что не будет дублироваться для каждой функции, которая его использует. Наличие маски в постоянной памяти более вероятно, будет полезно в 32-битном коде, где у вас есть только 8 регистров XMM, поэтому vecabs может просто ANDPS с операндом источника памяти, если у него нет регистра, свободного для сохранения постоянной лежащий вокруг.

TODO: узнайте, как избежать дублирования константы везде, где она встроена. Вероятно, использование глобальной константы, а не анонимного set1, было бы неплохо. Но тогда вам нужно инициализировать его, но я не уверен, что intrinsics работают как инициализаторы для глобальных переменных __m128. Вы хотите, чтобы он заходил в раздел данных только для чтения, а не для конструктора, который запускается при запуске программы.

В качестве альтернативы используйте

__m128i minus1;  // undefined
#if _MSC_VER && !__INTEL_COMPILER
minus1 = _mm_setzero_si128();  // PXOR is cheaper than MSVC silly load from the stack
#endif
minus1 = _mm_cmpeq_epi32(minus1, minus1);  // or use some other variable here, which will probably cost a mov insn without AVX, unless the variable is dead.
const __m128 absmask = _mm_castsi128_ps(_mm_srli_epi32(minus1, 1));

Дополнительный PXOR довольно дешев, но он все еще является uop и еще 4 байта по размеру кода. Если у кого-то есть лучшее решение для преодоления нежелания MSVC испускать нужный нам код, оставьте комментарий или отредактируйте. Это нехорошо, если вставить в петлю, хотя, потому что pxor/pcmp/psrl все будет внутри цикла.

Загрузка 32-битной константы с помощью movd и трансляция с помощью shufps может быть в порядке (опять же, вам, вероятно, придется вручную вытащить это из цикла). Эти 3 инструкции (mov-немедленный для GP reg, movd, shufps) и movd медленны на AMD, где векторная единица делится между двумя целыми ядрами. (Их версия гиперпотока.)

Выбор лучшей последовательности asm

Хорошо, давайте посмотрим на это, чтобы сказать, что Intel Sandybridge через Skylake, с небольшим упоминанием о Nehalem. См. подсказки для микроархива Agner Fog's и инструкции для того, как я это сделал. Я также использовал номера Skylake, которые были связаны в сообщении на форумах http://realwordtech.com/.

Допустим, что вектор, который мы хотим abs(), находится в xmm0, и является частью длинной цепи зависимостей, как это типично для кода FP.

Итак, допустим, что любые операции, не зависящие от xmm0, могут начать несколько циклов до готовности xmm0. Я тестировал, а инструкции с операндами памяти не добавляют лишнюю задержку в цепочку зависимостей, предполагая, что адрес операнда памяти не является частью цепочки dep (т.е. Не является частью критического пути).

Я не совсем понимаю, как рано операция памяти может начаться, когда она является частью микро-fused uop. Насколько я понимаю, Buffer Re-Order Buffer (ROB) работает с плавными uops, а треки от выхода до выхода на пенсию (от 168 (SnB) до 224 (SKL)). Также есть планировщик, который работает в незанятом домене, имея только uops, которые имеют свои входные операнды, но еще не выполнены. В то же время, когда они декодируются (или загружаются из кеша uop), uops могут входить в ROB (сплавленный) и планировщик (не используется). Если я правильно понимаю это, это от 54 до 64 записей в Sandybridge до Broadwell и 97 в Skylake. Есть некоторые необоснованные предположения о том, что он больше не является планировщиком унифицированного (ALU/load-store).

Там также говорят о том, что Skylake обрабатывает 6 часов в час. Насколько я понимаю, Skylake будет считывать целые строки uop-cache (до 6 uops) за такт в буфер между кэшем uop и ROB. Проблема в ROB/scheduler по-прежнему 4-х. (Даже nop по-прежнему 4 за часы). Этот буфер помогает где границы выравнивания кода /uop кэш-линии вызывают узкие места для предыдущих проектов Sandybridge-microarch. Ранее я думал, что эта "очередь вопросов" была этим буфером, но, по-видимому, это не так.

Однако он работает, планировщик достаточно велик, чтобы данные из кэша были готовы вовремя, если адрес не находится на критическом пути.

1a: маска с операндом памяти

ANDPS  xmm0, [mask]  # in the loop

• байты: 7 insn, 16 данных. (AVX: 8 insn)
• fused-domain uops: 1 * n
• время ожидания добавлено к критическому пути: 1c (предполагается, что кэш L1 попал)
• пропускная способность: 1/c. (Skylake: 2/c) (ограничен 2 нагрузками /c )
• "latency" , если xmm0 был готов, когда этот insn выдал: ~ 4c в кеше L1.

1b: маска из регистра

movaps   xmm5, [mask]   # outside the loop

ANDPS    xmm0, xmm5     # in a loop
# or PAND   xmm0, xmm5    # higher latency, but more throughput on Nehalem to Broadwell

# or with an inverted mask, if set1_epi32(0x80000000) is useful for something else in your loop:
VANDNPS   xmm0, xmm5, xmm0   # It the dest that NOTted, so non-AVX would need an extra movaps

• байты: 10 insn + 16 данных. (AVX: 12 insn байтов)
• fused-domain uops: 1 + 1 * n
• латентность добавлена ​​в цепочку dep: 1c (с тем же предупреждением о пропуске кеша для раннего цикла)
• пропускная способность: 1/c. (Skylake: 3/c)

PAND - пропускная способность 3/c на Nehalem до Broadwell, но латентность = 3c (если используется между двумя операциями FP-домена и еще хуже на Nehalem). Я предполагаю, что только port5 имеет проводку для пересылки побитовых операций непосредственно на другие исполнительные блоки FP (pre Skylake). Pre-Nehalem и AMD, побитовые операторы FP обрабатываются одинаково с целыми операциями FP, поэтому они могут работать на всех портах, но имеют задержку пересылки.

1c: сгенерируйте маску "на лету":

# outside a loop
PCMPEQD  xmm5, xmm5  # set to 0xff...  Recognized as independent of the old value of xmm5, but still takes an execution port (p1/p5).
PSRLD    xmm5, 1     # 0x7fff...  # port0
# or PSLLD xmm5, 31  # 0x8000...  to set up for ANDNPS

ANDPS    xmm0, xmm5  # in the loop.  # port5

• bytes: 12 (AVX: 13)
• fused-domain uops: 2 + 1 * n (без операций с памятью)
• латентность добавлена ​​в цепочку dep: 1c
• пропускная способность: 1/c. (Skylake: 3/c)
• для всех 3-х процессоров: 1/c, насыщающих все 3 порта ALU-порта
• "задержка" , если xmm0 была готова, когда эта последовательность была выпущена (без цикла): 3c (+ 1c) может задержать байпас на SnB/IvB, если ANDPS должен ждать получения целочисленных данных. Agner Fog говорит в некоторых случаях там нет дополнительной задержки для целого- > FP-булева на SnB/IvB.)

Эта версия по-прежнему занимает меньше памяти, чем версии с постоянной 16B в памяти. Он также идеален для нерегулярно называемой функции, потому что нет никакой нагрузки, чтобы пропустить кеш-код.

"Задержка байпаса" не должна быть проблемой. Если xmm0 является частью длинной цепи зависимостей, команды генерации маски будут выполняться задолго до того, чтобы результат целого числа xmm5 успел достигнуть ANDPS до того, как xmm0 будет готов, даже если он займет медленную полосу.

Haswell не имеет байпасной задержки для целочисленных результатов → FP boolean, согласно тестированию Agner Fog. Его описание для SnB/IvB говорит, что это имеет место с выводами некоторых целых инструкций. Таким образом, даже в случае "стоячего старта" начала-от-цепочки, где xmm0 готов, когда эта последовательность команд выдает, это всего лишь 3c на * хорошо, 4c на * Bridge. Задержка, вероятно, не имеет значения, освобождают ли исполнительные блоки отставание от uops так быстро, как они выдаются.

В любом случае выход ANDPS будет в домене FP и не будет иметь байпасной задержки, если используется в MULPS или что-то в этом роде.

В Nehalem байпасные задержки составляют 2c. Таким образом, в начале цепочки отбрасывания (например, после неверного предсказания ветвления или промаха я $) в Nehalem, "задержка" , если xmm0 была готова, когда эта последовательность была выпущена 5c. Если вы очень много заботитесь о Nehalem и ожидаете, что этот код станет первым, что будет происходить после частых ложных предсказаний или похожих конвейеров, которые не позволят машине OoOE не приступить к вычислению маски до готовности xmm0, тогда это может не лучший выбор для ситуаций без цикла.

2a: AVX max (x, 0-x)

VXORPS  xmm5, xmm5, xmm5   # outside the loop

VSUBPS  xmm1, xmm5, xmm0   # inside the loop
VMAXPS  xmm0, xmm0, xmm1

• байты: AVX: 12
• fused-domain uops: 1 + 2 * n (без операций с памятью)
• латентность добавлена ​​в цепочку dep: 6c (Skylake: 8c)
• пропускная способность: 1 на 2c (два порта1 uops). (Skylake: 1/c, если MAXPS использует те же два порта, что и SUBPS.)

Skylake сбрасывает отдельный блок добавления вектора FP и добавляет вектор в единицы FMA на портах 0 и 1. Это удваивает пропускную способность FP, за счет увеличения задержки на 1 c. Задержка FMA уменьшается до 4 (от 5 в * хорошо). x87 FADD по-прежнему представляет собой задержку в 3 цикла, поэтому есть еще 3-тактный скалярный сумматор 80 бит-FP, но только на одном порту.

2b: тот же, но без AVX:

# inside the loop
XORPS  xmm1, xmm1   # not on the critical path, and doesn't even take an execution unit on SnB and later
SUBPS  xmm1, xmm0
MAXPS  xmm0, xmm1

• bytes: 9
• fused-domain uops: 3 * n (без операций с памятью)
• латентность добавлена ​​в цепочку dep: 6c (Skylake: 8c)
• пропускная способность: 1 на 2c (два порта1 uops). (Skylake: 1/c)
• "latency" , если xmm0 был готов, когда эта последовательность была выпущена (без цикла): тот же

Обнуление регистра с идентификацией обнуления, которую процессор распознает (например, xorps same,same), обрабатывается во время переименования регистра в микроархитектуре семейства Sandbridge и имеет нулевую задержку и пропускную способность 4/c. (То же, что и reg- > reg, что IvyBridge и позже может устранить.)

Это не бесплатно, хотя: он все еще занимает uop в плавленном домене, поэтому, если ваш код только узкополочен по частоте выпуска 4uop/cycle, это замедлит вас. Это более вероятно с гиперпотоком.

3: ANDPS (x, 0-x)

VXORPS  xmm5, xmm5, xmm5   # outside the loop.  Without AVX: zero xmm1 inside the loop

VSUBPS  xmm1, xmm5, xmm0   # inside the loop
VANDPS  xmm0, xmm0, xmm1

• байты: AVX: 12 без AVX: 9
• fused-domain uops: 1 + 2 * n (без операций с памятью). (Без AVX: 3 * n)
• латентность добавлена ​​в цепочку dep: 4c (Skylake: 5c)
• пропускная способность: 1/c (насыщенный p1 и p5). Skylake: 3/2c: (3 вектора uops/cycle)/(uop_p01 + uop_p015).
• "latency" , если xmm0 был готов, когда эта последовательность была выпущена (без цикла): тот же

Это должно работать, но IDK - то, что происходит с NaN. Хорошее наблюдение, что ANDPS является более низкой задержкой и не требует добавления порта FPU.

Это самый маленький размер с не-AVX.

4: сдвиг влево/вправо:

PSLLD  xmm0, 1
PSRLD  xmm0, 1

• bytes: 10 (AVX: 10)
• fused-domain uops: 2 * n
• латентность добавлена ​​в цепочку dep: 4c (2c + байпасные задержки)
• пропускная способность: 1/2c (saturate p0, также используется FP mul). (Skylake 1/c: удвоенная пропускная способность вектора)

• "задержка" , если xmm0 была готова, когда эта последовательность была выпущена (без цикла): тот же

  Это самый маленький (в байтах) с AVX.

  У этого есть возможности, где вы не можете сэкономить регистр, и он не используется в цикле. (В петле без каких-либо запасных частей, используйте andps xmm0, [mask]).

Я предполагаю, что 1-байтовая байпасная пересылка от FP до целочисленного сдвига, а затем еще 1c на обратном пути, поэтому это происходит так же медленно, как SUBPS/ANDPS. Он сохраняет uop-порт без выполнения, поэтому он имеет преимущества, если проблема с пропускной способностью промежуточного домена является проблемой, и вы не можете вытащить генерации маски из цикла. (например, потому что это функция, вызываемая в цикле, а не внутри).

Когда использовать что: Загрузка маски из памяти делает код простым, но имеет риск промаха в кеше. И берет 16B данных ro вместо 9 команд байтов.

• Требуется в цикле: 1c: создать маску вне цикла (с помощью pcmp/shift); используйте один andps внутри. Если вы не можете сэкономить реестр, пролейте его в стек и 1a: andps xmm0, [rsp + mask_local]. (Генерация и хранение с меньшей вероятностью приведет к пропуску кеша, чем константа). Только добавляет 1 цикл к критическому пути в любом случае, с одной командой с одним-хупом внутри цикла. Это port5 uop, поэтому, если ваш цикл насыщает порт в случайном порядке и не привязан к задержке, PAND может быть лучше. (SnB/IvB перемещает единицы на p1/p5, но Haswell/Broadwell/Skylake могут перемещаться только на p5. Skylake действительно увеличивал пропускную способность для (V)(P)BLENDV, но не для других операций в случайном порядке. Если номера AIDA верны, -AVX BLENDV - 1c lat ~ 3/c tput, но AVX BLENDV - 2c lat, 1/c tput (по-прежнему является улучшением tput по сравнению с Haswell))

• Требуется один раз в часто называемой функции без цикла (так что вы не можете амортизировать создание маски в нескольких целях):

  • Если пропускная способность uop является проблемой: 1a: andps xmm0, [mask]. Случайный промах кеша должен быть амортизирован за сбережения в долларах, если это действительно было узким местом.
  • Если латентность не является проблемой (функция используется только как часть коротких цепочек отрезков, не связанных с циклом, например arr[i] = abs(2.0 + arr[i]);), и вы хотите избежать постоянной в памяти: 4, потому что он всего 2 раза. Если abs входит в начало или конец цепочки отрезка, не будет задержки байпаса от нагрузки или хранилища.
  • Если пропускная способность uop не является проблемой: 1c: генерировать "на лету" с целым числом pcmpeq / shift. Отсутствие кэширования возможно и добавляет только 1c к критическому пути.

• Нужно (за пределами любых циклов) в нередко называемой функции: просто оптимизируйте размер (ни небольшая версия не использует константу из памяти). не-AVX: 3. AVX: 4. Они неплохие и не могут пропустить кеш-промах. 4-часовая латентность хуже для критического пути, чем вы получите с версией 1c, поэтому, если вы не думаете, что 3 байта команд - это большая сделка, выберите 1c. Версия 4 интересна для ситуаций с давлением в регистре, когда производительность не важна, и вы бы хотели не проливать ничего.

• Процессоры AMD: там задержка байпаса в/из andps (которая сама по себе имеет задержку 2 с), но я думаю, что это все же лучший выбор. Он по-прежнему превосходит задержку 5-6 циклов SUBPS. MAXPS - 2 с. С высокими задержками функций FP на процессорах семейства Bulldozer вы даже более вероятно, что выполнение вне очереди может генерировать вашу маску "на лету", чтобы она была готова, когда другой операнд на andps есть. Я предполагаю, что Bulldozer через Steamroller не имеет отдельного блока добавления FP, и вместо этого вектор добавляет и умножает в блоке FMA. 3 всегда будет плохим выбором для процессоров AMD Bulldozer. 2 выглядит лучше в этом случае из-за более короткой задержки байпаса от домена fma до домена fp и обратно. См. Руководство по микроаргуту Agner Fog, стр. 182 (15.11 Задержка данных между различными доменами выполнения).

• Silvermont: аналогичные задержки для SnB. По-прежнему используйте 1c для циклов и проб. также для одноразового использования. Silvermont вышел из строя, поэтому он может заранее подготовить маску, чтобы добавить только один цикл к критическому пути.