Про оптимизацию функции memset используя SSE

Продолжаю интересоваться возможностями SIMD команд в плане оптимизации своего кода. Сегодня поговорим, про заполнение памяти и соответственно функцию memset.

Функция memset, как известно, заполняет область памяти переданным байтом, соответственно на вход получает указатель на эту самую область и сам байт. Поскольку задача оптимизировать функцию с использованием SSE команд, писать мы будем на ассемблере. А значит, параметры функции будем передавать в регистрах процессора. Договоримся следующим образом. Указатель на память, которую необходимо заполнить передаем в регистре EDI, размер памяти (в байтах) – в ECX, а значение которым будем заполнять - в EAX.

Чтобы работать с ассемблером непосредственно в Visual C++ рекомендую, кроме служебного слова _asm, посмотреть в MSDN, что означает вот такая конструкция __declspec(naked). Местами это сильно облегчит жизнь.

Стандартный вариант функции memset выглядит следующим образом

mov         bl,al 
mov         bh,bl 
mov         eax,ebx 
shl         eax,10h 
mov         ax,bx 
mov         ebx, ecx 
shr         ecx, 2 
rep stosd
mov         ecx,ebx 
and         ecx,3 
rep stosb

Наша задача ускорить его, используя SSE команды.

Но прежде чем предложить измененный вариант, необходимо поговорить о том, как мы будем осуществлять сравнение скоростей. Я набросал простенькое консольное приложение, которое выделяло память, вызывало 1000 раз функцию и замеряло время. Размеры блоков варьировались от 50 байт до 10 мегабайт.

Когда мы используем SSE, следует учитывать, что память, с которой мы работаем, должна быть выровнена к 16 байтам (иначе пересылка содержимого регистров XMM в память будет крайне медленной). Поэтому работа новой функции разбивается на три этапа. Первый заполняем память командой rep stosb, до того момента пока указатель не будет кратен 16, затем помещаем во все байты регистра XMM0, и в цикле копируем его в память. И, наконец, вновь при помощи rep stosb заполняем остаток. На первом и последнем шаге размер буфера будет от 0 и до 15 байт.

Выглядит эта новая функция, следующим образом:

 test ecx, ecx
 jz func_exit
  
 cmp ecx, 0x1F
 jge sse_part

 mov         bl,al 
 mov         bh,bl 
 mov         eax,ebx 
 shl         eax,10h 
 mov         ax,bx 
 mov         ebx, ecx 
 shr         ecx, 2 
 rep stosd
 mov         ecx,ebx 
 and         ecx,3 
 rep stosb
 jmp func_exit
sse_part:
 mov         ebx, edi
 and         ebx, 0x0F
 jz xmm_align
       
 xor         bl, 0x0F
 inc         ebx
 sub         ecx, ebx

loop_byte_2:
 mov         [edi], al
 inc         edi
 dec         ebx
 jnz loop_byte_2

xmm_align:
 pxor        xmm0, xmm0
 movd        xmm0, eax
 punpcklwd   xmm0, xmm0
 pshufd      xmm0, xmm0, 0   
 movdqa      xmm1, xmm0  
 psllw       xmm1, 8
 por         xmm0, xmm1
 mov         ebx, ecx
 and         ebx, 0x0F
 shr         ecx, 4

loop_xmm:
 movntdq     [edi], xmm0
 add         edi, 0x10
 dec         ecx
 jnz loop_xmm
 
 mov         ecx, ebx
 rep stosb 

func_exit:
 sfence
 emms
 ret

Итак, и первый и второй вариант прекрасно работают. Теперь про интересное, а именно посмотрим на график скорости в зависимости от размера заполняемого блока. На нем по вертикальной оси прописаны размеры блока в байтах, гистограммы показывают скорость копирования в МБ/сек.



Не трудно видеть, что обычная функция существенно обгоняет SSE вариант на блоках до 1 мегабайта, однако проигрывает практически вдвое в случае, когда размер блока больше 1 мегабайта. Дополнительные измерения на отрезке от 500 000 байт до 1 000 000 байт показали, что смена лидера происходит в случае, когда размер блока примерно равен 590 000 байт. Не трудно догадаться, с чем связано такое поведение. У процессора, на котором производилось тестирование, L2 Cache – 512 КБ, соответственно, когда мы заполняли один и тот же блок постоянно, вся работа производилась внутри кеша, пока его хватало. На больших же блоках кеша не хватало, и мы имели резкое падение скорости работы обычной функции. Т.е. фактически мы имеем некорректный тестовый стенд.

Ну и что-то вроде вывода из всего этого хозяйства, который я сделал лично для себя. Если размер блока большой (больше мегабайта), то я пользую SSE вариант и не забиваю голову сомненьями. Если меньше, то смотрю по ситуации. Например, если много маленьких блоков разбросанных по памяти, и работать приходится то с одним то с другим, т.е. гарантировать, что все они поместятся в кешь и будут там постоянно находится я не могу, то снова пользую SSE вариант. А если надо 10 байт обнулить и потом с ними постоянно работать, то ну его этот SSE буду пользовать классический rep stosb.

А если серьезно, то вывод таков, что при оптимизации, надо не забывать учитывать наличие кеша процессора, и писать код с оглядкой на этот замечательный механизм. Будет время напишу более подробно, ибо вот memset то мы оптимизировали, а на подходе функция memcpy, которая так же крайне важна и нуждается в оптимизации.