汇编语言 (x86)：如何创建一个循环来计算斐波那契数列
Assembly Language (x86): How to create a loop to calculate Fibonacci sequence
我正在使用 Visual Studio 2013 Ultimate 在 MASM 中编写汇编语言 (x86)。我正在尝试使用数组来计算使用数组的 n 个元素的斐波那契数列。换句话说，我试图转到一个数组元素，获取它之前的两个元素，将它们相加，然后将结果存储在另一个数组中。
我在设置变址寄存器时遇到了问题。
我的程序设置如下：
TITLE fibonacci.asm
INCLUDE Irvine32.inc
.data
fibInitial BYTE 0, 1, 2, 3, 4, 5, 6
fibComputed BYTE 5 DUP(0)
.code
main PROC
MOVZX si, fibInitial
MOVZX di, fibComputed
MOV cl, LENGTHOF fibInitial
L1:
MOV ax, [si - 1]
MOV dx, [si - 2]
MOV bp, ax + dx
MOV dl, TYPE fibInitial
MOVZX si, dl
MOV [edi], bp
MOV dh, TYPE fibComputed
MOVZX di, dl
loop L1
exit
main ENDP
END main
我无法编译它，因为 MOV ebp, ax + dx 行显示 "error A2031: must be index or base register" 的错误消息。但是，我确定我忽略了其他逻辑错误。
相关：Code-golf 使用扩展精度 adc 循环打印 Fib(10**9): my x86 asm answer 的前 1000 位数字，并将二进制转换为字符串。内部循环针对速度进行了优化，其他部分针对大小进行了优化。
计算一个 Fibonacci sequence 只需要保持两个状态：当前元素和前一个元素。除了计算它的长度外，我不知道你想用 fibInitial 做什么。这不是你做 for $n (0..5).
的 perl
我知道你根本只是在学习asm，但我还是要谈谈性能。没有太多理由学习 asm without knowing what's fast and what's not. If you don't need performance, let a compiler make the asm for you, from C sources. Also see the other links at https://whosebug.com/tags/x86/info
为您的状态使用寄存器简化了在计算 a[1] 时需要查看 a[-1] 的问题。您从 curr=1、prev=0 开始，然后从 a[0] = curr 开始。要生成 Fibonacci numbers 的“现代”从零开始的序列，请从 curr=0、prev=1、
开始
幸运的是，我最近正在考虑斐波那契代码的高效循环，所以我花时间写了一个完整的函数。请参阅下面的展开和矢量化版本（节省存储指令，但即使在编译 32 位 CPU 时也能使 64 位整数更快）：
; 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
另一个循环条件可以是
dec esi ; often you'd use ecx for counts, but we had it in esi
jnz .loop
AMD CPUs 可以融合 cmp/branch，但不能融合 dec/branch。英特尔 CPUs 也可以 dec/jnz. (Or signed less than zero / greater than zero). dec/inc don't update the Carry flag, so you can't use them with above/below unsigned ja/jb. I think the idea is that you could do an adc (add with carry) in a loop, using inc/dec for the loop counter to not disturb the carry flag, but .
lea ecx, [eax + edx] 需要一个额外的字节（地址大小前缀），这就是我使用 32 位目标和 64 位地址的原因。 （这些是 64 位模式下 lea 的默认操作数大小）。对速度没有直接影响，只是通过代码大小间接影响。
备用循环体可以是：
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
展开循环以进行更多迭代意味着更少的改组。而不是 mov 指令，您只需跟踪哪个寄存器保存哪个变量。也就是说，您使用一种寄存器重命名来处理分配。
.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
展开的问题是您需要清理遗留的任何奇怪的迭代。 2 的幂展开因子可以使清理循环稍微容易一些，但是添加 12 并不比添加 16 快。（请参阅此 post 的先前修订版，了解使用 lea 在第 3 个寄存器中生成 curr + prev，因为我没有意识到你实际上不需要临时文件。感谢 rcgldr 抓住了它。）
请参阅下面的完整工作展开版本，它可以处理任何计数。
测试前端（此版本中的新增功能：用于检测写入超过缓冲区末尾的 asm 错误的金丝雀元素。）
// fib-main.c
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
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 = %x\n", buf[count]);
}
}
此代码完全有效并经过测试（除非我错过了将本地文件中的更改复制回答案 >.<）：
peter@tesla:~/src/SO$ yasm -f elf64 fib.asm && gcc -std=gnu11 -g -Og fib-main.c fib.o
peter@tesla:~/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
展开版本
再次感谢 rcgldr 让我思考如何在循环设置中处理奇数与偶数，而不是在最后进行清理迭代。
我选择了无分支设置代码，它将 4 * count%2 添加到起始指针。这可以是零，但加零比分支看看我们是否应该更便宜。斐波那契数列很快就会溢出寄存器，因此保持序言代码紧凑和高效很重要，而不仅仅是循环内的代码。 （如果我们要进行优化，我们希望针对许多长度较短的调用进行优化）。
; 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
要生成从零开始的序列，请执行
curr=count&1; // and esi, 1
buf += curr; // lea [rdi], [rdi + rsi*4]
prev= 1 ^ curr; // xor eax, esi
代替现在的
curr = 1;
prev = count & 1;
buf += count & 1;
我们还可以在两个版本中通过使用esi来保存prev来保存mov指令，现在prev依赖于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
矢量化：
斐波那契数列不是特别可并行化的。没有从 F(i) 和 F(i-4) 或类似方法得到 F(i+4) 的简单方法。我们可以对向量做的是更少的内存存储。开始于：
a = [f3 f2 f1 f0 ] -> store this to buf
b = [f2 f1 f0 f-1]
然后 a+=b; b+=a; a+=b; b+=a; 产生：
a = [f7 f6 f5 f4 ] -> store this to buf
b = [f6 f5 f4 f3 ]
在将两个 64 位整数打包到一个 128b 向量中时，这就没那么傻了。即使在 32 位代码中，您也可以使用 SSE 进行 64 位整数数学运算。
此答案的先前版本有一个未完成的打包 32 位矢量版本，无法正确处理 count%4 != 0。为了加载序列的前 4 个值，我使用了 pmovzxbd 因此当我只能使用 4B 时我不需要 16B 的数据。将序列的第一个 -1 .. 1 值放入向量寄存器要容易得多，因为只有一个非零值可以加载和随机播放。
;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
没有必要进一步展开，dep 链延迟限制了吞吐量，因此我们始终可以平均每个周期存储一个元素。减少 uops 中的循环开销可以帮助超线程，但这非常小。
如您所见，处理所有极端情况即使是两个展开也非常复杂，难以跟踪。它需要额外的启动开销，即使您试图优化它以将其保持在最低限度。很容易得到很多条件分支。
更新主要内容：
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>
#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]);
}
}
性能
对于刚好低于 8192 的计数，在我的 Sandybridge i5 上，由两个展开的非矢量版本在其理论最大吞吐量附近运行，即每个周期 1 个存储（每个周期 3.5 条指令）。 8192 * 4B/int = 32768 = 一级缓存大小。实际上，我看到 ~3.3 到 ~3.4 insn/cycle。不过，我用 Linux perf 来计算整个程序，而不仅仅是紧密循环。
无论如何，进一步展开真的没有任何意义。很明显，在 count=47 之后这不再是斐波那契数列，因为我们使用 uint32_t。然而，对于大 count，吞吐量受内存带宽限制，低至 ~2.6 insn / cycle。在这一点上，我们基本上是在研究如何优化 memset。
64 位矢量版本以每个周期 3 个 insns（每两个时钟一个 128b 存储）运行，阵列大小约为 L2 缓存大小的 1.5 倍。 （即 ./fib64 49152）。随着阵列大小增加到 L3 缓存大小的较大部分，在 L3 缓存大小的 3/4 时，性能下降到每周期约 2 insn（每 3 个时钟存储一次）。它在大小 > L3 缓存时每 6 个周期稳定到 1 个存储。
因此，当我们适合 L2 而不是 L1 缓存时，使用向量存储效果更好。
考虑到 fib(93) = 12200160415121876738 是适合 64 位无符号整数的最大值，尝试优化它可能没有多大意义，除非计算 fib(n) 模数（通常是质数） ) 大 n 的数字。
有一种方法可以在 log2(n) 次迭代中直接计算 fib(n)，使用斐波那契的卢卡斯序列方法或矩阵方法。卢卡斯序列更快，如下所示。可以修改这些以执行对某个数字取模的数学运算。
/* lucas sequence method */
uint64_t fibl(int n) {
uint64_t a, b, p, q, qq, aq;
a = q = 1;
b = p = 0;
while(1){
if(n & 1) {
aq = a*q;
a = b*q + aq + a*p;
b = b*p + aq;
}
n >>= 1;
if(n == 0)
break;
qq = q*q;
q = 2*p*q + qq;
p = p*p + qq;
}
return b;
}
.386
.model flat, stdcall
.stack 4096
ExitProcess proto, dwExitCode:dword
.data
fib word 1, 1, 5 dup(?);you create an array with the number of the fibonacci series that you want to get
.code
main proc
mov esi, offset fib ;set the stack index to the offset of the array.Note that this can also be set to 0
mov cx, lengthof fib ;set the counter for the array to the length of the array. This keeps track of the number of times your loop will go
L1: ;start the loop
mov ax, [esi]; move the first element to ax ;move the first element in the array to the ax register
add ax, [esi + type fib]; add the second element to the value in ax. Which gives the next element in the series
mov[esi + 2* type fib], ax; assign the addition to the third value in the array, i.e the next number in the fibonacci series
add esi, type fib;increment the index to move to the next value
loop L1; repeat
invoke ExitProcess, 0
main endp
end main
我正在使用 Visual Studio 2013 Ultimate 在 MASM 中编写汇编语言 (x86)。我正在尝试使用数组来计算使用数组的 n 个元素的斐波那契数列。换句话说，我试图转到一个数组元素，获取它之前的两个元素，将它们相加，然后将结果存储在另一个数组中。
我在设置变址寄存器时遇到了问题。
我的程序设置如下：
TITLE fibonacci.asm
INCLUDE Irvine32.inc
.data
fibInitial BYTE 0, 1, 2, 3, 4, 5, 6
fibComputed BYTE 5 DUP(0)
.code
main PROC
MOVZX si, fibInitial
MOVZX di, fibComputed
MOV cl, LENGTHOF fibInitial
L1:
MOV ax, [si - 1]
MOV dx, [si - 2]
MOV bp, ax + dx
MOV dl, TYPE fibInitial
MOVZX si, dl
MOV [edi], bp
MOV dh, TYPE fibComputed
MOVZX di, dl
loop L1
exit
main ENDP
END main
我无法编译它，因为 MOV ebp, ax + dx 行显示 "error A2031: must be index or base register" 的错误消息。但是，我确定我忽略了其他逻辑错误。
相关：Code-golf 使用扩展精度 adc 循环打印 Fib(10**9): my x86 asm answer 的前 1000 位数字，并将二进制转换为字符串。内部循环针对速度进行了优化，其他部分针对大小进行了优化。
计算一个 Fibonacci sequence 只需要保持两个状态：当前元素和前一个元素。除了计算它的长度外，我不知道你想用 fibInitial 做什么。这不是你做 for $n (0..5).
我知道你根本只是在学习asm，但我还是要谈谈性能。没有太多理由学习 asm without knowing what's fast and what's not. If you don't need performance, let a compiler make the asm for you, from C sources. Also see the other links at https://whosebug.com/tags/x86/info
为您的状态使用寄存器简化了在计算 a[1] 时需要查看 a[-1] 的问题。您从 curr=1、prev=0 开始，然后从 a[0] = curr 开始。要生成 Fibonacci numbers 的“现代”从零开始的序列，请从 curr=0、prev=1、
幸运的是，我最近正在考虑斐波那契代码的高效循环，所以我花时间写了一个完整的函数。请参阅下面的展开和矢量化版本（节省存储指令，但即使在编译 32 位 CPU 时也能使 64 位整数更快）：
; 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
另一个循环条件可以是
dec esi ; often you'd use ecx for counts, but we had it in esi
jnz .loop
AMD CPUs 可以融合 cmp/branch，但不能融合 dec/branch。英特尔 CPUs 也可以 dec/jnz. (Or signed less than zero / greater than zero). dec/inc don't update the Carry flag, so you can't use them with above/below unsigned ja/jb. I think the idea is that you could do an adc (add with carry) in a loop, using inc/dec for the loop counter to not disturb the carry flag, but
lea ecx, [eax + edx] 需要一个额外的字节（地址大小前缀），这就是我使用 32 位目标和 64 位地址的原因。 （这些是 64 位模式下 lea 的默认操作数大小）。对速度没有直接影响，只是通过代码大小间接影响。
备用循环体可以是：
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
展开循环以进行更多迭代意味着更少的改组。而不是 mov 指令，您只需跟踪哪个寄存器保存哪个变量。也就是说，您使用一种寄存器重命名来处理分配。
.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
展开的问题是您需要清理遗留的任何奇怪的迭代。 2 的幂展开因子可以使清理循环稍微容易一些，但是添加 12 并不比添加 16 快。（请参阅此 post 的先前修订版，了解使用 lea 在第 3 个寄存器中生成 curr + prev，因为我没有意识到你实际上不需要临时文件。感谢 rcgldr 抓住了它。）
请参阅下面的完整工作展开版本，它可以处理任何计数。
测试前端（此版本中的新增功能：用于检测写入超过缓冲区末尾的 asm 错误的金丝雀元素。）
// fib-main.c
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
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 = %x\n", buf[count]);
}
}
此代码完全有效并经过测试（除非我错过了将本地文件中的更改复制回答案 >.<）：
peter@tesla:~/src/SO$ yasm -f elf64 fib.asm && gcc -std=gnu11 -g -Og fib-main.c fib.o
peter@tesla:~/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
展开版本
再次感谢 rcgldr 让我思考如何在循环设置中处理奇数与偶数，而不是在最后进行清理迭代。
我选择了无分支设置代码，它将 4 * count%2 添加到起始指针。这可以是零，但加零比分支看看我们是否应该更便宜。斐波那契数列很快就会溢出寄存器，因此保持序言代码紧凑和高效很重要，而不仅仅是循环内的代码。 （如果我们要进行优化，我们希望针对许多长度较短的调用进行优化）。
; 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
要生成从零开始的序列，请执行
curr=count&1; // and esi, 1
buf += curr; // lea [rdi], [rdi + rsi*4]
prev= 1 ^ curr; // xor eax, esi
代替现在的
curr = 1;
prev = count & 1;
buf += count & 1;
我们还可以在两个版本中通过使用esi来保存prev来保存mov指令，现在prev依赖于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
矢量化：
斐波那契数列不是特别可并行化的。没有从 F(i) 和 F(i-4) 或类似方法得到 F(i+4) 的简单方法。我们可以对向量做的是更少的内存存储。开始于：
a = [f3 f2 f1 f0 ] -> store this to buf
b = [f2 f1 f0 f-1]
然后 a+=b; b+=a; a+=b; b+=a; 产生：
a = [f7 f6 f5 f4 ] -> store this to buf
b = [f6 f5 f4 f3 ]
在将两个 64 位整数打包到一个 128b 向量中时，这就没那么傻了。即使在 32 位代码中，您也可以使用 SSE 进行 64 位整数数学运算。
此答案的先前版本有一个未完成的打包 32 位矢量版本，无法正确处理 count%4 != 0。为了加载序列的前 4 个值，我使用了 pmovzxbd 因此当我只能使用 4B 时我不需要 16B 的数据。将序列的第一个 -1 .. 1 值放入向量寄存器要容易得多，因为只有一个非零值可以加载和随机播放。
;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
没有必要进一步展开，dep 链延迟限制了吞吐量，因此我们始终可以平均每个周期存储一个元素。减少 uops 中的循环开销可以帮助超线程，但这非常小。
如您所见，处理所有极端情况即使是两个展开也非常复杂，难以跟踪。它需要额外的启动开销，即使您试图优化它以将其保持在最低限度。很容易得到很多条件分支。
更新主要内容：
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>
#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]);
}
}
性能
对于刚好低于 8192 的计数，在我的 Sandybridge i5 上，由两个展开的非矢量版本在其理论最大吞吐量附近运行，即每个周期 1 个存储（每个周期 3.5 条指令）。 8192 * 4B/int = 32768 = 一级缓存大小。实际上，我看到 ~3.3 到 ~3.4 insn/cycle。不过，我用 Linux perf 来计算整个程序，而不仅仅是紧密循环。
无论如何，进一步展开真的没有任何意义。很明显，在 count=47 之后这不再是斐波那契数列，因为我们使用 uint32_t。然而，对于大 count，吞吐量受内存带宽限制，低至 ~2.6 insn / cycle。在这一点上，我们基本上是在研究如何优化 memset。
64 位矢量版本以每个周期 3 个 insns（每两个时钟一个 128b 存储）运行，阵列大小约为 L2 缓存大小的 1.5 倍。 （即 ./fib64 49152）。随着阵列大小增加到 L3 缓存大小的较大部分，在 L3 缓存大小的 3/4 时，性能下降到每周期约 2 insn（每 3 个时钟存储一次）。它在大小 > L3 缓存时每 6 个周期稳定到 1 个存储。
因此，当我们适合 L2 而不是 L1 缓存时，使用向量存储效果更好。
考虑到 fib(93) = 12200160415121876738 是适合 64 位无符号整数的最大值，尝试优化它可能没有多大意义，除非计算 fib(n) 模数（通常是质数） ) 大 n 的数字。
有一种方法可以在 log2(n) 次迭代中直接计算 fib(n)，使用斐波那契的卢卡斯序列方法或矩阵方法。卢卡斯序列更快，如下所示。可以修改这些以执行对某个数字取模的数学运算。
/* lucas sequence method */
uint64_t fibl(int n) {
uint64_t a, b, p, q, qq, aq;
a = q = 1;
b = p = 0;
while(1){
if(n & 1) {
aq = a*q;
a = b*q + aq + a*p;
b = b*p + aq;
}
n >>= 1;
if(n == 0)
break;
qq = q*q;
q = 2*p*q + qq;
p = p*p + qq;
}
return b;
}
.386
.model flat, stdcall
.stack 4096
ExitProcess proto, dwExitCode:dword
.data
fib word 1, 1, 5 dup(?);you create an array with the number of the fibonacci series that you want to get
.code
main proc
mov esi, offset fib ;set the stack index to the offset of the array.Note that this can also be set to 0
mov cx, lengthof fib ;set the counter for the array to the length of the array. This keeps track of the number of times your loop will go
L1: ;start the loop
mov ax, [esi]; move the first element to ax ;move the first element in the array to the ax register
add ax, [esi + type fib]; add the second element to the value in ax. Which gives the next element in the series
mov[esi + 2* type fib], ax; assign the addition to the third value in the array, i.e the next number in the fibonacci series
add esi, type fib;increment the index to move to the next value
loop L1; repeat
invoke ExitProcess, 0
main endp
end main