LINUX.ORG.RU
Форум — Development  

XOR vs SWAP test

 , , ,


0

2

Товарищи, я столкнулся с не совсем предсказуемым поведением своего процессора.

Оказалось, что при проверке XOR работает медленнее, чем swap или обмен двух переменных через третью.

Исходный код: http://ideone.com/bJK71K

Сборка: 

g++ main.cpp -O2 -o swap_test

Получаемый код: 

xchg   %ebp,%ebx ; XOR

mov    %ebp,%edx ; третья переменная
mov    %ebx,%ebp
mov    %edx,%ebx

mov    %ebx,%edx ; std::swap
mov    %ebp,%ebx
mov    %edx,%ebp

stdout: 

NUMSTEPS = 4294967295
swap	1641.8 ms.
XOR	2575.36 ms.
+var	1627 ms.

Процессор Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz

В качестве ОС — 64-разрядная убутна.

Если вас не затруднит — я прошу добровольев запустить код у себя, так как есть серьезные подозрения, что на других процессорах, особенно на AMD, xchg может иметь профит во времени.

Буду рад обоснованной критике и разъяснению возможных ошибок.



Последнее исправление: cetjs2 (всего исправлений: 2)

Оказалось, что при проверке XOR работает медленнее, чем swap или обмен двух переменных через третью.

Ну как-бы да. А вообще, читай Агнера Фога и документацию на процессор (Software Optimization Guide в частности).

devl547 ★★★★★
()

Умный компиятор зачем-то заменил тройной xor на xchg.

Deleted
() 
AMD A10-4600M APU with Radeon(tm) HD Graphics

~/desktop/test $ ./swap_test 
NUMSTEPS = 4294967295
swap    4821.18 ms.
XOR     3192.92 ms.
+var    4836.27 ms.
WRG ★★★★
()

А теперь смотри веселуху:

devl547@localhost ~/Downloads $ g++ -march=native -Ofast -mfpmath=sse -fno-tree-pre -funroll-loops -funsafe-loop-optimizations -fselective-scheduling -fsel-sched-pipelining -ftree-loop-im -funswitch-loops -g0 -pipe ideone_bJK71K.cpp -o test
devl547@localhost ~/Downloads $ ./test 
NUMSTEPS = 4294967295
swap	450.86 ms.
XOR	747.888 ms.
+var	455.998 ms.
devl547@localhost ~/Downloads $ g++ -march=native -O2 ideone_bJK71K.cpp -o testdevl547@localhost ~/Downloads $ ./test 
NUMSTEPS = 4294967295
swap	4656.58 ms.
XOR	4060.61 ms.
+var	4639.47 ms.
devl547 ★★★★★
()
Ответ на: комментарий от devl547

Тоже интеререса ради добавил -march=native 

~/desktop/test $ ./swap_test 
NUMSTEPS = 4294967295
swap    3240.62 ms.
XOR     3192.09 ms.
+var    3193.66 ms.
Не думал, что на столько сильно влияет

WRG ★★★★
()
Ответ на: комментарий от pony

Наркоман дофига? К слову, я с -O0 собрал, но тест вырубил после 2 минут ожидания.

Да и в целом, писать такие тесты на плюсах - это измерять размер песчинки рулеткой.

devl547 ★★★★★
()
Последнее исправление: devl547 (всего исправлений: 1)
Ответ на: комментарий от devl547

Вобще пушка 

~/desktop/test $ ./swap_test 
NUMSTEPS = 4294967295
swap    374.149 ms.
XOR     887.959 ms.
+var    366.526 ms.

WRG ★★★★
()

что при проверке XOR работает медленнее, чем swap или обмен двух переменных через третью.

и что тут удивительного? Радуйся, что компилятор догадался xor×3 свернуть в xchg.

emulek ★
()

g++ main.cpp -O2 -o swap_test

$ ./swap_test 
NUMSTEPS = 4294967295
swap    2063.01 ms.
XOR     2060.69 ms.
+var    2060.49 ms.

g++ main.cpp -pipe -O2 -march=native -g0 -s -Wall -march=native -mfpmath=both -mprefer-avx128 -funroll-loops -fno-tree-pre -ftree-vectorize -funswitch-loops -ftree-loop-distribution -o swap_test

$ ./swap_test 
NUMSTEPS = 4294967295                                                                                                                                                            
swap    235.726 ms.                                                                                                                                                              
XOR     572.556 ms.                                                                                                                                                              
+var    230.856 ms.

Ну и какие из этого выводы?

no-such-file ★★★★★
()
Ответ на: комментарий от no-such-file

-mfpmath=both -mprefer-avx128

У тебя FX?
Тогда первое в принципе не имеет смысла - блок FPU/SSE у нас один.
А второе само включается при выборе march=bdverX

Ну и какие из этого выводы?

В первом случае - оверхед на вызов цикла. Во втором - надо смотреть, что нагенерировал компилятор. Ну не пишут такие тесты на ЯВУ, не пишут.

devl547 ★★★★★
()
Последнее исправление: devl547 (всего исправлений: 2)
Ответ на: комментарий от emulek

я к тому, что если он хочет измерить что-то настолько низкоуровневое, то нужно писать на асме.

Я так понимаю, вот этот кусок нужен ТСу:


 80486a1:	89 04 24             	mov    %eax,(%esp)
 80486a4:	e8 97 ff ff ff       	call   8048640 <gettimeofday@plt>
 80486a9:	b9 fd ff ff ff       	mov    $0xfffffffd,%ecx
 80486ae:	eb 09                	jmp    80486b9 <main+0x39>
 80486b0:	89 d8                	mov    %ebx,%eax
 80486b2:	83 e9 09             	sub    $0x9,%ecx
 80486b5:	89 f3                	mov    %esi,%ebx
 80486b7:	89 c6                	mov    %eax,%esi
 80486b9:	83 f9 01             	cmp    $0x1,%ecx
 80486bc:	75 f2                	jne    80486b0 <main+0x30>
 80486be:	8d 54 24 28          	lea    0x28(%esp),%edx
 80486c2:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
 80486c9:	00 
 80486ca:	89 14 24             	mov    %edx,(%esp)
 80486cd:	e8 6e ff ff ff       	call   8048640 <gettimeofday@plt>
 80486d2:	b8 fc ff ff ff       	mov    $0xfffffffc,%eax
 80486d7:	89 f6                	mov    %esi,%esi
 80486d9:	8d bc 27 00 00 00 00 	lea    0x0(%edi,%eiz,1),%edi
 80486e0:	31 de                	xor    %ebx,%esi
 80486e2:	31 f3                	xor    %esi,%ebx
 80486e4:	31 de                	xor    %ebx,%esi
 80486e6:	83 e8 09             	sub    $0x9,%eax
 80486e9:	75 f5                	jne    80486e0 <main+0x60>
 80486eb:	8d 4c 24 30          	lea    0x30(%esp),%ecx
 80486ef:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
 80486f6:	00 
 80486f7:	89 0c 24             	mov    %ecx,(%esp)
 80486fa:	e8 41 ff ff ff       	call   8048640 <gettimeofday@plt>
 80486ff:	b8 fd ff ff ff       	mov    $0xfffffffd,%eax
 8048704:	eb 13                	jmp    8048719 <main+0x99>
 8048706:	8d 76 00             	lea    0x0(%esi),%esi
 8048709:	8d bc 27 00 00 00 00 	lea    0x0(%edi,%eiz,1),%edi
 8048710:	89 d9                	mov    %ebx,%ecx
 8048712:	83 e8 09             	sub    $0x9,%eax
 8048715:	89 f3                	mov    %esi,%ebx
 8048717:	89 ce                	mov    %ecx,%esi
 8048719:	83 f8 01             	cmp    $0x1,%eax
 804871c:	75 f2                	jne    8048710 <main+0x90>
 804871e:	8d 54 24 38          	lea    0x38(%esp),%edx
 8048722:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
devl547 ★★★★★
()
Последнее исправление: devl547 (всего исправлений: 1)
Ответ на: комментарий от devl547

Так это ты всех девелоперов сейчас заставляешь софт с -O0 собирать, зараза!

ВНЕЗАПНО: все девелоперы так и собирали всегда.

emulek ★
()
Ответ на: комментарий от devl547

А второе само включается при выборе march=bdverX

sse вообще дефолт на x86-64 ЕМНИП

Тогда первое в принципе не имеет смысла - блок FPU/SSE у нас один.

Блок-то может и один, но 2 конвеера. Даю компиляторы больше свободы выбора, деградации вроде бы нет, ну и ладно.

no-such-file ★★★★★
()
Ответ на: комментарий от emulek

ВНЕЗАПНО: все девелоперы так и собирали всегда.

Иди вымой рот с мылом. Везде -O2 или аналоги по-дефолту используется при релизной сборке.

devl547 ★★★★★
()
Ответ на: комментарий от devl547

я к тому, что если он хочет измерить что-то настолько низкоуровневое, то нужно писать на асме.

а я к тому, что ТС сам не понимает, что он измеряет, и зачем ему это нужно.

XOR вы тут вообще к чему приплели? Его нет в коде.

emulek ★
()
Ответ на: комментарий от devl547

Везде -O2 или аналоги по-дефолту используется при релизной сборке.

ничего, что мы тут тестим XOR, которой нет? Или ты думаешь, что это говно кто-то в продакшен вставит?

emulek ★
()
Ответ на: комментарий от emulek

XOR вы тут вообще к чему приплели? Его нет в коде.

Уймись уже. Омские школьники все такие упоротые?

gettimeofday(&t2, NULL);
for(i = 0; i < NUMSTEPS; ++i){
	a^=b;
	b^=a;
	a^=b;
}

Bitwise XOR assignment / a ^= b / a xor_eq b / a = a ^ b

devl547 ★★★★★
()
Последнее исправление: devl547 (всего исправлений: 2)
Ответ на: комментарий от emulek

с -O2 все просто

        jmp     .L2
        .p2align 4,,10
        .p2align 3

.L5:
        movl    %ebx, %ebp
        movl    %edx, %ebx
.L2:
        subl    $1, %eax
        movl    %ebp, %edx
        jne     .L5
        leaq    48(%rsp), %rdi
        xorl    %esi, %esi
        call    gettimeofday
        movl    $-1, %eax
        .p2align 4,,10
        .p2align 3
.L3:
        subl    $1, %eax
        xchgl   %ebp, %ebx
        jne     .L3
        leaq    64(%rsp), %rdi
        xorl    %esi, %esi
        call    gettimeofday
        movl    $-1, %eax
        jmp     .L4
        .p2align 4,,10
        .p2align 3
.L6:
        movl    %ebp, %ebx
        movl    %edx, %ebp
.L4:
        subl    $1, %eax
        movl    %ebx, %edx
        jne     .L6

с -O2 плюс ключи 

        jmp     .L2
        .p2align 5,,7
        .p2align 3
.L5:
        movl    %ebx, %ebp
        subl    $9, %ecx
        movl    %edx, %ebx
.L2:
        cmpl    $1, %ecx
        movl    %ebp, %edx
        jne     .L5
        xorl    %esi, %esi
        leaq    64(%rsp), %rdi
        call    gettimeofday
        movl    $-4, %eax
        .p2align 5,,24
        .p2align 3
.L3:
        movl    %ebp, %ecx
        xorl    %ebx, %ecx
        xorl    %ecx, %ebx
        movl    %ebx, %ebp
        xorl    %ecx, %ebp
        subl    $9, %eax
        jne     .L3
        xorl    %esi, %esi
        leaq    80(%rsp), %rdi
        call    gettimeofday
        movl    $-3, %eax
        jmp     .L4
        .p2align 5,,7
        .p2align 3
.L6:
        movl    %ebx, %ebp
        subl    $9, %eax
        movl    %esi, %ebx
.L4:
        cmpl    $1, %eax
        movl    %ebp, %esi
        jne     .L6

Вся разница - в раскрутке.

no-such-file ★★★★★
()
Ответ на: комментарий от no-such-file

не. Во втором случае у тебя получилось

.L3:
        movl    %ebp, %ecx
        xorl    %ebx, %ecx
        xorl    %ecx, %ebx
        movl    %ebx, %ebp
        xorl    %ecx, %ebp
        subl    $9, %eax
        jne     .L3

а в первом таки

.L3:
        subl    $1, %eax
        xchgl   %ebp, %ebx
        jne     .L3
emulek ★
()
Ответ на: комментарий от anonymous

В исходнике - есть. В выхлопе компилятора - есть.
Даже в дизасме есть.

И да, ты что это разлогинился?

Для совсем идиотов привожу выхлоп objdump -S при сборке с дебагом:

	for(i = 0; i < NUMSTEPS; ++i){
		a^=b;
 80486e0:	31 de                	xor    %ebx,%esi
		b^=a;
 80486e2:	31 f3                	xor    %esi,%ebx
		a^=b;
 80486e4:	31 de                	xor    %ebx,%esi

devl547 ★★★★★
()
Последнее исправление: devl547 (всего исправлений: 2)

Такие темы уже можно считать разжиганием срача. А дохтура в такие треды не пускать по нац признаку.

Напишите уже в вики куда-нибудь почему еще одна переменная быстрее и для чего и в каких ситуациях нужен XOR.

unt1tled ★★★★
()
Ответ на: комментарий от devl547

Спасибо лично Вам за разъяснения.

Так же спасибо всем, принявшим участие в обсуждении.

stream13
() автор топика
Ответ на: комментарий от unt1tled

Не всегда и не везде она быстрее. Зависит от процессора. Более того, сегодня нашел разработчика, который рассказывал про пережигание частей кристалла, не x86 ядра в x86 кристалле и прочие ужасы.

С намеком, что процессоры могут сильно отличаться.

Подытожил советом юзать Open CL о_0

Да, что с нацпризнаком, Вы там гадаете на urandom-е?

stream13
() автор топика
Ответ на: комментарий от stream13

Не всегда и не везде она быстрее. Зависит от процессора.

на процессорах из 70ых да, быстрее делать xor

Да, что с нацпризнаком, Вы там гадаете на urandom-е?

интересный ход мыслей

emulek (говорят, онже drBatty) любит разводить лютые срачи на тему низкоуровневого программирования

unt1tled ★★★★
()
11 сентября 2014 г.
Ответ на: комментарий от no-such-file

Ну и какие из этого выводы?

зачётные флаги конпелятора рулять, gentoo тоже

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development