Ensamblado x86-64 - Suma de múltiplos de 3 o 5
Estoy tratando de aprender un ensamblaje básico de x86 y por eso he comenzado a resolver los problemas del Proyecto Euler. Esperaba alguna crítica de mi código que, con suerte, incluye la eficiencia de las operaciones o la legibilidad / estilo del código en sí. Proporcionaré el Makefile para Linux de 64 bits.
El propósito del código es sumar todos los números de [0, 1000) que son divisibles por 3 o 5.
El código se puede ejecutar usando make RUN=euler_1.
NÓTESE BIEN:
Soy consciente de que la mayoría de los compiladores reemplazan los módulos de números conocidos con alguna combinación de movy shrpara evitar la división de enteros. Por ejemplo, vea este hilo .
Makefile
.PHONY: clean
all: $(RUN).elf ./$^
%.elf: %.o
ld $^ -o $@ -lc -e main -dynamic-linker /lib64/ld-linux-x86-64.so.2
%.o: %.asm
nasm -f elf64 $^
clean:
rm -f *.o *.elf
euler_1.asm
extern printf
global main
section .data
fmt: db "%d", 0x0a, 0
section .text
;; main - Calculate the sum of all numbers between [0, 1000) that are divisible
;; by 3 or 5.
;; sum : R8
main:
; sum = 0
mov r8, 0
; for i in [0, 1000) {
mov rcx, 0
for0:
; if i % 3 == 0 or i % 5 == 0 {
; i % 3 == 0
mov rax, rcx
mov rdx, 0
mov r9, 3
div r9
test rdx, rdx
jne if01
; sum = sum + i
add r8, rcx
jmp if0
if01:
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne if0
; sum = sum + i
add r8, rcx
jmp if0
; }
if0:
inc rcx
cmp rcx, 1000
jl for0
; }
; printf("%d", sum)
lea rdi, [rel fmt]
mov rsi, r8
mov rax, 0
call printf
; sys_exit(0)
mov rdi, 0
mov rax, 60
syscall
Respuestas
Aquí hay algunas cosas que pueden ayudarlo a mejorar su código. La otra revisión hizo algunos puntos positivos, pero aquí hay algunos que no se cubren allí.
Decide si estás usando stdlib o no
La Makefilellamada y para printfambas indican que estás usando la biblioteca C estándar, lo cual está bien, pero luego el programa termina usando una syscallque no lo es. La razón es que el inicio C estándar configura las cosas antes de que mainse llame y luego también las derriba nuevamente después de las maindevoluciones. Este código omite el desmontaje al utilizar en su lugar syscallpara finalizar el programa, lo cual no es una buena práctica. Hay dos alternativas: o no use la biblioteca C en absoluto (es decir, escriba su propia rutina de impresión ) o deje que el desmontaje realmente suceda:
xor eax, eax ; set exit code to 0 to indicate success
ret ; return to _libc_start_main which called our main
Para obtener más información sobre cómo funcionan el inicio y el desmontaje en Linux, lea esto .
Administre los registros con cuidado
Una de las cosas que hacen los programadores expertos en lenguaje ensamblador (y los buenos compiladores) es administrar el uso de registros. En este caso, el uso final de la suma es imprimirla, y para imprimirla necesitamos el valor en el rsiregistro. Entonces, ¿por qué no usarlo en rsilugar de r8como suma corriente?
Sepa cómo poner a cero eficientemente un registro
Obviamente, si lo escribimos mov r8, 0tiene el efecto deseado de cargar el valor 0 en el r8registro, y como señalan las otras reseñas, hay mejores formas de hacerlo, pero veamos más profundamente. El código actualmente hace esto:
; sum = 0
mov r8, 0
; for i in [0, 1000) {
mov rcx, 0
Eso funciona, pero veamos el archivo de lista para ver en qué lo ha convertido NASM:
13 ; sum = 0
14 00000000 41B800000000 mov r8, 0
15 ; for i in [0, 1000) {
16 00000006 B900000000 mov rcx, 0
La primera columna es solo el número de línea del archivo de listado, la segunda es la dirección y la tercera es la instrucción codificada. Entonces vemos que las dos instrucciones usan 11 bytes. ¡Podemos hacerlo mejor! La otra revisión mencionó correctamente la xorinstrucción, así que intentémosla:
19 00000000 4D31C0 xor r8, r8
20 00000003 4831C9 xor rcx, rcx
Mejor, solo seis bytes. Podemos hacerlo mejor aún. Como se señaló correctamente en uno de los comentarios, en una máquina x86 de 64 bits, si se encuentra en xorla mitad inferior de un rXXregistro, también borra la mitad superior. Así que hagamos eso:
19 00000000 4D31C0 xor r8, r8
20 00000003 31C9 xor ecx, ecx
Eso ahorró un byte, pero no hay e8registro. ¿Podemos hacerlo mejor borrando ecxy luego copiando ese valor en r8?
14 00000000 31C9 xor ecx, ecx
20 00000002 4989C8 mov r8, rcx
No, no podemos, a menos que también sigamos los consejos anteriores y usemos en rsilugar de r8:
19 00000000 31C9 xor ecx, ecx
20 00000002 31F6 xor esi, esi
Ahora tenemos cuatro bytes y ya no necesitamos la mov rsi, r8instrucción que nos ahorra otros 3 bytes, para un ahorro neto de 10 bytes con solo esas dos cosas.
Evitar divsi es práctico
La divinstrucción es una de las más lentas en la arquitectura x86_64 y también puede causar una excepción si tratamos de dividir por cero. Por ambas razones, a menudo es mejor evitar la instrucción si podemos. En este caso, una forma de evitarlo es observar que se parece mucho fizzbuzzy mantener dos contadores: uno que cuenta hacia atrás desde 5 y el otro que cuenta hacia atrás desde 3.
Use etiquetas locales donde sea práctico
Está claro que maindebe ser un símbolo global de archivo, pero for0y if01(ambos nombres deficientes, como ya se ha señalado) no es necesario. En NASM, podemos designar etiquetas locales prefijando esas etiquetas con un solo punto para que en lugar de for0nosotros podamos usar .for0. La ventaja de hacer esto es que podemos reutilizar una etiqueta en otra función sin tener que preocuparnos por la colisión.
Evite los saltos incondicionales donde sea práctico
El procesador x86 hace todo lo posible para averiguar qué instrucción se ejecutará a continuación. Tiene todo tipo de cosas para que eso suceda, incluido el almacenamiento en caché de varios niveles y la predicción de ramas. Lo hace para intentar que el software se ejecute más rápido. Puede ayudarlo evitando ramificarse donde sea práctico, y especialmente evitando saltos incondicionales. Pensándolo bien, a menudo podemos hacer esto reestructurando el código. Aquí está el código original:
test rdx, rdx
jne if01
; sum = sum + i
add rsi, rcx
jmp if0
if01:
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne if0
; sum = sum + i
add rsi, rcx
jmp if0
; }
if0:
inc rcx
cmp rcx, 1000
jl for0
Podemos reescribir esto así:
test rdx, rdx
je .accumulate
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne .next
.accumulate:
; sum = sum + i
add rsi, rcx
; }
.next:
inc rcx
cmp rcx, 1000
jl .for0
if01yif0no son los nombres más grandes.En lugar de recargar
r9, use dos registros. Dejer9siempre contienen 3, yr10siempre contienen 5.Incremento
r8en un solo lugar.Ejecutar el bucle hacia abajo (1000 a 0), en lugar de hacia arriba, ahorra una instrucción (
cmp).mov rdx, 0está codificado en 7 bytes.xor rdx, rdxes mucho más corto.
Todo lo dicho, considera
main:
mov r8, 0
mov r9, 3
mov r10, 5
; for i in (1000, 0]
mov rcx, 999
for0:
mov rax, rcx
xor rdx, rdx
div r9
test rdx, rdx
jeq accumulate
mov rax, rcx
xor rdx, rdx
div r10
test rdx, rdx
jne next
accumulate:
add r8, rcx
next:
dec rcx
jne for0
PD: Espero que sepas que este problema tiene una solución aritmética muy sencilla.
Algunas notas rápidas sobre sus opciones de implementación y cómo las abordaría:
No necesita un tamaño de operando de 64 bits para divcuando sus números solo suben a 1000, eso es significativamente más lento que div r32en Intel antes de Ice Lake: expliqué los detalles en otra Revisión de código: Verificar si un número es primo en NASM Win64 Assembly .
(Y, en general, para otras instrucciones, test edx, edxguardaría el tamaño del código allí. Incluso con números de 64 bits y 64 bits div, i % 5siempre caben en 32 bits, por lo que es seguro ignorar los 32 altos. Consulte las ventajas de usar registros / instrucciones de 32 bits en x86-64 : es el tamaño de operando predeterminado para x86-64, no necesita prefijos de código de máquina. Para mayor eficiencia, úselo a menos que realmente necesite un tamaño de operando de 64 bits para esa instrucción específica y una extensión cero implícita a 64 -bit no hará lo que necesita. Sin embargo, no gaste instrucciones adicionales; a menudo se necesita un tamaño de operando de 64 bits, por ejemplo, para incrementos de puntero).
Por supuesto, para la división por constantes de tiempo de compilación, dives una opción lenta que los compiladores evitan por completo, en lugar de utilizar un inverso multiplicativo de punto fijo. Como en ¿Por qué GCC usa la multiplicación por un número extraño al implementar la división de enteros? en SO, o esta revisión de código .
Además, no necesita dividir en absoluto si usa contadores regresivos que restablece a 3 o 5 cuando llegan a 0 (y / o se desenrollan) para manejar el patrón 3, 5, como FizzBuzz: vea esta respuesta de Stack Overflow donde escribí un gran tutorial sobre tales técnicas, que no repetiré aquí. A diferencia de FizzBuzz, solo desea contar un número una vez, incluso si es un múltiplo de 3 y 5.
Podrías simplemente desenrollar por 15 (para que el patrón se repita completamente) y codificar algo como
.unroll15_loop:
; lets say ECX=60 for example
add eax, ecx ; += 60
lea eax, [rax + rcx + 3] ; += 63
lea eax, [rax + rcx + 5] ; += 65
lea eax, [rax + rcx + 6] ; += 66
...
add ecx, 15
cmp ecx, 1000-15
jbe .unroll15_loop
; handle the last not full group of 15 numbers
O aplique algo de matemáticas y en lugar de mirar cada número, use una fórmula de forma cerrada para la suma de los múltiplos de 3 y 5 en un rango de 15 números, compensado por i * nmulsdónde ies el inicio de su rango y nmulses el número de múltiplos.
por ejemplo, en el [60, 75)rango, tenemos 60, 63, 65, 66, 69, 70, 72. Así que son 8 de los 15 números. Entonces es como [0, 15)pero + 8*60. O haga la parte 0..14 a mano o con un bucle y recuerde el resultado. (El Proyecto Euler trata tanto de matemáticas como de programación; depende de usted cuántas matemáticas desea hacer frente a cuánta fuerza bruta desea que haga su programa).
Convenientemente, 8 resulta ser uno de los factores de escala que admiten los modos de direccionamiento x86, por lo que incluso podemos hacerlo
lea eax, [rax + rcx*8 + 0 + 3 + 5 + 6 + 9 + 10 + 12]
(3 + 5 + 6 + ... es una expresión constante para que el ensamblador pueda hacerlo por usted en el momento del ensamblaje, produciendo un [reg + reg*scale + disp8]modo de direccionamiento. Desafortunadamente, LEA de 3 componentes tiene una latencia de 3 ciclos en las CPU de Intel, y ese bucle- La dependencia llevada será el cuello de botella para el bucle. Por lo tanto, sería más eficiente usar una addinstrucción separada ).
Y, por supuesto, hemos reducido esto a básicamente una suma de una serie linealmente creciente, y podríamos aplicar la fórmula de Gauss ( n * (n+1) / 2) para una forma cerrada en todo el rango de intervalo, solo teniendo que manejar la limpieza de n%15los números que se acercan n. Por cierto, clang sabe cómo convertir un bucle for simple sum += i;en la forma cerrada, organizándolo para evitar el desbordamiento del temporal antes de dividirlo por 2. (desplazamiento a la derecha). Charla CppCon2017 de Matt Godbolt “¿Qué ha hecho mi compilador últimamente por mí? Desatornillar la tapa del compilador ”lo usa como ejemplo. Ver tambiénhttps://stackoverflow.com/questions/38552116/how-to-remove-noise-from-gcc-clang-assembly-output
Use instrucciones de movimiento condicional cuando sea apropiado
Para extender la discusión en la respuesta de @Edward : si puede usar instrucciones de movimiento condicional, eso reducirá aún más la cantidad de ramificaciones y, por lo tanto, ayudará al procesador.
Si se combina con la sugerencia de mantener los contadores de módulo 3 y módulo 5 en lugar de hacer una división, entonces un esquema del cuerpo del bucle principal podría verse así (aunque no probado):
%define mod3_reg r8
%define mod5_reg r9
%define zero_reg r10
%define count_reg rcx
%define accum_reg rsi
%define addend_reg rdi
%define limit 1000
...
mainloop:
xor addend_reg, addend_reg
inc mod3_reg
cmp mod3_reg, 3
cmove addend_reg, count_reg
cmove mod3_reg, zero_reg
inc mod5_reg
cmp mod5_reg, 5
cmove addend_reg, count_reg
cmove mod5_reg, zero_reg
add accum_reg, addend_reg
inc count_reg
cmp count_reg, limit
jl mainloop
(Tenga en cuenta que para hacer coincidir un valor inicial de 0 para el contador, necesitaría inicializar mod3_rega 2 y mod5_rega 4. Si ajusta para comenzar con 1, por otro lado, podría inicializar ambos a 0, lo que sería un un poco más simple.)
También tenga en cuenta que, de acuerdo con algunos comentarios de @PeterCordes, puede haber problemas con la cmovcreación de suficientes dependencias adicionales en el ciclo que podría no valer la pena. Este sería un caso en el que, si se preocupara mucho por el rendimiento, sería importante ejecutar un punto de referencia en su máquina de destino.