tag: jvm,stack,stack frame,栈,栈帧
原文：JVM Stacks and Stack Frames
前情提要
对于没有深度递归的函数来说，无需担心上篇文章中的算法。当知道正在处理数据集有限时，我会使用这种简单的基本递归形式。由于你并不知道在应用程序中会处理多少数据，因此确保你的递归算法是尾递归(tail-recursive)就变得十分重要，否则你将可能遇到讨厌的 StackOverflowError.
举个例子，如果你用一个较大的list来运行上文中的sum函数，将出现 StackOverflowError，这与我们开发出稳定、出色的函数式程序相悖。
object RecursiveSum extends App {
def sum(list: List[Int]): Int = list match {
case Nil => 0
case x :: xs => x + sum(xs)
}
val list = List.range(1, 10000) // MUCH MORE DATA
val x = sum(list)
println(x)
}
具体到底需要多少数字才能引发 StackOverflowError，这取决于JVM的设置。Java默认的Stack大小是1024kb，这是非常小的内存。
关于尾递归，下篇文章我会继续讲解，本文我想讨论下JVM Stack 和 Stack frames。如果你不熟悉这些概念，本文有助于你理解，同时有益于debug stack trace。
什么是 Stack ?
为了理解递归算法中可能发生的 "stack overflow"问题，你需知晓写的递归算法到底发生了什么。
首先需要知晓的是：所有计算机语言都有 "栈" 这个概念，也称之为 "调用栈"。
Java/JVM中栈的官方定义
Oracle关于栈和栈帧提供了如下描述：
每个JVM线程拥有一个私有的 Java虚拟机栈，创建线程的同时栈也被创建。一个JVM栈由许多帧组成，称之为"栈帧"。JVM中的栈和C等常见语言中的栈比较类似，都用于保存局部变量和部分计算结果，同时也参与方法调用和返回。
因此，你可以想象一下，一个栈拥有许多栈帧，如下图：
如Oracle官方说明，每个线程拥有自己的私有栈，因此在多线程应用中将有多个栈，每个栈有自己的栈帧。
Java中的栈
为了更好的解释栈，下面所有的引用都都来自一个免费的在线电子书，由 Bill Venners 撰写的 《Inside the Java Virtual Machine》
当一个新的线程创建时，JVM会为这个线程创建一个新的Stack。一个Java Stack在一个个独立的栈帧中存储了线程的状态。JVM只会在Java Stack中做两个操作：push 和 pop.
一个线程当前正在执行的方法称之为线程的 当前方法，当前方法对应的栈帧称为 当前帧，当前方法所属的类称为 当前类，当前类的常量池称为 当前常量池。 在执行一个方法时，JVM会保存当前类和当前常量池的轨迹。当JVM执行 需要操作栈帧中数据的指令时，JVM会在当前栈帧进行处理。
当一个线程执行一个Java方法时，JVM将创建一个新的栈帧并且把它push到栈顶。此时新的栈帧就变成了当前栈帧，方法执行时，使用栈帧来存储参数、局部变量、中间指令以及其他数据。
什么是栈帧？
Bill Venners 书中所言：
栈帧由三部分组成：局部变量表、操作数栈以及帧数据。
书中还有：
每个方法涉及的局部变量表和操作数栈的大小取决于每个具体的方法，但是大小在编译后便已确定，而且已经包含在class文件中。
重要的是：栈帧的大小因局部变量表和操作数栈而异。书中对于size的描述如下：
当JVM执行一个方法时，它会检查class中的数据，以便确定一个方法执行时在局部变量表和操作数栈中所需存储的word size。然后，JVM会为当前方法创建一个size相对应的栈帧，然后把它push到栈顶。
Word size、操作数栈和常量池
简述下 word size、operand stack(操作数栈)、constant pool(常量池)这三个短语的定义：
- word size：它是一个度量单位，在不同类型的JVM中，word size的大小不一定会相同。但是，它至少会有32位以保证可以存储long或double类型。
- operand stack：操作数栈在 oracle.com 中被定义。捎带提一嘴，其中的定义涉及到了机器代码，例如：它展示了使用iadd指令进行两个integer的加法操作。 欢迎你深入学习这些细节，但是我们这里只想让你简单知道：操作数栈只是栈帧中的一块内存区域。
- 常量池：Java运行时常量时在 oracle.com 中定义. 写道：一个运行时常量池 ... 包含了许多种常量，编译时的常见数值字面量、运行时需要处理的方法和字段引用等. 运行时常量池和一些编程语言中的符号表有点类似，只不过它比符号表存储的数据范围更广。
小结
关于栈和栈帧，我们做个小结：
- 每个JVM线程有一个私有栈，栈在线程创建的同时被创建。
- 栈由许多帧组成，也叫 "栈帧"
- 每次方法调用都会创建一个栈帧
换句话说，当一个Java/Scala/JVM方法被执行时：
- 当方法被执行时，一个新的栈帧被创建并用来给这个方法存储数据
- 栈帧大小各不相同，取决于方法的参数、局部变量和算法
- 当一个方法被执行时，程序只能访问当前栈帧中的数据，你能看到的只有栈顶的帧
最后一个关于栈和递归的资源
最后我想分享下 Sedgewick 和 Wayne 《Algorithms》 书中的一个讨论：
上面有两行关于递归的非常重要的信息：
- 当方法调用return时，数据将从stack中pop出来，这样程序才能恢复到调用者处继续执行。
- 递归算法有时会产生非常深的调用从而耗尽栈的空间
分析
上述讨论都是为了希望你看到递归算法可能产生的潜在问题：
- 当一个方法递归调用自己时，新的方法所产生的数据(也可以理解为新的栈帧)将会被push到栈顶
- 方法每次调用自己时，会拷贝一份当前方法的数据并push到栈中。因此，递归的每层调用都需要创建一个新的栈帧
- 这样的结果是，栈中越来越多的内存将随着递归调用而被消耗，如果递归调用自己一百万次，那么将会产生一百万个栈帧
