Почему strcmp не оптимизирован SIMD?

Ответ 1

В реализации SSE2 каким образом компилятор должен убедиться, что в конце строки не происходит доступа к памяти? Сначала он должен знать длину, и для этого требуется сканирование строки для завершающего нулевого байта.

Если вы просматриваете длину строки, вы уже выполнили большую часть работы функции strcmp. Поэтому нет пользы для использования SSE2.

Однако Intel добавила инструкции для обработки строк в наборе инструкций SSE4.2. Они обрабатывают проблему с завершающим нулевым байтом. Для хорошей записи на них читайте этот блог-пост:

http://www.strchr.com/strcmp_and_strlen_using_sse_4.2

Ответ 2

GCC в этом случае использует встроенный strcmp. Если вы хотите использовать версию из glibc, используйте -fno-builtin. Но вы не должны предполагать, что встроенная версия GCC strcmp или glibc implementationaiton strcmp эффективна. Я знаю по опыту, что GCC builtin memcpy и glibc memcpy не так эффективны, как могут быть.

Предлагаю вам посмотреть Agner Fog asmlib. Он оптимизировал несколько стандартных функций библиотеки в сборке. См. Файл strcmp64.asm. Это имеет две версии: общую версию для процессоров без SSE4.2 и версию для процессоров с SSE4.2. Вот основной цикл для версии SSE4.2

compareloop:
        add     rax, 16                ; increment offset
        movdqu  xmm1, [rs1+rax]        ; read 16 bytes of string 1
        pcmpistri xmm1, [rs2+rax], 00011000B ; unsigned bytes, equal each, invert. returns index in ecx
        jnbe    compareloop            ; jump if not carry flag and not zero flag

В родовой версии он пишет

Это очень простое решение. Существует не так много, используя SSE2 или что-то сложное

Вот основной цикл общей версии:

_compareloop:
        mov     al, [ss1]
        cmp     al, [ss2]
        jne     _notequal
        test    al, al
        jz      _equal
        inc     ss1
        inc     ss2
        jmp     _compareloop 

Я бы сравнил производительность GCC builtin strcmp, GLIBC strcmp и asmlib strcmp. Вы должны посмотреть на разборку, чтобы убедиться, что вы получили встроенный код. Например, GCC memcpy не использует встроенную версию размером больше 8192.

Изменить: Что касается длины строки, версия Agner SSE4.2 считывает до 15 байтов за пределы строки. Он утверждает, что это редко проблема, поскольку ничего не написано. Это не проблема для распределенных стеков массивов. Для статически распределенных массивов это может быть проблемой для границ страницы памяти. Чтобы обойти это, он добавляет 16 байтов в раздел .bss после раздела .data. Более подробную информацию см. В разделе 1.7. Инструкции по строкам и меры предосторожности в мануале asmlib.

Ответ 3

Когда была разработана стандартная библиотека для C, реализации методов string.h, которые были наиболее эффективными при работе с большими объемами данных, были бы разумно эффективными для небольших количеств и наоборот. Хотя могут быть некоторые сценарии сравнения строк, сложное использование инструкций SIMD могло бы обеспечить лучшую производительность, чем "наивная реализация", во многих реальных сценариях сравниваемые строки будут отличаться в первых нескольких символах. В таких ситуациях наивная реализация может дать результат за меньшее время, чем "более сложный" подход будет определять, как должно быть проведено сравнение. Обратите внимание, что даже если код SIMD способен обрабатывать 16 байт за раз и останавливается, когда обнаружено условие несоответствия или завершения строки, все равно придется выполнять дополнительную работу, эквивалентную использованию наивного подхода для последних 16 символов, отсканированных, Если много групп из 16 байтов совпадают, возможность быстрого сканирования через них может принести пользу производительности. Но в тех случаях, когда первые 16 байтов не совпадают, было бы более эффективно начинать с сравнения по каждому символу.

Кстати, еще одно потенциальное преимущество "наивного" подхода состоит в том, что можно было бы определить его встроенным как часть заголовка (или компилятор мог бы считать себя имеющим специальные "знания" об этом). Рассмотрим:

int strcmp(char *p1, char *p2)
{
  int idx=0,t1,t2;
  do
  {
    t1=*p1; t2=*p2;
    if (t1 != t2)
    {
      if (t1 > t2) return 1;
      return -1;
    }
    if (!t1)
      return 0;
    p1++; p2++;
  } while(1);
}
...invoked as:
if (strcmp(p1,p2) > 0) action1();
if (strcmp(p3,p4) != 0) action2();

В то время как метод будет немного большим, чтобы быть вложенным, встраивание может в первом случае позволить компилятору устранить код, чтобы проверить, было ли возвращаемое значение больше нуля, а во втором - исключить код который проверял, было ли t1 больше, чем t2. Такая оптимизация невозможна, если метод был отправлен через косвенный скачок.

Ответ 4

Я подозреваю, что в SIMD-версиях функций библиотеки просто нет смысла с очень небольшим количеством вычислений. Я полагаю, что такие функции, как strcmp, memcpy и аналогичные, фактически ограничены полосой пропускания памяти, а не скоростью процессора.

Ответ 5

Это зависит от вашей реализации. В MacOS X такие функции, как memcpy, memmove и memset, имеют реализации, которые оптимизируются в зависимости от используемого вами оборудования (один и тот же вызов будет выполнять другой код в зависимости от процессора, настроенного во время загрузки); эти реализации используют SIMD и для больших объемов (мегабайт) используют некоторые довольно причудливые трюки для оптимизации использования кеша. Насколько мне известно, ничего для strcpy и strcmp.

Убедить стандартную библиотеку С++ в использовании такого кода сложно.

Ответ 6

Создание версии SSE2 strcmp было для меня интересной задачей.
Мне действительно не нравятся внутренние функции компилятора из-за раздувания кода, поэтому я решил выбрать метод автоматической векторизации. Мой подход основан на шаблонах и аппроксимирует регистр SIMD как массив слов разных размеров.

Я попытался написать автоинъекционную реализацию и протестировать ее с помощью компиляторов GCC и MSVС++.

Итак, я узнал:
1. GCC авто-векторный инструмент хорош (удивительный?)
2. Авто-векторный анализатор MSVC хуже, чем GCC (не векторизовать мою функцию упаковки)
3. Все компиляторы отказались генерировать инструкцию PMOVMSKB, это действительно печально.

Результаты:
Версия, сгенерированная онлайн-GCC, достигает ~ 40% с автоинъекцией SSE2. На моей Windows-машине с автоматическим векторизованным кодом процессора Bulldozer архитектура быстрее, чем онлайн-компилятор, и результаты соответствуют встроенной версии strcmp. Но самое лучшее в этой идее состоит в том, что один и тот же код может быть скомпилирован для любого набора команд SIMD, по крайней мере, на ARM и X86.

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

Параметры командной строки для GCC: -std = С++ 11 -O2 -m64 -mfpmath = sse -march = native -ftree-vectorize -msse2 -march = native -Wall -Wextra

Ссылки:
Исходный код, скомпилированный онлайн-компилятором Coliru
Сборка + Исходный код (Проводник компилятора)

@PeterCordes, спасибо за помощь.

Ответ 7

AVX 2.0 будет быстрее на самом деле

Изменить: Это связано с регистрами и IPC

Вместо того, чтобы полагаться на 1 большую инструкцию, вы можете использовать множество команд SIMD с 16 регистрами по 32 байта, ну, в UTF16 вы даете вам 265 символов, чтобы играть с!

double, что с avx512 за несколько лет!

Инструкции AVX также имеют высокую пропускную способность.

Согласно этому блогу: https://blog.cloudflare.com/improving-picohttpparser-further-with-avx2/

Сегодня на последних процессорах Haswell мы имеем мощный AVX2 инструкции. Инструкции AVX2 работают на 32 байта, и большая часть логические/логические команды выполняются с пропускной способностью 0,5 цикла за инструкцию. Это означает, что мы можем выполнить примерно 22 AVX2 инструкции за такое же количество времени, которое требуется для выполнения одного PCMPESTRI. Почему бы не сделать снимок?

Изменить 2.0 Блоки SSE/AVX имеют мощность, и смешивание инструкций SSE и/или AVX с обычными включает в себя коммутатор контекста с ограничением производительности, который не должен иметься с инструкцией strcmp.

Ответ 8

Я не вижу смысла в "оптимизации" функции типа strcmp.

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

Если вы хотите быстро делать строки со строками, вам понадобятся специализированные инструменты, такие как конечные машины (lexx приходит на ум для синтаксического анализатора).

Что касается С++ std::string, они неэффективны и медленны по множеству причин, поэтому усиление проверки длины в сравнениях пренебрежимо.