JVM 栈和栈帧

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等常见语言中的栈比较类似,都用于保存局部变量和部分计算结果,同时也参与方法调用和返回。

因此,你可以想象一下,一个栈拥有许多栈帧,如下图:

the stack

如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到栈中。因此,递归的每层调用都需要创建一个新的栈帧
  • 这样的结果是,栈中越来越多的内存将随着递归调用而被消耗,如果递归调用自己一百万次,那么将会产生一百万个栈帧

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏影子

jsp的C标签一般使用方法以及js接收servlet中的对象及对象数字

42180
来自专栏hbbliyong

一个小程序引发的思考

   既然是一个小程序引发的思考,那么我们就先看看这个小程序,看看他有何神奇之处: namespace ConsoleApplication1 { cl...

25340
来自专栏用户2442861的专栏

《Effective Modern C++》读书笔记

Note:为避免各种侵权问题,本文并没有复制原书任意文字(代码除外,作者已经声明代码可以被使用)。需要原书完整中文翻译的读者请等待官方译本的发布。

72320
来自专栏F_Alex

数据结构与算法(六)-背包、栈和队列

  前言:许多基础数据类型都和对象的集合有关。具体来说,数据类型的值就是一组对象的集合,所有操作都是关于添加、删除或是访问集合中的对象。而且有很多高级数据结构都...

14140
来自专栏企鹅号快讯

Python进阶系列连载(5)——生成器(上)

作者:王大伟 Python爱好者社区唯一小编 博客:https://ask.hellobi.com/blog/wangdawei 生成器 还记得在迭代器里我们...

403100
来自专栏刘望舒

设计模式(九)模版方法模式

1.模版方法模式简介 模版方法模式介绍 在软件开发中,有时会遇到类似的情况,某个方法的实现需要多个步骤,其中有些步骤是固定的,而有些步骤并不固定,存在可变性。为...

20760
来自专栏数据科学与人工智能

【Python环境】Python面试题汇总(一)

拿网络上关于Python的面试题汇总了,给出了自认为合理的答案,有些题目不错,可以从中学到点什么,答案如不妥,请指正...... +++++++++++++++...

37260
来自专栏Java Web

《编写高质量代码》学习笔记(2)

写着写着发现简书提醒我文章接近字数极限,建议我换一篇写了。 ---- 建议52:推荐使用String直接量赋值 一般对象都是通过new关键字生成的,但是Str...

37440
来自专栏增长技术

采用现代Objective-C

多年来,Objective-C语言已经有了革命性的发展。虽然核心理念和实践保持不变, 但语言中的部分内容经历了重大的变化和改进。现代化的Objective-C在...

9830
来自专栏风口上的猪的文章

.NET面试题系列[10] - IEnumerable的派生类

IEnumerable分为两个版本:泛型的和非泛型的。IEnumerable只有一个方法GetEnumerator。如果你只需要数据而不打算修改它,不打算为集合...

13720

扫码关注云+社区

领取腾讯云代金券