Методы оптимизации сборки Intel x86 в примере задачи
https://stackoverflow.com/questions/1414911
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я довольно долго изучаю ассемблер и пытаюсь переписать в него некоторые простые процедуры \ функции, чтобы увидеть преимущества в производительности (если таковые имеются).Моим основным инструментом разработки является 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-битный регистр.
Спасибо вам за уделенное время.
Спасибо вам, ребята, за ваш ценный вклад.Хотел бы я ответить всем вам одновременно, к сожалению, по сравнению с современными процессорами, у меня есть только один "канал", и я могу выполнить только одну инструкцию "ответить" одновременно ;-) Итак, я попытаюсь подвести некоторые итоги здесь и написать дополнительные комментарии под вашими ответами.
Прежде всего, я хотел сказать, что перед публикацией своего вопроса я придумал решение, представленное Ваутером ван Нифтериком, и оно на самом деле было намного медленнее затем мой ассемблерный код.Поэтому я решил не публиковать эту процедуру здесь, но вы можете увидеть, что я использовал тот же подход и в своей циклической версии процедуры Delphi.Это прокомментировано там, потому что это давало мне худшие результаты.
Для меня это загадка.Я еще раз запустил свой код с помощью подпрограмм Ваутера и ФилсА, и вот результаты:
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, потому что сначала она копирует его в ecx, но не выполняет предварительное сохранение ecx.
Итак, мой вывод таков, что:разница во времени выполнения 5 и 4a, а также 4b (до третьей правки) это не касалось зависимости данных, но было вызвано дополнительной парой инструкций push / pop.
Меня очень интересуют ваши комментарии.
Через несколько дней Джи Джей изобрел еще более быструю программу (Время 10d), чем у PhiS.Отличная работа, Джи-Джи!
Решение
Ваш asm-код работает относительно медленно, потому что используйте stack end для записи в память 8 раз.Посмотри на это...
procedure DecodePixels(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
xor ecx, ecx
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 1
mov [DecPixels + 4], ecx
xor ecx, ecx
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 1
mov [DecPixels], ecx
end;
Возможно, это даже быстрее, чем код с таблицей подстановки!
Улучшенная версия:
procedure DecodePixelsI(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
mov ecx, 0 //Faster than: xor ecx, ecx
add al, al
rcl ch, 1
add al, al
rcl cl, 1
ror ecx, 16
add al, al
rcl ch, 1
add al, al
rcl cl, 1
mov [DecPixels + 4], ecx
mov ecx, 0 //Faster than: xor ecx, ecx
add al, al
rcl ch, 1
add al, al
rcl cl, 1
ror ecx, 16
add al, al
rcl ch, 1
add al, al
rcl cl, 1
mov [DecPixels], ecx
end;
Версия 3:
procedure DecodePixelsX(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
add al, al
setc byte ptr[DecPixels + 7]
add al, al
setc byte ptr[DecPixels + 6]
add al, al
setc byte ptr[DecPixels + 5]
add al, al
setc byte ptr[DecPixels + 4]
add al, al
setc byte ptr[DecPixels + 3]
add al, al
setc byte ptr[DecPixels + 2]
add al, al
setc byte ptr[DecPixels + 1]
setnz byte ptr[DecPixels]
end;
Версия 4:
const Uint32DecPix : array [0..15] of cardinal = (
$00000000, $00000001, $00000100, $00000101,
$00010000, $00010001, $00010100, $00010101,
$01000000, $01000001, $01000100, $01000101,
$01010000, $01010001, $01010100, $01010101
);
procedure DecodePixelsY(EncPixels: byte; var DecPixels: TDecodedPixels); inline;
begin
pcardinal(@DecPixels)^ := Uint32DecPix[EncPixels and $0F];
pcardinal(cardinal(@DecPixels) + 4)^ := Uint32DecPix[(EncPixels and $F0) shr 4];
end;
Другие советы
В общем, я бы лично воздержался от попыток оптимизировать код с помощью трюков на уровне ассемблера, если не вам действительно нужны дополнительные 2-3% скорости, и вы готовы платить цену за код, который сложнее читать, поддерживать и переносить.
Чтобы сократить этот последний 1%, вам, возможно, даже придется поддерживать несколько версий, оптимизированных для каждого процессора, и если появятся более новые процессоры и улучшенный компилятор pascal, вы от этого не выиграете.
Этот код на Delphi работает быстрее чем ваш самый быстрый код на ассемблере:
procedure DecodePixels5(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels[0] := (EncPixels shr 0) and $01;
DecPixels[1] := (EncPixels shr 1) and $01;
DecPixels[2] := (EncPixels shr 2) and $01;
DecPixels[3] := (EncPixels shr 3) and $01;
DecPixels[4] := (EncPixels shr 4) and $01;
DecPixels[5] := (EncPixels shr 5) and $01;
DecPixels[6] := (EncPixels shr 6) and $01;
DecPixels[7] := (EncPixels shr 7) and $01;
end;
Results:
Time1 : 1,03096806151283 ms. <- Delphi loop.
Time2 : 0,740308641141395 ms. <- Delphi unrolled loop.
Time3 : 0,996602425688886 ms. <- BASM loop.
Time4a : 0,608267951561275 ms. <- BASM unrolled loop.
Time4b : 0,574162510648039 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,499628206138524 ms. !!! <- Delphi unrolled loop 5.
Это быстро, потому что операции могут выполняться только с регистрами, вместо необходимости хранить и извлекать память.Современные процессоры выполняют это частично параллельно (новая операция может быть запущена до завершения предыдущей), поскольку результаты последовательных команд независимы друг от друга.
Машинный код выглядит примерно так:
push ebx;
// DecPixels[0] := (EncPixels shr 0) and 1;
movzx ecx,al
mov ebx,ecx
// shr ebx,$00
and bl,$01
mov [edx],bl
// DecPixels[1] := (EncPixels shr 1) and 1;
mov ebx,ecx
shr ebx,1
and bl,$01
mov [edx+$01],bl
// DecPixels[2] := (EncPixels shr 2) and 1;
mov ebx,ecx
shr ebx,$02
and bl,$01
mov [edx+$02],bl
// DecPixels[3] := (EncPixels shr 3) and 1;
mov ebx,ecx
shr ebx,$03
and bl,$01
mov [edx+$03],bl
// DecPixels[4] := (EncPixels shr 4) and 1;
mov ebx,ecx
shr ebx,$04
and bl,$01
mov [edx+$04],bl
// DecPixels[5] := (EncPixels shr 5) and 1;
mov ebx,ecx
shr ebx,$05
and bl,$01
mov [edx+$05],bl
// DecPixels[6] := (EncPixels shr 6) and 1;
mov ebx,ecx
shr ebx,$06
and bl,$01
mov [edx+$06],bl
// DecPixels[7] := (EncPixels shr 7) and 1;
shr ecx,$07
and cl,$01
mov [edx+$07],cl
pop ebx;
Редактировать:Как и предполагалось, поиск по таблице действительно выполняется быстрее.
var
PixelLookup:Array[byte] of TDecodedPixels;
// You could precalculate, but the performance gain would hardly be worth it because you call this once only.
for I := 0 to 255 do
DecodePixels5b(I, PixelLookup[I]);
procedure DecodePixels7(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels := PixelLookup[EncPixels];
end;
Results:
Time1 : 1,03096806151283 ms. <- Delphi loop.
Time2 : 0,740308641141395 ms. <- Delphi unrolled loop.
Time3 : 0,996602425688886 ms. <- BASM loop.
Time4a : 0,608267951561275 ms. <- BASM unrolled loop.
Time4b : 0,574162510648039 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,499628206138524 ms. !!! <- Delphi unrolled loop 5.
Time7 : 0,251533475182096 ms. <- simple table lookup
Развивая ответ Ника Ди, я попробовал следующие версии, основанные на табличном поиске, все из которые быстрее, чем те реализации, которые вы предоставляете (и быстрее, чем код Ваутера ван Нифтерика).
Учитывая следующий упакованный массив:
const Uint64DecPix : PACKED ARRAY [0..255] OF UINT64 =
( $0000000000000000, $0000000000000001, $0000000000000100, $0000000000000101, $0000000000010000, $0000000000010001, $0000000000010100, $0000000000010101, $0000000001000000, $0000000001000001, $0000000001000100, $0000000001000101, $0000000001010000, $0000000001010001, $0000000001010100, $0000000001010101,
$0000000100000000, $0000000100000001, $0000000100000100, $0000000100000101, $0000000100010000, $0000000100010001, $0000000100010100, $0000000100010101, $0000000101000000, $0000000101000001, $0000000101000100, $0000000101000101, $0000000101010000, $0000000101010001, $0000000101010100, $0000000101010101,
$0000010000000000, $0000010000000001, $0000010000000100, $0000010000000101, $0000010000010000, $0000010000010001, $0000010000010100, $0000010000010101, $0000010001000000, $0000010001000001, $0000010001000100, $0000010001000101, $0000010001010000, $0000010001010001, $0000010001010100, $0000010001010101,
$0000010100000000, $0000010100000001, $0000010100000100, $0000010100000101, $0000010100010000, $0000010100010001, $0000010100010100, $0000010100010101, $0000010101000000, $0000010101000001, $0000010101000100, $0000010101000101, $0000010101010000, $0000010101010001, $0000010101010100, $0000010101010101,
$0001000000000000, $0001000000000001, $0001000000000100, $0001000000000101, $0001000000010000, $0001000000010001, $0001000000010100, $0001000000010101, $0001000001000000, $0001000001000001, $0001000001000100, $0001000001000101, $0001000001010000, $0001000001010001, $0001000001010100, $0001000001010101,
$0001000100000000, $0001000100000001, $0001000100000100, $0001000100000101, $0001000100010000, $0001000100010001, $0001000100010100, $0001000100010101, $0001000101000000, $0001000101000001, $0001000101000100, $0001000101000101, $0001000101010000, $0001000101010001, $0001000101010100, $0001000101010101,
$0001010000000000, $0001010000000001, $0001010000000100, $0001010000000101, $0001010000010000, $0001010000010001, $0001010000010100, $0001010000010101, $0001010001000000, $0001010001000001, $0001010001000100, $0001010001000101, $0001010001010000, $0001010001010001, $0001010001010100, $0001010001010101,
$0001010100000000, $0001010100000001, $0001010100000100, $0001010100000101, $0001010100010000, $0001010100010001, $0001010100010100, $0001010100010101, $0001010101000000, $0001010101000001, $0001010101000100, $0001010101000101, $0001010101010000, $0001010101010001, $0001010101010100, $0001010101010101,
$0100000000000000, $0100000000000001, $0100000000000100, $0100000000000101, $0100000000010000, $0100000000010001, $0100000000010100, $0100000000010101, $0100000001000000, $0100000001000001, $0100000001000100, $0100000001000101, $0100000001010000, $0100000001010001, $0100000001010100, $0100000001010101,
$0100000100000000, $0100000100000001, $0100000100000100, $0100000100000101, $0100000100010000, $0100000100010001, $0100000100010100, $0100000100010101, $0100000101000000, $0100000101000001, $0100000101000100, $0100000101000101, $0100000101010000, $0100000101010001, $0100000101010100, $0100000101010101,
$0100010000000000, $0100010000000001, $0100010000000100, $0100010000000101, $0100010000010000, $0100010000010001, $0100010000010100, $0100010000010101, $0100010001000000, $0100010001000001, $0100010001000100, $0100010001000101, $0100010001010000, $0100010001010001, $0100010001010100, $0100010001010101,
$0100010100000000, $0100010100000001, $0100010100000100, $0100010100000101, $0100010100010000, $0100010100010001, $0100010100010100, $0100010100010101, $0100010101000000, $0100010101000001, $0100010101000100, $0100010101000101, $0100010101010000, $0100010101010001, $0100010101010100, $0100010101010101,
$0101000000000000, $0101000000000001, $0101000000000100, $0101000000000101, $0101000000010000, $0101000000010001, $0101000000010100, $0101000000010101, $0101000001000000, $0101000001000001, $0101000001000100, $0101000001000101, $0101000001010000, $0101000001010001, $0101000001010100, $0101000001010101,
$0101000100000000, $0101000100000001, $0101000100000100, $0101000100000101, $0101000100010000, $0101000100010001, $0101000100010100, $0101000100010101, $0101000101000000, $0101000101000001, $0101000101000100, $0101000101000101, $0101000101010000, $0101000101010001, $0101000101010100, $0101000101010101,
$0101010000000000, $0101010000000001, $0101010000000100, $0101010000000101, $0101010000010000, $0101010000010001, $0101010000010100, $0101010000010101, $0101010001000000, $0101010001000001, $0101010001000100, $0101010001000101, $0101010001010000, $0101010001010001, $0101010001010100, $0101010001010101,
$0101010100000000, $0101010100000001, $0101010100000100, $0101010100000101, $0101010100010000, $0101010100010001, $0101010100010100, $0101010100010101, $0101010101000000, $0101010101000001, $0101010101000100, $0101010101000101, $0101010101010000, $0101010101010001, $0101010101010100, $0101010101010101);
PUint64DecPix : pointer = @Uint64DecPix;
вы можете написать следующее:
procedure DecodePixelsPS1Pas (EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;
процедура декодирования пикселей SPS1PASINLINE (EncPixels:Байт;var декапиксели:tdecodedпиксели);встроенный;начало
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);конец;
процедура декодирования пикселей SPS1ASM (EncPixels:Байт;var декапиксели:tdecodedпиксели);asm
lea ecx, Uint64DecPix //[<-Добавлено в ПРАВКЕ 3]
//mov ecx, dword ptr PUint64DecPix - альтернатива приведенной выше строке (для меня медленнее)
movzx eax, al
movq xmm0, [8 * eax + ecx] // Используя XMM, а не MMX, чтобы нам не приходилось выдавать emms в конце
movq [edx], xmm0 //используйте MOVQ, потому что ему не нужно выравнивание по памяти
конец;
Стандартные реализации PAS и ASM довольно схожи по скорости, но реализация PAS, отмеченная "INLINE", является самой быстрой, потому что она избавляет от всех вызовов / ret, участвующих в вызове подпрограммы.
--РЕДАКТИРОВАТЬ--:Я забыл сказать:поскольку вы неявно предполагаете что-то о расположении памяти вашей структуры TDecodedPixels, было бы лучше, если бы вы объявили это как
PACKED ARRAY [0..7] of byte
--РЕДАКТИРОВАТЬ 2--:Вот мои результаты для сравнения:
Time1 : 2.51638266874701 ms. <- Delphi loop.
Time2 : 2.11277620479698 ms. <- Delphi unrolled loop.
Time3 : 2.21972066282167 ms. <- BASM loop.
Time4a : 1.34093090043567 ms. <- BASM unrolled loop.
Time4b : 1.52222070123437 ms. <- BASM unrolled loop instruction switch.
Time5 : 1.17106364076999 ms. <- Wouter van Nifterick
TimePS1 : 0.633099318488802 ms. <- PS.Pas
TimePS2 : 0.551617593856202 ms. <- PS.Pas Inline
TimePS3 : 0.70921094720139 ms. <- PS.Asm (speed for version before 3rd EDIT)
Компиляторы очень хорошо справляются с оптимизацией небольших подпрограмм.
Я бы оптимизировал ваш код, используя таблицу подстановки.
Поскольку вы декодируете один байт - 256 различных состояний - вы можете предварительно вычислить 256 массивов с распакованными значениями.
Редактировать: Обратите внимание, что процессоры Pentium могут выполнять определенные инструкции параллельно (Суперскалярная архитектура), это называется спариванием.
Чистое программное решение
Используя красивую технику из этот вопрос, который снова вдохновлен этот вопрос у нас будет отличное решение, подобное этому, только с одна строка кода (исключая декларации)
type TPackedDecodedPixels = record
case integer of
0: (a: TDecodedPixels);
1: (v: Int64);
end;
procedure DecodePixels(EncPixels: byte; var DecPixels: TDecodedPixels); inline;
const
magic = $8040201008040201;
mask = $8080808080808080;
begin
TPackedDecodedPixels(DecPixels).v := SwapEndian(((EncPixels*magic) and mask) shr 7);
end;
Конечно, вам нужно убедиться, что DecPixels находится должным образом выровненный по 8 байтам или вы можете страдать от некоторого замедления (или даже сбоев в других архитектурах).Вы также можете легко векторизовать функцию, чтобы сделать ее быстрее
Объяснение:
Предположим, у нас есть следующий битовый шаблон в виде abcdefgh.Мы хотим, чтобы выходной массив содержал
0000000a 0000000b 0000000c 0000000d 0000000e 0000000f 0000000g 0000000h (1)
Читая это в маленький эндиан в виде 64-битного целого числа мы получим %0000000h0000000g0000000f0000000e0000000d0000000c0000000b0000000a.Мы должны найти магическое число, которое сдвигает исходные биты на позиции, из которых мы можем извлечь необходимые биты
Давайте умножим это значение на магическое число
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
abcdefgh (1-byte value)
x 1000000001000000001000000001000000001000000001000000001000000001
__________________________________________________________________
= h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
На этом этапе биты всех пикселей были перемещены в наиболее значимые биты соответствующих байтов.Поскольку они уже лежали в нужном месте, нам просто нужно удалить оставшиеся кусочки с помощью and
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
& 1000000010000000100000001000000010000000100000001000000010000000
__________________________________________________________________
= h0000000g0000000f0000000e0000000d0000000c0000000b0000000a0000000 (8-byte array)
Теперь биты пикселей находятся в наиболее значимый биты соответствующих байтов, нам нужно выполнить логический сдвиг вправо на 7 чтобы переместить их в наименее значимый положение.Поскольку OP хочет получить значение в обратном порядке, нам нужно SwapEndian() чтобы преобразовать байты в большой порядковый номер.Если вам просто нужен маленький конец, вы можете остановиться на этом шаге
Итак, магическое число - это %1000000001000000001000000001000000001000000001000000001000000001 = $8040201008040201 а маска - это %1000000010000000100000001000000010000000100000001000000010000000 = $8080808080808080.Конечно, на самом деле, чтобы решить проблему и получить эти значения, нам нужно выполнить обратное движение от конечного результата → умноженный результат → магическое число
Но почему я поместил байты в конце строки в (1), а затем должен был преобразовать обратно в конец строки в конце строки?Почему бы просто не расположить байты в порядке окончания и не найти для этого магическое число?Если вам это интересно, то это потому, что таким образом это будет работать не более чем для 7 бит одновременно.Я поступил именно так в моем старом ответе и придется немного отколоть, а потом объединить это обратно позже
0abcdefg
x 0000000000000010000001000000100000010000001000000100000010000001
__________________________________________________________________
= 00000000abcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefg
& 0000000000000001000000010000000100000001000000010000000100000001
__________________________________________________________________
= 000000000000000a0000000b0000000c0000000d0000000e0000000f0000000g
Аппаратная поддержка
На самом деле это частный случай расширение бита с постоянной маской.В AVX2 Intel представила pdep инструкция в BMI2 набор инструкций предназначен для этой цели, так что вам просто нужна одна инструкция, чтобы получить результат.На других языках вы можете использовать это с встроенной функцией _pext_u64.К сожалению, AFAIK Free Pascal не поддерживает его, и вам приходится использовать assembly напрямую.Однако выражение будет выглядеть следующим образом
TPackedDecodedPixels(DecPixels).v := _pext_u64(EncPixels, $0101010101010101);
Проверка правильности:
Я пытался сравнивая версию OP с обеими моими версиями и до сих пор не обнаружил никакой проблемы.Тот Самый выходные данные компилятора это похоже на это
mov al, dil
mov rbx, rsi
movzx edi, al
movabs rax, 0x8040201008040201
imul rdi, rax
movabs rax, 0x8080808080808080
and rdi, rax
shr rdi, 0x7
call 4016a0 <SYSTEM_$$_SWAPENDIAN$INT64$$INT64>
mov QWORD PTR [rbx], rax
Вывод FPC по-прежнему неоптимален, потому что компилятор не знает, как заменить вызов на SwapEndian с BSWAP, и он копирует данные без необходимости.Почему mov al, dil; movzx edi, al вместо того, чтобы просто movzx edi, dil?.Как вы можете видеть, выходные данные компиляторов C и C ++ следующие намного лучше
Я как раз собирался привести тот же алгоритм, что и у Ваутера ван Нифтерика.
Кроме того, я бы объяснил более высокую производительность с точки зрения цепочек зависимостей.В каждой из предложенных вами версий, когда вы разворачивали свой базовый цикл, вы сохраняли зависимость между двумя последовательными итерациями:каждый ваш шрам, 01 доллар;требует, чтобы предыдущее значение al было вычислено.Если вы организуете свои развернутые итерации таким образом, чтобы их можно было выполнять параллельно, они фактически будут выполняться на современном процессоре.Пусть вас не вводят в заблуждение ложные зависимости, которые могут быть подавлены переименованием регистра.
Кто-то указал, что Pentium может выполнять две инструкции одновременно.Это правда, но современные процессоры (начиная с Pentium Pro, PII, ..., Core, Core 2) выполняют гораздо больше, чем две инструкции одновременно, когда у них есть такая возможность, то есть когда нет зависимости между выполняемыми инструкциями.Обратите внимание, что в версии Ваутера ван Нифтерика каждая строка может выполняться независимо от других.
http://www.agner.org/optimize/ содержит всю информацию, которая вам когда-либо могла понадобиться для понимания архитектуры современных процессоров и того, как использовать их преимущества.
если вы поддерживаете только 80386 и выше, вы можете использовать набор инструкций BTcc и SETcc следующим образом:
BT ax,1
SETC [dx]
inc dx
BT ax,2
SETC [dx]
inc dx
и т.д.
Как насчет чего-то вроде:
/* input byte in eax, address to store result in edx */
and eax, 0xff /* may not be needed */
mov ebx, eax
shl ebx, 7
or eax, ebx
mov ebx, eax
shl ebx, 14
or eax, ebx
mov ebx, eax
and eax, 0x01010101
mov [edx], eax
shr ebx, 4
and ebx, 0x01010101
mov [edx+4], ebx
Вероятная причина, по которой 4b работает быстрее, чем 4a, заключается в том, что он лучше распараллеливается.Из 4а:
mov bl, al;
and bl, $01; // data dep (bl)
mov [edx], bl; // data dep (bl)
shr al, $01;
mov bl, al; // data dep (al)
and bl, $01; // data dep (bl)
mov [edx + $01], bl; // data dep (bl)
Инструкции, помеченные как "data dep", не могут начать выполняться до завершения предыдущей инструкции, и я записал регистры, которые вызывают эту зависимость от данных.Современные процессоры способны запускать инструкцию до завершения последней, если нет зависимости.Но то, как вы упорядочили эти операции, предотвращает это.
В 4b у вас меньше зависимостей от данных:
mov bl, al;
and bl, $01; // data dep (bl)
shr al, $01;
mov [edx], bl;
mov bl, al;
and bl, $01; // data dep (bl)
shr al, $01;
mov [edx + $01], bl;
При таком порядке следования команд меньшее количество инструкций зависит от предыдущей инструкции, поэтому появляется больше возможностей для параллелизма.
Я не могу гарантировать, что это причина разницы в скорости, но это вероятный кандидат.К сожалению, трудно найти такие абсолютные ответы, как те, которые вы ищете;современные процессоры имеют предикторы ветвлений, многоуровневые кэши, аппаратные средства предварительной выборки и всевозможные другие сложности, которые могут затруднить выявление причин различий в производительности.Лучшее, что вы можете сделать, - это много читать, проводить эксперименты и ознакомиться с инструментами для проведения точных измерений.
Я догадываюсь дело в том, что запись в память (фактически, кэш-память) происходит медленнее, чем работа с регистрами.
Итак,
mov [edx+...], bl
shr al, $01;
mov bl, al;
дает процессору некоторое время для записи bl к памяти перед началом bl регистрация необходима снова, в то время как
shr al, $01;
mov [edx], bl;
mov bl, al;
потребности bl немедленно, поэтому процессор должен остановиться и дождаться завершения записи в память.
Это меня удивляет.Современные процессоры Intel выполняют сумасшедшую конвейеризацию и переименование регистров, поэтому, на мой взгляд, во всяком случае, DecodePixels4b должен быть быстрее, поскольку зависимости каждой инструкции находятся дальше назад.Вышесказанное - это все объяснение, которое я могу предложить, помимо этого:
x86 - ужасный набор команд, и Intel делает удивительные и очень продвинутые трюки, чтобы сделать его эффективным.На вашем месте я бы занялся чем-нибудь другим.Сегодня спрос на мегамасштабируемое программное обеспечение для ПК очень невелик.Мое дружеское предложение - присмотреться к процессорам для мобильных устройств (в основном ARM), потому что в мобильных устройствах проблемы с быстродействием процессора, энергопотреблением и временем автономной работы означают, что микрооптимизированное программное обеспечение более важно.И у ARM есть превосходный набор команд для x86.
SIMD
Если вы расширите алгоритм на обработку массивов, то SIMD станет вариантом оптимизации.Вот SIMD-версия, которая занимает 1/3 времени от оптимизированного C-эквивалента:
int main ()
{
const int
size = 0x100000;
unsigned char
*source = new unsigned char [size],
*dest,
*dest1 = new unsigned char [size * 32],
*dest2 = new unsigned char [size * 32];
for (int i = 0 ; i < size ; ++i)
{
source [i] = rand () & 0xff;
}
LARGE_INTEGER
start,
middle,
end;
QueryPerformanceCounter (&start);
dest = dest1;
for (int i = 0 ; i < size ; ++i)
{
unsigned char
v = source [i];
for (int b = 0 ; b < 8 ; ++b)
{
*(dest++) = (v >> b) & 1;
}
}
unsigned char
bits [] = {1,2,4,8,16,32,64,128,1,2,4,8,16,32,64,128},
zero [] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
ones [] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
QueryPerformanceCounter (&middle);
__asm
{
movdqu xmm1,bits
movdqu xmm2,zero
movdqu xmm3,ones
mov ecx,0x100000/4
mov esi,source
mov edi,dest2
l1:
lodsd
movd xmm0,eax
movd xmm4,eax
punpcklbw xmm0,xmm0
punpcklbw xmm4,xmm4
punpcklwd xmm0,xmm0
punpcklwd xmm4,xmm4
punpckldq xmm0,xmm0
punpckhdq xmm4,xmm4
pand xmm0,xmm1
pand xmm4,xmm1
pcmpeqb xmm0,xmm2
pcmpeqb xmm4,xmm2
paddb xmm0,xmm3
paddb xmm4,xmm3
movdqu [edi],xmm0
movdqu [edi+16],xmm4
add edi,32
dec ecx
jnz l1
}
QueryPerformanceCounter (&end);
cout << "Time taken = " << (middle.QuadPart - start.QuadPart) << endl;
cout << "Time taken = " << (end.QuadPart - middle.QuadPart) << endl;
cout << "memcmp = " << memcmp (dest1, dest2, size * 32) << endl;
return 0;
}
Невероятное умное решение, Крис, что бы вы сделали с обратной задачей:сделать байт из массива в 8 байт?
Неоптимизированное решение обратной задачи:
BtBld PROC Array:DWORD, Pixels:DWORD
mov eax, [Array]
add eax, 7
mov edx, [Pixels]
mov bx, 0
mov ecx, 8
rpt: or bx, [eax]
dec eax
shl bx, 1
loop rpt
shr bx, 1
mov [edx], bl
ret
BtBld ENDP
Как вы заметили, разница в скорости в реализациях 4a и 4b обусловлена оптимизацией процессора (путем параллельного выполнения нескольких инструкций / конвейерной обработки инструкций).Но дело не в операндах, а в природе самого оператора.
4a Instruction Sequence:
AND - MOV - SHR
4b Instruction Sequence:
AND - SHR - MOV
Оба AND и SHR используют регистр флагов, поэтому эти две инструкции имеют состояние ожидания в своем конвейере.
Прочтите их следующим образом:
4a: AND (piped) MOV (piped) SHR
4b: AND (WAIT) SHR (piped) MOV
Заключение:у 4b в конвейере на 7 больше состояний ожидания, чем у 4a, поэтому он работает медленнее.
Джош упомянул, что существуют зависимости от данных, т.е.:
mov bl, al;
and bl, $01; // data dep (bl)
но это не совсем верно, поскольку эти две инструкции могут частично выполняться параллельно на уровне процессора:
mov bl, al -> (A:) read al (B:) write bl => (2 clocks in i386)
and bl, 01 -> (C:) read 01 (D:) write bl => idem
Последовательно они занимают 4 такта, но конвейерно они занимают только 3 "такта" (на самом деле термин "часы" неадекватен с точки зрения конвейера, но я использовал его в контексте простоты)
[--A--][--B--]
[--C--]<wait>[---D--]
