Fork me on GitHub
image frame

Konglong's blog

Knowledge advances by steps and not by leaps.

Java-8-垃圾收集调优指南4-可用的收集器(译).md

各种收集器的性能特点

对这一点的讨论是关于串行收集器(serial collector)的。Java HotSpot VM 包含三种不同类型的收集器,每一种具有不同的性能特点。

  • 串行收集器使用单个线程执行所有的垃圾收集工作,这使得它相对而言比较高效,因为没有线程间的通信开销。它最适合单处理器的机器,因为它不能利用多处理器硬件的优势,但是在多处理器上对小数据集(最大约 100 MB)的应用来说它还是有用的。在某些硬件和操作系统配置上默认选择串行收集器,或者可以使用选项 -XX:+UseSerialGC 显式地启用它。

  • 并行收集器(也称为 throughput collector)并行地执行 minor 收集,这可以显著地降低垃圾收集的开销。它适用于在多处理器或多线程硬件上运行的中到大型数据集的应用。在某些硬件和操作系统配置上默认选择并行收集器,或者可以使用选项 -XX:+UseParallelGC 显式地启用它。

    • parallel compaction 这个特性可使并行收集器并行地执行 major 收集。没有 parallel compaction,收集器就使用单个线程来执行 major 收集,这会显著地限制可扩展性(scalability)。如果命令行指定了 -XX:+UseParallelGC 选项,默认就会启用 parallel compaction 特性。想关掉这个特性就使用 -XX:-UseParallelOldGC 选项。
  • 并发为主的收集器(mostly concurrent collector)并发地执行它的大部分工作(例如,在应用仍在运行的同时)以保持垃圾收集引起的暂停较短。它适用于中到大型数据集且响应时间比总的吞吐量更重要的应用,因为用来最小化暂停时间的技术会降低应用的性能。Java HotSpot VM 提供了两个并发为主的收集器(mostly concurrent collector)供我们选择;请看 The Mostly Concurrent Collectors。使用选项 -XX:+UseConcMarkSweepGC 启用 CMS 收集器,或 -XX:+UseG1GC 启用 G1 收集器。

选择合适的收集器

除非你的应用对暂停时间有严格的要求,否则就先运行你的应用,让虚拟机去选择收集器。如有必要,可调整堆的大小以改进性能。如果性能仍不满足你的目标,就使用下面的指导方针作为选择收集器的起点。

  • 如果应用的数据集很小(最大约 100 MB),就使用选项 -XX:+UseSerialGC 选择串行收集器。

  • 如果应用将运行在单核处理器上,且对暂停时间没有要求,就让虚拟机去选择收集器,或者使用选项 -XX:+UseSerialGC 选择串行收集器。

  • 如果 (a) 应用的性能峰值是第一优先级的,且 (b) 对暂停时间没有要求或者大于等于 1 秒的暂停是可接受的,就让虚拟机去选择收集器,或者使用选项 -XX:+UseParallelGC. 选择并行收集器。

  • 如果响应时间比总的吞吐量更重要,且垃圾收集暂停必须保持短于约 1 秒,就使用选项 -XX:+UseConcMarkSweepGC-XX:+UseG1GC 选择并发收集器。

这些指导方针只是为选择收集器提供一个起点,因为性能取决于堆的大小、应用维持的活数据的数量、可用的处理器的数量和速度。暂停时间对这些因素特别敏感,因此之前提及的 1 秒的阈值只是一个近似值:并行收集器(parallel collector)会在许多数据大小和硬件的组合上经历长于 1 秒的暂停时间;相反地,在某些组合上并发收集器(concurrent collector)也许不能保持暂停短于 1 秒。

如果推荐的收集器不能实现想要的性能,首先尝试调整堆和分代的大小来满足想要的目标。如果性能仍然不好,就尝试一个不同的收集器:使用并发收集器来降低暂停时间,或者在多处理器硬件上使用并行收集器提高总的吞吐量。

参考资源

原文 Java 8 Garbage Collection Tuning Guide: Available Collectors

Java-8-垃圾收集调优指南3-调整分代大小(译)

分代的内存布局

有几个参数会影响分代的大小。图 4-1 “Heap Parameters” 图解了堆中 committed space 和 virtual space 之间的不同。虚拟机初始化时,会预留整个堆空间。预留的堆空间可以使用 -Xmx 选项指定。如果 -Xms 参数的值小于 -Xmx 参数的值,那么并非整个预留空间都立即被投入到虚拟机中。在该图中,未投入的空间(uncommitted space)被贴上 “virtual” 标签。堆的不同部分(新生代、老生代)可以根据需要增长至虚拟空间(virtual space)的界限内。

一些参数是堆中一部分与另一部分的比例。例如,参数 NewRatio 表示老生代对新生代的相对大小。

Figure 4-1 Heap Parameters

Description of “Figure 4-1 Heap Parameters”

该图由排成一行的六个矩形组成,从左到右依次被标记为:

1. Eden
2. Survivor
3. Survivor
4. Virtual
5. Tenured
6. Virtual

矩形分组的标签如下:

  • 总大小:矩形 1 到 6
  • Committed vs. Virtual:Committed 由矩形 1-3 和 5 组成;Virtual 由矩形 4 和 6 组成。
  • 老生代和新生代的比例:老生代由矩形 5-6 组成;新生代由矩形 1-4 组成。
  • Eden和一个Survivor的比例:Eden 是矩形 1;Survivor 是矩形 2。

调整堆大小

下述有关堆的增大和缩小以及默认堆大小的讨论并不适用于并行收集器(parallel collector)。(要了解并行收集器的默认堆大小以及为其调整大小的细节,请看 The Parallel CollectorParallel Collector Ergonomics 部分)不过,控制堆总大小和分代大小的参数仍然适用于并行收集器。

最重要的影响垃圾收集参数是总的可用内存。因为当分代装满时,垃圾收集就会发生,吞吐量与可用内存数量成反比。

缺省情况下,虚拟机在每次收集时会增大或缩小堆,为了在每次收集时尽力保持空闲空间与活对象的比例在指定的范围内。目标范围由 -XX:MinHeapFreeRatio=<minimum>-XX:MaxHeapFreeRatio=<maximum> 参数指定的百分数设定。堆总大小的界限由 -Xms<min>-Xmx<max> 设定。64 位 Solaris 操作系统 (SPARC Platform Edition) 平台上的默认参数如表 4-1 所示:

Table 4-1 Default Parameters for 64-Bit Solaris Operating System

Parameter Default Value
MinHeapFreeRatio 40
MaxHeapFreeRatio 70
-Xms 6656k
-Xmx calculated

有了这些参数,如果分代中空闲空间的百分比降至 40% 以下,分代就会扩大以维持 40% 的空闲空间,直至该分代被允许的最大大小。类似地,如果空闲空间超过 70%,分代将被缩小,为了保持仅 70% 的空间是空闲的,但这还要视分代的最小大小而定。

正如表 4-1 指出的,默认的最大堆大小是 JVM 计算得出的值。Java SE 中针对并行收集器和 Server JVM 的计算现在已经用于所有的垃圾收集器。计算的一部分是最大堆大小的上限值,这个值在 32 位和 64 位平台上是不同的。请看 The Parallel CollectorDefault Heap Size 部分。针对 Client JVM 也有一个类似的计算,该计算会产生比 Server JVM 更小的最大堆大小。

下面是有关服务端应用的堆大小的普遍指导方针:

  • 除非你认为暂停时间有问题,否则可尝试允许分配尽可能多的内存给虚拟机。默认大小通常太小。

  • -Xms-Xmx 设置为相同的值就能通过从虚拟机中删除最重要的调整大小的决策逻辑来增加可预测性(predictability)。但是,如果你的选择很糟糕,虚拟机就不能弥补你的过失了。

  • 通常,增加处理器数量的同时也要增加内存,因为分配操作是可以并行的。

新生代

在总的可用内存之后,第二个最影响垃圾收集性能的因素是专用于新生代的堆的比例。新生代越大,minor 收集发生的频次越低。但是,对于有限的堆大小,更大的新生代就意味着更小的老生代,这会增加 major 收集的频率。最佳选择取决于应用程序中对象生命周期的分布。

缺省情况下,新生代的大小由 NewRatio 参数控制。例如,-XX:NewRatio=3 意思是新生代和老生代的比例是 1:3。换句话说,eden 和两个 survivor 加在一起的大小是整个堆的 1/4。

参数 NewSizeMaxNewSize 限定了新生代的上下界。将它们设置为相同的值就固定了新生代的大小,正如参数 -Xms-Xmx 值相同就固定了整个堆的大小。以比 NewRatio 允许的整数倍更精细的粒度调整新生代是有用的。

调整 survivor 空间的大小

使用参数 SurvivorRatio 可以调整 survivor 空间的大小,但这对于性能并不重要。例如,-XX:SurvivorRatio=6 将一个 survivor 空间和 eden 的比例设置为 1:6。换句话说,每个 survivor 空间是 eden 的 1/6,新生代的 1/8(不是 1/7,因为有两个 survivor 空间)。

如果 survivor 空间太小,复制收集(copying collection)会直接溢出到老生代。如果 survivor 太大,它们就会毫无益处地空着。每次垃圾收集时,虚拟机会选择一个阈值,这就是一个对象在被移至老生代之前可被复制的次数。选择这个阈值是为了保持两个 survivor 的一半是满的。命令行选项 -XX:+PrintTenuringDistribution 可用来显示这个阈值和新生代中对象的年龄。观察应用的生命周期分布也是有用的。

表 4-2 为 64 位 Solaris 提供了默认参数值:

Table 4-2 Default Parameter Values for Survivor Space Sizing

Parameter Server JVM Default Value
NewRatio 2
NewSize 1310M
MaxNewSize not limited
SurvivorRatio 8

新生代的最大大小将从整个堆的最大大小和参数 NewRatio 的值计算得到。MaxNewSize 参数的默认值 “not limited” 意思是计算得到的值并不受 MaxNewSize 的限制,除非在命令行给 MaxNewSize 指定了一个值。

下面是针对服务端应用的普遍指导方针:

  • 首先决定你能承担的分配给虚拟机的最大堆大小。然后绘制 性能指标相对于新生代大小的 图表,以找出最佳设置。

    • 注意,最大堆大小应该始终小于机器上安装的内存数量,以避免过度的缺页错误(page faults)和抖动(thrashing)。
  • 如果总的堆大小确定了,那么增加新生代的大小就需要减小老生代的大小。保持老生代足够大以容纳应用在任何给定时间使用的所有活数据,加上一些闲散零碎的(slack)空间(10 到 20% 或更多)。

  • 取决于之前说明的关于老生代的约束:

    • 准许分配很多内存给新生代。
    • 增加处理器数量的同时增加新生代的大小,因为分配操作是可以并行的。

垃圾收集选项参考文档

Oracle 文档中心:http://docs.oracle.com

Java 文档中心:http://docs.oracle.com/en/java/

垃圾收集选项很多,有任何疑问可参考 Java SE Tools Reference for UNIX -> java command -> Advanced Garbage Collection Options

参考资源

原文 Java 8 Garbage Collection Tuning Guide: Sizing the Generations

Java Garbage Collection Basics

Getting Started with the G1 Garbage Collector

Java 8 垃圾收集调优指南2-分代(译)

如何分代与分代收集

Java SE 平台的一个强大之处是它保护开发人员避开内存分配和垃圾收集的复杂性。然而,当垃圾收集是主要瓶颈的时候,理解这个被隐藏的实现的某些方面还是很有用的。关于应用使用对象的方式,垃圾收集器做出了几个假设,它们被反映在可调参数中,可以调整这些参数以获得更好的性能同时又不牺牲这层抽象的强大。

正在运行的程序中,当一个对象通过任何指针都不再可到达时,它就被认为是垃圾。最简单的垃圾收集算法是遍历每一个可到达的对象,剩下的对象都被当作垃圾。这种方式花费的时间与活对象的数量成正比,这对于维护着大量活数据的大型应用来说是难以承受的。

虚拟机包含多个不同的垃圾收集算法,并使用分代收集将它们结合在一起。简单的垃圾收集检查堆中每一个活对象,而分代收集则利用在大部分应用上通过实证都被观察到的几个属性来最小化回收不再使用的对象所需的工作。这些被观察到的属性中最重要的是弱分代假说,这个假说称大部分对象只存活很短的一段时间。

下图中的蓝色区域是对象生命周期的一个典型分布。x 轴表示对象生命周期(用被分配的字节来度量)。y 轴上的字节数就是具有对应生命周期的对象的总字节数。左边的那个尖峰代表分配后不久就可以回收的对象(换句话说,已死的对象)。例如,Iterator 对象经常只存活于单个循环期间。

Figure 3-1 Typical Distribution for Lifetimes of Objects

Description of “Figure 3-1 Typical Distribution for Lifetimes of Objects”

有些对象存活得更久些,所以蓝色区域一直延伸到右端。举例来说,典型地有一些对象在初始化时就被分配,且一直存活直到所在进程退出。在这两个极端之间是存活于中间计算过程中的对象,上图中它们就是 初始的尖峰 右边的那个块。尽管一些应用有着看起来很不一样的分布,但非常非常多的应用都拥有这个大体上的形状。通过聚焦于大多数对象都“英年早逝”这个事实使得高效的解决方案成为可能。

为了针对这种情况进行优化,内存就被分代(保存不同年龄的对象的内存池)管理。当分代装满时,垃圾收集就会在分代中发生。绝大多数对象被分配在年轻对象专用的内存池(新生代)中,大多数对象都在那儿死去。当新生代装满时,就会导致一次 minor 收集。minor 收集只会对新生代进行回收,其他分代的垃圾不会被回收。minor 收集可以被优化,假设弱分代假说成立,且新生代中的大部分对象都是垃圾且可被回收。首要的是(to the first order),这种收集的成本与被收集的活对象(指收集过程中被扫描的对象)的数量成正比;充满死对象的新生代收集起来非常快。典型地,在每一次 minor 收集期间新生代中幸存对象的某一小部分会被移动至老生代。最终,老生代会装满且必须被收集,这就会导致一次 major 收集,在这个过程中,整个堆都会被收集。major 收集通常持续时间比 minor 收集长得多,因为涉及相当多数量的对象。

正如在 Ergonomics 一节指出的那样,ergonomics 动态选择垃圾收集器,为了给各种各样的应用提供好的性能。串行垃圾收集器是为具有小数据集的应用设计的,为它选择的默认参数对大部分小型应用来说都是有效的。并行或吞吐量垃圾收集器的目的是用于具有中到大型数据集的应用。ergonomics 选择的堆大小参数加上大小自适应策略的特性目的是为服务器应用提供更好的性能。大部分情形下,这些选择都工作得很好,但并非所有情形,那些例外情形通向这个文档的核心信条:

注意:如果垃圾收集成为了瓶颈,很可能你既需要自定义总的堆大小,还要自定义各个分代的大小。检查垃圾收集器的冗长输出,探索你的个性化性能指标对垃圾收集器参数的敏感度。

图 3-2 展现了分代的默认布局(适用于所有收集器,除了 Parallel 和 G1 收集器):

Figure 3-2 Default Arrangement of Generations, Except for Parallel Collector and G1

Description of “Figure 3-2 Default Arrangement of Generations, Except for Parallel Collector and G1”

初始化时,会虚拟地保留一个最大的地址空间,但并未将它分配给物理内存,除非它被需要。为对象内存保留的整个地址空间可被划分为新生代(young)、老生代(tenured)。
新生代由伊甸园(eden) 和两个幸存者(survivor)空间组成。大部分对象最初被分配在 eden 区。任何时刻都有一个 survivor 区是空着的,用作 eden 区中活对象的目的地;另一个 survivor 在接下来的复制收集(the next copying collection)期间用作目的地。像这样对象在两个 survivor 之间来回复制,直到它们变得足够老而被拷贝至老生代。

性能考虑因素(Performance Considerations)

垃圾收集的性能有两个主要的的量度:

1. 吞吐量是指未花在垃圾收集上的总时间所占的百分比。吞吐量包括为对象分配内存所花费的时间(但一般不需要调优分配速度)。
2. 暂停是指因正在进行垃圾收集而使应用表现得无响应的时间。

用户有不同的垃圾收集需求。举例老说,一些用户认为对于 web server 来说正确的指标是吞吐量,因为垃圾收集期间的暂停是可容忍的或者可以简单地被网络延迟掩盖。然而,在交互式图形应用中,即使很短的暂停也会负面地影响用户体验。

而一些用户对其他考虑因素比较敏感。footprint 是一个进程的工作集,使用页(pages)和缓存行(cache line)来度量。在物理内存有限或有许多进程的系统上,footprint 可能会影响可扩展性/可伸缩性(scalability)。垃圾收集的敏捷度(promptness)就是对象变成死的和其内存变得可用之间的间隔时间,对于分布式系统(包括远程方法调用 RMI)来说,这是一个重要的考虑因素。

总之,为具体的分代选择大小就是在这些考虑因素之间进行平衡。例如,非常大的新生代可以最大化吞吐量,但这样做是以增加 footprint、降低垃圾收集的敏捷度(promptness)和暂停时间变长为代价的。新生代很小可以最小化新生代的暂停时间,代价是减小了吞吐量。调整一个分代的大小不会影响另一个分代的垃圾收集频率和暂停次数。

没有一个为分代选择大小的正确方法。最好的选择就是根据用户需求和应用使用内存的方式来决定。因此虚拟机对垃圾收集器的选择并不总是最佳的,使用 Sizing the Generations 一节描述的命令行选项可以覆盖默认选择。

度量(Measurement)

吞吐量和 footprint 最好使用特定于应用的指标来度量。例如,web server 的吞吐量可以使用客户端负载生成器(client load generator)来测试,而它的 footprint 在 Solaris 上可以使用 pmap 命令来测量。而垃圾收集导致的暂停通过查看虚拟机自身的诊断输出就可以轻松估算出来。

命令行选项 -verbose:gc 可使 JVM 在每次收集时打印关于堆和垃圾收集的信息。例如,这就是来自于一个大型服务器应用的输出:

1
2
3
[GC 325407K->83000K(776768K), 0.2300771 secs]
[GC 325816K->83372K(776768K), 0.2454258 secs]
[Full GC 267628K->83769K(776768K), 1.8479984 secs]

输出展示了两次 minor 收集,接着的是一次 major 收集。箭头前后的数字(例如,第一行中的 325407K->83000K)分别表示垃圾收集前、后新生代和老生代中活对象加在一起的大小。minor 收集之后,活对象的总大小仍然包含一些已经是垃圾(不再是活的)但 minor 收集没法回收的对象。这些对象要么就在老生代中,要么被老生代中的死对象引用。

紧接着的圆括号中的数字(例如,(776768K) 仍来自第一行)是堆的 committed size:不用向操作系统请求更多内存,直接可用于 Java 对象的内存空间的数量。注意,这个数字只包含两个 survivor 中的一个。除在垃圾收集期间之外,都只有一个 survivor 用于在任何给定的时间存储对象。

每行的最后一项(例如,0.2300771 secs)表示垃圾收集所花费的时间,在这个实例中大约是 1/4 秒。

第三行中有关 major 收集的输出格式是类似的。

注意:-verbose:gc 选项产生的输出的格式在将来的发布中可能会改变。

命令行选项 -XX:+PrintGCDetails 可使 JVM 打印更多有关垃圾收集的信息。下面是一个使用串行垃圾收集器的 JVM 中该选项的输出:

1
[GC [DefNew: 64575K->959K(64576K), 0.0457646 secs] 196016K->133633K(261184K), 0.0459067 secs]

这表明 minor 收集回收了新生代大约 98% 的空间,DefNew: 64575K->959K(64576K),花了 0.0457646 secs (大约 45 毫秒)。

整个堆的使用减少至大约 51%(196016K->133633K(261184K)),最终的总时间表明收集操作还有一些微小的额外开销(除新生代的收集之外)。

注意:-XX:+PrintGCDetails 选项产生的输出的格式在将来的发布中可能改变。

-XX:+PrintGCTimeStamps 选项会在垃圾收集开始时添加一个时间戳。要查看垃圾收集发生的频率,这个选项很有用。

1
111.042: [GC 111.042: [DefNew: 8128K->8128K(8128K), 0.0000505 secs]111.042: [Tenured: 18154K->2311K(24576K), 0.1290354 secs] 26282K->2311K(32704K), 0.1293306 secs]

这次收集开始于进入应用执行期大约 111 秒(about 111 seconds into the execution of the application)。此外,还显示了使用老生代来描绘 major 收集的信息。minor 收集大约同时开始执行。老生代的使用减少至大约 10%(18154K->2311K(24576K)),花了 0.1290354 secs(大约 130 毫秒)。

参考资源

原文 Java 8 Garbage Collection Tuning Guide: Generations

Java 8 垃圾收集调优指南1-工效学(译)

概述

工效学(Ergonomics)就是通过 JVM 和垃圾收集器调优(例如基于行为的调优)来改进应用性能的过程。JVM 为垃圾收集器(garbage collector)、堆大小(heap size)和运行时编译器(runtime compiler)提供了依赖于平台的默认选择。这些选择可以满足不同类型应用的需求,但只需更少的命令行调优。此外,基于行为的调优(behavior-based tuning)动态地调整堆的大小来满足应用特有的行为。

请先使用这些默认值,然后再考虑使用后续章节中描述的更详细的控制。

垃圾收集器、堆和运行时编译器的默认选择

有如下配置的机器被称为服务器级别的机器:

  • 2 个或更多的物理处理器
  • 2 GB 或更多的物理内存

在服务器级别的机器上,默认的选择如下:

  • 吞吐量垃圾收集器(throughput garbage collector)
  • 初始堆大小为物理内存的 1/64,高达 1 G
  • 最大堆大小为物理内存的 1/4,高达 1 G
  • Server runtime compiler

关于 64 位系统中初始堆大小和最大堆大小,请看 The Parallel CollectorDefault Heap Size_部分。

服务器级别的机器之定义适用于所有平台,除了运行着 Windows 的 32 位平台。运行时编译器有两个选择:client、server,可通过命令行选项来覆盖默认选择:-<client|server>

基于行为的调优(Behavior-Based Tuning)

对于 parallel collector,Java SE 提供了两个可调参数来帮助应用实现其特有的行为:最大暂停时间目标和应用吞吐量目标;请看 The Parallel Collector 部分。但这两个选项在其他收集器中不可用。注意,这些行为无法总是被满足。应用需要有足够大的堆来至少容纳所有的活数据。此外,最小堆大小可能会阻止达成这些期望的目标。

最大暂停时间目标(Maximum Pause Time Goal)

暂停时间是指垃圾收集器暂停应用并回收不再使用的空间所花费的时间。这个目标的意图是限制暂停时间的最大值。暂停时间的平均值和相对于平均值的差值(variance on the average)由垃圾收集器维护。从执行一开始就计算平均值,但进行了加权处理,为了使更多最近的暂停占有更大的比例。如果平均时间加上 暂停时间相对于平均时间的差值 大于最大暂停时间目标,垃圾收集器就认为这个目标还未被实现。

最大暂停时间目标由命令行选项 -XX:MaxGCPauseMillis=<nnn> 指定。它被解释为给垃圾收集器的一个提示——期望暂停时间小于等于 <nnn> 毫秒。垃圾收集器会调整 Java 堆大小和其他与垃圾收集相关参数,来尽力保持垃圾收集暂停时间短于 <nnn> 毫秒。默认情况下没有最大暂停时间目标。这些调整可能会导致垃圾收集器更频繁地运行,进而降低了应用的总吞吐量。垃圾收集器会优先尽力满足任何暂停时间目标,然后才是吞吐量目标。然而,在某些情况下,期望的暂停时间目标还是无法被满足。

吞吐量目标(Throughput Goal)

我们使用收集垃圾花费的时间和干其他事儿所花费的时间(被称为应用时间(application time))来度量吞吐量目标。这个目标由 -XX:GCTimeRatio=<nnn> 选项指定。垃圾收集时间与应用时间(application time)的比值是 1 / (1 + <nnn>)。例如,-XX:GCTimeRatio=19 设置的目标为期望总时间的 1/20 或 5% 用于垃圾收集。

垃圾收集花费的时间是新生代和老生代加在一起的总时间。如果吞吐量目标还未被满足,就会增加各代的大小,目的是努力增加在两次收集之间应用可运行的时间。

Footprint Goal

如果吞吐量目标和最大暂停时间目标已被满足,垃圾收集器就会减小堆的大小,直到其中一个目标不能被满足(总是吞吐量目标)。然后再设法解决那个未被满足的目标。

调优策略(Tuning Strategy)

不要给堆选择一个最大值,除非你知道你需要的堆比默认的最大堆还要大。选择一个对你的应用来说足够了的吞吐量目标。

堆会增长或收缩至可支持所选择的吞吐量目标的大小。应用程序行为的改变可能导致堆增长或缩小。例如,如果应用开始以更高的速度为对象分配内存,堆就会增长以维护相同的吞吐量。

如果堆增长到它的最大大小而吞吐量目标还未被满足,那么相对于吞吐量目标来看,最大堆大小太小了。将最大堆大小设置为一个接近于此平台上全部的物理内存但又不会导致应用交换(swapping of application)的值。再次执行应用程序。如果吞吐量目标仍未满足,那么相对于此平台上可用的内存来看,应用时间(application time)的目标太高了。

如果吞吐量目标可被满足,但暂停时间又太长了,那就选择一个最大暂停时间目标。选择最大暂停时间目标可能意味着你的吞吐量目标将不会被满足,因此请选择对应用来说可接受的折衷值。

典型的情形是堆大小将随着垃圾收集器努力满足互相抗衡的目标(competing goals)而振荡(oscillate)。即使应用程序已达到稳定状态,也还是如此。实现吞吐量目标(可能需要更大的堆)的压力与最大暂停时间和最小 footprint 目标(这两个可能需要更小的堆)相互抗衡着。

参考资源

原文 Java 8 Garbage Collection Tuning Guide: Ergonomics

证明二叉堆至少有一半的节点是叶节点

命题

二叉堆至少有 1/2 的节点是叶节点。

证明

首先,回顾哈 优先队列与堆 中讲述的二叉堆的结构性:二叉堆是一棵完全二叉树,即其元素总是从左到右一层一层填入,要么树被完全填满,要么就只有最底层未填满。

先证明对于理想二叉堆,该命题成立

令 a 为理想二叉堆的节点总数量,b 为叶节点的数量,h 为树的高度(注意,根节点的深度为 0)。每一层的节点数为 1, 2, 4, 8, …,很明显,这是一个等比数列,公比 q 为 2,首项为 1。

应用等比数列的求和公式可得到:

$ a = \frac{1-2^{h+1}}{1-2} = 2^{h+1}-1 $
$ b = 2^h $

进而 $ \frac{b}{a} = \frac{2^h}{2^{h+1}-1} > \frac{2^h}{2^{h+1}} $
而 $ \frac{2^h}{2^{h+1}} = \frac{1}{2} $
因此 $ \frac{b}{a} > \frac{1}{2} $。也就是说,对于理想二叉堆,命令成立。

再证明对于非理想二叉堆,该命题也成立

首先,将非理想二叉堆看作由两部分组成:

  1. 去掉最底层后的理想二叉堆
  2. 最底层,该层未填满。

令 a 为理想二叉堆的节点总数量,b 为理想二叉堆的叶节点数量,k 为最底层的叶节点数量。

因此节点总数为 $ a+k $;最底层的节点数为偶数时,叶节点数为 $ b+k-\frac{k}{2} = b+\frac{k}{2} $;为奇数时,叶节点数为 $ b+k-\frac{k+1}{2} = b+\frac{k}{2}-\frac{1}{2} $。

因为 $ \frac{b+\frac{k}{2}}{a+k} > \frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} $
所以,只需要证明 $ \frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} >= \frac{1}{2} $ 即可。

首先

\begin{array}{rcl}
\frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} - \frac{1}{2}
&=& \frac{2b+k-1}{2(a+k)} - \frac{a+k}{2(a+k)}\\
&=& \frac{2b-a-1}{2(a+k)}\\
\end{array}

又有

\begin{array}{rcl}
\frac{b}{a} &>& \frac{1}{2} (前一小节已证明)\\
2b &>& a\\
2b-a &>& 0\\
\end{array}

因为 2b, a 都是正整数,所以 2b-a 也必然是整数。

进而 $ 2b-a > 0 $ 等价于 $ 2b-a \geq 1 $。

进而 $ \frac{2b-a-1}{2(a+k)} \geq 0 $,也就是 $ \frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} - \frac{1}{2} \geq 0 $,即 $ \frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} \geq \frac{1}{2} $。

因此,命题对于非理想二叉堆也成立。

  • © 2016-2020 Konglong
  • Powered by Hexo Theme Ayer
    • PV:
    • UV:

请我喝杯咖啡吧~

支付宝
微信