Я изучаю ассемблер довольно долго, и я пытаюсь переписать некоторые простые процедуры\функции, чтобы увидеть преимущества производительности (если они есть). Моим основным инструментом разработки является Delphi 2007, и первые примеры будут на этом языке, но их можно легко перевести на другие языки.
Проблема заключается в следующем:
Мы дали значение без знака, в котором каждый из восьми бит представляет пиксель в одной строке экрана. Каждый отдельный пиксель может быть сплошным (1) или прозрачным (0). Таким образом, мы имеем 8 пикселей, упакованных в одно байтовое значение. Я хочу распаковать эти пиксели в массив из восьми байтов таким образом, что младший пиксель (бит) будет располагаться под самым низким индексом массива и так далее. Вот пример:
One byte value -----------> eight byte array
10011011 -----------------> [1][1][0][1][1][0][0][1]
Array index number -------> 0 1 2 3 4 5 6 7
Ниже представлены пять методов, которые решают проблему. Затем я покажу свое сравнение времени и то, как я это делал.
Мои вопросы состоят из двух частей:
1.
Я прошу вас дать подробный ответ относительно методов DecodePixels4a и DecodePixels4b. Почему метод 4b несколько медленнее, чем 4a?
Если, например, он медленнее, потому что мой код не выровнен правильно, тогда покажите мне, какие команды в данном методе могут быть лучше выровнены и как это сделать, чтобы не нарушить метод.
Я хотел бы видеть реальные примеры теории. Пожалуйста, имейте в виду, что я изучаю сборку, и я хочу получить знания из ваших ответов, что позволяет мне в будущем писать улучшенный оптимизированный код.
2.
Можете ли вы написать более быструю рутину, чем DecodePixels4a? Если да, представьте его и опишите шаги по оптимизации, которые вы предприняли.
Посредством более быстрой подпрограммы я подразумеваю подпрограмму, которая выполняется в кратчайшие сроки в тестовой среде среди всех предложенных здесь процедур.
Разрешены все процессоры семейства Intel и совместимые с ними.
Ниже вы найдете написанные мной подпрограммы:
procedure DecodePixels1(EncPixels: Byte; var DecPixels: TDecodedPixels);
var
i3: Integer;
begin
DecPixels[0] := EncPixels and $01;
for i3 := 1 to 7 do
begin
EncPixels := EncPixels shr 1;
DecPixels[i3] := EncPixels and $01;
//DecPixels[i3] := (EncPixels shr i3) and $01; //this is even slower if you replace above 2 lines with it
end;
end;
//Lets unroll the loop and see if it will be faster.
procedure DecodePixels2(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels[0] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[1] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[2] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[3] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[4] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[5] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[6] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[7] := EncPixels and $01;
end;
procedure DecodePixels3(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
push ecx;
mov bl, al;
and bl, $01;
mov [edx], bl;
mov ecx, $00;
@@Decode:
inc ecx;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + ecx], bl;
cmp ecx, $07;
jnz @@Decode;
pop ecx;
pop ebx;
pop eax;
end;
end;
//Unrolled assembly loop
procedure DecodePixels4a(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
mov bl, al;
and bl, $01;
mov [edx], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $01], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $02], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $03], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $04], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $05], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $06], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $07], bl;
pop ebx;
pop eax;
end;
end;
// it differs compared to 4a only in switching two instructions (but seven times)
procedure DecodePixels4b(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $01], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $02], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $03], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $04], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $05], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $06], bl; //
mov bl, al;
and bl, $01;
mov [edx + $07], bl;
pop ebx;
pop eax;
end;
end;
И вот как я их тестирую:
program Test;
{$APPTYPE CONSOLE}
uses
SysUtils, Windows;
type
TDecodedPixels = array[0..7] of Byte;
var
Pixels: TDecodedPixels;
Freq, TimeStart, TimeEnd :Int64;
Time1, Time2, Time3, Time4a, Time4b: Extended;
i, i2: Integer;
begin
if QueryPerformanceFrequency(Freq) then
begin
for i2 := 1 to 100 do
begin
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels1(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time1 := Time1 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels2(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time2 := Time2 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels3(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time3 := Time3 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels4a(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time4a := Time4a + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels4b(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time4b := Time4b + ((TimeEnd - TimeStart) / Freq * 1000);
end;
Writeln('Time1 : ' + FloatToStr(Time1 / 100) + ' ms. <- Delphi loop.');
Writeln('Time2 : ' + FloatToStr(Time2 / 100) + ' ms. <- Delphi unrolled loop.');
Writeln('Time3 : ' + FloatToStr(Time3/ 100) + ' ms. <- BASM loop.');
Writeln('Time4a : ' + FloatToStr(Time4a / 100) + ' ms. <- BASM unrolled loop.');
Writeln('Time4b : ' + FloatToStr(Time4b / 100) + ' ms. <- BASM unrolled loop instruction switch.');
end;
Readln;
end.
Ниже приведены результаты моей машины (Intel® Pentium® E2180 на Win32 XP):
Time1 : 1,68443549919493 ms. <- Delphi loop.
Time2 : 1,33773024572211 ms. <- Delphi unrolled loop.
Time3 : 1,37015271374424 ms. <- BASM loop.
Time4a : 0,822916962526627 ms. <- BASM unrolled loop.
Time4b : 0,862914462301607 ms. <- BASM unrolled loop instruction switch.
Результаты довольно стабильны - время варьируется только на несколько процентов между каждым тестом, который я сделал. И это всегда верно: Time1 > Time3 > Time 2 > Time4b > Time4a
Итак, я думаю, что разница между Time4a и Time4b зависит от того, что инструкции переключаются в методе DecodePixels4b. Иногда это 4%, иногда это до 10%, но 4b всегда медленнее, чем 4a.
Я думал о другом методе с использованием инструкций MMX для записи в память восьми байтов за один раз, но я не могу найти быстрый способ распаковать байт в 64-разрядный регистр.
Спасибо за ваше время.
Спасибо, ребята, за ценный вклад. Если бы я мог ответить всем вам в одно и то же время, к сожалению, по сравнению с современным процессором у меня есть только один "труба" и может выполнять только одну инструкцию "ответ" в то время;-) Итак, я попытаюсь подытожить некоторые вещи здесь и написать дополнительные комментарии по вашим ответам.
Прежде всего, я хотел сказать, что перед отправкой моего вопроса я придумал решение, представленное Wouter van Nifterick, и это было фактически медленнее, чем мой код сборки. Поэтому я решил не публиковать эту процедуру здесь, но вы можете заметить, что я применил тот же подход и в моей программе Delphi для этой программы. Это прокомментировано там, потому что это давало мне более серьезные результаты.
Это загадка для меня. Я снова запустил свой код с помощью процедур Wouter и PhilS и вот результаты:
Time1 : 1,66535493194387 ms. <- Delphi loop.
Time2 : 1,29115785420688 ms. <- Delphi unrolled loop.
Time3 : 1,33716934524107 ms. <- BASM loop.
Time4a : 0,795041753757838 ms. <- BASM unrolled loop.
Time4b : 0,843520166815013 ms. <- BASM unrolled loop instruction switch.
Time5 : 1,49457681191307 ms. <- Wouter van Nifterick, Delphi unrolled
Time6 : 0,400587402866258 ms. <- PhiS, table lookup Delphi
Time7 : 0,325472442519827 ms. <- PhiS, table lookup Delphi inline
Time8 : 0,37350491544239 ms. <- PhiS, table lookup BASM
Посмотрите на результат Time5, довольно странный, не так ли? Я предполагаю, что у меня есть другая версия Delphi, так как мой сгенерированный код сборки отличается от того, что предоставляется Wouter.
Второе главное изменение:
Я знаю, почему обычная 5 была медленнее на моей машине. Я проверил "Проверка диапазона" и "Проверка переполнения" в моих параметрах компилятора. Я добавил директиву assembler в подпрограмму 9, чтобы узнать, помогает ли она. Похоже, что с этой директивной процедурой сборки так же хорошо, как в Delphi встроенный вариант или даже немного лучше.
Вот окончательные результаты:
Time1 : 1,22508325749317 ms. <- Delphi loop.
Time2 : 1,33004145373084 ms. <- Delphi unrolled loop.
Time3 : 1,1473583622526 ms. <- BASM loop.
Time4a : 0,77322594033463 ms. <- BASM unrolled loop.
Time4b : 0,846033593023372 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,688689382044384 ms. <- Wouter van Nifterick, Delphi unrolled
Time6 : 0,503233741036693 ms. <- PhiS, table lookup Delphi
Time7 : 0,385254722925063 ms. <- PhiS, table lookup Delphi inline
Time8 : 0,432993919452751 ms. <- PhiS, table lookup BASM
Time9 : 0,362680491244212 ms. <- PhiS, table lookup BASM with assembler directive
Третье главное изменение:
По мнению @Pascal Cuoq и @j_random_hacker, разница в времени выполнения между подпрограммами 4a, 4b и 5 обусловлена зависимостью данных. Однако я должен не согласиться с этим мнением, основываясь на дальнейших тестах, которые я сделал.
Я также изобрел новую процедуру 4c на основе 4a. Вот он:
procedure DecodePixels4c(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push ebx;
mov bl, al;
and bl, 1;
mov [edx], bl;
mov bl, al;
shr bl, 1;
and bl, 1;
mov [edx + $01], bl;
mov bl, al;
shr bl, 2;
and bl, 1;
mov [edx + $02], bl;
mov bl, al;
shr bl, 3;
and bl, 1;
mov [edx + $03], bl;
mov bl, al;
shr bl, 4;
and bl, 1;
mov [edx + $04], bl;
mov bl, al;
shr bl, 5;
and bl, 1;
mov [edx + $05], bl;
mov bl, al;
shr bl, 6;
and bl, 1;
mov [edx + $06], bl;
shr al, 7;
and al, 1;
mov [edx + $07], al;
pop ebx;
end;
end;
Я бы сказал, что он довольно зависим от данных.
И вот тесты и результаты. Я сделал четыре теста, чтобы убедиться, что это не случайность. Я также добавил новые времена для подпрограмм, предложенных GJ (Time10a, Time10b).
Test1 Test2 Test3 Test4
Time1 : 1,211 1,210 1,220 1,213
Time2 : 1,280 1,258 1,253 1,332
Time3 : 1,129 1,138 1,130 1,160
Time4a : 0,690 0,682 0,617 0,635
Time4b : 0,707 0,698 0,706 0,659
Time4c : 0,679 0,685 0,626 0,625
Time5 : 0,715 0,682 0,686 0,679
Time6 : 0,490 0,485 0,522 0,514
Time7 : 0,323 0,333 0,336 0,318
Time8 : 0,407 0,403 0,373 0,354
Time9 : 0,352 0,378 0,355 0,355
Time10a : 1,823 1,812 1,807 1,813
Time10b : 1,113 1,120 1,115 1,118
Time10c : 0,652 0,630 0,653 0,633
Time10d : 0,156 0,155 0,172 0,160 <-- current winner!
Как вы можете видеть результаты 4a, 4b, 4c и 5 очень близки друг к другу.
Почему это? Поскольку я удален из 4a, 4b (4c уже не имеет его), две инструкции: push eax и pop eax. Поскольку я знаю, что я не буду использовать где-либо еще в своем коде значение под eax, мне не нужно его защищать.
Теперь мой код имеет только одну пару push/pop, а также процедуру 5.
Обычная 5 пресервирует значение eax beacause, прежде всего, сделав ее копию под ecx, но не deser't preereserve ecx.
Итак, я пришел к выводу, что разница во времени исполнения 5 и 4a и 4b (до третьего редактирования) не относилась к данным зависимым, но была вызвана дополнительной парой инструкций push/pop.
Я очень заинтересован в ваших комментариях.
Через несколько дней GJ изобрел даже более быструю рутину (Time 10d), чем PhiS. Хорошая работа GJ!
