быстрый xor на amd x86_64

Offtop: Говорят, циклы с декрементом работают быстрее.

Что-то как-то С не оптимально переводит в асм (может и исходник крив), но если поработать руками, имхо, можно порядком подсократить алгоритм. Напиши тоже самое на асме руками и сравни.

А кто RAND_bytes в исходники ложить будет?

Вощем собирал так:

gcc -O3 -funroll-loop test.c

Выхлоп теста:

 test for i = 1000
duration 1 = 63.398000
duration 2 = 85.329000
duration 3 = 7112.810000
 test for i = 100000
duration 1 = 56.890000
duration 2 = 85.336000
duration 3 = 8485.580000
 test for i = 10000000
duration 1 = 78.274000
duration 2 = 85.708000
duration 3 = 8758.358000

PS: Athlon 64 X2 4200+

gcc -lssl

Без -funroll-loops
./a.out
test for i = 1000
duration 1 = 7569.908000
duration 2 = 2070.178000
duration 3 = 10426.047000
test for i = 100000
duration 1 = 7617.404000
duration 2 = 2069.797000
duration 3 = 10413.663000
test for i = 10000000
duration 1 = 7520.315000
duration 2 = 2086.907000
duration 3 = 10471.985000

С -funroll-loops
./a.out
test for i = 1000
duration 1 = 9025.555000
duration 2 = 1999.697000
duration 3 = 2356.148000
test for i = 100000
duration 1 = 9027.357000
duration 2 = 2001.889000
duration 3 = 2360.036000
test for i = 10000000
duration 1 = 9048.975000
duration 2 = 2220.350000
duration 3 = 2481.062000

-funroll-loops подтянуло SSE2 вариант до приемлимового времени. И затормозило первый вариант. Будем разбиратся, спасибо.

Кстати -O2 у меня работает быстрее, чем -O3.

Посмотри у Агнера и на strchr

шифруй блоками по 4 байта.

И это, в строке

int llen = len % sizeof(__uint64_t);

наверное, нужно деление, а не взятие остатка.

А в строке

xor_buf_key2(buf, 10, 0xc, lkey);

и ее аналогах неплохо было бы передавать актуалный размер массива )

кажись выравнивание массива до 16 байт должно помочь

кажись выравнивание массива до 16 байт должно помочь

Если на 16 байт не выровнено (при сборке на 32-битном хосте, например), то movdqa экзепшн выкидывает.

-funroll-loops подтянуло SSE2 вариант до приемлимового времени.

Потому что xor ничего не стоит, а загрузка из памяти - очень даже. Поэтому компилятор с -O3 генерит код так, чтобы загрузка в следующий регистр и ксор с предыдущим чередовались. Так процессор может суперскалярность свою напрячь.

mv логично, но тогда возникает вопрос для чего создавались SSE инструкции, если они не увиличивают скорость.

AF, вообще то да, спасибо.

Подправил тест (изначально он длину не правильную подставлял и он молотил по 10 байт только). Код тут:


http://codepaste.net/q3vpie Компилируем так gcc ./xor1.c -O2 -g -lssl -funroll-loops

Теперь да, SSE на больших буферах SSE выигрывает у регистров, но не намного:
test for i = 7000
duration 1 = 8007.167000
duration 2 = 292.539000
duration 3 = 242.309000

test for i = 9000
duration 1 = 10298.895000
duration 2 = 376.129000
duration 3 = 308.588000

Вообще я ожидал прироста где-то на 40%...

Ваша программа не компилируется, но мой вариант выдает duration = 6.218000 на 10000000 байтов на Celeron(R) Dual-Core CPU T3000 @ 1.80GHz в 32-битном режиме.

А без funroll-loops SSE ровно в 2 раза и выигрывает у регистров.

Где может быть ошибка?

Dimanc что gcc пишет у тебя? Так без данных сложно определит где ошибка. У меня все работает нормально.

Интересно можно ли функции сделать атрибут unroll-loops?

xor.c:33:17: warning: return type defaults to ‘int’
xor.c: In function ‘xor_buf_key3’:
xor.c:40:25: warning: implicit declaration of function ‘__builtin_ia32_pxor128’
xor.c:40:33: error: incompatible types when assigning to type ‘__m128i’ from type ‘int’
xor.c: In function ‘test’:
xor.c:48:19: warning: unused variable ‘end’
xor.c:48:12: warning: unused variable ‘start’
xor.c: In function ‘main’:
xor.c:109:7: warning: pointer targets in passing argument 1 of ‘RAND_bytes’ differ in signedness
/usr/include/openssl/rand.h:102:6: note: expected ‘unsigned char *’ but argument is of type ‘char *’
xor.c:103:22: warning: unused variable ‘len’
xor.c:114:1: warning: control reaches end of non-void function
xor.c: In function ‘xor_buf_key3’:
xor.c:44:1: warning: control reaches end of non-void function

32 бит у меня.

для большого буфера

это сколько?!

>Интересно можно ли функции сделать атрибут unroll-loops?

Можно вручную цикл раскрутить.

mv логично, но тогда возникает вопрос для чего создавались SSE инструкции, если они не увиличивают скорость.

А они увеличивают. Попробуй написать конверсию цветовых пространств, и с SSE разницу в разы получишь. У меня экран из rgb16 в rgb32 в 4 с копейками раза быстрее с SSE2 разворачивается, и это учитывая, что данные тоже в кэш не помещаются, и многое упирается в паять. Или вот, например, сложение с сатурацией: в SSE это одна команда, да ещё и векторная, а в обычной логике вообще бранч (if) есть, что не есть гуд для процессора.

Просто в данном случае всё упирается в пропускную способность памяти, а обработка данных совсем простая, поэтому развернуться негде особо. Если вручную на ассемблере заоптимизировать оба варианта (uint64_t и SSE), то разницы в скорости между ними не будет.

> это сколько?!

больше 400 байт

Про память тут дело говорят. Попробуй добавить ручной prefetch.

>Если на 16 байт не выровнено (при сборке на 32-битном хосте, например), то movdqa экзепшн выкидывает.

А movdqu? Тут очень даже может быть невыровненная хрень, которая всё тормозит.

>__m128i *lbuf = (__m128i *)buf;
алсо, говорят, что алиасить указатели — нехорошо...

> Можно вручную цикл раскрутить.

В моем случае нельзя, так как размер буфера подаваемого на вход не известен.

В вашем коде функции *xor*() получают в параметрах длину буфера, разве нет?

А movdqu? Тут очень даже может быть невыровненная хрень, которая всё тормозит.

movdqu канает, но оно медленнее, чем movdqa. Хотя, ЕМНИП, на Нехалемах уже пофиг.

В моем случае нельзя, так как размер буфера подаваемого на вход не известен.

Крути блоками по 8-16 регистров, делов-то.

Ну типа это.. Всем спасибо. Было довольно продуктивно.

У меня на говноатоме вроде адекватные результаты. Не делал только аналог второго варианта.

Вариант 1: http://codepaste.net/gq3ic3

Atom N270, gcc 4.5, O3:

Time with: 2360, time without: 11630, profit: 293%

Pentium III, icc 7.1, O3

Time with: 8340, time without: 12540, profit: nan%

Вариант 3: http://codepaste.net/g8xnnh

Atom N270, gcc 4.5, O3:

Time with: 2360, time without: 3890, profit: 65%

Pentium III, icc 7.1, O3:

Time with: 8360, time without: 6450, profit: nan%

//хз, почему на пентиуме наны, сейчас восемь часов утра, последний раз я проснулся сутки назад, а уснул полутора суток...
////указатели таки пришлось поалиасить АГРРРРРПРРРХХХХХ

>////указатели таки пришлось поалиасить АГРРРРРПРРРХХХХХ

А чем это плохо?

Да при размере буфера в сотни байт вполне можно раскрутить, как уже говорили, руками целиком, или хотя бы на 1-2к итераций, и в зависимости от размера буфера джампать в серёдку раскрученного цикла.

Yareg, спасибо очень интересно. Хорошую теорию по этой теме нашел тут http://lwn.net/Articles/255364/

Не понятно почему prefetch через блок, а не на следующий.

Скорее всего __m128i _mm_stream_load_si128 (__m128i *p); тоже делает prefetch перед следующей загрузкой. Надо будет глянуть.

Ключик можно 1 раз грузить.


[root@max TEST]# ./xor128
Time with: 4120, time without: 13180, profit: 220%
[root@max TEST]# ./xor128_orig
Time with: 7570, time without: 13220, profit: 75%

--- xor128_orig.c   2011-01-13 11:01:38.000000000 -0800
+++ xor128.c   2011-01-13 11:02:03.000000000 -0800
@@ -63,10 +63,11 @@ static inline void do_with(unsigned char
{
unsigned long i;
__m128i a,c;
+
+ c=_mm_set1_epi32(key.key);
for(i=0;i<N;i+=16)
{
_mm_prefetch(&b[i+256],_MM_HINT_NTA);
- c=_mm_set1_epi32(key.key);
a=_mm_load_si128((__m128i *)&b[i]); //FFFFFFFFFFFFFFFFFFFFFFFFFFFUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUu-
a=_mm_xor_si128(a,c);
_mm_store_si128((__m128i *)&b[i],a);

Когда-то от нечего делать писал умножение матриц на SSE2 (ну расширение с 128-битными регистрами для плавающих чисел). Так вот - точно так же, вариант с SSE2 проигрывал float-варианту на сопроцессоре.

Процессор, на котором все проверялось, был, кажется, тоже от AMD.