01.03.2006

Программерский бред

Не помню, с чего, но чего-то задумался о довольно обыденной процедуре swap. На память пришли два метода - естественный (с использованием временной переменной) и навороченный (с использованием xor; подсмотрен мною довольно давно в книжке Бруно Бабэ).
Формально оба метода используют всего три операции. Или не три? Решил проверить - просто подсмотреть, сколько инструкций ассемблера реально использует каждый из методов.
Реализовал оба метода (хотя для трех и одной строчки кода "реализовал" - громкое слово). Пометил обе переменные как volatile для того, чтобы компиляторы не удаляли неиспользуемые переменные. Прогнал через два компилятора (gcc и Microsoft Visual C++ 6.0) c ключами оптимизации по скорости. Результат свел в таблицу.

"swap" technique tests





























  Method 1 Method 2
C source code
void test( )
{
volatile int a;
volatile int b;
int tmp;

tmp = a;
a = b;
b = tmp;
}
void test( )
{
volatile int a;
volatile int b;

a ^= b ^= a ^= b;
}
MsVC 6.0 assembly output

[cl /c /O2 /Fatest.asm test.c]
4 assembler instructions

_test  PROC NEAR  ; COMDAT
; File test.c
; Line 2
push ecx
; Line 7
mov eax, DWORD PTR _a$[esp+4]
; Line 8
mov ecx, DWORD PTR _b$[esp+4]
mov DWORD PTR _a$[esp+4], ecx
; Line 9
mov DWORD PTR _b$[esp+4], eax
; Line 10
pop ecx
ret 0
_test ENDP
12 assembler instructions

_test   PROC NEAR  ; COMDAT
; Line 2
sub esp, 8
; Line 6
mov eax, DWORD PTR _b$[esp+8]
mov ecx, DWORD PTR _a$[esp+8]
xor eax, ecx
mov DWORD PTR _a$[esp+8], eax
mov edx, DWORD PTR _b$[esp+8]
mov eax, DWORD PTR _a$[esp+8]
xor edx, eax
mov DWORD PTR _b$[esp+8], edx
mov ecx, DWORD PTR _b$[esp+8]
mov edx, DWORD PTR _a$[esp+8]
xor ecx, edx
mov DWORD PTR _a$[esp+8], ecx

; Line 7
add esp, 8
ret 0
_test1 ENDP
GCC 3.4.4 assebly output

[gcc.exe -S -O3 test.c]
4 assembler instructions

_test:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl -4(%ebp), %edx
movl -8(%ebp), %eax
movl %eax, -4(%ebp)
movl %edx, -8(%ebp)

leave
ret
12 assembler instructions

_test:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl -4(%ebp), %ecx
movl -8(%ebp), %edx
xorl %edx, %ecx
movl %ecx, -4(%ebp)
movl -4(%ebp), %ecx
movl -8(%ebp), %eax
xorl %eax, %ecx
movl %ecx, -8(%ebp)
movl -8(%ebp), %eax
movl -4(%ebp), %edx
xorl %edx, %eax
movl %eax, -4(%ebp)

leave
ret


Число инструкций для первого метода - 4 для обоих компиляторов. Для второго - 12, то есть в три (!!!) раза больше. Правда, из этих двенадцати три инструкции оперируют только регистрами, но, в общем, это не спасает.
Конечно, тесты довольно искусственные, но, в общем, похоже, что использование блока кода
int a, b;
...
{
int tmp;
tmp = a;
a = b;
b = tmp;
}
...

дает значительный выигрыш по сравнению с использованием строчки
a ^= b ^= a ^= b;

И при этом памяти используется ничуть не больше.
То есть, данная строчка является не более чем программерскими понтами. =)
Кстати, реализация swap вручную дала бы выигрыш всего в одну инструкцию:
    mov eax,  DWORD PTR _a$[esp+4]
xchg eax, DWORD PTR _b$[esp+4]
mov DWORD PTR _a$[esp+4], eax

6 комментариев: