根据上一篇文章的思路，我写了两段代码，放入了Compiler Explorer，使用O3编译，看编译后的机器码
我尽力了，本来想做并排代码块好对比，但奈何没有html基础，搞不出来，凑合看好了
源码
pub fn recurse_without_result(arr: &[u8], start: usize, end: usize) -> usize{
if end <= start { return 0; }
if arr[start] == arr[end]{
recurse_without_result(arr, start+1, end-1)
}
else{
std::cmp::min(
recurse_without_result(arr, start+1, end),
recurse_without_result(arr, start, end-1)
) + 1
}
}
pub fn recurse_with_result(arr: &[u8], start: usize, end: usize, ret: usize) -> usize{
if end <= start { return ret; }
if arr[start] == arr[end]{
recurse_with_result(arr, start+1, end-1, ret)
}
else{
std::cmp::min(
recurse_with_result(arr, start+1, end, ret + 1),
recurse_with_result(arr, start, end-1, ret + 1)
)
}
}
为了简化代码，这次的array没用Generic，而是直接用了u8，也就是byte array
recurse_without_result机器码分析
现在来逐行分析第一种，不带参数的机器码
第一段(base case 段)
对应if end <= start { return 0; }
example::recurse_without_result:
;Linux calling convention - 保存Callee Saved Registers
;将这些register全都放入stack中
pushq %rbp
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rbx
pushq %rax
;%rcx = end
;%rdx = start
;这里assembly可以理解成 if %rcx <= %rdx { goto .LBB0_1; } 对应源代码第一行
cmpq %rdx, %rcx
jbe .LBB0_1 ;跳到.LBB0_1, 会将%r14归零，然后返回%r14, 见下面代码块
;初始化要用的寄存器
movq %rcx, %rbx ;%rbx = end
;rust存储Slice是一个fat pointer，一个保存长度，一个保存首项指针
movq %rsi, %r15 ;%r15 = arr.len
movq %rdi, %r12 ;%r12 = &arr
xorl %r14d, %r14d ;%r14 = 0
movq %rdx, %r13 ;%r13 = start
上面跳转到的.LBB0_1
.LBB0_1:
xorl %r14d, %r14d ;%r14 = 0
jmp .LBB0_7 ;跳到.LBB0_7, 是函数返回的代码块，下面有解释，先不用管，理解成return 0就行
第二段(tail recursion段)
对应 if arr[start] == arr[end]{ return recurse_without_result(arr, start+1, end-1); }
.LBB0_3:
cmpq %r15, %r13
jae .LBB0_9
;if %r13 >= %r15 { goto .LBB0_9; } 这段实际上跳到了panic代码，是rust用来保护数组索引在其长度范围内(防止 Index Out Of Range Error)
;多提一嘴，rust里面可以用unsafe code优化掉这个bound checking
cmpq %r15, %rbx
jae .LBB0_10
;if %rbx > %r15 { goto .LBB0_10; } 也是跳到panic，跟上一个一样属于对于slice的bound checking，因为我们要访问这两个数组索引位置
movzbl (%r12,%r13), %ecx ;%ecx = arr[%r13]
leaq 1(%r13), %rax ;%rax = 1 + %r13
cmpb (%r12,%rbx), %cl ;%cl 跟 %ecx是同一个register，存的是相同的byte
jne .LBB0_6
;if %ecx != arr[%rbx] { goto .LBB0_6; } 下面可以看到，跳到了递归的代码
addq $-1, %rbx ;%rbx -= 1
movq %rax, %r13 ;%r13 = %rax
cmpq %rax, %rbx
ja .LBB0_3 ;if %rbx > %rax { goto .LBB0_3; }
jmp .LBB0_7 ;goto .LBB0_7 跳到函数返回代码，返回当前%r15中的值
可以看到，.LBB0_3实现的是一个while循环，条件是%rbx > %rax
%rbx每个循环-1，%rax每个循环+1，对应递归时的end和start
不难看出，这里编辑器将一个递归优化成了tail recursion，变成了一个循环，至于为什么这么作？记得最开始那段Linux Calling Convention吗，每次函数调用都会造成大量的寄存器存到stack中。而优化了尾递归后，stack自始至终没有变过，不产生额外空间消耗，更重要的是没有时间成本很高的从内存读取数据的操作
第三段(递归段)
对应else{ return std::cmp::min( recurse_without_result(arr, start+1, end-1), recurse_without_result(arr, start, end-1) ) + 1; }
.LBB0_6:
movq example::recurse_without_result@GOTPCREL(%rip), %rbp
;保存递归函数的pointer, 相当于C语言的函数指针，在编译最后动态链接的时候会转为这个函数代码开始的位置
;下面这4h行都是即将传入递归函数的参数，可以理解为传参的过程
movq %r12, %rdi ;%rdi = %r12 &arr
movq %r15, %rsi ;%rsi = %r15 arr.len
movq %rax, %rdx ;%rdx = %rax - %r13存了start的值，jump到.LBB0_6之前%rax = %r13 + 1, 所以这段对应start+1
movq %rbx, %rcx ;%rcx = %rbx
callq *%rbp
;进行递归，传入的参数是现在的%rsi, %rdi (rust Slice "arr"的信息，传多少次都不会变), 和当前的%rcx, %rdx, 分别对应end, start
;函数返回后，根据Linux calling convention, 返回值会放在%rax中，但因为下次递归%rax的值还会变，所以要先存一下
movq %rax, %r14 ;%r14 = %rax
;开始准备下一次递归的参数
movq %r12, %rdi ;%rdi = %r12 &arr
movq %r15, %rsi ;%rsi = %r15 arr.len
movq %r13, %rdx ;%rdx = %r13 - 这里存的是%13，即start的值
addq $-1, %rbx ;%rbx -= 1
movq %rbx, %rcx ;%rcx = %rbx - 对应end-1
callq *%rbp ;递归
cmpq %rax, %r14 ;比较第二次递归(%rax)和第一次递归(%r14)的返回值
cmovaq %rax, %r14 ;if %r14 > %rax { %r14 = %rax; }
;注意上面就是一个%r14 = min(%r14, %rax)函数
addq $1, %r14 ;%r14 += 1
可能有人有问题，%rsi和%rdi不是说永远不会变吗，那为什么还要每次递归都先暂时存到%r12和%r14中?
好问题，这个我认为是编译器没看出来，实际是能优化掉的。
第四段(返回值段)
.LBB0_7:
;如果是从base case部分跳过来的，那%r14是0，把0放入%rax作为返回值
;如果是尾递归部分(.LBB0_3)跳过来的
;如果是从上一段走下来的, 那%r14是两次递归的最小值+1
movq %r14, %rax
;一下就是恢复这个函数被call之前的寄存器和stack值
addq $8, %rsp ;最下面这8byte存的是在call这个函数之前%rax返回值，可以回去看第一段的代码验证
;至于最开始为什么存我暂时也不清楚，等之后再学学看看能不能回来解释明白
;所有callee saved registers全都被恢复
popq %rbx
popq %r12
popq %r13
popq %r14
popq %r15
popq %rbp
retq ;返回call这个函数的那行代码
第五段(Panic段)
这里的代码就是rust panic时将会显示出来的错误信息
可以看到.L__unnamed_*里面存了代码名称，以及一些错误信息
这段不需要了解太多，是rust独有的特性，不过可以大概猜一下，频繁的操作%r15相比是在处理错误信息中会显示的"数组长度是xxx, 访问了xxx"，毕竟到这里%r15是之前end的值
要记得，如果之前通过unsafe的手段优化掉了bound checking，这段代码会直接消失
所以，如果知道代码会被编译成什么样子，你可以极致的优化代码大小，这个代码可以减少足足27行(这段有23行，之前还有4行bounds checking)，也能因为CPU少运行了部分代码带来稍微一点点的性能提升(当然，性能提升相当小，不过想象一下如果你进行了很多次的数组访问，有时可能大部分的程序都在进行bounds checking)
C语言压根就没有bounds checking，所以直接写的代码就会很快
这也体现了rust的特性，rust可以很快，不过你必须了解它要想快你要付出的安全性上的代价
.LBB0_9:
cmpq %r15, %rdx
cmovbeq %r15, %rdx
leaq .L__unnamed_1(%rip), %rax
movq %rdx, %rdi
movq %r15, %rsi
movq %rax, %rdx
callq *core::panicking::panic_bounds_check@GOTPCREL(%rip)
ud2
.LBB0_10:
leaq .L__unnamed_2(%rip), %rdx
movq %rbx, %rdi
movq %r15, %rsi
callq *core::panicking::panic_bounds_check@GOTPCREL(%rip)
ud2
.L__unnamed_3:
.ascii "/app/example.rs"
.L__unnamed_1:
.quad .L__unnamed_3
.asciz "\017\000\000\000\000\000\000\000\003\000\000\000\b\000\000"
.L__unnamed_2:
.quad .L__unnamed_3
.asciz "\017\000\000\000\000\000\000\000\003\000\000\000\026\000\000"
举一反三 - Inline到底是什么
学代码初期可能会有的一个问题就是我如果只给一行代码写了子程序，那这个程序难道不会跳来跳去，同时在stack上面allocate一堆内存吗?
这时候，一般得到的回答都是"编译器会给他们Inline掉，相当于直接拷贝那行"
那么从这个汇编代码的解读过程，你应该能得到关于inline更深的理解
每次函数call都会导致寄存器register被存入stack中(寄存器的数量取决于你的函数的复杂度，函数用不上的register不会被存在stack中)，而inline就是直接在汇编中，将原来的代码整合进去
可以看到，我们的编译器尽一切可能去减少function call的数量，用尾递归把function call优化成循环，把min()函数用conditional move直接一行汇编解决
举一反四(再反一个) - 我为什么应该尽量用标准库
想象一下如果你想自己实现一个min(x,y)函数会怎么处理，我想应该是像下面这样
#[inline]
fn min<T: std::cmp::PartialOrd + Copy>(x: &T, y: &T) -> T{
if x > y { y.clone() } else { x.clone() } //注意这里的clone，C语言中直接传回指针比较容易，但rust中比较麻烦
//不过一般有Copy Trait的类型都比较小，比如integer，所以clone一个的代价跟pointer差不多
//对于size较大的类型，可以用pointer的版本，但这段代码仅供展示，就不做那么严谨了
}
那么直接使用标准库，在汇编中直接inline，可以节省拷贝的时间，也能给Compiler更多的优化空间
比如这篇文章的代码中，Compiler发现我们不会再使用较大的那个值，那就直接搞成了一行conditional move
很多的标准库函数都要比自己实现的来的更优化，所以学习一个语言的标准库对代码效率有很大的提升。
现在来看传值的递归
进行横向对比，在传值的递归中，最开始会多传一个参数，保存到%r14寄存器中
|
|
而%r14的用途跟不传值的递归是一样的，保存的是返回值
少了一段将%r14归0的代码，因为0是会在主程序中给出的
*没有这段代码能够减少一次代码的jump，但这个jump是jmp，强制跳转类型的，因此是predictable的，对性能根本没影响
甚至于尾递归那段都一模一样
不同的只有递归call那段
.LBB0_5:
addq $1, %r14 ;因为两个递归都要传ret+1，所以直接在这里加了
movq example::recurse_with_result@GOTPCREL(%rip), %rbp
;跟之前一样的传参
movq %r12, %rdi
movq %r15, %rsi
movq %rax, %rdx
movq %rbx, %rcx
movq %r14, %r8 ;ret被传到下一次递归
callq *%rbp ;递归
;下面这两行比较玄学，我也不清楚为什么这么做
movq %rbp, %r9 ;先把%rbp存的递归函数指针放到%r9
movq %rax, %rbp ;然后把上个函数返回值存进刚刚腾出来的%rbp
;下面5行又跟不传参的递归一样，处理下次递归的参数
addq $-1, %rbx
movq %r12, %rdi
movq %r15, %rsi
movq %r13, %rdx
movq %rbx, %rcx
movq %r14, %r8 ;多一个传ret的步骤
callq *%r9 ;递归
;取最小值
cmpq %rax, %rbp
cmovaq %rax, %rbp
movq %rbp, %r14
;后面接函数返回的代码
不忘初心 - 到底哪个好
时间上没什么区别，多出来和少的那几行代码根本不会造成什么影响，现在4GHz的处理器，10个tick的差异顶天了。
那么空间上会差多少？
答案：0
因为传递ret的空间是用的寄存器(%r8)，每次进行递归的时候，%r8会被暂存到%r14中， 而%r14本来在不传参的递归里面也是要存返回值的，因此可以看到两种方式，函数一开始都往stack上放了7个寄存器的值，使用空间7*8 = 56 bytes
那么占用Stack总空间都是 (递归深度-1) * 56 bytes
所以两种方法没有实质上的区别，至少在这篇文章的情景下没有。
总结
本文章比较了传参递归与不传参递归的差别，得出的结论是没有实质上的区别，几乎可以画上等号。
不过在实际编程过程中，并不是每个递归算法都能够选择去在递的过程中还是在归的过程中传返回值。比如有的回溯算法必须要带着参数递归下去。
因此不要拿本文作为比较的依据，此文章旨在让读者了解一些代码编译成汇编语言后的变化，以及一些常见的优化方式。
Appendix - 机器码源码
|
|
|
|