Как оптимизировать цикл?

Question

У меня есть следующая функция узкого места.

typedef unsigned char byte;
void CompareArrays(const byte * p1Start, const byte * p1End, const byte * p2, byte * p3)
{
     const byte b1 = 128-30;
     const byte b2 = 128+30;
     for (const byte * p1 = p1Start; p1 != p1End; ++p1, ++p2, ++p3) {
        *p3 = (*p1 < *p2 ) ? b1 : b2;
    }
}

Я хочу заменить C++ код внутренними функциями SSE2. Я пробовал _mm_cmpgt_epi8, но он использовал подписанное сравнение. Мне нужно сравнение без знака.

Есть ли какая-нибудь хитрость (SSE, SSE2, SSSE3) для решения моей проблемы?

Примечание: Я не хочу использовать многопоточность в этом случае.

Answer 1

Вместо смещения ваших значений со знаком, чтобы сделать их беззнаковыми, несколько более эффективным способом было бы сделать следующее:

• использовать _mm_min_epu8, чтобы получить мин без знака p1, p2
• сравните этот минимум на равенство с p2, используя _mm_cmpeq_epi8
• , итоговая маска теперь будет 0x00 для элементов, где p1 = p2
• youтеперь можно использовать эту маску с _mm_or_si128 и _mm_andc_si128, чтобы выбрать соответствующие значения b1 / b2

Обратите внимание, что всего это 4 инструкции по сравнению с 5 с использованием подхода сравнения смещение + знак.

Answer 2

Да, это можно сделать в SIMD, но для создания маски потребуется несколько шагов.

Руслик понял это правильно, я думаю. Вы хотите xor каждого компонента с 0x80, чтобы перевернуть смысл сравнения со знаком и без знака. _mm_xor_si128 (PXOR) дает вам это - вам нужно будет создать маску как статический массив символов где-то перед загрузкой в ​​SIMD-регистр. Затем _mm_cmpgt_epi8 дает вам маску, и вы можете использовать побитовое AND (например, _mm_and_si128) для выполнения перемещения в маске.

Answer 3

Вы можете вычесть 127 из ваших чисел, а затем использовать _mm_cmpgt_epi8

Answer 4

Да, SSE здесь работать не будет. Вы можете улучшить производительность этого кода на многоядерном компьютере, используя OpenMP:

void CompareArrays(const byte * p1Start, const byte * p1End, const byte * p2, byte * p3)
{
     const byte b1 = 128-30;
     const byte b2 = 128+30;

     int n = p1End - p1Start;
     #pragma omp parallel for
     for (int i = 0; i < n; ++p1, ++i) 
     {
        p3[i] = (p1[i] < p2[i]) ? b1 : b2;
     }
}

Answer 5

К сожалению, многие из приведенных выше ответов неверны. Давайте предположим, что 3-битное слово:

без знака: 4 5 6 7 0 1 2 3 == подписано: -4 -3 -2 -1 0 1 2 3 (биты: 100 101 110 111 000 001 010 011)

Метод Пола Р. неверен. Предположим, мы хотим знать, если 3> 2. min (3,2) == 2, что говорит о да, поэтому метод работает здесь. Теперь предположим, что мы хотим знать, если 7> 2. Значение 7 равно -1 в знаковом представлении, поэтому min (-1,2) == -1, что неверно указывает на то, что 7 не больше 2 без знака.

Метод Андрея тоже неверен. Предположим, что мы хотим знать, если 7> 2, или a = 7, и b = 2. Значение 7 равно -1 в представлении со знаком, поэтому первый член (a> b) не выполняется, и метод предполагает, что 7 не больше чем 2.

Однако метод BJobnh, исправленный Алексеем, является правильным. Просто вычтите 2 ^ (n-1) из значений, где n - количество бит. В этом случае мы бы вычли 4, чтобы получить новые соответствующие значения:

старая подпись: -4 -3 -2 -1 0 1 2 3 => новая подпись: 0 1 2 3 -4 -3 -2 -1 == новая без знака 0 1 2 3 4 5 6 7.

Другими словами, unsigned_greater_than (a, b) эквивалентен sign_greater_than (a - 2 ^ (n-1), b - 2 ^ (n-1)).

Answer 6

используйте pcmpeqb и будьте с Силаю.