内联比递归定义如何有效？

Question

我的《编程范例》教科书，《编程语言基础》（第3版）第1章有一个练习：

练习1.12

通过用subst-in-s-exp的定义代替它的定义并简化生成的过程，消除对subst-in-s-exp的一次调用。结果将是不需要subst-in-s-exp的subst版本。这项技术称为内联，用于优化编译器。

原始代码将具有两个功能：subst并且subst-in-sexp基本上将输入符号中所有出现的旧符号替换为新符号。

(define subst
  (lambda (new old slist)
    (if (null? slist) '()
        (cons
         (subst-in-s-exp new old (car slist))
         (subst new old (cdr slist))))))

(define subst-in-s-exp
  (lambda (new old sexp)
    (if (symbol? sexp)
        (if (eqv? sexp old) new sexp)
        (subst new old sexp))))

这个问题的答案是消除subst-in-sexp，这就是

(define subst
  (lambda (slist old new)
    (cond
      [ (null? slist) '()]
      [ (eqv? (car slist) old) (cons new (subst (cdr slist) old new))]
      [ else (cons (car slist) (subst (cdr slist) old new))])))

为什么除了更短（更少的空间）外，内联更好？递归的大小是否改变？换句话说，这种内联会创建更少的堆栈元素吗？

此外，如何使用这个想法来使我的C ++，Python和Java代码更快？我可以轻松扩展这个想法吗？谢谢。

我在Scheme（实际上是Racket）中对此进行了标记，因为这是本书中使用的语言。

Answer 1

内联是相当标准的编译器优化，但是正如AoeAoe所说，通常最好编写代码以使其可读并让编译器为您完成所有内联。

内联的直接好处是它消除了代码中的分支。这意味着您的CPU可以继续直接阅读代码，而不必花费几个时钟周期来查找要执行的下一部分代码。

但是，内联还有其他好处。您最终将获得更大的代码块，这意味着编译器需要处理更多的代码和数据。它可能能够将更多内容粘贴到寄存器中，或者进行连续折叠以消除更多计算。编译器还可以更好地执行指令调度，因为它有更多的指令可以移动。

缺点是内联会增加您生成的代码大小。尤其是在现代CPU运行速度比内存快得多的情况下，内联较少的代码通常会更好，以便将所有热部分代码保留在L1缓存中。