Режим 12 _mm_cmpistri - PullRequest
Новая
       62

Режим 12 _mm_cmpistri

0 голосов
/ 26 декабря 2018

Алгоритм Simd для поиска по подстроке в 2016 бумаге : 

bool like(const uint8_t* string, __m128i pat, [...]) {
    size_t i = 0;
    while (i + 16 < str_len) {
        __m128i str = _mm_loadu_si128(&string[i]);
        size_t j = _mm_cmpistri(pat, str, 12);  // mode 12
        if (j >= 16) i += 16;
        else {
            if (j + pat_len <= 16) return true;
            i += j;
        }
    }
    // Process remainder
    if (i + pat_len <= str_len) {
        __m128i str = _mm_loadu_si128(&string[i]);
        size_t j = _mm_cmpestri(pat, pat_len,
                                str, str_len - i, 12);
        if (j < 16 && j + pat_len <= 16) return true;
    }
    return false;
}

Что такое режим 12 из _mm_cmpistri?

Это довольно медленно?

Спасибо.

1 Ответ

0 голосов
/ 26 декабря 2018

pcmpistri имеет пропускную способность один на 2 такта на Райзене, один на 3 такта на Скайлэйке.Это одна из самых быстрых строковых инструкций SSE4.2, более быстрая, чем инструкции с явной длиной.(https://agner.org/optimize/). Это довольно хорошо для поиска по подстроке, но не для простых strchr / memchr поисков: Насколько быстрее строковые инструкции SSE4.2 по сравнению с SSE2 для memcmp? и SSE42 & STTNI - PcmpEstrM в два раза медленнее, чем PcmpIstrM, это правда?

Обратите внимание, что в вашем заголовке упоминается _mm_cmpestri, медленная версия для строк с явной длиной. Но ваш код использует _mm_cmpistri, быстрая версия для строк неявной длины.

(Остальная часть кода в этом цикле поиска должна компилироваться довольно эффективно. Если компилятор использует ветвь вместо cmov для i+=16 против i+=j условие, прогноз ветвления + умозрительное выполнение скрывают зависимость, поэтому несколько итераций могут выполняться одновременно, за счет пропуска ветвления для большинства случаев нахождения частичного совпадения в конце входного вектора. По крайней мере, я так думаюэто то, для чего это условие. Использование cmov создаст зависимость данных между входными векторами, а задержка инструкции будет ~ 2 или в 3 раза больше, чем черезположить.)

Я не знаю, насколько хорошо он сравнивается с хорошо настроенным strstr, использующим AVX2, который избегает строковых инструкций SSE4.2. Я думаю, это может зависетьо длине подстроки, которую вы ищете, или, возможно, о других свойствах данных, например, о количестве ложноположительных кандидатов на начало или конец найденной строки.

Микробенчмарки, которые вы уже нашли в https://github.com/WojciechMula/sse4-strstr должно быть хорошо.Войцех пишет хороший код и достаточно разбирается в настройке для различных x86-арок, чтобы действительно хорошо оптимизировать.Я не смотрел на его тесты строк, но я смотрел на его код popcnt, который исследует использование Harley-Seal с AVX512F vpernternlogd для большого ускорения.

Руководство Intel по ISA ref(vol.2) имеет целый раздел о режимах для строковых инструкций (Раздел 4.1, «Работа с управляющим байтом Imm8 для PCMPESTRI / PCMPESTRM / PCMPISTRI / PCMPISTRM»)), отдельно от записи в https://www.felixcloutier.com/x86/pcmpistri.

Обычно вы пишете режим в шестнадцатеричном или двоичном, а не в десятичном виде, потому что он имеет несколько битовых полей.12 = 0b00001100.

Руководство по встроенным функциям Intel также содержит псевдокод для получения полной информации о работе, но это довольно тяжело, если вы не знаете цели высокого уровня.Как только вы это сделаете, это может быть полезно.https://software.intel.com/sites/landingpage/IntrinsicsGuide/#expand=2403,6062,4147,948&techs=SSE4_2,AVX,AVX2&text=pcmpi

См. Также https://www.strchr.com/strcmp_and_strlen_using_sse_4.2 для более удобного чтения различных режимов.Цитируем часть этого здесь:

Операции агрегирования

Сердцем инструкции обработки строки является операция агрегации (непосредственные биты [3: 2]).

  • ...

  • В равном порядке (imm [3: 2] = 11).Поиск подстроки (strstr) .Первый операнд содержит строку для поиска, второй - строку для поиска. Битовая маска содержит 1, если подстрока находится в соответствующей позиции: 

     operand2 = "WhenWeWillBeWed!", operand1 = "We"
 IntRes1  =  000010000000100

Послевычисляя функцию агрегирования, IntRes1 можно дополнить, расширить до байтовой маски (_mm_cmpistrm) или сжать до индекса (_mm_cmpistri).Результат записывается в регистры xmm0 или ECX.Руководство Intel хорошо объясняет эти детали, поэтому нет необходимости повторять их здесь.

Младшие 2 бита байта (00) указывают формат символов: в данном случае 00 unsigned BYTE.

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

Биты 5: 4 являются «полярностью»,Я думаю, что для работы с концом строки.

Бит 6 - это направление сканирования битов для «индексных» версий инструкции, которые возвращают индекс вместо маски.(например, bsr против bsf).0 в этом случае находит начало первого совпадения вместо конца последнего совпадения.

Бит 7 (старший бит 8-битного непосредственного) не используется / зарезервирован.

См. Также https://www.officedaytime.com/simd512e/simdimg/str.php?f=pcmpistri для таблиц / диаграмм шагов, которые приводят к результату,и как разные поля в немедленном изменении / выборе операций, выполняемых на разных этапах.

...