Показаны сообщения с ярлыком Чит-коды программиста. Показать все сообщения
Показаны сообщения с ярлыком Чит-коды программиста. Показать все сообщения

24.03.2006

Вы будете смеяться, но...

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

C source


int get_gcd( int a, int b )
{
while (1)
{
if (b == 0)
return a;
a %= b;
a ^= b ^= a ^= b;
}
}

int get_gcd_2( int a, int b )
{
while (1)
{
if (b == 0)
return a;
a %= b;
{
int c = a;
a = b;
b = c;
}
}
}








RVCT codeGCC code
get_gcd PROC
PUSH {r4,lr}
MOV r4,r1
|L1.8|
CMP r4,#0
POPEQ {r4,pc}
MOV r1,r4
BL __aeabi_idivmod
EOR r0,r1,r4
EOR r4,r0,r4
EOR r0,r4,r0

B |L1.8|
ENDP

get_gcd_2 PROC
PUSH {r4,lr}
B |L1.68|
|L1.48|
CMP r4,#0
POPEQ {r4,pc}
MOV r1,r4
BL __aeabi_idivmod
MOV r0,r4
|L1.68|
MOV r4,r1

B |L1.48|
ENDP
get_gcd:
mov ip, sp
stmfd sp!, {r4, fp, ip, lr, pc}
sub fp, ip, #4
mov r4, r1
.L4:
cmp r4, #0
beq .L5
mov r1, r4
bl __modsi3
eor r0, r0, r4
eor r4, r4, r0
eor r0, r0, r4

b .L4
.L5:
ldmea fp, {r4, fp, sp, lr}
bx lr

get_gcd_2:
mov ip, sp
stmfd sp!, {r4, fp, ip, lr, pc}
sub fp, ip, #4
mov r4, r1
.L10:
cmp r4, #0
beq .L11
mov r1, r4
bl __modsi3
mov r3, r0
mov r0, r4
mov r4, r3

b .L10
.L11:
ldmea fp, {r4, fp, sp, lr}
bx lr




C source


void swap_memory( int* array, int len )
{
int i;

for (i = 0; i < (len / 1); i++)
{
array[i] ^= array[len - i - 1] ^= array[i] ^= array[len - i - 1];
}
}

void swap_memory_2( int* array, int len )
{
int i;

for (i = 0; i < (len / 1); i++)
{
int c = array[i];
array[i] = array[len - i - 1];
array[len - i - 1] = c;
}
}








RVCT codeGCC code
swap_memory PROC
MOV r2,#0
PUSH {lr}
B |L1.64|
|L1.12|
SUB r3,r1,r2
ADD r3,r0,r3,LSL #2
LDR lr,[r3,#-4]
LDR r12,[r0,r2,LSL #2]
EOR r12,r12,lr
STR r12,[r0,r2,LSL #2]
LDR lr,[r3,#-4]
EOR r12,r12,lr
STR r12,[r3,#-4]
LDR r3,[r0,r2,LSL #2]
EOR r3,r12,r3
STR r3,[r0,r2,LSL #2]

ADD r2,r2,#1
|L1.64|
CMP r2,r1
BLT |L1.12|
POP {pc}
ENDP

swap_memory_2 PROC
MOV r2,#0
PUSH {lr}
|L1.84|
CMP r2,r1
POPGE {pc}
SUB r12,r1,r2
ADD r12,r0,r12,LSL #2
LDR lr,[r12,#-4]
LDR r3,[r0,r2,LSL #2]
STR lr,[r0,r2,LSL #2]

ADD r2,r2,#1
STR r3,[r12,#-4]
B |L1.84|
ENDP
swap_memory:
mov ip, sp
stmfd sp!, {r4, r5, r6, fp, ip, lr, pc}
sub fp, ip, #4
mov lr, #0
mov r4, r1
cmp lr, r4
mov r5, r0
bge .L3
mvn r6, #3
mov ip, r5
.L5:
ldr r0, [ip, #0]
rsb r1, lr, r4
add r1, r5, r1, asl #2
ldr r3, [r1, r6]
eor r0, r0, r3
str r0, [ip, #0]
ldr r2, [r1, r6]
eor r2, r2, r0
str r2, [r1, r6]
ldr r3, [ip, #0]
eor r3, r3, r2
str r3, [ip], #4

add lr, lr, #1
cmp lr, r4
blt .L5
.L3:
ldmea fp, {r4, r5, r6, fp, sp, lr}
bx lr

swap_memory_2:
mov ip, sp
stmfd sp!, {r4, r5, fp, ip, lr, pc}
sub fp, ip, #4
mov ip, #0
mov r4, r1
cmp ip, r4
bge .L9
mvn r5, #3
mov lr, r0
.L11:
rsb r3, ip, r4
add r3, r0, r3, asl #2
ldr r2, [r3, r5]
ldr r1, [lr, #0]
str r2, [lr], #4
str r1, [r3, r5]

add ip, ip, #1
cmp ip, r4
blt .L11
.L9:
ldmea fp, {r4, r5, fp, sp, lr}
bx lr


В общем, для себя я сделал вывод - лучше не выпендриваться, использовать дополнительную переменную и не мешать компилятору самому оптимизировать данный кусок кода.

23.03.2006

В догонку...

...к экспериментам со swap. Еще два компилятора - под процессоры ARM, RVCT (компилятор от ARM) и gcc из Symbian SDK.



















 Метод 1Метод 2
C source code
void f0( int a, int b );
void f1( )
{
static int a = 0;
static int b = 0;

a ^= b ^= a ^= b;
f0(a, b);
}
void f0( int a, int b );

void f2( )
{
static int a = 0;
static int b = 0;

{
int c;
c = a;
a = b;
b = c;
}

f0(a, b);
}
RVCT
[armcc -O3 -S]
||f1|| PROC
LDR r2,|L1.32|
LDM r2,{r0,r1} ; a@f1_0, b@f1_1
EOR r0,r0,r1
EOR r1,r0,r1
EOR r0,r1,r0
STR r1,[r2,#4] ; b@f1_1
STR r0,[r2,#0] ; a@f1_0

B ||f0||
|L1.32|
DCD ||.data$0||
ENDP

||f2|| PROC
LDR r2,|L1.20|
LDR r0,[r2,#4] ; a@f2_0, b@f2_1
LDR r1,[r2,#0]
STM r2,{r0,r1} ; a@f2_0, b@f2_1

B ||f0||
|L1.20|
DCD ||.data$0||
ENDP
Symbian SDK gcc
[gcc -O3 -S]
f1:
mov ip, sp
stmfd sp!, {fp, ip, lr, pc}
ldr r3, .L2
ldr r2, .L2+4
ldr r0, [r3, #0]
ldr r1, [r2, #0]
eor r0, r0, r1
str r0, [r3, #0]
eor r1, r1, r0
str r1, [r2, #0]
eor r0, r0, r1
str r0, [r3, #0]

sub fp, ip, #4
bl f0
ldmea fp, {fp, sp, lr}
bx lr

f2:
mov ip, sp
stmfd sp!, {fp, ip, lr, pc}
ldr r2, .L2
ldr r3, .L2+4
ldr r0, [r2, #0]
ldr r1, [r3, #0]
str r0, [r3, #0]
str r1, [r2, #0]

sub fp, ip, #4
bl f0
ldmea fp, {fp, sp, lr}
bx lr


P.S. Стоит, пожалуй, обратить внимание и на то, что в данных случаях RVCT выигрывает у Symbian's gcc =).

Трюк со switch/case


Любопытна реализация конструкции switch/case в компиляторе RVCT для процессоров ARM. Довольно специфическая вещь, но, может быть, кому-нибудь пригодится - в качестве примера.
Данный трюк используется при компиляции кода в режиме THUMB. Этот режим используется для получения компактного кода для процессоров ARM.
Итак, условия:

  • конструкция switch/case;

  • ключ switch является целочисленным;

  • значения в case-метках идут "почти" подряд (т.е., возможны пропуски);

  • используется пять и более case-меток.


Пример:

int a;
...
switch (a)
{
case 10:
return 123;
case 11:
return 43;
case 12:
return 12;
case 13:
return 21;
case 15:
return 98;
}
return 1;

В этом случае RVCT генерирует вызов специальной процедуры __ARM_switch8 и сразу после точки вызова - таблицу переходов. Таблица переходов состоит из (n + 2) байтов плюс байт для выравнивания по границе слова (n - число case-меток).
Таблица переходов имеет следующий вид:











СмещениеЗначение
0Число case-меток
1Смещение до первой case-метки
2Смещение до второй case-метки
3Смещение до третьей case-метки
......
nСмещение до n-ой case-метки
n + 1Смещение до default-метки (default-метка может быть неявной)
[n + 2]Дополнение до границы слова (если нужно)


В функцию передается номер case-метки a. После этого выполняются следующие действия:

  1. По адресу [lp] считывается число case-меток n;

  2. Переданный номер case-метки a "обрезается" по отрезку [0..n];

  3. Выполняется переход по адресу, указанному в таблице по индексу a.


lp - адрес возврата из процедуры.
Для приведенного выше примера код выглядит следующим образом (значиние a содержится в регистре r0):

SUBS r0,r0,#0xa
BL __ARM_switch8
DCB 0x06,0x04
DCB 0x06,0x08
DCB 0x0a,
0x0e
DCB 0x0c,0x0e

Красным цветом выделены переходы по неявной default-метке. В частности, такой переход выполняется в случае, если значение a равно 14.

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