сравните буферы как можно быстрее - PullRequest
Новая
       2

сравните буферы как можно быстрее

6 голосов
/ 26 мая 2011

Мне нужно сравнить два буфера по частям на равенство. Мне не нужна информация о соотношении двух буферов, просто если каждые два блока равны или нет. Моя машина Intel поддерживает до SSE4.2

Наивный подход: 

const size_t CHUNK_SIZE = 16; //128bit for SSE2 integer registers
const int ARRAY_SIZE = 200000000;

char* array_1 = (char*)_aligned_malloc(ARRAY_SIZE, 16);
char* array_2 = (char*)_aligned_malloc(ARRAY_SIZE, 16);

for (size_t i = 0; i < ARRAY_SIZE; )
{
    volatile bool result = memcmp(array_1+i, array_2+i, CHUNK_SIZE);
    i += CHUNK_SIZE;
}

По сравнению с моей первой попыткой использовать SSE: 

union U
{
    __m128i m;
    volatile int i[4];
} res;

for (size_t i = 0; i < ARRAY_SIZE; )
{
    __m128i* pa1 = (__m128i*)(array_1+i);
    __m128i* pa2 = (__m128i*)(array_2+i);
    res.m = _mm_cmpeq_epi32(*pa1, *pa2);
    volatile bool result =  ( (res.i[0]==0) || (res.i[1]==0) || (res.i[2]==0) || (res.i[3]==0) );
    i += CHUNK_SIZE;
}

Прирост скорости составляет около 33%. Могу ли я сделать что-нибудь лучше?

Ответы [ 2 ]

4 голосов
/ 26 мая 2011

Вы действительно не должны использовать скалярный код и объединения для проверки всех отдельных векторных элементов - вместо этого сделайте что-то вроде этого: 

for (size_t i = 0; i < ARRAY_SIZE; i += CHUNK_SIZE)
{
    const __m128i a1 = _mm_load_si128(array_1 + i);
    const __m128i a2 = _mm_load_si128(array_2 + i);
    const __m128i vcmp = _mm_cmpeq_epi32(a1, a2);
    const int vmask = _mm_movemask_epi8(vcmp);
    const bool result = (vmask == 0xffff);
    // you probably want to break here if you get a mismatch ???
}
2 голосов
/ 26 мая 2011

Поскольку вы можете использовать SSE 4.1, существует другая альтернатива, которая может быть быстрее: 

for (size_t i = 0; i < ARRAY_SIZE; i += CHUNK_SIZE;)
{
    __m128i* pa1 = (__m128i*)(array_1+i);
    __m128i* pa2 = (__m128i*)(array_2+i);
    __m128i temp = _mm_xor_si128(*pa1, *pa2);
    bool result = (bool)_mm_testz_si128(temp, temp);
}

_mm_testz_si128(a, b) возвращает 0, если a & b != 0, и возвращает 1, если a & b == 0.Преимущество состоит в том, что вы можете использовать эту версию и с новыми инструкциями AVX, где размер фрагмента составляет 32 байта.

...