Оптимальное 8-битное сравнение SSE без знака

Question

Я пытаюсь найти наиболее удобный способ выполнения 8-битных беззнаковых сравнений с использованием SSE (до SSE 4.2).

Наиболее распространенный случай, над которым я работаю, это сравнение для> 0U, например

_mm_cmpgt_epu8(v, _mm_setzero_si128())                // #1

(что, конечно, также можно считать простым тестом для ненулевого значения.)

Но меня также несколько интересует более общий случай, например,

_mm_cmpgt_epu8(v1, v2)                                // #2

Первый случай может быть реализован с 2 инструкциями, используя различные методы, например, сравнить с 0, а затем инвертировать результат. Во втором случае обычно требуется 3 инструкции, например вычесть 128 из обоих операндов и выполнить сравнение со знаком. (См. Этот вопрос для различных решений 3 инструкции.)

В идеале я ищу решение с одной инструкцией для #1 и решение с двумя инструкциями для #2. Если ни то, ни другое невозможно, меня также интересуют мысли о том, какая из возможных реализаций двух или трех инструкций наиболее эффективна на современных процессорах Intel (Sandy Bridge, Ivy Bridge, Haswell).

---

Лучшие реализации для случая № 2 на данный момент:

• 1. сравнить с равным max без знака и инвертировать результат:

#define _mm_cmpgt_epu8(v0, v1) \ _mm_andnot_si128(_mm_cmpeq_epi8(_mm_max_epu8(v0, v1), v1), \ _mm_set1_epi8(-1))

Две арифметические инструкции + одна побитовая = 1,33 пропускной способности.

• 2. инвертировать знаковые биты для обоих аргументов (== вычесть 128) и использовать знаковое сравнение:

#define _mm_cmpgt_epu8(v0, v1) \ _mm_cmpgt_epi8(_mm_xor_si128(v0, _mm_set1_epi8(-128)), \ _mm_xor_si128(v1, _mm_set1_epi8(-128)))

Одна арифметическая инструкция + два побитовых = 1,16 пропускной способности.

---

Лучшие реализации для случая № 1, полученные из реализаций случая № 2 выше:

• 1.

#define _mm_cmpgtz_epu8(v0) \ _mm_andnot_si128(_mm_cmpeq_epi8(v0, _mm_set1_epi8(0)), \ _mm_set1_epi8(-1))

Одна арифметическая инструкция + одна побитовая = 0,83 пропускной способности.

• 2.

#define _mm_cmpgtz_epu8(v0) \ _mm_cmpgt_epi8(_mm_xor_si128(v0, _mm_set1_epi8(-128)), \ _mm_set1_epi8(-128)))

Одна арифметическая инструкция + одна побитовая = 0,83 пропускной способности.

Answer 1

Вот пример из библиотеки Simd:

    const __m128i K_INV_ZERO = SIMD_MM_SET1_EPI8(0xFF);//_mm_set1_epi8(-1);

    SIMD_INLINE __m128i NotEqual8u(__m128i a, __m128i b)
    {
        return _mm_andnot_si128(_mm_cmpeq_epi8(a, b), K_INV_ZERO);
    }

    SIMD_INLINE __m128i Greater8u(__m128i a, __m128i b)
    {
        return _mm_andnot_si128(_mm_cmpeq_epi8(_mm_min_epu8(a, b), a), K_INV_ZERO);
    }

    SIMD_INLINE __m128i GreaterOrEqual8u(__m128i a, __m128i b)
    {
        return _mm_cmpeq_epi8(_mm_max_epu8(a, b), a);
    }

    SIMD_INLINE __m128i Lesser8u(__m128i a, __m128i b)
    {
        return _mm_andnot_si128(_mm_cmpeq_epi8(_mm_max_epu8(a, b), a), K_INV_ZERO);
    }

    SIMD_INLINE __m128i LesserOrEqual8u(__m128i a, __m128i b)
    {
        return _mm_cmpeq_epi8(_mm_min_epu8(a, b), a);
    }

Answer 2

В духе копирования кода из библиотек SIMD, вот как это делает Vector Class Library (C++) Agner Fog:

// vector operator >= : returns true for elements for which a >= b (unsigned)
static inline Vec16cb operator >= (Vec16uc const & a, Vec16uc const & b) {
#ifdef __XOP__  // AMD XOP instruction set
    return _mm_comge_epu8(a,b);
#else  // SSE2 instruction set
    return _mm_cmpeq_epi8(_mm_max_epu8(a,b),a); // a == max(a,b)
#endif
}

// vector operator <= : returns true for elements for which a <= b (unsigned)
static inline Vec16cb operator <= (Vec16uc const & a, Vec16uc const & b) {
    return b >= a;
}

// vector operator > : returns true for elements for which a > b (unsigned)
static inline Vec16cb operator > (Vec16uc const & a, Vec16uc const & b) {
#ifdef __XOP__  // AMD XOP instruction set
    return _mm_comgt_epu8(a,b);
#else  // SSE2 instruction set
    return Vec16cb(Vec16c(~(b >= a)));
#endif
}

// vector operator < : returns true for elements for which a < b (unsigned)
static inline Vec16cb operator < (Vec16uc const & a, Vec16uc const & b) {
    return b > a;
}

// vector operator ~ : bitwise not
static inline Vec16uc operator ~ (Vec16uc const & a) {
    return Vec16uc( ~ Vec128b(a));
}

где поразрядно не определяется как

// vector operator ~ : bitwise not
static inline Vec128b operator ~ (Vec128b const & a) {
    return _mm_xor_si128(a, _mm_set1_epi32(-1));
}

Answer 3

У меня была идея сделать >= в двух инструкциях:

• вычесть с беззнаковой насыщенностью
• сравнить с нулем

Это не помогает >, хоть.

Кроме того, это в значительной степени эквивалентно ответу SIMM- библиотеки ErmIg (max_epu8(a,b) -> cmpeq с a), но хуже, потому что ему нужен обнуленный регистр. Это работает для SSE2, а не для SSE4.1. psubusb работает на тех же портах, что и pminusb,

---

Предыдущая версия этого ответа имела ошибочную идею, что b-a имеет установленный бит знака, если a>b, Но на самом деле это один бит слева от того, что требует тестирования: флаг переноса / бит (который не существует для SIMD с упакованным целым числом).

Посмотрите историю редактирования для некоторых идей о передаче бита знака остальной части элемента с pshufb (отрицательный результат) или pblendvb (которая может быть одиночной на Skylake только для версии без VEX).