Bienvenido a nuestro espacio, en este lugar vas a encontrar la resolución de lo que necesitas.
relacionado: Code-golf imprime los primeros 1000 dígitos de Fib (10 ** 9): mi respuesta asm x86 usando una precisión extendida adc bucle y convertir binario en cadenas. El bucle interior está optimizado para la velocidad, otras partes para el tamaño.
Calcular una secuencia de Fibonacci solo requiere mantener dos partes de estado: el elemento actual y el anterior. No tengo idea de lo que intentas hacer con fibInitial, aparte de contar su longitud. Esto no es perl donde lo haces for $n (0..5).
Sé que estás aprendiendo algo, pero todavía voy a hablar sobre el rendimiento. No hay muchas razones para aprender asm sin saber qué es rápido y qué no. Si no necesita rendimiento, deje que un compilador lo haga por usted, a partir de fuentes C. Consulte también los otros enlaces en https://stackoverflow.com/tags/x86/info
El uso de registros para su estado simplifica el problema de tener que mirar a[-1] mientras calcula a[1]. Empiezas con curr=1, prev=0y empezar con a[0] = curr. Para producir la secuencia “moderna” que comienza con cero de números de Fibonacci, comience con curr=0, prev=1.
Por suerte para ti, recientemente estaba pensando en un bucle eficiente para el código de Fibonacci, así que me tomé el tiempo para escribir una función completa. Vea a continuación una versión desenrollada y vectorizada (guarda las instrucciones de la tienda, pero también hace que las entradas de 64 bits sean rápidas incluso cuando se compila para una CPU de 32 bits):
; fib.asm
;void fib(int32_t *dest, uint32_t count);
; not-unrolled version. See below for a version which avoids all the mov instructions
global fib
fib:
; 64bit SysV register-call ABI:
; args: rdi: output buffer pointer. esi: count (and you can assume the upper32 are zeroed, so using rsi is safe)
;; locals: rsi: endp
;; eax: current edx: prev
;; ecx: tmp
;; all of these are caller-saved in the SysV ABI, like r8-r11
;; so we can use them without push/pop to save/restore them.
;; The Windows ABI is different.
test esi, esi ; test a reg against itself instead of cmp esi, 0
jz .early_out ; count == 0.
mov eax, 1 ; current = 1
xor edx, edx ; prev = 0
lea rsi, [rdi + rsi * 4] ; endp = &out[count]; // loop-end pointer
;; lea is very useful for combining add, shift, and non-destructive operation
;; this is equivalent to shl rsi, 4 / add rsi, rdi
align 16
.loop: ; do
mov [rdi], eax ; *buf = current
add rdi, 4 ; buf++
lea ecx, [rax + rdx] ; tmp = curr+prev = next_cur
mov edx, eax ; prev = curr
mov eax, ecx ; curr=tmp
;; see below for an unrolled version that doesn't need any reg->reg mov instructions
; you might think this would be faster:
; add edx, eax ; but it isn't
; xchg eax, edx ; This is as slow as 3 mov instructions, but we only needed 2 thanks to using lea
cmp rdi, rsi ; while(buf < endp);
jb .loop ; jump if (rdi BELOW rsi). unsigned compare
;; the LOOP instruction is very slow, avoid it
.early_out:
ret
Una condición de bucle alternativo podría ser
dec esi ; often you'd use ecx for counts, but we had it in esi
jnz .loop
Las CPU AMD pueden fusionar cmp / branch, pero no dec / branch. Las CPU Intel también pueden macro-fusible dec/jnz. (O con signo menor que cero / mayor que cero). dec/inc no actualice la bandera Carry, por lo que no puede usarlos con arriba / abajo sin firmar ja/jb. Creo que la idea es que puedas hacer una adc (agregar con acarreo) en un bucle, usando inc/dec para que el contador de bucle no perturbe la bandera de acarreo, pero las ralentizaciones de las banderas parciales hacen que esto sea malo en las CPU modernas.
lea ecx, [eax + edx] necesita un byte extra (tamaño de la dirección prefix), por lo que utilicé un destino de 32 bits y una dirección de 64 bits. (Estos son los tamaños de operandos predeterminados para lea en modo de 64 bits). Sin impacto directo en la velocidad, solo indirecto a través del tamaño del código.
Un cuerpo de bucle alternativo podría ser:
mov ecx, eax ; tmp=curr. This stays true after every iteration
.loop:
mov [rdi], ecx
add ecx, edx ; tmp+=prev ;; shorter encoding than lea
mov edx, eax ; prev=curr
mov eax, ecx ; curr=tmp
Desenrollar el bucle para hacer más iteraciones significaría menos barajado. En lugar de mov instrucciones, solo tiene que hacer un seguimiento de qué registro contiene qué variable. es decir, maneja las asignaciones con una especie de cambio de nombre de registros.
.loop: ;; on entry: ; curr:eax prev:edx
mov [rdi], eax ; store curr
add edx, eax ; curr:edx prev:eax
.oddentry:
mov [rdi + 4], edx ; store curr
add eax, edx ; curr:eax prev:edx
;; we're back to our starting state, so we can loop
add rdi, 8
cmp rdi, rsi
jb .loop
Lo que pasa con el desenrollado es que necesitas limpiar las iteraciones extrañas que quedan. Los factores de desenrollado del poder de dos pueden hacer que el ciclo de limpieza sea un poco más fácil, pero agregar 12 no es más rápido que agregar 16. (Consulte la revisión anterior de esta publicación para obtener una versión tonta de desenrollar por 3 utilizando lea para producir curr + prev en un tercer registro, porque no me di cuenta de que en realidad no necesitas un temp. Gracias a rcgldr por captar eso).
Consulte a continuación para obtener una versión completa sin enrollar que maneja cualquier recuento.
Probar frontend (nuevo en esta versión: un elemento canary para detectar errores de ASM escribiendo más allá del final del búfer).
// fib-main.c
#include
#include
#include
void fib(uint32_t *buf, uint32_t count);
int main(int argc, const char *argv[])
uint32_t count = 15;
if (argc > 1)
count = atoi(argv[1]);
uint32_t buf[count+1]; // allocated on the stack
// Fib overflows uint32 at count = 48, so it's not like a lot of space is useful
buf[count] = 0xdeadbeefUL;
// uint32_t count = sizeof(buf)/sizeof(buf[0]);
fib(buf, count);
for (uint32_t i ; i < count ; i++)
printf("%u ", buf[i]);
putchar('n');
if (buf[count] != 0xdeadbeefUL)
printf("fib wrote past the end of buf: sentinel = %xn", buf[count]);
Este código está completamente funcionando y probado (a menos que me perdí de copiar un cambio en mi archivo local nuevamente en la respuesta>. <):
[email protected]:~/src/SO$ yasm -f elf64 fib.asm && gcc -std=gnu11 -g -Og fib-main.c fib.o
[email protected]:~/src/SO$ ./a.out 48
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 512559680
versión desenrollada
Gracias de nuevo a rcgldr por hacerme pensar en cómo manejar el recuento de pares e impares en la configuración del ciclo, en lugar de con una iteración de limpieza al final.
Fui por el código de configuración sin ramas, que agrega 4 * count% 2 al puntero de inicio. Eso puede ser cero, pero agregar cero es más barato que ramificar para ver si debemos o no. La secuencia de Fibonacci desborda un registro muy rápidamente, por lo que mantener el código del prólogo ajustado y eficiente es importante, no solo el código dentro del ciclo. (Si estamos optimizando, querríamos optimizar para muchas llamadas de corta duración).
; 64bit SysV register-call ABI
; args: rdi: output buffer pointer. rsi: count
;; locals: rsi: endp
;; eax: current edx: prev
;; ecx: tmp
;; all of these are caller-saved in the SysV ABI, like r8-r11
;; so we can use them without push/pop to save/restore them.
;; The Windows ABI is different.
;void fib(int32_t *dest, uint32_t count); // unrolled version
global fib
fib:
cmp esi, 1
jb .early_out ; count below 1 (i.e. count==0, since it's unsigned)
mov eax, 1 ; current = 1
mov [rdi], eax
je .early_out ; count == 1, flags still set from cmp
;; need this 2nd early-out because the loop always does 2 iterations
;;; branchless handling of odd counts:
;;; always do buf[0]=1, then start the loop from 0 or 1
;;; Writing to an address you just wrote to is very cheap
;;; mov/lea is about as cheap as best-case for branching (correctly-predicted test/jcc for count%2==0)
;;; and saves probably one unconditional jump that would be needed either in the odd or even branch
mov edx, esi ;; we could save this mov by using esi for prev, and loading the end pointer into a different reg
and edx, eax ; prev = count & 1 = count%2
lea rsi, [rdi + rsi*4] ; end pointer: same regardless of starting at 0 or 1
lea rdi, [rdi + rdx*4] ; buf += count%2
;; even count: loop starts at buf[0], with curr=1, prev=0
;; odd count: loop starts at buf[1], with curr=1, prev=1
align 16 ;; the rest of this func is just *slightly* longer than 16B, so there's a lot of padding. Tempting to omit this alignment for CPUs with a loop buffer.
.loop: ;; do
mov [rdi], eax ;; *buf = current
; on loop entry: curr:eax prev:edx
add edx, eax ; curr:edx prev:eax
;.oddentry: ; unused, we used a branchless sequence to handle odd counts
mov [rdi+4], edx
add eax, edx ; curr:eax prev:edx
;; back to our starting arrangement
add rdi, 8 ;; buf++
cmp rdi, rsi ;; while(buf < endp);
jb .loop
; dec esi ; set up for this version with sub esi, edx; instead of lea
; jnz .loop
.early_out:
ret
Para producir la secuencia que comienza con cero, haga
curr=count&1; // and esi, 1
buf += curr; // lea [rdi], [rdi + rsi*4]
prev= 1 ^ curr; // xor eax, esi
en lugar de la corriente
curr = 1;
prev = count & 1;
buf += count & 1;
También podemos salvar un mov instrucción en ambas versiones usando esi sostener prev, ahora eso prev depende de count.
;; loop prologue for sequence starting with 1 1 2 3
;; (using different regs and optimized for size by using fewer immediates)
mov eax, 1 ; current = 1
cmp esi, eax
jb .early_out ; count below 1
mov [rdi], eax
je .early_out ; count == 1, flags still set from cmp
lea rdx, [rdi + rsi*4] ; endp
and esi, eax ; prev = count & 1
lea rdi, [rdi + rsi*4] ; buf += count & 1
;; eax:curr esi:prev rdx:endp rdi:buf
;; end of old code
;; loop prologue for sequence starting with 0 1 1 2
cmp esi, 1
jb .early_out ; count below 1, no stores
mov [rdi], 0 ; store first element
je .early_out ; count == 1, flags still set from cmp
lea rdx, [rdi + rsi*4] ; endp
mov eax, 1 ; prev = 1
and esi, eax ; curr = count&1
lea rdi, [rdi + rsi*4] ; buf += count&1
xor eax, esi ; prev = 1^curr
;; ESI:curr EAX:prev (opposite of other setup)
;;
;; optimized for code size, NOT speed. Prob. could be smaller, esp. if we want to keep the loop start aligned, and jump between before and after it.
;; most of the savings are from avoiding mov reg, imm32,
;; and from counting down the loop counter, instead of checking an end-pointer.
;; loop prologue for sequence starting with 0 1 1 2
xor edx, edx
cmp esi, 1
jb .early_out ; count below 1, no stores
mov [rdi], edx ; store first element
je .early_out ; count == 1, flags still set from cmp
xor eax, eax ; movzx after setcc would be faster, but one more byte
shr esi, 1 ; two counts per iteration, divide by two
;; shift sets CF = the last bit shifted out
setc al ; curr = count&1
setnc dl ; prev = !(count&1)
lea rdi, [rdi + rax*4] ; buf+= count&1
;; extra uop or partial register stall internally when reading eax after writing al, on Intel (except P4 & silvermont)
;; EAX:curr EDX:prev (same as 1 1 2 setup)
;; even count: loop starts at buf[0], with curr=0, prev=1
;; odd count: loop starts at buf[1], with curr=1, prev=0
.loop:
...
dec esi ; 1B smaller than 64b cmp, needs count/2 in esi
jnz .loop
.early_out:
ret
vectorizado:
La secuencia de Fibonacci no es particularmente paralelizable. No hay una forma sencilla de obtener F (i + 4) de F (i) y F (i-4), ni nada por el estilo. Lo que pueden hacer con los vectores es menos tiendas en la memoria. Empezar con:
a = [f3 f2 f1 f0 ] -> store this to buf
b = [f2 f1 f0 f-1]
Luego a+=b; b+=a; a+=b; b+=a; produce:
a = [f7 f6 f5 f4 ] -> store this to buf
b = [f6 f5 f4 f3 ]
Esto es menos tonto cuando se trabaja con dos entradas de 64 bits empaquetadas en un vector de 128b. Incluso en código de 32 bits, puede usar SSE para hacer cálculos matemáticos enteros de 64 bits.
Una versión anterior de esta respuesta tiene una versión de vector de 32 bits empaquetada sin terminar que no maneja adecuadamente count%4 != 0. Para cargar los primeros 4 valores de la secuencia, usé pmovzxbd así que no necesitaba 16B de datos cuando solo podía usar 4B. Obtener los primeros valores -1 .. 1 de la secuencia en registros vectoriales es mucho más fácil, porque solo hay un valor distinto de cero para cargar y barajar.
;void fib64_sse(uint64_t *dest, uint32_t count);
; using SSE for fewer but larger stores, and for 64bit integers even in 32bit mode
global fib64_sse
fib64_sse:
mov eax, 1
movd xmm1, eax ; xmm1 = [0 1] = [f0 f-1]
pshufd xmm0, xmm1, 11001111b ; xmm0 = [1 0] = [f1 f0]
sub esi, 2
jae .entry ; make the common case faster with fewer branches
;; could put the handling for count==0 and count==1 right here, with its own ret
jmp .cleanup
align 16
.loop: ; do
paddq xmm0, xmm1 ; xmm0 = [ f3 f2 ]
.entry:
;; xmm1: [ f0 f-1 ] ; on initial entry, count already decremented by 2
;; xmm0: [ f1 f0 ]
paddq xmm1, xmm0 ; xmm1 = [ f4 f3 ] (or [ f2 f1 ] on first iter)
movdqu [rdi], xmm0 ; store 2nd last compute result, ready for cleanup of odd count
add rdi, 16 ; buf += 2
sub esi, 2
jae .loop ; while((count-=2) >= 0);
.cleanup:
;; esi <= 0 : -2 on the count=0 special case, otherwise -1 or 0
;; xmm1: [ f_rc f_rc-1 ] ; rc = count Rounded down to even: count & ~1
;; xmm0: [ f_rc+1 f_rc ] ; f(rc+1) is the value we need to store if count was odd
cmp esi, -1
jne .out ; this could be a test on the Parity flag, with no extra cmp, if we wanted to be really hard to read and need a big comment explaining the logic
;; xmm1 = [f1 f0]
movhps [rdi], xmm1 ; store the high 64b of xmm0. There is no integer version of this insn, but that doesn't matter
.out:
ret
No tiene sentido desenrollar esto más, la latencia de la cadena de depuración limita el rendimiento, por lo que siempre podemos promediar el almacenamiento de un elemento por ciclo. Reducir la sobrecarga del bucle en uops puede ayudar para el hiperproceso, pero eso es bastante menor.
Como puede ver, manejar todos los casos de esquina incluso cuando se desenrolla por dos es bastante complejo de seguir. Requiere una sobrecarga de inicio adicional, incluso cuando intentas optimizarla para mantenerla al mínimo. Es fácil terminar con muchas ramas condicionales.
principal actualizado:
#include
#include
#include
#include
#ifdef USE32
void fib(uint32_t *buf, uint32_t count);
typedef uint32_t buftype_t;
#define FMTx PRIx32
#define FMTu PRIu32
#define FIB_FN fib
#define CANARY 0xdeadbeefUL
#else
void fib64_sse(uint64_t *buf, uint32_t count);
typedef uint64_t buftype_t;
#define FMTx PRIx64
#define FMTu PRIu64
#define FIB_FN fib64_sse
#define CANARY 0xdeadbeefdeadc0deULL
#endif
#define xstr(s) str(s)
#define str(s) #s
int main(int argc, const char *argv[])
uint32_t count = 15;
if (argc > 1)
count = atoi(argv[1]);
int benchmark = argc > 2;
buftype_t buf[count+1]; // allocated on the stack
// Fib overflows uint32 at count = 48, so it's not like a lot of space is useful
buf[count] = CANARY;
// uint32_t count = sizeof(buf)/sizeof(buf[0]);
if (benchmark)
int64_t reps = 1000000000 / count;
for (int i=0 ; i<=reps ; i++)
FIB_FN(buf, count);
else
FIB_FN(buf, count);
for (uint32_t i ; i < count ; i++)
printf("%" FMTu " ", buf[i]);
putchar('n');
if (buf[count] != CANARY)
printf(xstr(FIB_FN) " wrote past the end of buf: sentinel = %" FMTx "n", buf[count]);
Rendimiento
Para el recuento justo por debajo de 8192, la versión no vectorial desenrollada por dos se ejecuta cerca de su rendimiento máximo teórico de 1 tienda por ciclo (3.5 instrucciones por ciclo), en mi Sandybridge i5. 8192 * 4B / int = 32768 = tamaño de caché L1. En la práctica, veo ~ 3.3 a ~ 3.4 insn / ciclo. Estoy contando todo el programa con Linux. perf, sin embargo, no solo el bucle cerrado.
De todos modos, realmente no tiene sentido desenrollar más. Y obviamente esto dejó de ser una secuencia de Fibonacci después de count = 47, ya que usamos uint32_t. Sin embargo, para grandes count, el rendimiento está limitado por el ancho de banda de la memoria, hasta ~ 2.6 insn / ciclo. En este punto, básicamente estamos viendo cómo optimizar Memset.
La versión vectorial de 64 bits funciona a 3 insns por ciclo (una tienda de 128b por dos relojes) hasta un array tamaño de aproximadamente 1,5 veces el tamaño de la caché L2. (es decir ./fib64 49152). Como el array el tamaño aumenta a fracciones más grandes del tamaño de la caché L3, el rendimiento disminuye hasta ~ 2 insn por ciclo (una tienda por cada 3 relojes) a 3/4 del tamaño de la caché L3. Se nivela a 1 tienda por 6 ciclos en tamaños> caché L3.
Entonces, almacenar con vectores funciona mejor cuando encajamos en la caché L2 pero no en la caché L1.
valoraciones y reseñas
Te invitamos a añadir valor a nuestro contenido informacional añadiendo tu veteranía en las notas.