Вопросы о производительности разных реализаций strlen

Question

Я реализовал strlen() функционировать по-разному, в том числе SSE2 assembly, SSE4.2 assembly а также SSE2 intrinsicЯ также провел некоторые эксперименты на них, с strlen() in <string.h> а также strlen() in glibc, Однако их производительность в миллисекундах (времени) неожиданна.

Моя экспериментальная среда:CentOS 7.0 + gcc 4.8.5 + Intel Xeon

Ниже приведены мои реализации:

1. strlen используя сборку SSE2

   long strlen_sse2_asm(const char* src){
   long result = 0;
   asm(
       "movl %1, %%edi\n\t"
       "movl $-0x10, %%eax\n\t"
       "pxor %%xmm0, %%xmm0\n\t"
       "lloop:\n\t"
           "addl $0x10, %%eax\n\t"
           "movdqu (%%edi,%%eax), %%xmm1\n\t"
           "pcmpeqb %%xmm0, %%xmm1\n\t"
           "pmovmskb %%xmm1, %%ecx\n\t"
           "test %%ecx, %%ecx\n\t"
           "jz lloop\n\t"
   
       "bsf %%ecx, %%ecx\n\t"
       "addl %%ecx, %%eax\n\t"
       "movl %%eax, %0"
       :"=r"(result)
       :"r"(src)
       :"%eax"
       );
   return result;
   }
   

2.strlen используя сборку SSE4.2

long strlen_sse4_2_asm(const char* src){
long result = 0;
asm(
    "movl %1, %%edi\n\t"
    "movl $-0x10, %%eax\n\t"
    "pxor %%xmm0, %%xmm0\n\t"
    "lloop2:\n\t"
        "addl $0x10, %%eax\n\t"
        "pcmpistri $0x08,(%%edi, %%eax), %%xmm0\n\t"
        "jnz lloop2\n\t"

        "add %%ecx, %%eax\n\t"
        "movl %%eax, %0"

    :"=r"(result)
    :"r"(src)
    :"%eax"
    );
return result;
}

3. strlen с использованием встроенного SSE2

long strlen_sse2_intrin_align(const char* src){
if (src == NULL || *src == '\0'){
    return 0;
}
const __m128i zero = _mm_setzero_si128();
const __m128i* ptr = (const __m128i*)src;

if(((size_t)ptr&0xF)!=0){
    __m128i xmm = _mm_loadu_si128(ptr);
    unsigned int mask = _mm_movemask_epi8(_mm_cmpeq_epi8(xmm,zero));
    if(mask!=0){
        return (const char*)ptr-src+(size_t)ffs(mask);
    }
    ptr = (__m128i*)(0x10+(size_t)ptr & ~0xF);
}
for (;;ptr++){
    __m128i xmm = _mm_load_si128(ptr);
    unsigned int mask = _mm_movemask_epi8(_mm_cmpeq_epi8(xmm,zero));
    if (mask!=0)
        return (const char*)ptr-src+(size_t)ffs(mask);
}

}

4. Я также посмотрел, что реализовано в ядре Linux. Ниже приведена его реализация.

   size_t strlen_inline_asm(const char* str){
   int d0;
   size_t res;
   asm volatile("repne\n\t"
   "scasb"
   :"=c" (res), "=&D" (d0)
   : "1" (str), "a" (0), "" (0xffffffffu)
   : "memory");
   
   return ~res-1;
   }
   

По своему опыту я также добавил стандартную библиотеку и сравнил ее производительность. Мои подписки main код функции:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <xmmintrin.h>
#include <x86intrin.h>
#include <emmintrin.h>
#include <time.h>
#include <unistd.h>
#include <sys/time.h>
int main()
{
    struct timeval tpstart,tpend;
    int i=0;
    for(;i<1023;i++){
            test_str[i] = 'a';
    }
    test_str[i]='\0';
    gettimeofday(&tpstart,NULL);
    for(i=0;i<10000000;i++)
            strlen(test_str);
    gettimeofday(&tpend,NULL);
    printf("strlen from stirng.h--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);

    gettimeofday(&tpstart,NULL);
    for(i=0;i<10000000;i++)
            strlen_inline_asm(test_str);
    gettimeofday(&tpend,NULL);
    printf("strlen_inline_asm--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);

    gettimeofday(&tpstart,NULL);
    for(i=0;i<10000000;i++)
            strlen_sse2_asm(test_str);
    gettimeofday(&tpend,NULL);
    printf("strlen_sse2_asm--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);

    gettimeofday(&tpstart,NULL);
    for(i=0;i<10000000;i++)
            strlen_sse4_2_asm(test_str);
    gettimeofday(&tpend,NULL);
    printf("strlen_sse4_2_asm--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);

    gettimeofday(&tpstart,NULL);
    for(i=0;i<10000000;i++)
            strlen_sse2_intrin_align(test_str);
    gettimeofday(&tpend,NULL);
    printf("strlen_sse2_intrin_align--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);

    return 0;
}

Результат: (мс)

strlen from stirng.h--->23.518000
strlen_inline_asm--->222.311000
strlen_sse2_asm--->782.907000
strlen_sse4_2_asm--->955.960000
strlen_sse2_intrin_align--->3499.586000

У меня есть несколько вопросов по этому поводу:

1. Зачем strlen из string.h так быстро? Я думаю, что его код должен быть идентифицирован strlen_inline_asm потому что я скопировал код из /linux-4.2.2/arch/x86/lib/string_32.c[ http://lxr.oss.org.cn/source/arch/x86/lib/string_32.c#L164%5D
2. Зачем sse2 intrinsic а также sse2 assembly так отличаются по производительности?
3. Может ли кто-нибудь помочь мне, как разобрать код, чтобы я мог видеть, что имеет функцию strlen статическая библиотека была преобразована компилятором? я использовал gcc -s но не нашел разборки strlen from the <string.h>
4. Я думаю, что мой код может быть не очень хорошо, я был бы признателен, если бы вы могли помочь мне улучшить мой код, особенно сборочные.

Благодарю.

Answer 1

Как я уже говорил в комментариях, ваша самая большая ошибка - это сравнение с -O0, Я обсуждал, почему именно тестирование -O0 это ужасная идея в первой части другого поста.

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

-O0 объясняет, что встроенный asm намного быстрее, чем C, с помощью встроенных функций (или обычного скомпилированного C, для реализации C strlen, заимствованной из glibc)

ИДК -O0 все равно оптимизировал бы цикл отсутствия, который неоднократно отбрасывает результат работы библиотеки strlen, или если бы он каким-то образом просто избежал какой-то другой огромной ошибки производительности. Не интересно догадываться, что именно произошло в таком некорректном тесте.

---

Я ужесточил вашу версию SSE2 inline-asm. Главным образом только потому, что я недавно играл с встроенными ограничениями ввода / вывода gcc asm и хотел посмотреть, как это будет выглядеть, если я напишу его, чтобы компилятор мог выбирать, какие регистры использовать для временных файлов, и избегал ненужных инструкций.

Один и тот же встроенный ассемблер работает для 32- и 64-битных целей x86; см. это скомпилировано для обоих на проводнике компилятора Godbolt. При компиляции в автономную функцию не требуется сохранять / восстанавливать какие-либо регистры даже в 32-битном режиме:

ВНИМАНИЕ: он может читать после конца строки до 15 байтов. Это может быть причиной ошибки. См. Безопасно ли читать после конца буфера на одной и той же странице на x86 и x64? подробнее об избежании этого: доберитесь до границы выравнивания, затем используйте выровненные нагрузки, потому что это всегда безопасно, если вектор содержит не менее 1 байта строковых данных. Я оставил код без изменений, потому что интересно обсудить эффект выравнивания указателей для SSE и AVX. Выравнивание указателей также позволяет избежать разбиения строки кэша и разбиения страницы на 4 тыс. (Что является ошибкой производительности до Skylake).

#include <immintrin.h>

size_t strlen_sse2_asm(const char* src){

  // const char *orig_src = src; // for a pointer-increment with a "+r" (src) output operand

  size_t result = 0;
  unsigned int tmp1;
  __m128i zero = _mm_setzero_si128(), vectmp;

  // A pointer-increment may perform better than an indexed addressing mode
  asm(
    "\n.Lloop:\n\t"
        "movdqu   (%[src], %[res]), %[vectmp]\n\t"  // result reg is used as the loop counter
        "pcmpeqb  %[zerovec], %[vectmp]\n\t"
        "pmovmskb %[vectmp], %[itmp]\n\t"
        "add      $0x10, %[res]\n\t"
        "test     %[itmp], %[itmp]\n\t"
        "jz  .Lloop\n\t"

    "bsf %[itmp], %[itmp]\n\t"
    "add %q[itmp], %q[res]\n\t"   // q modifier to get quadword register.
    // (add %edx, %rax doesn't work).  But in 32bit mode, q gives a 32bit reg, so the same code works
    : [res] "+r"(result), [vectmp] "=&x" (vectmp), [itmp] "=&r" (tmp1)

    : [zerovec] "x" (zero) // There might already be a zeroed vector reg when inlining
      , [src] "r"(src)
      , [dummy] "m" (*(const char (*)[])src) // this reads the whole object, however long gcc thinks it is
    : //"memory"        // not needed because of the dummy input
    );
  return result;
  // return result + tmp1;  // doing the add outside the asm makes gcc sign or zero-extend tmp1.
  // No benefit anyway, since gcc doesn't know that tmp1 is the offset within a 16B chunk or anything.
}

Обратите внимание на фиктивный ввод, как альтернативу "memory" clobber, чтобы сообщить компилятору, что встроенный asm читает память, на которую указывает src, а также значение src сам. (Компилятор не знает, что делает asm; для всего, что он знает, asm просто выравнивает указатель с and или что-то еще, так что если предположить, что все входные указатели разыменованы, это приведет к пропущенным оптимизациям при переупорядочении / объединении нагрузок и сохранений в ассемблере. Кроме того, это позволяет компилятору знать, что мы только читаем память, а не модифицируем ее.) Руководство GCC использует пример с этим синтаксисом массива неопределенной длины. "m" (*(const char (*)[])src)

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

Если бы вы могли сбрить другой моп из внутреннего цикла, это было бы до 4 мопов, которые могли бы выпустить по одному за цикл. Таким образом, 5 мопов означают, что для каждой итерации может потребоваться 2 цикла для запуска с внешнего интерфейса на процессорах Intel SnB. ( Или 1,25 цикла на более поздних процессорах, таких как Haswell, и, возможно, на SnB, если я ошибся в поведении целых чисел.)

Использование выровненного указателя позволит нагрузке складываться в операнд памяти для pcmpeqb, (Также необходимо для корректности, если начало строки не выровнено, а конец находится ближе к концу страницы). Интересно, что использование нулевого вектора в качестве пункта назначения для pcmpeqb в теории это нормально: вам не нужно заново обнулять вектор между итерациями, потому что вы выходите из цикла, если он когда-либо не равен нулю. Он имеет задержку в 1 цикл, поэтому преобразование нулевого вектора в зависимость, переносимую циклом, является проблемой только в том случае, если пропуск кэша задерживает старую итерацию. Однако удаление этой цепочки зависимостей, переносимых циклами, может помочь на практике, позволяя бэкэнду работать быстрее, когда он наверстывает упущенное после кеша, который задерживает старую итерацию.

AVX полностью решает проблему (за исключением корректности, если строка заканчивается в конце страницы). AVX позволяет складывать груз даже без предварительной проверки выравнивания. 3-операнд неразрушающий vpcmpeqb избегает превращения нулевого вектора в переносимую петлей зависимость. AVX2 позволит проверять 32B одновременно.

Развертывание поможет в любом случае, но поможет больше без AVX. Выровняйте по границе 64B или что-то, а затем загрузите всю строку кэша в четыре вектора по 16B. Делать комбинированную проверку на результат POR Объединение их всех может быть хорошим, так как pmovmsk + compare-and-branch это 2 мопс.

Использование SSE4.1 PTEST не помогает (по сравнению с pmovmsk / test / jnz) потому что это 2 мопа и не может слить макрос test Можно.

PTEST может напрямую проверять, чтобы весь вектор 16B был полностью нулевым или единичным (используя ANDNOT -> часть CF), но не, если один из байтовых элементов равен нулю. (Так что мы не можем избежать pcmpeqb).

---

Посмотрите руководства Agner Fog по оптимизации asm и другие ссылки на вики x86. Большинство оптимизаций (Agner Fog, Intel и AMD) будут касаться оптимизации memcpy и strlen, в частности, IIRC.

Answer 2

Если вы прочитаете исходный код функции strlen в glibc, вы увидите, что функция проверяет не строку char с помощью char, а longword с помощью longword со сложными побитовыми операциями: http://www.stdlib.net/~colmmacc/strlen.c.html. Я предполагаю, что это объясняет его скорость, но тот факт, что он даже быстрее, чем инструкции в сборке, действительно удивляет.