Байт-массив перестраивает оптимизацию SSE

Я хотел бы перевести этот код, используя встроенные функции SSE. Я нашел инструкцию pshufb SSSE3 и аналогичную __builtin_ia32_pshufb128(v128i, v128i) GCC внутреннюю, которая может быть использована с этим кодом. Код переставляет вектор байтов s по индексу k путем замены байтов в массиве определенным образом.

void permutation(int k, std::vector<char> & s) 
{
  for(size_t j = 1; j < s.size(); ++j) 
  {
      std::swap(s[k % (j + 1)], s[j]); 
      k = k / (j + 1);
  }
}

Я потратил хороший час на размышление о том, как перевести код на pshufb. Можно ли переставить 16-байты с одним pshufb или требуется ли несколько инструкций? Достаточно хорошее решение будет переставлять всего 16 байт.

EDIT: дальнейший контекст проблемы: я повторяю все возможные перестановки s. Вычисление вперед k = 0, 1, 2,... несколько результатов для одного и того же s в порядке. Однако мне нужно воспроизвести k -ую перестановку позже предпочтительно как операцию O (1).

Ответы

Ответ 1

Одиночный вызов

Обратите внимание, что вы можете записать номер k в системе позиционных обозначений с mixed radix, чтобы каждая цифра в этом представлении определите индексы обмениваемых элементов для нескольких последовательных значений j.

Например, для строк длиной 12 вы можете написать любой k как трехзначное число с основами:

720 = 1*2*3*4*5*6  (0-th digit, lowest value)
504 = 7*8*9        (1-th digit)
1320 = 10*11*12    (2-th digit, highest value)

Теперь вы можете предварительно скопировать для каждой позиции и для каждого значения цифры в этой позиции кумулятивную перестановку всех ваших элементов и сохранить ее в таблице поиска. Затем вы сможете сделать несколько свопов по одной инструкции.

Вот пример (предварительная компиляция будет самой сложной):

//to be precomputed:
__m128i mask0[ 720];
__m128i mask1[ 504];
__m128i mask2[1320];

__m128i permutation(int k, __m128i s) {
    s = _mm_shuffle_epi8(s, mask0[k %  720]); k /=  720;  //j = [1..5]
    s = _mm_shuffle_epi8(s, mask1[k %  504]); k /=  504;  //j = [6..8]
    s = _mm_shuffle_epi8(s, mask2[k       ]);             //j = [9..11]
    return s;
}

Вы можете изменить разложение на базы, чтобы сбалансировать количество шагов и размер таблицы поиска.

Примечание: операция разделения выполняется очень медленно. Используйте только деления по константам времени компиляции, тогда оптимизатор преобразует их в умножения. Проверьте сгенерированную сборку, чтобы убедиться, что нет инструкций разделения.

Многие вызовы

К сожалению, индексные вычисления по-прежнему будут потреблять большую часть времени с предлагаемым решением, см. сгенерированная сборка. Эти служебные данные могут быть значительно уменьшены, если вы обрабатываете сразу несколько последовательных значений k.

Простейшим подходом к оптимизации решения будет: итерация над цифрами k отдельно, а не выполнение одиночного цикла над k. Тогда расчеты индекса становятся ненужными. Кроме того, вы можете повторно использовать частично вычисленные результаты.

__m128i s;// = ???
for (int k0 = 0; k0 <  720; k0++) {
    __m128i s0 = _mm_shuffle_epi8(s, mask0[k0]);
    for (int k1 = 0; k1 <  504; k1++) {
        __m128i s1 = _mm_shuffle_epi8(s0, mask1[k1]);
        for (int k2 = 0; k2 < 1320; k2+=4) {
            //for k = (((k2+0) * BASE1) + k1) * BASE0 + k0:
            __m128i sx0 = _mm_shuffle_epi8(s1, mask2[k2+0]);
            //for k = (((k2+1) * BASE1) + k1) * BASE0 + k0:
            __m128i sx1 = _mm_shuffle_epi8(s1, mask2[k2+1]);
            //for k = (((k2+2) * BASE1) + k1) * BASE0 + k0:
            __m128i sx2 = _mm_shuffle_epi8(s1, mask2[k2+2]);
            //for k = (((k2+3) * BASE1) + k1) * BASE0 + k0:
            __m128i sx3 = _mm_shuffle_epi8(s1, mask2[k2+3]);

            // ... check four strings: sx0, sx1, sx2, sx3
        }
    }
}

Таким образом, вам нужно сделать одну перетасовку для каждой перестановки в среднем (см. сборка), которая кажется близкой к совершенству.

Код и результаты

Вот полный рабочий код всех решений.

Обратите внимание, что генерация таблиц поиска не является тривиальной, чтобы полностью объяснить, а соответствующий код довольно большой (и заполнен неприятными деталями).

Тест производительности Intel Core 2 Duo E4700 Allendale (2600 МГц) дает результаты:

2.605 s: original code         (k < 12739451)
0.125 s: single-call fast code (k < 12739451)
4.822 s: single-call fast code (k < 479001600)
0.749 s: many-call fast code   (k < 479001600)

Таким образом, версия с одним вызовом примерно 20 раз быстрее, чем исходный код, а версия с многочисленными вызовами - 6.5 раз быстрее, чем версия с одним вызовом.