Problemas com ADC / SBB e INC / DEC em loops apertados em algumas CPUs

Estou escrevendo um tipo BigInteger simples no Delphi. Ele consiste principalmente em uma matriz dinâmica de TLimb, em que um TLimb é um inteiro não assinado de 32 bits e um campo de tamanho de 32 bits, que também contém o bit de sinal para o BigInteger.

Para adicionar dois BigIntegers, eu crio um novo BigInteger do tamanho apropriado e depois, após alguma escrituração, chamo o seguinte procedimento, passando-lhe três pointers para as respectivas partidas dos arrays para o operando esquerdo e direito e o resultado, assim como o número de membros para esquerda e direita, respectivamente.

Código simples :

class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, RSize: Integer); asm // EAX = Left, EDX = Right, ECX = Result PUSH ESI PUSH EDI PUSH EBX MOV ESI,EAX // Left MOV EDI,EDX // Right MOV EBX,ECX // Result MOV ECX,RSize // Number of limbs at Left MOV EDX,LSize // Number of limbs at Right CMP EDX,ECX JAE @SkipSwap XCHG ECX,EDX // Left and LSize should be largest XCHG ESI,EDI // so swap @SkipSwap: SUB EDX,ECX // EDX contains rest PUSH EDX // ECX contains smaller size XOR EDX,EDX @MainLoop: MOV EAX,[ESI + CLimbSize*EDX] // CLimbSize = SizeOf(TLimb) = 4. ADC EAX,[EDI + CLimbSize*EDX] MOV [EBX + CLimbSize*EDX],EAX INC EDX DEC ECX JNE @MainLoop POP EDI INC EDI // Do not change Carry Flag DEC EDI JE @LastLimb @RestLoop: MOV EAX,[ESI + CLimbSize*EDX] ADC EAX,ECX MOV [EBX + CLimbSize*EDX],EAX INC EDX DEC EDI JNE @RestLoop @LastLimb: ADC ECX,ECX // Add in final carry MOV [EBX + CLimbSize*EDX],ECX @Exit: POP EBX POP EDI POP ESI end; // RET is inserted by Delphi compiler. 

Este código funcionou bem, e eu fiquei bem satisfeito com isso, até que notei, na minha configuração de desenvolvimento (Win7 em uma VM Parallels em um iMac) uma simples rotina de adição PURE PASCAL, fazendo o mesmo enquanto emulando o carry com uma variável e algumas cláusulas if eram mais rápidas do que minha rotina simples e direta de assembly manual.

Levei um tempo para descobrir que em certos processadores (incluindo meu iMac e um laptop mais antigo), a combinação de DEC ou INC e ADC ou SBB poderia ser extremamente lenta. Mas na maioria dos meus outros (eu tenho cinco outros PCs para testá-lo, embora quatro deles sejam exatamente iguais), foi bem rápido.

Então eu escrevi uma nova versão, emulando INC e DEC usando LEA e JECXZ , assim:

Parte da emulação de código :

 @MainLoop: MOV EAX,[ESI + EDX*CLimbSize] LEA ECX,[ECX - 1] // Avoid INC and DEC, see above. ADC EAX,[EDI + EDX*CLimbSize] MOV [EBX + EDX*CLimbSize],EAX LEA EDX,[EDX + 1] JECXZ @DoRestLoop // LEA does not modify Zero flag, so JECXZ is used. JMP @MainLoop @DoRestLoop: // similar code for the rest loop 

Isso tornou meu código nas máquinas “lentas” quase três vezes mais rápido, mas cerca de 20% mais lento nas máquinas “mais rápidas”. Então, agora, como código de boot, eu faço um loop de tempo simples e uso isso para decidir se configurarei a unidade para chamar a (s) rotina (s) simples ou emulada (s). Isso é quase sempre correto, mas às vezes ele escolhe as rotinas simples (mais lentas) quando deveria ter escolhido as rotinas de emulação.

Mas eu não sei se esta é a melhor maneira de fazer isso.

Questão

Eu dei a minha solução, mas os asm gurus aqui talvez saibam uma maneira melhor de evitar a lentidão em certos processadores?

Atualizar

As respostas de Peter e Nils me ajudaram muito a seguir o caminho certo. Esta é a parte principal da minha solução final para a versão DEC :

Código simples:

 class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, RSize: Integer); asm PUSH ESI PUSH EDI PUSH EBX MOV ESI,EAX // Left MOV EDI,EDX // Right MOV EBX,ECX // Result MOV ECX,RSize MOV EDX,LSize CMP EDX,ECX JAE @SkipSwap XCHG ECX,EDX XCHG ESI,EDI @SkipSwap: SUB EDX,ECX PUSH EDX XOR EDX,EDX XOR EAX,EAX MOV EDX,ECX AND EDX,$00000003 SHR ECX,2 CLC JE @MainTail @MainLoop: // Unrolled 4 times. More times will not improve speed anymore. MOV EAX,[ESI] ADC EAX,[EDI] MOV [EBX],EAX MOV EAX,[ESI + CLimbSize] ADC EAX,[EDI + CLimbSize] MOV [EBX + CLimbSize],EAX MOV EAX,[ESI + 2*CLimbSize] ADC EAX,[EDI + 2*CLimbSize] MOV [EBX + 2*CLimbSize],EAX MOV EAX,[ESI + 3*CLimbSize] ADC EAX,[EDI + 3*CLimbSize] MOV [EBX + 3*CLimbSize],EAX // Update pointers. LEA ESI,[ESI + 4*CLimbSize] LEA EDI,[EDI + 4*CLimbSize] LEA EBX,[EBX + 4*CLimbSize] // Update counter and loop if required. DEC ECX JNE @MainLoop @MainTail: // Add index*CLimbSize so @MainX branches can fall through. LEA ESI,[ESI + EDX*CLimbSize] LEA EDI,[EDI + EDX*CLimbSize] LEA EBX,[EBX + EDX*CLimbSize] // Indexed jump. LEA ECX,[@JumpsMain] JMP [ECX + EDX*TYPE Pointer] // Align jump table manually, with NOPs. Update if necessary. NOP // Jump table. @JumpsMain: DD @DoRestLoop DD @Main1 DD @Main2 DD @Main3 @Main3: MOV EAX,[ESI - 3*CLimbSize] ADC EAX,[EDI - 3*CLimbSize] MOV [EBX - 3*CLimbSize],EAX @Main2: MOV EAX,[ESI - 2*CLimbSize] ADC EAX,[EDI - 2*CLimbSize] MOV [EBX - 2*CLimbSize],EAX @Main1: MOV EAX,[ESI - CLimbSize] ADC EAX,[EDI - CLimbSize] MOV [EBX - CLimbSize],EAX @DoRestLoop: // etc... 

Eu removi muito espaço em branco, e acho que o leitor pode obter o resto da rotina. É semelhante ao loop principal. Uma melhoria de velocidade de aprox. 20% para BigIntegers maiores e 10% para os pequenos (apenas alguns membros).

A versão de 64 bits agora usa a adição de 64 bits sempre que possível (no loop principal e no Main3 e Main2, que não são “fall-through” como antes) e antes, 64 bits era bem mais lenta que 32 bits, mas agora é 30% mais rápido que 32 bits e duas vezes mais rápido que o loop original de 64 bits.

O que você está vendo é uma barraca de bandeira parcial.

CPUs Intel (exceto P4) renomear cada bit de flag separadamente, portanto, o JNE depende apenas da última instrução que configurou todos os flags que ele usa (nesse caso, apenas o sinalizador Z ). De fato, CPUs Intel recentes podem até combinar internamente um inc/jne em um único inc e branch branch (macro-fusão). No entanto, o problema ocorre ao ler um bit de sinalização que não foi modificado pela última instrução que atualizou quaisquer sinalizadores.

Agner Fog diz que os processadores da Intel (mesmo PPro / PII) não param no inc / jnz . Não é realmente o inc/jnz que está inc/jnz , é o adc na próxima iteração que tem que ler o flag CF depois que inc escreveu outras flags mas deixou CF não modificada.

 ; Example 5.21. Partial flags stall when reading unmodified flag bits cmp eax, ebx inc ecx jc xx ; Partial flags stall (P6 / PIII / PM / Core2 / Nehalem) 

Agner Fog também diz mais genericamente: “Evite código que dependa do fato de que INC ou DEC deixam o flag carry inalterado”. (para Pentium M / Core2 / Nehalem). A sugestão para evitar inc / dec é inteiramente obsoleta e aplicada somente a P4. Outras CPUs renomeam diferentes partes de EFLAGS separadamente, e só têm problemas quando a mesclagem é necessária (ler um sinalizador que não foi modificado pela última insn para gravar qualquer sinalizador).

Nas máquinas onde é rápido (Sandybridge e mais tarde), eles estão inserindo um extra uop para mesclar o registrador de flags quando você lê bits que não foram escritos pela última instrução que o modificou. Isto é muito mais rápido do que procanvasr por 7 ciclos, mas ainda não é ideal.

P4 sempre rastreia registros inteiros, em vez de renomear registradores parciais, nem mesmo EFLAGS. Então inc/jz tem uma dependência “falsa” de qualquer coisa que tenha escrito as bandeiras antes dela. Isso significa que a condição de loop não pode detectar o final do loop até que a execução da cadeia de dep adc chegue lá, portanto, o erro de ramificação que pode acontecer quando as ramificações de loop não são detectadas antecipadamente. Evita, no entanto, qualquer sinalização de sinalização parcial.

Seu lea / jecxz evita o problema bem. É mais lento no SnB e depois porque você não desenrolou o loop. Sua versão LEA é de 11 uops (pode emitir uma iteração por 3 ciclos), enquanto a versão inc é de 7 uops (pode emitir um iter por 2 ciclos), sem contar o upl de mesclagem de flag que insere em vez de travar.

Se a instrução de loop não fosse lenta , seria perfeita para isso. Na verdade, é rápido na família AMD Bulldozer (1 m-op, com o mesmo custo de uma mesa convergente e combinada) e na Via Nano3000. É ruim em todos os processadores da Intel, embora (7 uops na família SnB).


Desenrolando

Quando você desenrola, você pode obter outro pequeno ganho usando pointers em vez de modos de endereçamento indexados, porque os modos de endereçamento de 2-reg não podem micro-fundir em SnB e mais tarde . Um grupo de instruções load / adc / store é de 6 uops sem micro-fusão, mas apenas 4 com micro-fusão. As CPUs podem emitir 4 uops / clock de domínio fundido. (Veja o documento de microarquitetura da Agner Fog, e tabelas de instruções, para detalhes sobre este nível.)

Salve uops quando puder para ter certeza de que a CPU pode emitir instruções mais rapidamente do que executar, para ter certeza de que ela pode enxergar longe o suficiente no stream de instruções para absorver quaisquer bolhas na busca de insn (por exemplo, branch mispredict). A instalação no buffer de loop 28uop também significa economia de energia (e no Nehalem, evitando gargalos de decodificação de instruções). Há coisas como alinhamento de instruções e cruzar limites de linha de cache uop que dificultam a sustentação de 4 uops / clock sem o loop buffer também.

Outro truque é manter os pointers no final dos buffers e contar até zero. (Então, no início do seu loop, você obtém o primeiro item como end[-idx] .)

  ; pure loads are always one uop, so we can still index it ; with no perf hit on SnB add esi, ecx ; point to end of src1 neg ecx UNROLL equ 4 @MainLoop: MOV EAX, [ESI + 0*CLimbSize + ECX*CLimbSize] ADC EAX, [EDI + 0*CLimbSize] MOV [EBX + 0*CLimbSize], EAX MOV EAX, [ESI + 1*CLimbSize + ECX*CLimbSize] ADC EAX, [EDI + 1*CLimbSize] MOV [EBX + 1*CLimbSize], EAX ; ... repeated UNROLL times. Use an assembler macro to repeat these 3 instructions with increasing offsets LEA ECX, [ECX+UNROLL] ; loop counter LEA EDI, [EDI+ClimbSize*UNROLL] ; Unrolling makes it worth doing LEA EBX, [EBX+ClimbSize*UNROLL] ; a separate increment to save a uop for every ADC and store on SnB & later. JECXZ @DoRestLoop // LEA does not modify Zero flag, so JECXZ is used. JMP @MainLoop @DoRestLoop: 

Um desenrolar de 4 deve ser bom. Não há necessidade de exagerar, desde que você está prob. vai ser capaz de saturar as portas de carga / armazenamento de pré-Haswell com um desenrolar de apenas 3 ou 4, talvez até 2.

Um desenrolar de 2 fará com que o loop acima faça exatamente 14 uops de domínio fundido para os processadores Intel. adc é 2 ALU (+1 de memory fundida), jecxz é 2, o resto (incluindo LEA) são todos 1. No domínio não fundido, 10 ALU / ramificação e 6 de memory (bem, 8 de memory se você realmente contar endereço de loja e armazenar dados separadamente).

  • 14 uops de domínio fundido por iteração: emita uma iteração por 4 clocks. (Os 2 uops ímpares no final têm que ser emitidos como um grupo de 2, mesmo do buffer de loop.)
  • 10 UU & branch uops: Leva 3.33c para executá-los todos em pré-haswell. Eu não acho que qualquer uma das portas seja um gargalo: uops da adc podem rodar em qualquer porta e lea pode rodar em p0 / p1. Os saltos usam port5 (e jecx também usa um dos p0 / p1)
  • 6 operações de memory: Leva 3c para executar em CPUs pré-Haswell, que podem lidar com 2 por clock. Haswell adicionou um AGU dedicado para as lojas, para que ele possa sustentar o 2load + 1store / clock.

Portanto, para CPUs pré-haswell, usando LEA / JECXZ, um desenrolar de 2 não saturará nem a ALU nem as portas de carga / armazenamento. Um desenrolar de 4 trará até 22 uops fundidos (6 ciclos para emissão). 14 ALU & branch: 4.66c para executar. 12 memory: 6 ciclos para executar. Assim, um desenrolar de 4 saturará CPUs pré-Haswell, mas apenas mal. A CPU não terá nenhum buffer de instruções para distribuir em um erro de ramificação.

Haswell e mais tarde sempre serão afunilados no frontend (4 uops por clock), porque a combinação load / adc / store leva 4 uops e pode ser mantida em um por clock. Portanto, nunca há uma “sala” para sobrecarga de loop sem cortar a taxa de transferência adc . É aqui que você deve saber não exagerar e desenrolar demais.

No Broadwell / Skylake, o adc é apenas um único uop com latência de 1c, e load / adc r, m / store parece ser a melhor sequência. adc m, r/i é de 4 uops. Isso deve sustentar um adc por clock, como a AMD.

Nos processadores da AMD, adc é apenas uma macro-op, então se a CPU puder sustentar uma taxa de emissão de 4 (ou seja, sem gargalos de decodificação), eles também podem usar sua porta 2 load / 1 store para vencer Haswell. Além disso, o jecxz na AMD é tão eficiente quanto qualquer outro ramo: apenas uma macro-op. A matemática de precisão múltipla é uma das poucas coisas em que os processadores da AMD são bons. Latências mais baixas em algumas instruções inteiras dão a elas uma vantagem em algumas rotinas GMP.


Um desenrolar de mais de 5 pode prejudicar o desempenho no Nehalem, porque isso tornaria o loop maior que o buffer de loop de 28uop. A decodificação de instruções limitaria você a menos de 4 uops por clock. Mesmo antes (Core2), há um buffer de loop de instrução x86 de 64B (64B de código x86, não uops), o que ajuda alguns a decodificar.

A menos que essa rotina adc seja o único gargalo no seu aplicativo, eu manteria o fator de desmembramento para talvez 2. Ou talvez até não desenrole, se isso economizar muito código de prólogo / epílogo, e seus BigInts não forem muito grandes. Você não quer inflar muito o código e criar erros de cache quando os chamadores chamam várias funções diferentes do BigInteger, como add, sub, mul e fazem outras coisas entre elas. Desenrolar-se demais para ganhar em microbenchmarks pode triggersr no pé se o seu programa não passar muito tempo em seu loop interno em cada chamada.

Se seus valores BigInt não são geralmente gigantescos, então não é apenas o loop que você precisa ajustar. Um desenrolar menor poderia ser bom para simplificar a lógica do prólogo / epílogo. Certifique-se de verificar os comprimentos para que o ECX não ultrapasse zero sem nunca ser zero, é claro. Este é o problema com desenrolar e vetores. : /


Salvando / restaurando CF para CPUs antigas, em vez de loop sem sinalização:

Essa pode ser a maneira mais eficiente:

 lahf # clobber flags sahf ; cheap on AMD and Intel. This doesn't restore OF, but we only care about CF # or setc al # clobber flags add al, 255 ; generate a carry if al is non-zero 

Usar o mesmo registrador que a cadeia adc dep não é realmente um problema: o eax estará sempre pronto ao mesmo tempo que a saída CF do último adc . (Na AMD e P4 / Silvermont as gravações de registro parcial têm um falso dep no registro completo. Elas não renomear regs parciais separadamente). O save / restore faz parte da cadeia dep adc, não da cadeia dep da condição loop.

A condição de loop apenas verifica os sinalizadores gravados por cmp , sub ou dec . Salvar / restaurar sinalizadores em torno dele não o torna parte da cadeia de dep do adc , portanto, o erro de ramificação no final do loop pode ser detectado antes que a execução do adc chegue lá. (Uma versão anterior desta resposta entendeu errado.)


Há quase certamente algum espaço para eliminar instruções no código de configuração, talvez usando registros onde os valores iniciam. Você não tem que usar edi e esi para pointers, embora eu saiba que facilita o desenvolvimento inicial quando você está usando registradores de maneiras consistentes com seu uso “tradicional”. (por exemplo, ponteiro de destino em EDI).

O Delphi permite usar o ebp ? É bom ter um 7º registro.

Obviamente, o código de 64 bits faria seu código BigInt rodar duas vezes mais rápido, mesmo que você tenha que se preocupar em fazer um único 32b adc no final de um loop de 64 bits adc . Também lhe daria 2x a quantidade de registros.

Existem tantos chips x86 com tempos de uso muito diferentes que você não pode realisticamente ter código ótimo para todos eles. Sua abordagem para ter duas boas funções conhecidas e benchmark antes do uso já é bastante avançada.

No entanto, dependendo do tamanho dos BigIntegers, é possível melhorar o código simplesmente desenrolando o loop. Isso removerá drasticamente a sobrecarga do loop.

Por exemplo, você poderia executar um bloco especializado que faz a adição de oito inteiros como este:

 @AddEight: MOV EAX,[ESI + EDX*CLimbSize + 0*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 0*CLimbSize] MOV [EBX + EDX*CLimbSize + 0*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 1*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 1*CLimbSize] MOV [EBX + EDX*CLimbSize + 1*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 2*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 2*CLimbSize] MOV [EBX + EDX*CLimbSize + 2*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 3*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 3*CLimbSize] MOV [EBX + EDX*CLimbSize + 3*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 4*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 4*CLimbSize] MOV [EBX + EDX*CLimbSize + 4*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 5*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 5*CLimbSize] MOV [EBX + EDX*CLimbSize + 5*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 6*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 6*CLimbSize] MOV [EBX + EDX*CLimbSize + 6*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 7*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 7*CLimbSize] MOV [EBX + EDX*CLimbSize + 7*CLimbSize],EAX LEA ECX,[ECX - 8] 

Agora você reconstrói seu loop, execute o bloco acima contanto que você tenha mais de 8 elementos para processar e fazer os poucos elementos restantes usando o loop de adição de elemento único que você já possui.

Para BitIntegers grandes, você gastará a maior parte do tempo na parte desenrolada, o que deve ser executado muito mais rápido agora.

Se você quiser ainda mais rápido, escreva sete blocos adicionais que são especializados nas contagens de elementos restantes e ramifique-os com base na contagem de elementos. Isso pode ser feito armazenando os sete endereços em uma tabela de consulta, carregando o endereço a partir dele e pulando diretamente para o código especializado.

Para contagens de elementos pequenos, isso remove completamente o loop inteiro e, para elementos grandes, você obtém todos os benefícios do loop desenrolado.