Можно ли оптимизировать эту функцию с помощью SIMD?

Question

Профилирование предполагает, что эта функция здесь настоящее горлышко бутылки для моего приложения:

static inline int countEqualChars(const char* string1, const char* string2, int size) { 
    int r = 0; 
    for (int j = 0; j < size; ++j) { 
     if (string1[j] == string2[j]) { 
      ++r; 
     } 
    } 

    return r; 
} 

Даже с -O3 и -march = родным, G ++ 4.7.2 не векторизаций этой функции (я проверил выход на ассемблер) , Теперь я не эксперт с SSE и друзьями, но я думаю, что сравнение более чем одного персонажа сразу должно быть быстрее. Любые идеи о том, как ускорить процесс? Целевая архитектура - x86-64.

Answer 1

флаги компилятора для векторизации:

-ftree-vectorize

-ftree-vectorize-march=<your_architecture>

Использование SSEx: встроенные функции

• Padd и выравнивают буфер до 16 байт (в зависимости от размера вектора на самом деле вы собираетесь использовать)

• Создать накопитель countU8 с _mm_set1_epi8 (0)

• Для всех n/16 в ставить (суб) векторы, сделайте следующее:

  • нагрузки 16 символами из обоего строк с _mm_load_si128 или _mm_loadu_si128 (для выровненных нагрузок)

  • _mm_cmpeq_epi8 сравнить октет параллельно. Каждое совпадение дает 0xFF (-1), 0x00 в противном случае.

  • Вычтите вышеуказанный результат вектор от countU8 использованием _mm_sub_epi8 (минус -1 -> +1)

  • Всегда после 255 циклов, 16 8bit счетчики должны быть извлечены в большее целое число типа, чтобы предотвратить переполнение. См распаковывать и горизонтальный добавить в этот хороший ответ за то, как сделать это: https://stackoverflow.com/a/10930706/1175253

Код:

#include <iostream> 
#include <vector> 

#include <cassert> 
#include <cstdint> 
#include <climits> 
#include <cstring> 

#include <emmintrin.h> 

#ifdef __SSE2__ 

#if !defined(UINTPTR_MAX) || !defined(UINT64_MAX) || !defined(UINT32_MAX) 
# error "Limit macros are not defined" 
#endif 

#if UINTPTR_MAX == UINT64_MAX 
    #define PTR_64 
#elif UINTPTR_MAX == UINT32_MAX 
    #define PTR_32 
#else 
# error "Current UINTPTR_MAX is not supported" 
#endif 

template<typename T> 
void print_vector(std::ostream& out,const __m128i& vec) 
{ 
    static_assert(sizeof(vec) % sizeof(T) == 0,"Invalid element size"); 
    std::cout << '{'; 
    const T* const end = reinterpret_cast<const T*>(&vec)-1; 
    const T* const upper = end+(sizeof(vec)/sizeof(T)); 
    for(const T* elem = upper; 
     elem != end; 
     --elem 
    ) 
    { 
     if(elem != upper) 
      std::cout << ','; 
     std::cout << +(*elem); 
    } 
    std::cout << '}' << std::endl; 
} 

#define PRINT_VECTOR(_TYPE,_VEC) do{ std::cout << #_VEC << " : "; print_vector<_TYPE>(std::cout,_VEC); } while(0) 

///@note SSE2 required (macro: __SSE2__) 
///@warning Not tested! 
size_t counteq_epi8(const __m128i* a_in,const __m128i* b_in,size_t count) 
{ 
    assert(a_in != nullptr && (uintptr_t(a_in) % 16) == 0); 
    assert(b_in != nullptr && (uintptr_t(b_in) % 16) == 0); 
    //assert(count > 0); 


/* 
    //maybe not so good with all that branching and additional loop variables 

    __m128i accumulatorU8 = _mm_set1_epi8(0); 
    __m128i sum2xU64 = _mm_set1_epi8(0); 
    for(size_t i = 0;i < count;++i) 
    { 

     //this operation could also be unrolled, where multiple result registers would be accumulated 
     accumulatorU8 = _mm_sub_epi8(accumulatorU8,_mm_cmpeq_epi8(*a_in++,*b_in++)); 
     if(i % 255 == 0) 
     { 
      //before overflow of uint8, the counter will be extracted 
      __m128i sum2xU16 = _mm_sad_epu8(accumulatorU8,_mm_set1_epi8(0)); 
      sum2xU64 = _mm_add_epi64(sum2xU64,sum2xU16); 

      //reset accumulatorU8 
      accumulatorU8 = _mm_set1_epi8(0); 
     } 
    } 

    //blindly accumulate remaining values 
    __m128i sum2xU16 = _mm_sad_epu8(accumulatorU8,_mm_set1_epi8(0)); 
    sum2xU64 = _mm_add_epi64(sum2xU64,sum2xU16); 

    //do a horizontal addition of the two counter values 
    sum2xU64 = _mm_add_epi64(sum2xU64,_mm_srli_si128(sum2xU64,64/8)); 

#if defined PTR_64 
    return _mm_cvtsi128_si64(sum2xU64); 
#elif defined PTR_32 
    return _mm_cvtsi128_si32(sum2xU64); 
#else 
# error "macro PTR_(32|64) is not set" 
#endif 

*/ 

    __m128i sum2xU64 = _mm_set1_epi32(0); 
    while(count--) 
    { 
     __m128i matches  = _mm_sub_epi8(_mm_set1_epi32(0),_mm_cmpeq_epi8(*a_in++,*b_in++)); 
     __m128i sum2xU16 = _mm_sad_epu8(matches,_mm_set1_epi32(0)); 
       sum2xU64 = _mm_add_epi64(sum2xU64,sum2xU16); 
#ifndef NDEBUG 
     PRINT_VECTOR(uint16_t,sum2xU64); 
#endif 
    } 

    //do a horizontal addition of the two counter values 
    sum2xU64 = _mm_add_epi64(sum2xU64,_mm_srli_si128(sum2xU64,64/8)); 
#ifndef NDEBUG 
    std::cout << "----------------------------------------" << std::endl; 
    PRINT_VECTOR(uint16_t,sum2xU64); 
#endif 

#if !defined(UINTPTR_MAX) || !defined(UINT64_MAX) || !defined(UINT32_MAX) 
# error "Limit macros are not defined" 
#endif 

#if defined PTR_64 
    return _mm_cvtsi128_si64(sum2xU64); 
#elif defined PTR_32 
    return _mm_cvtsi128_si32(sum2xU64); 
#else 
# error "macro PTR_(32|64) is not set" 
#endif 

} 

#endif 

int main(int argc, char* argv[]) 
{ 

    std::vector<__m128i> a(64); // * 16 bytes 
    std::vector<__m128i> b(a.size()); 
    const size_t nBytes = a.size() * sizeof(std::vector<__m128i>::value_type); 

    char* const a_out = reinterpret_cast<char*>(a.data()); 
    char* const b_out = reinterpret_cast<char*>(b.data()); 

    memset(a_out,0,nBytes); 
    memset(b_out,0,nBytes); 

    a_out[1023] = 1; 
    b_out[1023] = 1; 

    size_t equalBytes = counteq_epi8(a.data(),b.data(),a.size()); 

    std::cout << "equalBytes = " << equalBytes << std::endl; 

    return 0; 
} 

---

Самый быстрый реализация SSE я получил для больших и маленьких массивы:

size_t counteq_epi8(const __m128i* a_in,const __m128i* b_in,size_t count) 
{ 
    assert((count > 0 ? a_in != nullptr : true) && (uintptr_t(a_in) % sizeof(__m128i)) == 0); 
    assert((count > 0 ? b_in != nullptr : true) && (uintptr_t(b_in) % sizeof(__m128i)) == 0); 
    //assert(count > 0); 

    const size_t maxInnerLoops = 255; 
    const size_t nNestedLoops  = count/maxInnerLoops; 
    const size_t nRemainderLoops = count % maxInnerLoops; 

    const __m128i zero = _mm_setzero_si128(); 
    __m128i sum16xU8 = zero; 
    __m128i sum2xU64 = zero; 

    for(size_t i = 0;i < nNestedLoops;++i) 
    { 
     for(size_t j = 0;j < maxInnerLoops;++j) 
     { 
      sum16xU8 = _mm_sub_epi8(sum16xU8,_mm_cmpeq_epi8(*a_in++,*b_in++)); 
     } 
     sum2xU64 = _mm_add_epi64(sum2xU64,_mm_sad_epu8(sum16xU8,zero)); 
     sum16xU8 = zero; 
    } 

    for(size_t j = 0;j < nRemainderLoops;++j) 
    { 
     sum16xU8 = _mm_sub_epi8(sum16xU8,_mm_cmpeq_epi8(*a_in++,*b_in++)); 
    } 
    sum2xU64 = _mm_add_epi64(sum2xU64,_mm_sad_epu8(sum16xU8,zero)); 

    sum2xU64 = _mm_add_epi64(sum2xU64,_mm_srli_si128(sum2xU64,64/8)); 

#if UINTPTR_MAX == UINT64_MAX 
    return _mm_cvtsi128_si64(sum2xU64); 
#elif UINTPTR_MAX == UINT32_MAX 
    return _mm_cvtsi128_si32(sum2xU64); 
#else 
# error "macro PTR_(32|64) is not set" 
#endif 
} 

Answer 2

Конечно, это возможно.

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

Если длина очень короткая, будет трудно получить значительное ускорение от этого подхода. Если длина длинная, то это будет стоить того.

Answer 3

Авто-векторизация в текущем gcc заключается в том, чтобы помочь компилятору понять, что легко векторизовать код. В вашем случае: он будет понимать запрос векторизации, если вы удалите условное и переписать код в более повелительном образом:

static inline int count(const char* string1, const char* string2, int size) { 
      int r = 0; 
      bool b; 

      for (int j = 0; j < size; ++j) { 
        b = (string1[j] == string2[j]); 
        r += b; 
      } 

      return r; 
    } 

В этом случае:

movdqa 16(%rsp), %xmm1 
movl $.LC2, %esi 
pxor %xmm2, %xmm2 
movzbl 416(%rsp), %edx 
movdqa .LC1(%rip), %xmm3 
pcmpeqb 224(%rsp), %xmm1 
cmpb %dl, 208(%rsp) 
movzbl 417(%rsp), %eax 
movl $1, %edi 
pand %xmm3, %xmm1 
movdqa %xmm1, %xmm5 
sete %dl 
movdqa %xmm1, %xmm4 
movzbl %dl, %edx 
punpcklbw %xmm2, %xmm5 
punpckhbw %xmm2, %xmm4 
pxor %xmm1, %xmm1 
movdqa %xmm5, %xmm6 
movdqa %xmm5, %xmm0 
movdqa %xmm4, %xmm5 
punpcklwd %xmm1, %xmm6 

(и т.д.)