By Xi Yang, http://yangxi.anu.edu.au/
“或多或少, 语言影响了程序员写程序的风格。运行时系统需要把这风格和硬件特性对接上”。
Managed languages, 比如 Java, 为了提高生产力和安全性，要求创建的非本地变量有一个初始值, 0。所以这些语言的 run-time system 在返回申请的内存前,需要把这些内存清零 (zeroing). 比如程序1的输出应该是 “I am 0”.
int[] I = new int[1];
System.out.Println(“I am “+I[0])
程序1
Managed language 一般会内置 GC (Garbage Collection)。 GC会鼓励程序员申请大量的中小尺寸对象。这
就会导致 zeroing 的开销相应增大。图(1) 中可以看到 在 Core2 的机器上，zeroing 无情的干掉了将近 5%
cycles, 甚至可以高达12%!
图(1) Zeroing 消耗的 CPU cycles / 应用消耗的所有 CPU cycles
在现有的 Java 虚拟机中，流行的清0方式有两种， bulk zeroing 和 hot-path zeroing。 Bulk zeroing
就是 run-time system 先将一大片内存清0，然后直接在清0的空间上创建object. 比如图2 (a) 中, 左边
的 block 被整体清0, 然后在这个 block 上创建 object. Hot-path zeroing 是在创建object的时候才将
object 占据的部分清0。比如 图 2 (b) 中, 只清了object 需要的空间.
JikesRVM 用 bulk Zeroing，HotSpot VM 和 IBM J9 VM 用 Hot-path zeroing.
默认情况下, jikesRVM 使用 genImmix GC. GenImmix 是一个 generational GC. Young Generation
(Nursery Space) 是一个地址连续的空间, 用 bump pointer 管理分配, 采用 copy collection 策略.
Old generation (mature space) 是一个非连续的空间,使用 free list 管理, 并采用 Immix collector
策略. 每个 thread 从nursery 申请一个 block, 默认为 32k. 然后thread 在这个 block 中创建对象.
如果对象大小大于 block 时候, 从 Large object space 申请空间. 当 nursery space 满了以后, minor
GC 触发, 把存活的对象从 nursery space 拷贝到 mature space. JikesRVM 默认使用 bulk zeroing.
当 thread 从 nursery space 申请一个 block 时, 通过 memset() 把这个 block 清0. 然后 object 会
创建在这片已经清0的block 里边. 我们可以通过测量 memset() 函数消耗的 CPU cycles 比上 应用总共消
耗的 CPU cycles 来得到图(1)。
图2 (a) Bulk Zeroing
图2 (b) Hot-Path Zeroing
一次清一个 32K 的 block 不仅会污染cache, 而且创建对象的时候对应的内存很可能已经不在cache中，导致
temporal locality 不好。为了克服这个弱点, 很多 JVM 采用了 hot-path zeroing， 当创建 object 的时
候才清0。 这样清0 和 第一次访问object 之间时间非常短. 但是这也会带来两个问题： 1) JIT 会 inline
内存申请代码的 hot-path 部分, 由于 allocation 的代码非常频繁到处使用，inline 会增加代码体积。 2)
相对于一次清一个block, hot-path 中 清0 的指令会和其他指令交错在一起, 无法充分压榨 memory
bandwidth.
static int[] fresh;
public static void initfresh() {
for (int i=0; i < 1<<26; i++) { // 64 million
fresh = new int[8];
// initialize the fresh array
for (int j=0; j < 8; j++)
fresh[j] = j;
}
}
程序2
在现在的 x86 CMP 机器上,这两个清0的办法谁更好呢? 我们先上 micro-benchmark. 在程序2中, 我们申请
64 million 个 数组, 然后初始化这个数组.
图3 (a) 程序2在Core2Q 6600 上 bulkZeroing 和 hotpathZeroing 清0 策略下的性能
图3 (a) 显示在 Core2 上, hotpath zeroing 比 bulk zeroing 快了 24%. 原因是什么呢？ 来分解bus
transactions. 我们把他们的 bus transactions 分解成 program miss 导致的 fetch transactions,
prefetching miss 导致的 fetch transactions, 和 write transactions.
图3 (b) 在 Core2Q 上 程序2产生的 bus transactions 分布情况
图3 (b)显示了在两种清0策略 bus transactions 的分布情况。 左边的bar 是 bulk zeroing， 右边的bar
是 hot-path zeroing。 我们看到是 hot-path zeroing 策略下, prefetching miss 导致的 fetch bus
transactions 是 bulk zeroing 的 4倍。 Bulk Zeroing 密集的顺续清空一个 block， 这些指令可以压榨
memory bandwidth。 当CPU探测到 memory bus 高负载的情况下， 会抑制 prefetcher。 但是 hot-path
zeroing 清0 的指令是和 程序2 中更新 array 的指令交错运行的, 这样 memory bus 上的负载降低很多,
CPU 就会利用空闲的 memory bandwidth 做 prefetching。 同时程序2 会顺续的访问连续的内存, 所以
prefetching 的精确率非常高. 如果我们把prefetching 关掉会如何呢?
图4 关闭 prefetching 后, 程序2在Core2Q 上的运行时间
图4 显示当关掉prefetching 以后， hot-path zeroing 反而比 bulk zeroing 慢了 11%。
有没有更好的 trade-off 呢？ 清0的开销如此大, 有什么办法可以加快清0的速度呢? 对于 write-back
cache, 一次写操作可以产生两个 transactions — 一个是要把把数据从内存 fetch 到 cache, 另外一个
是当这个cache line被替换是需要把数据写回内存. 所以如果用 temporal instructions 来清0, 我们只
能利用一半的 memory bandwidth. 如果我们能跳过 cache 直接写入内存, 我们就能达到更高的 throughput.
x86 提供了这样的指令, non-temporal instructions. 在 Core2Q 和 i7-2600 上, non-temporal 的
throughput 是 temporal instructions 的两倍.
在 bulkZeroing 的基础上, 我们可以非常容易的实现 bulkNTzeroing — 把清0的指令换成 non-temporal
instructions. 清0以后, 创建 object 的时候, 由于数据没有在cache, 会产生cache miss。但是不要紧，
跟 hot-path zeroing 一样, hardware prefetching 可以帮我们把数据预先prefetch到cache.
由于使用 non-temporal instructions 不会污染 cache, 我们可以放心的把这部分清0的工作交给另外的Core,
这就是 concurrentZeroing. 图 6 中我们可以看到, 对于程序2, bulkNT性能几乎和 hotpathZeroing 一样.
ConcurrentZeroing 比 hot-path zeroing 快了 13%.
图6 程序2 在Core2Q 上的性能
Managed language 写的 application 会申请大量的存活时间很短的中小 size 对象. Run-time system
可以利用这一点来 shape application 的内存访问模式. 比如把 nursery space 设置成连续的地址空间,
并且使用 bump-pointer 来管理分配, 这样就会让连续的内存申请有很强的 spatial locality. 对于强
spatial locality 的访问, prefetch 可以预先把需要的数据 prefetch 到 cache. 有了 hardware
prefetching 的帮助, 我们就可以用 non-temporal instructions 来快速的清理一大片空间. Non-temporal
instructions 也不会污染 cache, 这样我们就可以放心的使用空闲的 core 来清0. 相看更详细的分析吗?
请看我们发表在 OOPSLA 2011 的论文, Why Nothing Matters: The Impact of Zeroing.
| 
用Java写“算法Intensive”的应用，本来就是错的。
高级语言，比如Phython应该用在复杂但是不常用的path上。
图片挂了？还是得用代理才能上？另1楼是python。
It is easy to understand bulkNTzeroing but it is quite difficult to understand why concurrentZeroing has any performance advantage since it will introduce sync between two cores.
@ 1楼
我猜你想说的是 Java 写的程序比 C 的慢。
其实比较 language 的快慢是没有意义的。 用特定 langage 写的程序的快慢 取决于 这个程序的质量 和 语言的实现 (compiler/JIT，runtime system) 的质量。
Java 的程序 或者 C 的程序的性能取决于程序员的质量和 JVM 和 C 的 compiler 的质量。 对于你说的 “算法 intensive 应用”, Java 的程序可以比 C 好，也可以差。
你说 Python 应用应该用在 slow-path 上，如果你指的是性能原因的话，那是由于 Python 的实现非常差， 连 JIT 都没有，GC 也非常原始，性能当然差。假设有一个非常好的 JIT, 完全可以生成质量非常高的代码。
@ 2 楼
Nursery Space 是很小 ,say 32MB, 和地址连续的。Nursery GC 是 stop-the-world GC, 就是说其他需要申请内存的 threads 都等在那里，当 Nursery GC 做完之后，唤醒应用 threads 之前，会先让 清0的那个工作线程跑起来，它知道 Nursery Space 里边都是垃圾而且连续，可以一溜烟清到底。应用 threads 会比 这个清0线程 晚一点醒来，当他们醒来的时候已经有大把 block 可以用了。所以他们之间基本没有 互相扯皮。
I see your points:
1. GC is exclusive: if it runs and all other threads must sleep;
2. The GC (ONE) thread can run in a free core to zeroing the memory using non-temporal writes
If that were the case, how about running the GC in the same core as the application thread?
Forgot to say:
congratulation to you since OOPSLA is one of toughest conf.s to publish a paper.
挺好的，理论上没问题。就像我之前利用non-temporal store优化JVM内memcopy实现一样，对于micro benchmark会有很好的体现，但是在实际应用中由于应用的复杂性体现有限。很早以前听coly和crystal说过你的这篇论文，我试过在hotspot vm上改后并测试specjvm效果不明显。不过，清理大片空间会很好。好像oracle暂时还没有人support这个，但是如果你愿意，你的patch我们可以详细测试，收到taobao jvm里。谢谢
@Multithread “If that were the case, how about running the GC in the same core as the application thread?”
By default, the number of GC thread JVM created is same as the number of hardware threads, which means that for the stop-the-world GC, gc threads run on all cores.
This is also why single thread java applications could get speedup when increasing the number of cores. More details in our ASPLOS paper, http://users.cecs.anu.edu.au/~steveb/downloads/pdf/powerperf-asplos-2011.pdf
David Patterson also introduced it in one of his articles, http://dl.acm.org/citation.cfm?id=2209271&preflayout=tabs
喜欢这样的文章，很实在。
any alternate links to see the pics?
投诉，图都木有了。
是不是这个意思，清0是个一次性操作，还通过cache来write-back不划算，绕过cache直接写内存更高效？
@11 @12
图片链接修复了，不好意思。
@13 sil
sil said “是不是这个意思，清0是个一次性操作，还通过cache来write-back不划算，绕过cache直接写内存更高效？”
绕过 cache 直接写内存是 双刃剑，好的方面是 不污染 cache, 而且充分利用贷款。 坏的方面是，如果这些内存会马上用到，那还得从内存再把刚写的数据 fetch 到 cache 里边。
这个paper 其实就是如果利用这个好的一方面，压制坏的一面。
Prefeching 在这里边起了很大的作用。 首先是 GC 可以 塑造 java application 内存访问的 pattern, application 总是快速的顺序的从地址连续的nursery space 上申请内存，但是中间会有一定间隔来做一些运算，另外 prefetching 很喜欢顺序的来 prefetch, 所以在 nursery space 申请内存的部分，可以prefetch 下面的几个 cache line。 这样就缓解了从内存中再次 fetch 数据进 cache 的惩罚。
这个方法有一个开销就是会加倍内存访问的数量。不过 memory bandwidth 是拿来用不是拿来看的，先榨干它再说。
谢谢作者的耐心解释。
对于Java语言来说，分配内存清0后，应该是马上要用到的，进行对象的初始化操作。这时候的效率问题就靠prefetch来解决，是这样么？
我想到一种情况，就是GC的mark过程中，这种绕过cache的方式会不会有用？mark是真正的一次性操作，object header写完之后，直到sweep阶段才会再到这个对象。
@ 16 sil
sil said “对于Java语言来说，分配内存清0后，应该是马上要用到的，进行对象的初始化操作。这时候的效率问题就靠prefetch来解决，是这样么？”
是的。
sil said “我想到一种情况，就是GC的mark过程中，这种绕过cache的方式会不会有用？mark是真正的一次性操作，object header写完之后，直到sweep阶段才会再到这个对象。”
well, NT instruction 还有一个缺点就是 如果 data 在 cache 中， NT 写的时候是要先 invalidate 掉这个 copy 的。 是不是能用 NT instruction 来加速 mark, 取决于实现了。系统就是这样，得 build 出来，然后做实验，才能知道是否可行。
@ 16 sil
至于 prefetch 对 mark-sweep gc 的影响，可以参考我们组07年的一篇论文
R. Garner, S. M. Blackburn, and D. Frampton, “Effective Prefetch for Mark-Sweep Garbage Collection,” in The 2007 International Symposium on Memory Management, 2007.
http://users.cecs.anu.edu.au/~steveb/downloads/pdf/pf-ismm-2007.pdf
@ 4
“我猜你想说的是 Java 写的程序比 C 的慢。
其实比较 language 的快慢是没有意义的。 用特定 langage 写的程序的快慢，，，，，，”
你的说法看似有道理，其实没有任何实际意义。。。
的确，从理论上：如果JAVA（甚至Python）的虚拟机实现的足够好，而C语言的编译器实现的又恰好足够差的话，JAVA或者Python写的程序的确是可以比C写的运行更快。。。可是我们是活在实际中而非假设中的，，现实世界是：做C编译器的人和做JAVA或Python虚拟机的人技术水平都很高，而实现C语言编译器的人只需要关注速度和空间，而实现虚拟机的人除了速度和空间还需要考虑易用性和动态特性等提高编程效率的问题，，，我承认易用性和高级的动态特性很有诱惑力，但是我们都是理性的人，应该清楚任何美好的东西的获取都需要在其他地方做出让步才能获得，，也就是所谓的“trade off”，，，，
所以，只要你拿同一个时代的JAVA虚拟机和C编译器来比较，，，比速度JAVA肯定是比不过C的。。
从本源上来说：人类认知世界和机器世界是两个世界，而编程语言是两个世界连接的纽带，编程语言如果更匹配其中一个世界，就必然更不匹配另一个世界。。。
从直觉上说：CPU只知道地址和数字，从来不知道什么对象，，只有人类世界中才有对象，，编程语言为了讨好人类硬往自己的元素里加入对象，，在把自己翻译到机器世界时怎么可能不引入冗余的空间和时间呢？？？？