A maneira mais rápida de calcular a ordem de grandeza na montagem x86

12

A tarefa é simples: escreva uma montagem que calcule a ordem de magnitude de um número inteiro usando o menor número possível de ciclos de relógio.

  • Ordem de magnitude é definida como log10, não log2.
  • O intervalo de entrada válido é 0para , inclusive. O comportamento para entrada fora desse intervalo é indefinido.1012
  • Os valores devem ser arredondados para o número inteiro mais próximo, com a exceção de que, dada a entrada, 0a saída deve ser 0. (Você pode considerar que essa é a melhor representação do infinito negativo possível em números inteiros não assinados).
  • Deve ser uma montagem x86.
  • O número inteiro deve ser um valor de tempo de execução , não um número inteiro estático / em linha. Portanto, não sabemos o que é em tempo de compilação.
  • Suponha que você já tenha um número inteiro carregado em um registro. (Mas inclua a definição do valor no registro na resposta para maior clareza).
  • Não é possível chamar nenhuma biblioteca ou função externa.
  • Livre para usar qualquer uma das instruções disponíveis nos documentos da Intel .
  • Não C.
  • Qualquer uma das arquiteturas ~ 7 Intel Core é aceitável (listada na página 10 ). Idealmente Nehalem (Intel Core i7).

A resposta vencedora é aquela que usa o menor número possível de ciclos de relógio. Ou seja, ele pode ter o máximo de operações por segundo. Os resumos aproximados do ciclo do relógio estão aqui: http://www.agner.org/optimize/instruction_tables.pdf . O cálculo dos ciclos do relógio pode acontecer depois que a resposta for postada.

math fastest-algorithm assembly Lance Pollard
fonte
'FYL2X' e outras instruções da FPU são permitidas?
Digital Trauma
1
O resultado deve ser um número inteiro? Se sim, como deve ser arredondado?
Digital Trauma
3
Então a entrada e a saída são números inteiros, sim? Mas a entrada pode ser tão grande quanto 10 ^ 12, então é muito grande para um int de 32 bits. Então, assumimos a entrada inteira de 64 bits?
Paul R
3
O critério de vencimento é baseado no número máximo ou médio de ciclos? E se for médio, qual é a distribuição de insumos?
precisa saber é o seguinte
2
Qual processador é direcionado? O documento vinculado lista mais de 20 processos diferentes (AMD, Intel, outros) e há uma variação considerável nas latências.
Digital Trauma

Respostas:

8

7 ciclos, tempo constante

Aqui está uma solução com base na minha resposta a esta pergunta SO . Ele usa BSR para contar quantos bits são necessários para armazenar o número. Ele procura quantos dígitos decimais são necessários para representar o maior número que muitos bits podem conter. Subtrai 1 se o número real for menor que a potência mais próxima de 10 com tantos dígitos.

    .intel_syntax noprefix
    .globl  main
main:
    mov rdi, 1000000000000              #;your value here
    bsr rax, rdi
    movzx   eax, BYTE PTR maxdigits[1+rax]
    cmp rdi, QWORD PTR powers[0+eax*8]
    sbb al, 0
    ret
maxdigits:
    .byte   0
    .byte   0
    .byte   0
    .byte   0
    .byte   1
    .byte   1
    .byte   1
    .byte   2
    .byte   2
    .byte   2
    .byte   3
    .byte   3
    .byte   3
    .byte   3
    .byte   4
    .byte   4
    .byte   4
    .byte   5
    .byte   5
    .byte   5
    .byte   6
    .byte   6
    .byte   6
    .byte   6
    .byte   7
    .byte   7
    .byte   7
    .byte   8
    .byte   8
    .byte   8
    .byte   9
    .byte   9
    .byte   9
    .byte   9
    .byte   10
    .byte   10
    .byte   10
    .byte   11
    .byte   11
    .byte   11
    .byte   12
powers:
    .quad   0
    .quad   10
    .quad   100
    .quad   1000
    .quad   10000
    .quad   100000
    .quad   1000000
    .quad   10000000
    .quad   100000000
    .quad   1000000000
    .quad   10000000000
    .quad   100000000000
    .quad   1000000000000

Compila no GCC 4.6.3 para ubuntu e retorna o valor no código de saída.

Não estou confiante em interpretar essa tabela de ciclos para qualquer processador moderno, mas usando o método da @ DigitalTrauma, no processador Nehalim, recebo 7 ?

ins        uOps Latency
---        -    - 
BSR r,r  : 1    3
MOVZX r,m: 1    -
CMP m,r/i: 1    1 
SBB r,r/i: 2    2
AShelly
fonte
Oh - vi o DigitalTrauma's depois que comecei a escrever o meu. Idéias semelhantes. Usando sua metodologia de contagem Acho get 3,1,1,1 = 6 para BSR, MOV, CMP, SBB
AShelly
Sim, acho que o seu supera o meu. Só vai para mostrar a) Eu não sou um programador de montagem e b) montagem é melhor deixado sozinho por nós, meros mortais ;-)
Digital Trauma
The integer must be a runtime value, not a static/inline integer. So we don't know what it is at compile time.
cat
1
à direita e a próxima linha diz: "Suponha que você já tenha um número inteiro carregado em um registro. (Mas inclua a definição do valor no registro na resposta para maior clareza)." Foi o que eu fiz.
AShelly
substitua o movzx eax por mov al. Os 24 bits principais do eax já serão zero, portanto o zx é redundante (e caro).
peter ferrie
6

Melhor caso 8 ciclos, pior caso 12 ciclos

Como não está claro na pergunta, estou baseando isso nas latências da Ivy Bridge.

A abordagem aqui é usar a bsrinstrução (bit scan reverse) como um log2 de pobre (). O resultado é usado como um índice em uma tabela de salto que contém entradas para os bits de 0 a 42. Estou assumindo que, dado que a operação em dados de 64 bits é implicitamente necessária, o uso da bsrinstrução é OK.

Na melhor das hipóteses, a entrada saltável pode mapear o bsrresultado diretamente para a magnitude. por exemplo, para entradas no intervalo 32-63, o bsrresultado será 5, que é mapeado para uma magnitude de 1. Nesse caso, o caminho da instrução é:

Instruction    Latency

bsrq                 3
jmp                  2
movl                 1
jmp                  2

total                8

Na pior das hipóteses, o bsrresultado será mapeado para duas magnitudes possíveis; portanto, a entrada saltável faz uma adicional cmppara verificar se a entrada é> 10 n . Por exemplo, para entradas na faixa de 64 a 127, o bsrresultado será 6. A entrada jumptable correspondente verifica se a entrada é> 100 e define a magnitude da saída de acordo.

Além do caminho do pior caso, temos uma instrução mov adicional para carregar um valor imediato de 64 bits para uso no cmp, portanto, o caminho do pior caso é:

Instruction    Latency

bsrq                 3
jmp                  2
movabsq              1
cmpq                 1
ja                   2
movl                 1
jmp                  2

total               12

Aqui está o código:

    /* Input is loaded in %rdi */
    bsrq    %rdi, %rax
    jmp *jumptable(,%rax,8)
.m0:
    movl    $0, %ecx
    jmp .end
.m0_1:
    cmpq    $9, %rdi
    ja  .m1
    movl    $0, %ecx
    jmp .end
.m1:
    movl    $1, %ecx
    jmp .end
.m1_2:
    cmpq    $99, %rdi
    ja  .m2
    movl    $1, %ecx
    jmp .end
.m2:
    movl    $2, %ecx
    jmp .end
.m2_3:
    cmpq    $999, %rdi
    ja  .m3
    movl    $2, %ecx
    jmp .end
.m3:
    movl    $3, %ecx
    jmp .end
.m3_4:
    cmpq    $9999, %rdi
    ja  .m4
    movl    $3, %ecx
    jmp .end
.m4:
    movl    $4, %ecx
    jmp .end
.m4_5:
    cmpq    $99999, %rdi
    ja  .m5
    movl    $4, %ecx
    jmp .end
.m5:
    movl    $5, %ecx
    jmp .end
.m5_6:
    cmpq    $999999, %rdi
    ja  .m6
    movl    $5, %ecx
    jmp .end
.m6:
    movl    $6, %ecx
    jmp .end
.m6_7:
    cmpq    $9999999, %rdi
    ja  .m7
    movl    $6, %ecx
    jmp .end
.m7:
    movl    $7, %ecx
    jmp .end
.m7_8:
    cmpq    $99999999, %rdi
    ja  .m8
    movl    $7, %ecx
    jmp .end
.m8:
    movl    $8, %ecx
    jmp .end
.m8_9:
    cmpq    $999999999, %rdi
    ja  .m9
    movl    $8, %ecx
    jmp .end
.m9:
    movl    $9, %ecx
    jmp .end
.m9_10:
    movabsq $9999999999, %rax
    cmpq    %rax, %rdi
    ja  .m10
    movl    $9, %ecx
    jmp .end
.m10:
    movl    $10, %ecx
    jmp .end
.m10_11:
    movabsq $99999999999, %rax
    cmpq    %rax, %rdi
    ja  .m11
    movl    $10, %ecx
    jmp .end
.m11:
    movl    $11, %ecx
    jmp .end
.m11_12:
    movabsq $999999999999, %rax
    cmpq    %rax, %rdi
    ja  .m12
    movl    $11, %ecx
    jmp .end
.m12:
    movl    $12, %ecx
    jmp .end

jumptable:
    .quad   .m0
    .quad   .m0
    .quad   .m0
    .quad   .m0_1
    .quad   .m1
    .quad   .m1
    .quad   .m1_2
    .quad   .m2
    .quad   .m2
    .quad   .m2_3
    .quad   .m3
    .quad   .m3
    .quad   .m3
    .quad   .m3_4
    .quad   .m4
    .quad   .m4
    .quad   .m4_5
    .quad   .m5
    .quad   .m5
    .quad   .m5_6
    .quad   .m6
    .quad   .m6
    .quad   .m6
    .quad   .m6_7
    .quad   .m7
    .quad   .m7
    .quad   .m7_8
    .quad   .m8
    .quad   .m8
    .quad   .m8_9
    .quad   .m9
    .quad   .m9
    .quad   .m9
    .quad   .m9_10
    .quad   .m10
    .quad   .m10
    .quad   .m10_11
    .quad   .m11
    .quad   .m11
    .quad   .m11_12
    .quad   .m12
    .quad   .m12
    .quad   .m12

.end:
/* output is given in %ecx */

Isso foi gerado principalmente a partir da saída do montador gcc para o código C de prova de conceito que eu escrevi . Observe que o código C usa um goto computável para implementar a tabela de salto. Ele também usa o __builtin_clzll()gcc builtin, que é compilado com a bsrinstrução (mais uma xor).

Eu considerei várias soluções antes de chegar a esta:

  • FYL2Xpara calcular o log natural e, em seguida, FMULpela constante necessária. Presumivelmente, isso venceria se fosse um concurso [tag: instruction: golf]. Mas FYL2Xtem como latência de 90-106 para a ponte Ivy.

  • Pesquisa binária codificada. Isso pode ser realmente competitivo - deixarei para outra pessoa implementar :).

  • Tabela de pesquisa completa de resultados. Eu tenho certeza que isso é teoricamente mais rápido, mas exigiria uma tabela de pesquisa de 1 TB - ainda não prática - talvez em alguns anos se a Lei de Moore continuar em vigor.

Trauma Digital
fonte
Se necessário, posso calcular uma latência média para todas as entradas permitidas.
Digital Trauma
jmpe jccnão tem latência, apenas custos de taxa de transferência. Previsão de ramificação + execução especulativa significa que as dependências de controle não fazem parte das cadeias de dependência de dados.
Peter Cordes