Можно ли проверить, равен ли какой-либо из 2 наборов из 3 целых чисел менее чем 9 сравнениям?

Расширяя метод сравнения SSE dawg, вы можете комбинировать результаты сравнений с помощью векторного ИЛИ и перемещать маску результатов сравнения обратно к целому числу для проверки на 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's table >.<
}

Это компилируется в довольно хороший ассемблер, очень похожий между clang и gcc, но clang -fverbose-asm добавляет хорошие комментарии к перетасовке. Всего 19 инструкций, включая ret, с приличным количеством параллелизма из отдельных цепочек зависимостей. С -msse4.1 или -mavx сохраняется еще пара инструкций. (Но, вероятно, не работает быстрее)

С clang версия Dawg примерно в два раза больше. С gcc происходит что-то нехорошее и это ужасно (более 80 инструкций. Похоже на баг оптимизации gcc, так как выглядит хуже, чем простой перевод исходников). Даже версия clang тратит так много времени на получение/извлечение данных из векторных регистров, что может быть быстрее просто выполнять сравнения без ответвления и ИЛИ значения истинности вместе.

Это компилируется в достойный код:

// 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;
}

Поэкспериментируйте с тем, как получить данные от вызывающей стороны в векторные регистры. Если группы из трех берутся из памяти, то проблема. передача указателей, чтобы векторная загрузка могла получить их из исходного местоположения. Прохождение через целочисленные регистры на пути к векторам — отстой (более высокая задержка, больше операций), но если ваши данные уже находятся в регистрах, это потеря для целочисленных хранилищ, а затем векторных загрузок. gcc тупой и следует рекомендациям руководства по оптимизации AMD по использованию памяти, хотя Агнер Фог говорит, что он обнаружил, что это не стоит того даже на процессорах AMD. На Интеле однозначно хуже, а на АМД видимо отмывка или может еще хуже, так что для -mtune=generic однозначно неправильный выбор. В любом случае...

Также возможно выполнить 8 из 9 сравнений всего за два сравнения упакованных векторов.

9-й может быть выполнен с целочисленным сравнением, и его истинное значение может быть объединено с векторным результатом. На некоторых процессорах (особенно AMD и, возможно, Intel Haswell и более поздних версиях) отсутствие переноса одного из 6 целых чисел в векторные регистры может быть выигрышным. Смешивание трех целочисленных сравнений без ветвлений с векторными перетасовками/сравнениями будет хорошо чередовать их.

Эти векторные сравнения можно настроить, используя shufps для целочисленных данных (поскольку он может объединять данные из двух исходных регистров). Это нормально для большинства процессоров, но требует много надоедливого приведения при использовании встроенных функций вместо реального ассемблера. Даже если есть задержка обхода, это неплохой компромисс по сравнению с чем-то вроде 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's one of the 9 that's 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, а есть и другие простые целочисленные инструкции. (Более короткая кодировка, некоторые из них могут работать на порту 6 на Haswell +, который не может обрабатывать векторные инструкции). Может быть более длинная цепочка отложений из-за цепочки перетасовок, которая строит 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. Если вы объедините два одинаковых числа, ответ будет 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 без ветвей должен быть в 4-8 раз быстрее.

Если ваш компилятор/архитектура поддерживает векторные расширения (например, clang и gcc) вы можете использовать что-то вроде:

#ifdef __SSE2__
#include <immintrin.h>
#elif defined __ARM_NEON
#include <arm_neon.h>
#elif defined __ALTIVEC__
#include <altivec.h>
//#elif ... TODO more architectures
#endif

static int hastrue128(void *x){
#ifdef __SSE2__
    return _mm_movemask_epi8(*(__m128i*)x);
#elif defined __ARM_NEON
    return vaddlvq_u8(*(uint8x16_t*)x);
#elif defined __ALTIVEC__
typedef __UINT32_TYPE__ v4si __attribute__ ((__vector_size__ (16), aligned(4), __may_alias__));
    return vec_any_ne(*(v4si*)x,(v4si){0});
#else
    int *y = x;
    return y[0]|y[1]|y[2]|y[3];
#endif
}

//if inputs will always be aligned to 16 add an aligned attribute
//otherwise ensure they are at least aligned to 4
int cmp3(  int* a  ,  int* b ){
typedef __INT32_TYPE__ i32x4 __attribute__ ((__vector_size__ (16), aligned(4), __may_alias__));
    i32x4 x = *(i32x4*)a, cmp, tmp, y0 = y0^y0, y1 = y0, y2 = y0;
    //start vectors off at 0 and add the int to each element for optimization
    //it adds the int to each element, but since we started it at zero,
    //a good compiler (not ICC at -O3) will skip the xor and add and just broadcast/whatever
    y0 += b[0];
    y1 += b[1];
    y2 += b[2];
    cmp =  x == y0;
    tmp =  x == y1; //ppc complains if we don't use temps here
    cmp |= tmp;
    tmp =  x ==y2;
    cmp |= tmp;
    //now hack off then end since we only need 3
    cmp &= (i32x4){0xffffffff,0xffffffff,0xffffffff,0};
    return hastrue128(&cmp);
}

int cmp4(  int* a  ,  int* b ){
typedef __INT32_TYPE__ i32x4 __attribute__ ((__vector_size__ (16), aligned(4), __may_alias__));
    i32x4 x = *(i32x4*)a, cmp, tmp, y0 = y0^y0, y1 = y0, y2 = y0, y3 = y0;
    y0 += b[0];
    y1 += b[1];
    y2 += b[2];
    y3 += b[3];
    cmp =  x == y0;
    tmp =  x == y1; //ppc complains if we don't use temps here
    cmp |= tmp;
    tmp =  x ==y2;
    cmp |= tmp;
    tmp =  x ==y3;
    cmp |= tmp;
    return hastrue128(&cmp);
}

На arm64 это компилируется в следующий код без ответвлений:

cmp3:
        ldr     q2, [x0]
        adrp    x2, .LC0
        ld1r    {v1.4s}, [x1]
        ldp     w0, w1, [x1, 4]
        dup     v0.4s, w0
        cmeq    v1.4s, v2.4s, v1.4s
        dup     v3.4s, w1
        ldr     q4, [x2, #:lo12:.LC0]
        cmeq    v0.4s, v2.4s, v0.4s
        cmeq    v2.4s, v2.4s, v3.4s
        orr     v0.16b, v1.16b, v0.16b
        orr     v0.16b, v0.16b, v2.16b
        and     v0.16b, v0.16b, v4.16b
        uaddlv h0,v0.16b
        umov    w0, v0.h[0]
        uxth    w0, w0
        ret
cmp4:
        ldr     q2, [x0]
        ldp     w2, w0, [x1, 4]
        dup     v0.4s, w2
        ld1r    {v1.4s}, [x1]
        dup     v3.4s, w0
        ldr     w1, [x1, 12]
        dup     v4.4s, w1
        cmeq    v1.4s, v2.4s, v1.4s
        cmeq    v0.4s, v2.4s, v0.4s
        cmeq    v3.4s, v2.4s, v3.4s
        cmeq    v2.4s, v2.4s, v4.4s
        orr     v0.16b, v1.16b, v0.16b
        orr     v0.16b, v0.16b, v3.16b
        orr     v0.16b, v0.16b, v2.16b
        uaddlv h0,v0.16b
        umov    w0, v0.h[0]
        uxth    w0, w0
        ret

А на ICC x86_64 -march=skylake выдает следующий безветвевой код:

cmp3:
        vmovdqu   xmm2, XMMWORD PTR [rdi]                       #27.24
        vpbroadcastd xmm0, DWORD PTR [rsi]                      #34.17
        vpbroadcastd xmm1, DWORD PTR [4+rsi]                    #35.17
        vpcmpeqd  xmm5, xmm2, xmm0                              #34.17
        vpbroadcastd xmm3, DWORD PTR [8+rsi]                    #37.16
        vpcmpeqd  xmm4, xmm2, xmm1                              #35.17
        vpcmpeqd  xmm6, xmm2, xmm3                              #37.16
        vpor      xmm7, xmm4, xmm5                              #36.5
        vpor      xmm8, xmm6, xmm7                              #38.5
        vpand     xmm9, xmm8, XMMWORD PTR __$U0.0.0.2[rip]      #40.5
        vpmovmskb eax, xmm9                                     #11.12
        ret                                                     #41.12
cmp4:
        vmovdqu   xmm3, XMMWORD PTR [rdi]                       #46.24
        vpbroadcastd xmm0, DWORD PTR [rsi]                      #51.17
        vpbroadcastd xmm1, DWORD PTR [4+rsi]                    #52.17
        vpcmpeqd  xmm6, xmm3, xmm0                              #51.17
        vpbroadcastd xmm2, DWORD PTR [8+rsi]                    #54.16
        vpcmpeqd  xmm5, xmm3, xmm1                              #52.17
        vpbroadcastd xmm4, DWORD PTR [12+rsi]                   #56.16
        vpcmpeqd  xmm7, xmm3, xmm2                              #54.16
        vpor      xmm8, xmm5, xmm6                              #53.5
        vpcmpeqd  xmm9, xmm3, xmm4                              #56.16
        vpor      xmm10, xmm7, xmm8                             #55.5
        vpor      xmm11, xmm9, xmm10                            #57.5
        vpmovmskb eax, xmm11                                    #11.12
        ret

И это даже работает на ppc64 с altivec - хотя определенно неоптимально

cmp3:
        lwa 10,4(4)
        lxvd2x 33,0,3
        vspltisw 11,-1
        lwa 9,8(4)
        vspltisw 12,0
        xxpermdi 33,33,33,2
        lwa 8,0(4)
        stw 10,-32(1)
        addi 10,1,-80
        stw 9,-16(1)
        li 9,32
        stw 8,-48(1)
        lvewx 0,10,9
        li 9,48
        xxspltw 32,32,3
        lvewx 13,10,9
        li 9,64
        vcmpequw 0,1,0
        lvewx 10,10,9
        xxsel 32,44,43,32
        xxspltw 42,42,3
        xxspltw 45,45,3
        vcmpequw 13,1,13
        vcmpequw 1,1,10
        xxsel 45,44,43,45
        xxsel 33,44,43,33
        xxlor 32,32,45
        xxlor 32,32,33
        vsldoi 1,12,11,12
        xxland 32,32,33
        vcmpequw. 0,0,12
        mfcr 3,2
        rlwinm 3,3,25,1
        cntlzw 3,3
        srwi 3,3,5
        blr
cmp4:
        lwa 10,8(4)
        lxvd2x 33,0,3
        vspltisw 10,-1
        lwa 9,12(4)
        vspltisw 11,0
        xxpermdi 33,33,33,2
        lwa 7,0(4)
        lwa 8,4(4)
        stw 10,-32(1)
        addi 10,1,-96
        stw 9,-16(1)
        li 9,32
        stw 7,-64(1)
        stw 8,-48(1)
        lvewx 0,10,9
        li 9,48
        xxspltw 32,32,3
        lvewx 13,10,9
        li 9,64
        xxspltw 45,45,3
        vcmpequw 13,1,13
        xxsel 44,43,42,45
        lvewx 13,10,9
        li 9,80
        vcmpequw 0,1,0
        xxspltw 45,45,3
        xxsel 32,43,42,32
        vcmpequw 13,1,13
        xxlor 32,32,44
        xxsel 45,43,42,45
        lvewx 12,10,9
        xxlor 32,32,45
        xxspltw 44,44,3
        vcmpequw 1,1,12
        xxsel 33,43,42,33
        xxlor 32,32,33
        vcmpequw. 0,0,11
        mfcr 3,2
        rlwinm 3,3,25,1
        cntlzw 3,3
        srwi 3,3,5
        blr

Как вы можете видеть из сгенерированного asm, есть еще немного возможностей для улучшения, но он будет компилироваться на risc-v, mips, ppc и других комбинациях архитектура + компилятор, которые поддерживают векторные расширения.