int eq3(int a, int b, int c, int d, int e, int f){
return a == d || a == e || a == f
|| b == d || b == e || b == f
|| c == d || c == e || c == f;
}
Эта функция получает 6 int и возвращает true, если любой из 3 первых ints равен любому из трех последних int. Есть ли побитовый взломать аналогичный способ сделать это быстрее?
Расширяя метод сравнения SSE с помощью dawg, вы можете комбинировать результаты сравнений с помощью вектора OR и перемещать маску результатов сравнения обратно в целое число для проверки на 0/ненулевое значение.
Кроме того, вы можете получить данные в векторах более эффективно (хотя он все еще довольно неуклюжий, чтобы получить много отдельных целых чисел в векторы, когда они живут в регистрах, а не сидеть в памяти).
Вам следует избегать хранилищ для переадресации магазинов, которые возникают в результате создания трех небольших магазинов и одной большой нагрузки.
///// UNTESTED ////////
#include <immintrin.h>
int eq3(int a, int b, int c, int d, int e, int f){
// Use _mm_set to let the compiler worry about getting integers into vectors
// Use -mtune=intel or gcc will make bad code, though :(
__m128i abcc = _mm_set_epi32(0,c,b,a); // args go from high to low position in the vector
// masking off the high bits of the result-mask to avoid false positives
// is cheaper than repeating c (to do the same compare twice)
__m128i dddd = _mm_set1_epi32(d);
__m128i eeee = _mm_set1_epi32(e);
dddd = _mm_cmpeq_epi32(dddd, abcc);
eeee = _mm_cmpeq_epi32(eeee, abcc); // per element: 0(unequal) or -1(equal)
__m128i combined = _mm_or_si128(dddd, eeee);
__m128i ffff = _mm_set1_epi32(f);
ffff = _mm_cmpeq_epi32(ffff, abcc);
combined = _mm_or_si128(combined, ffff);
// results of all the compares are ORed together. All zero only if there were no hits
unsigned equal_mask = _mm_movemask_epi8(combined);
equal_mask &= 0x0fff; // the high 32b element could have false positives
return equal_mask;
// return !!equal_mask if you want to force it to 0 or 1
// the mask tells you whether it was a, b, or c that had a hit
// movmskps would return a mask of just 4 bits, one for each 32b element, but might have a bypass delay on Nehalem.
// actually, pmovmskb apparently runs in the float domain on Nehalem anyway, according to Agner Fog table >.<
}
Это компилируется для довольно приятного asm, довольно похожего между clang и gcc, но clang -fverbose-asm помещает приятные комментарии в тасовку. Только 19 инструкций, включая ret, с приличным количеством parallelism от отдельных цепочек зависимостей. С помощью -msse4.1 или -mavx он сохраняет еще пару инструкций. (Но, вероятно, не работает быстрее)
С clang, версия dawg примерно в два раза больше. С gcc происходит что-то плохое, и это ужасно (более 80 инструкций. Похож на gcc-оптимизацию, так как выглядит хуже, чем просто прямой перевод источника). Даже версия clang тратит так много времени на получение данных в/из векторных regs, что, возможно, было бы быстрее просто делать сравнения без ветвей и OR значения истины вместе.
Это компилируется для достойного кода:
// 8bit variable doesn't help gcc avoid partial-register stalls even with -mtune=core2 :/
int eq3_scalar(int a, int b, int c, int d, int e, int f){
char retval = (a == d) | (a == e) | (a == f)
| (b == d) | (b == e) | (b == f)
| (c == d) | (c == e) | (c == f);
return retval;
}
Играйте с тем, как получить данные от вызывающего в векторные рег.
Если группы из трех поступают из памяти, тогда проблема. прохождение указателей, так что векторная нагрузка может получить их из их исходного местоположения. Переход через целые регистры на пути к векторам отстой (более высокая латентность, больше uops), но если ваши данные уже живут в regs, это потеря, чтобы делать целые магазины, а затем векторные нагрузки. gcc невнимателен и следует рекомендациям руководства по оптимизации AMD, чтобы отскочить через память, хотя Agner Fog говорит, что он обнаружил, что это не стоит даже на процессорах AMD. Это определенно хуже для Intel, и, по-видимому, мышь или, возможно, еще хуже на AMD, поэтому это определенно неправильный выбор для -mtune=generic. В любом случае...
9-й может быть выполнен с использованием целочисленного сравнения и имеет значение истинности ORed с векторным результатом. На некоторых процессорах (особенно AMD и, возможно, Intel Haswell и более поздних версиях), не перенося ни одно из 6 целых чисел в векторные regs, все могут быть победой. Смешивание трех целых нестационарных сравнений с векторными перетасовками/сравнениями будет чередовать их красиво.
Эти векторные сравнения могут быть установлены с помощью shufps для целочисленных данных (поскольку он может объединять данные из двух исходных регистров). Это хорошо для большинства процессоров, но требует много раздражающего кастинга при использовании встроенных средств вместо фактического asm. Даже если есть байпасная задержка, это не плохой компромисс против чего-то вроде punpckldq, а затем pshufd.
aabb ccab
==== ====
dede deff
c==f
с asm что-то вроде:
#### untested
# pretend a is in eax, and so on
movd xmm0, eax
movd xmm1, ebx
movd xmm2, ecx
shl rdx, 32
#mov edi, edi # zero the upper 32 of rdi if needed, or use shld instead of OR if you don't care about AMD CPUs
or rdx, rdi # de in an integer register.
movq xmm3, rdx # de, aka (d<<32)|e
# in 32bit code, use a vector shuffle of some sort to do this in a vector reg, or:
#pinsrd xmm3, edi, 1 # SSE4.1, and 2 uops (same as movd+shuffle)
#movd xmm4, edi # e
movd xmm5, esi # f
shufps xmm0, xmm1, 0 # xmm0=aabb (low dword = a; my notation is backwards from left/right vector-shift perspective)
shufps xmm5, xmm3, 0b01000000 # xmm5 = ffde
punpcklqdq xmm3, xmm3 # broadcast: xmm3=dede
pcmpeqd xmm3, xmm0 # xmm3: aabb == dede
# spread these instructions out between vector instructions, if you aren't branching
xor edx,edx
cmp esi, ecx # c == f
#je .found_match # if there one of the 9 that true more often, make it this one. Branch mispredicts suck, though
sete dl
shufps xmm0, xmm2, 0b00001000 # xmm0 = abcc
pcmpeqd xmm0, xmm5 # abcc == ffde
por xmm0, xmm3
pmovmskb eax, xmm0 # will have bits set if cmpeq found any equal elements
or eax, edx # combine vector and scalar compares
jnz .found_match
# or record the result instead of branching on it
setnz dl
Это также 19 инструкций (не считая окончательного jcc/setcc), но один из них - идиома xor-zeroing, а также другие простые целые инструкции. (Более короткое кодирование, некоторые могут работать на port6 на Haswell +, которые не могут обрабатывать векторные инструкции). Возможно, существует более длинная цепочка dep из-за цепи тасований, которая строит abcc.
Предполагая, что вы ожидаете высокую скорость результатов false, вы можете быстро выполнить "предварительную проверку", чтобы быстро изолировать такие случаи:
Если бит в a установлен, который не установлен ни в одном из d, e и f, то a не может быть равно ни одному из них.
Таким образом, что-то вроде
int pre_eq3(int a, int b, int c, int d, int e, int f){
int const mask = ~(d | e | f);
if ((a & mask) && (b & mask) && (c & mask)) {
return false;
}
return eq3(a, b, c, d, e, f);
}
может ускорить его (8 операций вместо 9 17, но гораздо более дорогостоящий, если результат будет фактически true). Если mask == 0, то, конечно, это не поможет.
Это может быть дополнительно улучшено, если с большой вероятностью a & b & c имеет несколько бит:
int pre_eq3(int a, int b, int c, int d, int e, int f){
int const mask = ~(d | e | f);
if ((a & b & c) & mask) {
return false;
}
if ((a & mask) && (b & mask) && (c & mask)) {
return false;
}
return eq3(a, b, c, d, e, f);
}
Теперь, если все из a, b и c имеют биты, установленные, где ни один из d, e и c не имеет битов, мы вышли довольно быстро.
Если вы хотите, чтобы побитовая версия выглядела как xor. Если вы xor два числа, которые будут одинаковыми, ответ будет равен 0. В противном случае бит будет переворачиваться, если один из них установлен, а другой - нет. Например, 1000 xor 0100 равно 1100.
Код, который у вас есть, скорее всего, вызовет как минимум 1 конвейерный поток, но, кроме того, он будет хорошо работать.
Я думаю, что использование SSE, вероятно, стоит исследовать.
Прошло 20 лет с тех пор, как я написал что-то, а не тестировалось, но что-то вроде:
#include <xmmintrin.h>
int cmp3(int32_t a, int32_t b, int32_t c, int32_t d, int32_t e, int32_t f){
// returns -1 if any of a,b,c is eq to any of d,e,f
// returns 0 if all a,b,c != d,e,f
int32_t __attribute__ ((aligned(16))) vec1[4];
int32_t __attribute__ ((aligned(16))) vec2[4];
int32_t __attribute__ ((aligned(16))) vec3[4];
int32_t __attribute__ ((aligned(16))) vec4[4];
int32_t __attribute__ ((aligned(16))) r1[4];
int32_t __attribute__ ((aligned(16))) r2[4];
int32_t __attribute__ ((aligned(16))) r3[4];
// fourth word is DNK
vec1[0]=a;
vec1[1]=b;
vec1[2]=c;
vec2[0]=vec2[1]=vec2[2]=d;
vec3[0]=vec3[1]=vec3[2]=e;
vec4[0]=vec4[1]=vec4[2]=f;
__m128i v1 = _mm_load_si128((__m128i *)vec1);
__m128i v2 = _mm_load_si128((__m128i *)vec2);
__m128i v3 = _mm_load_si128((__m128i *)vec3);
__m128i v4 = _mm_load_si128((__m128i *)vec4);
// any(a,b,c) == d?
__m128i vcmp1 = _mm_cmpeq_epi32(v1, v2);
// any(a,b,c) == e?
__m128i vcmp2 = _mm_cmpeq_epi32(v1, v3);
// any(a,b,c) == f?
__m128i vcmp3 = _mm_cmpeq_epi32(v1, v4);
_mm_store_si128((__m128i *)r1, vcmp1);
_mm_store_si128((__m128i *)r2, vcmp2);
_mm_store_si128((__m128i *)r3, vcmp3);
// bit or the first three of each result.
// might be better with SSE mask, but I don't remember how!
return r1[0] | r1[1] | r1[2] |
r2[0] | r2[1] | r2[2] |
r3[0] | r3[1] | r3[2];
}
Если все сделано правильно, SSE без ветвей должен быть быстрее на 4x - 8 раз.