Intel x86 montagem de otimização técnicas em um problema de amostra
https://stackoverflow.com/questions/1414911
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou aprendendo assembler um bom tempo e eu estou tentando reescrever alguns procedimentos simples \ funções a ele para ver os benefícios de desempenho (se houver). Minha ferramenta de desenvolvimento principal é Delphi 2007 e primeiros exemplos será nesse idioma, mas eles podem ser facilmente traduzidas para outros idiomas.
Os estados com problemas como:
Temos dado um valor de byte não atribuído em que cada um dos oito bits representa um pixel em uma linha de uma tela. Cada pixel pode ser sólido (1) ou transparente (0). Portanto, em outras palavras, temos 8 pixels embalados em um valor de byte. Eu quero descompactar os pixels em uma matriz de oito byte da maneira que mais jovem pixel (pouco) vai pousar sob o menor índice do array e assim por diante. Aqui está um exemplo:
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
A seguir apresento cinco métodos que estão resolvendo o problema. Em seguida vou mostrar a sua comparação do tempo e como eu fiz medir esses tempos.
As minhas perguntas consistem em duas partes:
1.
Eu estou lhe pedindo detalhou resposta a respeito dos métodos DecodePixels4a e DecodePixels4b. Por método 4b é um pouco mais lento do que o 4a?
Se, por exemplo, é mais lento porque o meu código não está alinhada corretamente, então me mostrar qual as instruções em um determinado método poderia ser mais bem alinhada e como fazer isso para não quebrar o método.
Eu gostaria de ver exemplos reais por trás da teoria. Por favor, tenha em mente que eu estou aprendendo montagem e eu quero ganhar o conhecimento de suas respostas que me permite no futuro para escrever código melhor otimizado.
2.
Você pode escrever mais rápido do que rotina DecodePixels4a? Se assim for, por favor apresentá-lo e descrever as etapas de otimização que você tenha tomado.
Por mais rápido rotina I média de rotina que é executado no menor período de tempo em seu ambiente de teste entre todas as rotinas aqui apresentadas.
processadores da família Intel Todos são permitidos e os que são compatíveis com eles.
Abaixo você encontrará rotinas escritas por mim:
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;
E aqui é como faço para testá-los:
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.
Aqui estão os resultados de minha máquina (Intel® Pentium® E2180 em 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.
Os resultados são bastante estável - vezes variam apenas por alguns por cento entre cada teste que eu fiz. E isso sempre foi verdade: Time1 > Time3 > Time 2 > Time4b > Time4a
Então eu acho que de diferença entre Time4a e Time4b depende de que as instruções de mudar na DecodePixels4b método. Às vezes é 4% às vezes é até 10%, mas 4b é sempre mais lento do que 4a.
Eu estava pensando sobre um outro método com o uso de instruções MMX para escrever na memória oito bytes de uma vez, mas eu não consigo descobrir maneira rápida de byte descompactar para o registo de 64 bits.
Obrigado pelo seu tempo.
Obrigado a vocês para o seu valioso contributo. Whish eu poderia responder a todos vocês, ao mesmo tempo, infelizmente, em comparação com o CPU moderna é que tenho apenas um "pipe" e pode executar apenas uma instrução "resposta" no momento ;-) Então, vou tentar resumir algumas coisas aqui e escrever comentários adicionais sob suas respostas.
Em primeiro lugar, eu queria dizer que antes de postar minha pergunta eu vim com a solução apresentada por Wouter van Nifterick e foi realmente forma mais lenta , em seguida, o meu código de montagem. Então eu decidi não publicar essa rotina aqui, mas você pode ver que eu tomou a mesma abordagem também no meu loop versão Delphi da rotina. É comentado lá porque estava me dando resultados worser.
Este é um mistério para mim. Eu executar o meu código mais uma vez com Wouter de e rotinas das PHILS e aqui estão os resultados:
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
Olhe para o resultado time5, muito estranho, não é? Eu acho que tenho versão diferente Delphi, desde a minha gerado montagem difere código da prevista por Wouter.
Segunda edição maior:
Eu sei porque 5 rotina foi mais lento no meu machnie. Eu tinha verificado "Range verificação" e "verificação de estouro" Na minha opções do compilador. Eu adicionei directiva assembler para 9 rotina para ver se isso ajuda. Parece que com este procedimento de montagem directiva é tão bom quanto Delphi variante em linha ou até mesmo um pouco melhor.
Aqui estão os resultados finais:
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
Terceira edição maior:
Na opinião @Pascal Cuoq e @j_random_hacker a diferença de tempos de execução entre rotinas 4a, 4b e 5 é causada pela dependência de dados. Contudo, tenho de discordar de que basear opinião sobre os outros testes que fiz.
Eu também inventou nova 4c rotina baseado em 4a. Aqui está:
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;
Eu diria que é dados bonitas dependente.
E aqui estão os testes e resultados. Eu fiz quatro testes para garantir que não é por acaso. Eu também acrescentou novos tempos para as rotinas de propostas por 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!
Como você pode ver os resultados de 4a, 4b, 4c e 5 são muito próximos uns dos outros.
Por que é que? Porque eu tenho removido a partir de 4a, 4b (4c já não tem) duas instruções: push eax e pop eax. Desde que eu sei que eu não vou usar em qualquer outro lugar no meu código o valor em EAX Eu não tenho a prereserve-lo.
Agora meu código tem apenas um par de push / pop assim como a rotina 5.
Rotina valor 5 prereserves de eax beacause em primeiro lugar fazer cópia do mesmo sob ecx mas deson't prereserve ecx.
Assim, a minha conclusão é que: a diferença de tempo de execução de 5 e 4a e 4b (antes da terceira edição) não dizem respeito a dados dependecny mas foi causado por par adicional de push / pop instruções .
Estou muito interessado em seus comentários.
Depois de alguns dias GJ inventado ainda mais rápido de rotina (Tempo 10d) do que Phis de. Agradável GJ trabalho!
Solução
Seu código asm é relatividade lento porque o uso da pilha final de gravação 8 vezes a memória. Verifique este ...
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;
Talvez seja ainda mais rápido do que o código com tabela de pesquisa!
Versão melhorada:
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;
Version 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;
Versão 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;
Outras dicas
Em geral, eu pessoalmente ficar longe tentando código otimizar usando truques em nível assembler, a menos Você realmente precisa que extra de 2 ou 3% da velocidade, e você está disposto a pagar o preço de código que é mais difícil de ler, manter e porto.
Para espremer o último 1%, você pode até ter de manter várias versões otimizadas por processador, e se processadores mais novos e um compilador pascal melhorou vem junto, você não vai se beneficiar dele.
Este código Delphi é mais rápido do seu código assembler mais rápido:
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.
É rápido porque as operações podem ser feitas com apenas registros, em vez de precisar de armazenar e buscar memória. Os processadores modernos executar esta parcialmente em paralelo (uma nova operação pode ser iniciado antes do acabado anterior), porque os resultados das instruções consecutivas são independentes uns dos outros.
Os olhares de código de máquina como esta:
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;
Edit:. Como sugerido, uma pesquisa de tabela é realmente mais rápida
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
Expandindo resposta Nick D's, eu tentei as versões baseadas seguinte table-lookup, todos que são mais rápidos do que as implementações que você dá (e mais rápido do que o código de Wouter van Nifterick).
Dada a seguinte matriz embalado:
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;
você pode escrever o seguinte:
procedure DecodePixelsPS1Pas (EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;
procedure DecodePixelsPS1PasInline (EncPixels: Byte; var DecPixels: TDecodedPixels);
inline;
begin
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;
procedure DecodePixelsPS1Asm (EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
lea ecx, Uint64DecPix //[<-Added in EDIT 3]
//mov ecx, dword ptr PUint64DecPix - alternative to the above line (slower for me)
movzx eax, al
movq xmm0, [8*eax+ecx] //Using XMM rather than MMX so we don't have to issue emms at the end
movq [edx], xmm0 //use MOVQ because it doesn't need mem alignment
end;
As PAS e ASM implementações padrão são bastante semelhantes velocidade-wise, mas a implementação PAS marcado com "inline" é o mais rápido, porque ele se livrar de toda a chamada / ret envolvido em chamando a rotina.
- EDIT--: Eu esqueci de dizer: uma vez que você está assumindo implicitamente algo sobre o layout de memória de sua estrutura TDecodedPixels, seria melhor se você declará-lo como
PACKED ARRAY [0..7] of byte
- EDIT2--: Aqui estão os meus resultados para comparação:
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)
Os compiladores fazem muito bom trabalho em otimizar pequenas rotinas.
Gostaria de otimizar seu código usando uma tabela de pesquisa.
Desde que você decodificar um único byte - 256 estados diferentes -. Você pode precalculate 256 matrizes com os valores desembalados
Editar: Note que os processadores Pentium pode executar instruções específicas em paralelo ( Superscalar arquitetura ), é chamado de emparelhamento.
solução de software Pure
Usando a técnica bonita de este questão, que é novamente inspirado por esta questão teremos uma grande solução como esta, com apenas uma linha de código (excluindo declarações)
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;
Claro que você precisa ter certeza de que DecPixels é propriamente 8-byte alinhado ou você pode sofrer de algum devagar (ou mesmo segfaults sobre outras arquiteturas). Você também pode facilmente vetorizar a função para torná-lo mais rápido
Explicação:
Suponha que tenhamos o padrão de bits seguinte como abcdefgh. Vamos querer a matriz de saída para conter
0000000a 0000000b 0000000c 0000000d 0000000e 0000000f 0000000g 0000000h (1)
Reading que em little endian como um inteiro de 64 bits teremos %0000000h0000000g0000000f0000000e0000000d0000000c0000000b0000000a. Temos de encontrar um número mágico que desloca os bits originais para as posições que podemos extrair os bits necessários
Vamos multiplicar o valor com o número mágico
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
abcdefgh (1-byte value)
x 1000000001000000001000000001000000001000000001000000001000000001
__________________________________________________________________
= h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
Neste ponto, todos os bits dos pixels foram movidos para os bits mais significativos dos bytes correspondentes. Como eles já mentiu no lugar certo, só precisamos de retirar os bits restantes com and
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
& 1000000010000000100000001000000010000000100000001000000010000000
__________________________________________________________________
= h0000000g0000000f0000000e0000000d0000000c0000000b0000000a0000000 (8-byte array)
Agora pedaços dos pixels estão em mais significativos bits dos bytes correspondentes, o que precisamos fazer um deslocamento para a direita lógico por 7 para movê-los para o menos significativo posição. Porque o OP quer que o valor na ordem inversa, precisamos SwapEndian() para converter os bytes para big endian. Se você quiser apenas pouco endian você pode parar nesta etapa
Assim, o número mágico é %1000000001000000001000000001000000001000000001000000001000000001 = $8040201008040201 ea máscara é %1000000010000000100000001000000010000000100000001000000010000000 = $8080808080808080. É claro que, na realidade, para resolver o problema e obter os valores que precisamos fazer para trás a partir do resultado final ? resultado multiplicado ? número mágico
Mas por que eu coloquei os bytes em little endian em (1) e depois ter de converter de volta para big endian? Por que não apenas organizar os bytes na ordem grande endian e encontrar o número mágico para isso? Caso você esteja se perguntando sobre isso, então é porque dessa forma ele só vai trabalhar para, no máximo, 7 bits de cada vez. Eu fiz dessa maneira na minha velha resposta e tem que dividir um pouco fora, em seguida, combiná-lo de volta mais tarde
0abcdefg
x 0000000000000010000001000000100000010000001000000100000010000001
__________________________________________________________________
= 00000000abcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefg
& 0000000000000001000000010000000100000001000000010000000100000001
__________________________________________________________________
= 000000000000000a0000000b0000000c0000000d0000000e0000000f0000000g
O suporte de hardware
Este é realmente um caso especial de expandir com uma máscara constante. Em AVX2 Intel introduziu o pdep instrução em BMI2 conjunto de instruções para o efeito, para que apenas precisa de uma única instrução para obter o resultado. Em outras línguas você pode usar isso com o _pext_u64 função intrínseca. Infelizmente AFAIK Free Pascal não apoiá-lo e você tem que usar a montagem diretamente. No entanto, a expressão será semelhante
TPackedDecodedPixels(DecPixels).v := _pext_u64(EncPixels, $0101010101010101);
correção Cheque:
Eu tentei comparando a versão do OP com ambas as minhas versões e não encontrou qualquer problema até agora. O saída do compilador é assim
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
A saída FPC ainda é sub-óptima porque o compilador não sabe para substituir a chamada para SwapEndian com BSWAP , e ele copia dados desnecessariamente. Por mov al, dil; movzx edi, al em vez de apenas movzx edi, dil ?. Como você pode ver, saídas de C e C ++ compiladores são muito melhor
Eu estava prestes a dar o mesmo algoritmo como Wouter van Nifterick.
Além disso, gostaria de explicar o melhor desempenho em termos de cadeias de dependência. Em cada uma das versões que você propostas, quando se desenrolou o seu ciclo básico, você manteve uma dependência entre duas iterações sucessivas: cada um de seu SHR al, $ 01; exige que o valor anterior de al ter sido calculado. Se você organizar suas iterações desenroladas de tal forma que eles podem ser executados em paralelo, eles vão realmente ser em um processador moderno. Não se deixe enganar por falsas dependências que podem ser suprimidos por renomeação registo.
Alguém apontou que o Pentium pode executar duas instruções ao mesmo tempo. Isso é verdade, mas os processadores modernos (desde o Pentium Pro, PII, ..., Core, Core 2) estão executando muito mais do que duas instruções ao mesmo tempo, quando eles têm a oportunidade - isto é, quando não há nenhuma dependência entre as instruções sendo executado. Note como na versão de Wouter van Nifterick cada linha pode ser executado independentemente dos outros.
http://www.agner.org/optimize/ tem todas as informações que você poderia nunca precisa entender a arquitetura de processadores modernos e como aproveitá-las.
Se você só suportam 80386 e acima, você pode usar BTCC e SETcc conjunto de instruções desta maneira:
BT ax,1
SETC [dx]
inc dx
BT ax,2
SETC [dx]
inc dx
etc
Como sobre algo como:
/* 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
A razão provável que 4b é mais rápido que 4a é que ele parallelizes melhor. De 4a:
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)
instruções marcados como "dados dep" não pode iniciar a execução até que a instrução anterior ter terminado, e eu escrevi os registros que causam essa dependência de dados. CPUs modernas são capazes de começar uma instrução antes do último foi concluído, se não houver nenhuma dependência. Mas a maneira que você ordenou que estas evita operações desta.
Em 4b, você tem menos dependências de dados:
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;
Com esta ordenação de instrução, menos as instruções dependem da instrução anterior, para que haja mais oportunidade para paralelismo.
Não posso garantir que esta é a razão para a diferença de velocidade, mas é um provável candidato. Infelizmente, é difícil encontrar respostas tão absoluta como aqueles que você está procurando; processadores modernos possuem preditores do ramo, caches multi-nível, hardware pré-fetchers, e todos os tipos de outras complexidades que podem torná-lo difícil de isolar as razões para as diferenças de desempenho. O melhor que você pode fazer é ler muito, realizar experiências, e se familiarizar com as ferramentas para fazer medições boas.
I palpite é que a escrita para a memória (na verdade, a memória cache) é mais lento do que trabalhar com registros.
Assim,
mov [edx+...], bl
shr al, $01;
mov bl, al;
dá o processador de algum tempo para escrever bl para a memória antes do registo bl seja necessário novamente, enquanto
shr al, $01;
mov [edx], bl;
mov bl, al;
necessidades bl imediatamente para o processador tem que parar e esperar para a gravação de memória para completo.
Este é surpreendente para mim. processadores Intel modernos fazer pipelining louco e registrar renomeando assim na minha opinião, se alguma coisa, DecodePixels4b deve ser mais rápido, uma vez que as dependências de cada instrução são mais para trás. A descrição acima é toda a explicação que posso oferecer, para além deste:
x86 é um conjunto de instruções terrível, e Intel faz incrível e muito avançado abracadabra para torná-lo eficiente. Se eu fosse você, gostaria de olhar em outra coisa. Há muito pouca demanda por software megaMcOptimised para PCs hoje. Minha sugestão amigável é olhar para processadores para dispositivos móveis (principalmente ARM), porque em dispositivos móveis, a velocidade do processador, consumo de energia e as preocupações da vida da bateria significa que o software otimizado para micro é mais importante. E ARM tem um conjunto de instruções x86 superior a.
SIMD
Se você estender o algoritmo para processamento de matrizes, em seguida, SIMD torna-se uma opção de otimização. Aqui está uma versão SIMD que é 1/3 do tempo de um C equivalente otimizada:
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;
}
solução inteligente incrível Chris , o que você faria com o problema inverso: fazer um byte de uma matriz de 8 bytes
Não solução para o problema inverso otimizado:
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
Como você pode observar, a diferença de velocidade na 4a e 4b implementação é por causa da otimização CPU (por executar múltiplas instruções em paralelo / pipeline). Mas o fator não está nos operandos, mas por causa da natureza do próprio operador.
4a Instruction Sequence:
AND - MOV - SHR
4b Instruction Sequence:
AND - SHR - MOV
Ambos E e SHR usar sinalizadores registar, assim que estas duas instruções tem estado de espera em seu pipeline.
Leia-os da seguinte forma:
4a: AND (piped) MOV (piped) SHR
4b: AND (WAIT) SHR (piped) MOV
Conclusão: 4b tem 7 mais espera pelo estado em que o gasoduto de 4a, portanto, é mais lento
.Josh mencionou que há dependências de dados, i:.
mov bl, al;
and bl, $01; // data dep (bl)
mas não é inteiramente verdade, pois esses dois instrução pode ser parcialmente executado em paralelo em nível de CPU:
mov bl, al -> (A:) read al (B:) write bl => (2 clocks in i386)
and bl, 01 -> (C:) read 01 (D:) write bl => idem
Sequencialmente tomam 4 relógios, mas pipeline eles levam apenas 3 "relógios" (na verdade, o termo "relógio" não é adequada na perspectiva gasoduto mas eu usei-lo no contexto de simplicidade)
[--A--][--B--]
[--C--]<wait>[---D--]
