Побитовое И медленнее с SIMD, чем скалярное
Я пытался улучшить производительность больших (несколько гигабайт) операций с битрейром. Я не эксперт SIMD, но кажется, что SIMD, во всех случаях, медленнее, чем скалярные операции. Я пробовал несколько оптимизаций, включая развертывание цикла, но безрезультатно. Судя по сборке, это потому, что скаляры могут использовать регистры. Но, если я делаю что-то глупое, пожалуйста, дайте мне знать. В противном случае, я счастлив держать скаляры... это намного, намного проще.
/* gcc -Wall -O3 bitwise-and.c -o bitwise-and -m64 -fomit-frame-pointer -mtune=nocona -msse2 */
#ifdef ENABLE_PREFETCH
#warning "SIMD PREFETCHING ENABLED"
#else
#warning "SIMD PREFETCHING DISABLED"
#endif
#ifdef ENABLE_SIMD_UNROLLING
#warning "UNROLLING SIMD"
#else
#warning "NOT UNROLLING SIMD"
#endif
#ifdef AVOID_TEMP_VARS
#warning "AVOIDING SIMD TEMPORARY VARIABLES"
#else
#warning "USING SIMD TEMPORARY VARIABLES"
#endif
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <string.h>
#include <signal.h>
#include <setjmp.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <emmintrin.h>
#include <xmmintrin.h>
#include <assert.h>
#define __forceinline __attribute__((always_inline))
double
microtime (void)
{
struct timeval time;
gettimeofday(&time, NULL);
return (double) time.tv_sec * 1E6 + (double) time.tv_usec;
}
__forceinline void
simd_bitwise_and (unsigned char *dst, const unsigned char *src, unsigned block_size)
{
const __m128i *wrd_ptr = (__m128i *) src;
const __m128i *wrd_end = (__m128i *) (src + block_size);
__m128i *dst_ptr = (__m128i *) dst;
_mm_empty();
do
{
__m128i xmm1;
__m128i xmm2;
#ifdef ENABLE_SIMD_UNROLLING
# ifdef ENABLE_PREFETCH
_mm_prefetch((src + 512), _MM_HINT_NTA);
# endif
xmm1 = _mm_load_si128(wrd_ptr++);
xmm2 = _mm_load_si128(dst_ptr);
xmm1 = _mm_and_si128(xmm1, xmm2);
_mm_store_si128(dst_ptr++, xmm1);
xmm1 = _mm_load_si128(wrd_ptr++);
xmm2 = _mm_load_si128(dst_ptr);
xmm1 = _mm_and_si128(xmm1, xmm2);
_mm_store_si128(dst_ptr++, xmm1);
xmm1 = _mm_load_si128(wrd_ptr++);
xmm2 = _mm_load_si128(dst_ptr);
xmm1 = _mm_and_si128(xmm1, xmm2);
_mm_store_si128(dst_ptr++, xmm1);
xmm1 = _mm_load_si128(wrd_ptr++);
xmm2 = _mm_load_si128(dst_ptr);
xmm1 = _mm_and_si128(xmm1, xmm2);
_mm_store_si128(dst_ptr++, xmm1);
#else
# ifdef AVOID_TEMP_VARS
xmm1 = _mm_and_si128(*dst_ptr, *wrd_ptr);
# else
xmm1 = _mm_load_si128(wrd_ptr);
xmm2 = _mm_load_si128(dst_ptr);
xmm1 = _mm_and_si128(xmm1, xmm2);
# endif
_mm_store_si128(dst_ptr, xmm1);
++dst_ptr;
++wrd_ptr;
#endif
} while (wrd_ptr < wrd_end);
}
__forceinline void
word_bitwise_and (unsigned char *dst, const unsigned char *src, unsigned block_size)
{
unsigned int *wrd_ptr = (unsigned int *) src;
unsigned int *wrd_end = (unsigned int *) (src + block_size);
unsigned int *dst_ptr = (unsigned int *) dst;
do
{
dst_ptr[0] &= wrd_ptr[0];
dst_ptr[1] &= wrd_ptr[1];
dst_ptr[2] &= wrd_ptr[2];
dst_ptr[3] &= wrd_ptr[3];
dst_ptr += 4;
wrd_ptr += 4;
} while (wrd_ptr < wrd_end);
}
int
main (int argc, char **argv)
{
unsigned char *dest;
unsigned char *key1;
unsigned char *key2;
size_t minlen = (1024UL * 1024UL * 512UL);
double start_time = 0.0f;
double end_time = 0.0f;
posix_memalign((void *) &key1, sizeof(__m128i), minlen);
posix_memalign((void *) &key2, sizeof(__m128i), minlen);
posix_memalign((void *) &dest, sizeof(__m128i), minlen);
key1[128] = 0xff;
key2[128] = 0x03;
// 128-bit SIMD Bitwise AND
memcpy(dest, key1, minlen);
start_time = microtime();
simd_bitwise_and(dest, key2, minlen);
end_time = microtime();
printf("Elapsed: %8.6fs\n", (end_time - start_time));
assert(0x03 == dest[128]);
// 4xWORD Bitwise AND
memcpy(dest, key1, minlen);
start_time = microtime();
word_bitwise_and(dest, key2, minlen);
end_time = microtime();
printf("Elapsed: %8.6fs\n", (end_time - start_time));
assert(0x03 == dest[128]);
free(dest);
free(key2);
free(key1);
return EXIT_SUCCESS;
}
/* vi: set et sw=2 ts=2: */
1 ответ
Здесь происходит то, что вас укусило ленивое распределение виртуальной памяти. Если вы измените свой код на это:
// 128-bit SIMD Bitwise AND
memcpy(dest, key1, minlen);
start_time = microtime();
simd_bitwise_and(dest, key2, minlen);
end_time = microtime();
printf("SIMD Elapsed : %8.6fs\n", (end_time - start_time));
assert(0x03 == dest[128]);
// 4xWORD Bitwise AND
memcpy(dest, key1, minlen);
start_time = microtime();
word_bitwise_and(dest, key2, minlen);
end_time = microtime();
printf("Scalar Elapsed: %8.6fs\n", (end_time - start_time));
assert(0x03 == dest[128]);
// 128-bit SIMD Bitwise AND
memcpy(dest, key1, minlen);
start_time = microtime();
simd_bitwise_and(dest, key2, minlen);
end_time = microtime();
printf("SIMD Elapsed : %8.6fs\n", (end_time - start_time));
assert(0x03 == dest[128]);
// 4xWORD Bitwise AND
memcpy(dest, key1, minlen);
start_time = microtime();
word_bitwise_and(dest, key2, minlen);
end_time = microtime();
printf("Scalar Elapsed: %8.6fs\n", (end_time - start_time));
assert(0x03 == dest[128]);
вы должны увидеть результаты примерно так:
$ ./bitwise-and
SIMD Elapsed : 630061.000000s
Scalar Elapsed: 228156.000000s
SIMD Elapsed : 182645.000000s
Scalar Elapsed: 202697.000000s
$
Объяснение: при первой итерации по выделению большого объема памяти вы генерируете ошибки страниц, так как ранее неиспользуемые страницы подключаются. Это дает искусственно высокое время для первого теста, который является тестом SIMD. На втором и последующих бенчмарках все страницы соединены, и вы получите более точный бенчмарк, и, как и ожидалось, процедура SIMD немного быстрее, чем скалярная процедура. Разница не так велика, как можно было бы ожидать, поскольку вы выполняете только одну инструкцию ALU на каждые 2 загрузки + 1 хранилище, поэтому производительность ограничивается пропускной способностью DRAM, а не вычислительной эффективностью.
Как общее правило при написании кода тестирования: всегда вызывайте процедуру тестирования по крайней мере один раз перед любыми фактическими измерениями времени, чтобы все распределения памяти были правильно подключены. После этого запустите процедуру тестирования несколько раз в цикле и игнорируйте все останцы.