оптимизация
Tuesday, 5 June 2007 22:27![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
детей в институте учат дельфям и ассемблеру. Лабораторная предлагает написать сортировку (естественно, методом пузырька) массива случайных чисел по возрастанию на чистых дельфях, и на дельфях с ассемблерной вставкой, измерить время выполнения и рассказать о преимуществах ассемблера.
Ну что у пузырька O(n^2) детям не говорят, фиг с ним. Интересно другое: берем массив на 30000 элементов, Celeron 1.70GHz, WINE@Etersoft:
delphi time: 710
inline asm time: 1854
под кошерной виндой на целероне 2.4 Ghz еще веселее - асм в среднем в четыре раза медленнее. В общем, препод сам поймет преимущества ассемблера ;)
скачать проект можно здесь.
процедура сортировки, чистый delphi:
procedure StraightInsertion(n:integer;var mas:massiv);
var i,j:integer;
x:integer;
begin
for i:=2 to n do
begin
x:=mas[i];
mas[0]:=x;
j:=i-1;
{ порядок сортировки. меньше => убыванию, больше => возрастанию }
while mas[j]>x do
begin
mas[j+1]:=mas[j];
dec(j);
end;
mas[j+1]:=x;
end;
end;
ассемблер:
procedure StraightInsertionAsm(n:integer;var mas:massiv);
var i,j:integer;
x:integer;
begin
asm
mov i,2d
@l1:
cmp i,eax;
jg @l4
mov ecx,i;
xor edx,edx;
mov edx,[mas];
mov ebx,[edx+4*ecx];
mov x,ebx;
mov [edx],ebx;
mov ebx,i;
dec ebx;
mov j,ebx;
@l3:
mov ecx,j;
mov ebx,[mas];
mov ebx,[ebx+ecx*4];
cmp x,ebx;
{ порядок сортировки. jle => убыванию, jge => возрастанию }
jge @l2
mov edx,[mas];
mov ebx,[edx+ecx*4];
mov [edx+ecx*4+4],ebx;
dec ecx;
mov j,ecx;
jmp @l3
@l2:
mov ebx,x;
mov edx,[mas];
mov [edx+ecx*4+4],ebx;
inc i;
jmp @l1
@l4:
end;
end;
Ну что у пузырька O(n^2) детям не говорят, фиг с ним. Интересно другое: берем массив на 30000 элементов, Celeron 1.70GHz, WINE@Etersoft:
delphi time: 710
inline asm time: 1854
под кошерной виндой на целероне 2.4 Ghz еще веселее - асм в среднем в четыре раза медленнее. В общем, препод сам поймет преимущества ассемблера ;)
скачать проект можно здесь.
процедура сортировки, чистый delphi:
procedure StraightInsertion(n:integer;var mas:massiv);
var i,j:integer;
x:integer;
begin
for i:=2 to n do
begin
x:=mas[i];
mas[0]:=x;
j:=i-1;
{ порядок сортировки. меньше => убыванию, больше => возрастанию }
while mas[j]>x do
begin
mas[j+1]:=mas[j];
dec(j);
end;
mas[j+1]:=x;
end;
end;
ассемблер:
procedure StraightInsertionAsm(n:integer;var mas:massiv);
var i,j:integer;
x:integer;
begin
asm
mov i,2d
@l1:
cmp i,eax;
jg @l4
mov ecx,i;
xor edx,edx;
mov edx,[mas];
mov ebx,[edx+4*ecx];
mov x,ebx;
mov [edx],ebx;
mov ebx,i;
dec ebx;
mov j,ebx;
@l3:
mov ecx,j;
mov ebx,[mas];
mov ebx,[ebx+ecx*4];
cmp x,ebx;
{ порядок сортировки. jle => убыванию, jge => возрастанию }
jge @l2
mov edx,[mas];
mov ebx,[edx+ecx*4];
mov [edx+ecx*4+4],ebx;
dec ecx;
mov j,ecx;
jmp @l3
@l2:
mov ebx,x;
mov edx,[mas];
mov [edx+ecx*4+4],ebx;
inc i;
jmp @l1
@l4:
end;
end;
no subject
2009-06-30 15:34 (UTC)Но я подозреваю, 32разрядный код, который генерит gcc с оптимизацией - человек читать-то сложно, не то что вручную писать.