La forma más rápida de calcular el orden de magnitud en el ensamblaje x86

12

La tarea es simple: escribir ensamblaje que calcule el orden de magnitud de un número entero utilizando la menor cantidad de ciclos de reloj posible.

  • El orden de magnitud se define como log10, no log2.
  • El rango de entrada válida es 0a , inclusive. El comportamiento para la entrada fuera de ese rango no está definido.1012
  • Los valores deben redondearse al entero más cercano, con la excepción de que, dada la entrada, 0la salida debe ser 0. (Puede considerar que esta es la mejor representación del infinito negativo que es posible en enteros sin signo).
  • Debe ser x86 ensamblado.
  • El entero debe ser un valor de tiempo de ejecución , no un entero estático / en línea. Entonces no sabemos qué es en tiempo de compilación.
  • Suponga que ya tiene un entero cargado en un registro. (Pero incluya establecer el valor en el registro en la respuesta para mayor claridad).
  • No se pueden llamar a bibliotecas o funciones externas.
  • Libre de usar cualquiera de las instrucciones disponibles en los documentos de Intel .
  • No C.
  • Cualquiera de las ~ 7 arquitecturas Intel Core son aceptables (enumeradas en la página 10 ). Idealmente Nehalem (Intel Core i7).

La respuesta ganadora es aquella que utiliza la menor cantidad de ciclos de reloj posibles. Es decir, puede tener la mayoría de las operaciones por segundo. Los resúmenes aproximados del ciclo del reloj están aquí: http://www.agner.org/optimize/instruction_tables.pdf . El cálculo de los ciclos de reloj puede ocurrir después de que se publique la respuesta.

math fastest-algorithm assembly Lance Pollard
fuente
¿Están permitidos 'FYL2X' y otras instrucciones de FPU?
Digital Trauma
1
¿Debería ser el resultado un número entero? Si es así, ¿cómo se debe redondear?
Digital Trauma
3
Entonces la entrada y la salida son números enteros, ¿sí? Pero la entrada puede ser tan grande como 10 ^ 12, por lo que es demasiado grande para un int de 32 bits. Entonces, ¿suponemos una entrada entera de 64 bits?
Paul R
3
¿El criterio ganador se basa en el número máximo o promedio de ciclos? Y si es promedio, ¿cuál es la distribución de entradas?
Runer112
2
¿Qué procesador está dirigido? El documento vinculado enumera más de 20 procesos diferentes (AMD, Intel, otros) y hay una variación considerable en las latencias.
Digital Trauma

Respuestas:

8

7 ciclos, tiempo constante

Aquí hay una solución basada en mi respuesta a esta pregunta SO . Utiliza BSR para contar cuántos bits se necesitan para contener el número. Busca cuántos dígitos decimales se necesitan para representar el número más grande que pueden contener muchos bits. Luego resta 1 si el número real es menor que la potencia más cercana de 10 con esa cantidad de 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 en GCC 4.6.3 para ubuntu y devuelve el valor en el código de salida.

No estoy seguro de interpretar esa tabla de ciclos para cualquier procesador moderno, pero usando el método @ DigitalTrauma, en el procesador Nehalim, obtengo 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
fuente
Oh, vi DigitalTrauma's después de que comencé a escribir el mío. Ideas similares Usando su metodología de conteo, creo que obtener 3,1,1,1 = 6 para BSR, MOV, CMP, SBB
AShelly
Sí, creo que el tuyo supera al mío. Solo va a mostrar a) No soy un programador de ensamblaje yb) el ensamblaje es mejor que lo dejemos nosotros simples mortales ;-)
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.
gato
1
a la derecha, y la siguiente línea dice: "Suponga que ya tiene un número entero cargado en un registro. (Pero incluya la definición del valor en el registro en la respuesta para mayor claridad)". Que es lo que he hecho.
AShelly
reemplace el movzx eax con mov al. Los primeros 24 bits de eax ya serán cero, por lo que el zx es redundante (y es costoso).
Peter Ferrie
6

Mejor caso 8 ciclos, peor caso 12 ciclos

Como no está claro en la pregunta, estoy basando esto en las latencias de Ivy Bridge.

El enfoque aquí es utilizar la bsrinstrucción (escaneo de bits inverso) como log2 () de un hombre pobre. El resultado se usa como índice en una tabla de salto que contiene entradas para los bits 0 a 42. Supongo que dado que la operación en datos de 64 bits es implícitamente requerida, entonces el uso de la bsrinstrucción está bien.

En el mejor de los casos, la entrada jumptable puede asignar el bsrresultado directamente a la magnitud. Por ejemplo, para entradas en el rango 32-63, el bsrresultado será 5, que se asigna a una magnitud de 1. En este caso, la ruta de instrucciones es:

Instruction    Latency

bsrq                 3
jmp                  2
movl                 1
jmp                  2

total                8

En el peor de los casos, el bsrresultado se correlacionará con dos posibles magnitudes, por lo que la entrada de la tabla de salto hace uno adicional cmppara verificar si la entrada es> 10 n . Por ejemplo, para las entradas en el rango 64-127, el bsrresultado será 6. La entrada correspondiente de la tabla de salto verifica si la entrada> 100 y establece la magnitud de salida en consecuencia.

Además de la ruta del peor de los casos, tenemos una instrucción mov adicional para cargar un valor inmediato de 64 bits para usar en cmp, por lo que la ruta de la instrucción del peor caso es:

Instruction    Latency

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

total               12

Aquí está el 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 */

Esto se generó principalmente a partir de la salida del ensamblador gcc para el código C de prueba de concepto que escribí . Tenga en cuenta que el código C usa un goto computable para implementar la tabla de salto. También utiliza el __builtin_clzll()gcc incorporado, que compila las bsrinstrucciones (más un xor).

Consideré varias soluciones antes de llegar a esta:

  • FYL2Xpara calcular el registro natural, luego FMULpor la constante necesaria. Esto presumiblemente ganaría esto si fuera un concurso [tag: instrucción: golf]. Pero FYL2Xtiene una latencia de 90-106 para el puente Ivy.

  • Búsqueda binaria codificada. En realidad, esto puede ser competitivo: dejaré que alguien más lo implemente :).

  • Tabla de búsqueda completa de resultados. Estoy seguro de que esto es teóricamente más rápido, pero requeriría una tabla de búsqueda de 1TB, aún no práctica, tal vez en unos pocos años si la Ley de Moore continúa vigente.

Trauma digital
fuente
Si es necesario, puedo calcular una latencia promedio para todas las entradas permitidas.
Digital Trauma
jmpy jccno tienen latencia, solo costos de rendimiento. La predicción de rama + ejecución especulativa significa que las dependencias de control no son parte de las cadenas de dependencia de datos.
Peter Cordes