（计算机系统结构专业论文）java虚拟机的自适应动态优化.pdf

j a 、，a 虚拟机的自适应动态优化 偏移表的访问，大大地降低遍历堆所带来的开销；同时活块池的引入使 得该算法很容易被应用在并行垃圾收集算法中。实验证明该算法使得标 准工业测试程序s p e c j b b 2 0 0 5 、s p e c j v m 9 8 和d a c 印。的性能有4 i 同程度的提 高，最高达到8 9 ；同时程序的局部性也优于线性标记缩并算法，与深 度遍历序相比，d t l b ( d a t a ，n a n s l a t i o nl o o k a s i d eb u 能r ) 失效率改善最多 为1 1 ，2 级c a c h e 失效率改善最多为1 3 6 。 第三，基于自适应动态优化框架提出预取优化算法来改善程序的局部 性。该算法基于自适应动态优化框架，它在即时编译器对程序编译的同时完 成插桩的工作，插桩用来收集访存对象的信息。如果检测到当前运行过程中 存在相关对象的访问，预取控制器将会插入相应的预取指令。自适应预取优 化算法的关键在于预取准确性和运行时开销之间的权衡。为了保证预取的 准确性，我们对程序进行插桩；为了降低运行时的开销，我们控制预取指令 的插入并且实现无效的插桩删除优化。实验结果表明该算法使得标准工业测 试程序s p e c j b b 2 0 0 5 、s p e c j v m 9 8 和d a c 印。的性能有不同程度的提高，最高达 到1 8 1 平均为7 1 5 。同时，运行时开销低于4 ，内存开销可以忽略彳i 计。 第四，描述了种基于对象亲缘关系的垃圾收集算法。该算法通过硬件性 能分析器来定位频繁引起c a c h e 失效的对象，根据对象之间的亲缘关系，建立对 象亲缘图，并与垃圾收集算法相结合，将亲缘度高的对象们排列在堆中相邻的 位置，这意味着访问完其中，。个对象，接下来访问另外一个对象的概率很高，将 它们放在一起可以改善对象之间的局部性，实验结果表明基于对象亲缘关系的 垃圾收集算法对s p e c j b b 2 0 0 5 、s p e c j v m 9 8 和d a c a p o 的性能有明显的提高，最 多为4 9 ，平均为3 4 ，同时采用硬件性能分析器收集信息使得p r o m i n g 的开销 很低，平均为0 4 7 ，最后我们将该算法和自适应预取优化相结合，结果表明大 部分程序的性能不会降低，对于个别程序，甚至有所提高。 关键词：j a a 虚拟机，自适应动态优化框架，垃圾收集，对象局部性，预取，亲 缘关系 a b s t r a c t j a al a n g u a g ei sw i d e l yu s e di ns 0 危御ed e s i g nf o ri t 8m e r i t si n8 0 舢哪e e n 酉n e e r j a 、，a 印p l i c a t i o 璐r u no nt h ej a v a 订r t u a lm a c h i n e c o m p a r e d 祈t h b i n a 唧c o d eg e n e r a t e db yt r a d i t i o n a lc o m p i l a t i o n ，i th 嬲f b a t u r 鹪o fb e t t e rm o d - u l a r i t y p l a t f o r mi n d e p e n d e n c e ，t y p es a f e t ya n ds oo n t h e s ef e a t u r e sm a k ej a v a l a n g u a g em o r es u i t a b l ef o rf 嬲ta n ds a f ed e v e l o p m e n to fm a n yl a r g es c a l e8 0 仡 w a r e s h 伽陀v e r ，t h o s ec h a r a c t e r sc a u s et r a d i t i o n a lc o m p i l a t i o nu n a b l et ow o r k r e s e a r c h e r sk e 印e x p l o r i n gn e wc o m p i l a t i o nt e c h n i q u e st og e tb e t t e rp e r f o r m a n c e o nj a 、，av i r t u a lm a c h i n e f 0 rt h es h o r to fr u n t i m ei n f o r m a t i o n ，s t a t i cc o m p i l a t i o na d a p t sc o m p l e x 百o b a la n a l y 8 i s ，w h i c hc a n ts a t i s 黟o u rr e q u i r e m e n t s t h ep o p u l a u r i t yo fj a v a v i r t u a lm a c h i n ei i l 、r o l v 豁c o m p i l a t i o na n do p t i m i z a t i o na tr u n t i m e ，i n d u s t r 涵 f o c u s e so na d 印t i v eo p t i m i z a t i o 璐，a n dt h e yw a n tt oo p t i m i z et h ea p p l i c a t i o i l s a c c o r d i n gt or 僦i m ef e e d b 她k t l l i s 拙s e r t a t i o ns y s t e m a t i c a l l y 锄dd e e p l yi n v e s t i g a t 髑t h ea d 印t i v e0 p t i m i z a t i o na n dl o c a h t yp r o b l e mi nj a 、，a 访r t u 越m a c h i n e t h ec o n t r i b u t i o n so ft h i s w o r ka l r e 潞f 0 1 1 0 、鸺： f i r s t l y ，w ed e s i g na n di m p l e m e n ta ne m c i e n ta d a p t i v eo p t i m i z a t i o n 行a m e l w o r k t h e 仃a m e w o r kc o l l e c t 8f i n e 舒a i n e di n f o r m a t i o nb yi n s t r u m e n t a t i o n ，w h i c h a l s ow i l lb ea d j u s t e da c c o r d i n gt ot h er u r l t i m ef e e d b a c k w bm s ou t i l i z et h ec h a 卜 a u c t e r 8o fj a v a 印p l i c a t i o i l st or e d u c et h es i d e - e 髓c to fi n s t r u m e n t a t i o n c o m p a r e dw i t hs t a t i ca n a l y s i s ，o u rw o r ki si m p l e m e n t e da tr u n t i m ea n di s i n d e p e n d e n to f 瑚i a b l ed a t as e t c o m p a u r e dw i t hd y n 锄i ca n a l y s i s ，、ed e s i g n e d a na d 印t i v eo p t i m i z a t i o nf r a m e w o r ki nj a v av i r t u a lm a c h i n e ，a n ds u p p l i e da g a pi nd y n a m i cc o m p i l a t i o nt e c h n i q u e s w bt r yt om a k e ! t h eo 、，e r h e a dl o w 鹤t t l l r o u g h o u tt h e 行a m e w o r k ：i t sd e s i g n ，i n s t r u m e n t a t i o n ，a i l d8 0o n t h er e s u l t s s h o wt h a tt h eo v e r h e a do ft h e 丘a m e w r o r ki s1 7 o na v e r a g e ，谢t hh i g h e s to f 2 5 t h ef r 锄e w o r kp r o v i d e sap l a t f o r mf o rl o c a l i t yo p t i m i z a t i o ni ns u b s e q u e n t c h a d t e r s j a 、，a 虚拟机的自适应动态优化 s e c o n d l y ，、 ，es u g g e s t e daf a s ts l i d em a r kc o m p a c ta l g o r i t h m a l l o c a t i o n o r d e ri st h eb e s tf o rl o c a l i t y w h i c hs l i d em a r kc o m p a c ta l g o r i t h mi sb a s e do n b u t t r a d i t i o n a ld e s i g nm a d et h ea l g o r i t h m so v e r h e a dt o o1 a 工g e i nt h i sd i s s e r t a t i o n ， ，ep r o p o s e daf a s ts l i d en l a r kc o m p a c ta l g o r i t h m ，w h i c hr e d u c e st h eo v e r h e a db y m a l r kb i tt a b l e ，1 i v eb l o c kp o o la n do 盔e tt a b l e t h er e s u l t ss h o wt h a ti ta c h i e v e s u pt o8 9 s p e e d u pi ni n d u s t r y s t a n d a r db e n c h m a r ks p e c j b b 2 0 0 5 、s p e c j v m 9 8 a n dd a c a p oo nt h ep e n t i u m4 ，1 1 i m p r o 、r e m e n ti nd t l bm i s sn u m b e r sa n d1 3 6 r e d u c ew i t hl 2c a c h em i s sn u n l b e r s t h i r d l y ，ad y n a m i cp r e f e t c ho p t i m i z a t i o ni sa d o p t e db 勰e d0 nt h ea d 印t i v e 行a m e w _ o r k w 毫i n s t r u m e n t 8t h ep r o g r a mi nj i tc o m p i l e rf o r1 0 a da d d r e s sp r o f l l i n g ，d e t e c t st h es t r i d ep a t t e r i l sp e r i o d i c a l l ya tr u n t i m e w h e nas t r i d ep a t t e r ni s d i s c o v e r e d ，、阮i n j e c t sp r e f e t c hi n s t r u c t i o na n dr e m o v e st h ei n s 乞r u m e n t a t i o ne f - f e c t t h ek e yp o i n t si nt h ed e s i g na r et h et r a d e o 凰b e t 、张e np r e f e t c h i n ga c c u r a c y a n dr u n t i m eo v e r h e a d i no r d e rt or e d u c et h er u n t i m eo 、r e r h e a d ，、 ，ed e 、，e l o p e d t e c h n i q u e st or e m o v et h er e d u n d a n ti n s t r u m e n t a t i o 璐，c o n t r o lt h ep r e f e t c hi n s t r u c t i o n 嫡e c t i o i l s ，a n dd i s a b l et h eu s e l e s si 璐t r u m e n t a t i o n o u rp a t t e r nd e t e c _ t i o ni sl i g h t - 、桃i g h t e dt h a t 、怕u s eas l i d i n gw i n l o wt of i l t e rt h et r a c ei n f o r m a t i o n f o rr u n t i m ea n a l y s i s ，a n dw eu s eas t r i d ef r e q u e n c ya r r a yt h a tc o v e r ss t r i d er a n g e b e t w e e n 一6 4a n d6 4 f i n a l i y t h ee x p e r i m e n 七a le v a l u a t i o n ss h o wt h a tt h ep r e f e t c h o p t i m i z a t i o nc a ns p e e d u ps p e c j b b 2 0 0 5 、s p e c j v m 9 8a n dd a c a p ob e n c h m a r k s u pt o1 8 1 ，w i t ha na v e r a g eo f7 1 5 a tt h es a m et i m e ，t h em a 撕m a lr u n t i m e o v e r h e a di sl e s st h a n4 ，a n dt h em e m o r yo v e r h e a di 8n e g l i g i b l e f i n a l l y ，w ec o n l b i n e do b j e c ta m n i t yw i t hg a _ r b a g ec o u e c t i o n f i r s t l y ，、 伦u s e h 缸d w a u r ep e r f o r m a n c ea n a l y z e rt oi o c a t ed e l e q u e n to b j e c t s ，f i i l do u tt h ea 伍n - i t yb e t 、e e nt h e m ，a n db u i l da na 伍n i t yg r a p h g a r b a g ec o l l e c t i o nr e f e r sa 伍n i t y g r a p h ，a n dt h er e l a t e do b j e c t sw d u l db ec o l o c a t e d ，s u c hd e s i g nc a ni m p r o v et h e l o c a t i o nb e t w e e nd e l e q u e n to b j e c t s ，b e c a u s er e l a t e do b j e c t s 龇ea l w a y sa c c e s s e d s e q u e n t l y t h ee x p e r i m e n t a le v a l u a t i o n ss h o wt h eg 盯b a g ec o l l e c t i o nb a s e do n o b j e c ta m n i t yc a ns p e e d u ps p e c j b b 2 0 0 5 、s p e c j v m 9 8a n dd a c a p ob e n c h m a r k s u pt o4 9 ，w i t ha na e r a g eo f3 4 a tt h es a m et i m e ，t h eo v e r h e a do f h a r d w a r em e t h o di s0 4 7 f i n a l l y ，w ei m p l e m e n t e dp r e f e t c ho p t i m i z a t i o no ni t ，t h e r e s u l ts h o w st h a tt h ep e r f o r m a n c ew o n tb er e d u c e d ，f o rs o m ea p p l i c a t i o n s ，t h e a b s t r a c t v p e r f o r m a n c e 盯eb e t t e r k e y w o r d s ：j v m ，f r a m e w o r ko fa d 印t i v eo p t i m i z a t i o n ，g a r b a g ec o l l e c t i o n ，o b j e c tl o c a l i t y ，p r e f e t c h ，a m n i t y 插图 1 1 c h e n e y 的拷贝g c 算法 1 5 1 2 m o o n 的近似深度优先拷贝算法 1 6 1 3w i l s o n 的层次分解拷贝算法1 8 2 1 h a r m o n yv m 的工作机制 2 6 2 2d r l 、，m 的主要组成部分3 1 3 1 已有的信息统计框架3 6 3 2 堆访问的分布3 7 3 3 相关对象访问的例子3 8 3 4 自适应的动态优化框架3 9 3 5n a u c e 缓冲区的结构3 9 3 6 统计对象信息的代码4 0 3 7 状态转换图4 1 3 8 自适应动态优化框架的开销v s 传统插桩法的开销 4 4 4 1 基于半空间的节点复制收集4 8 4 2 堆的布局5 1 4 3 滑动标记缩并算法：传统算法v s d r l 、，m 中的算法 5 2 4 4 快速的滑动标记缩并算法5 5 4 5 多个g c 线程的处理策略5 6 4 6 动态负载平衡机制5 7 4 7 各种标记所并算法的g c 时间比较 5 8 4 8 快速的滑动标记缩并算法的加速比5 9 4 9 快速的滑动标记缩并算法的d t l b 和l 2c a c h e 失效率的改善。 6 0 4 1 0 标记阶段时间v s 缩， ：阶段时间的最大值 6 1 j a 、，a 虚拟机的自适虑动态优化 4 1 1 快速的滑动标记缩并算法g ct i m e 的可缩放性比较6 1 5 1 导致频繁c a c h e 失效的代码片段 6 9 5 2 自适应预取优化算法中使用的数据结构 7 0 5 3 预取指令的插入7 1 5 4 自适应动态预取优化算法流程图 7 2 5 5 优化后的代码7 3 5 6 利用循环展开来减少冗余的插桩和预取 7 4 5 7 预取带来的性能提升 7 6 5 8 相关的对象访问的分布 7 7 5 9 预取前后内存的性能比较7 7 5 1 0 自适应预取优化算法的开销v 8 传统插桩法的开销 7 8 5 1 1 自适应预取优化算法的空间开销 7 9 5 1 2 各种步长的分布图8 0 6 1 哈希表的结构图8 3 6 2 对象晕排流程图8 5 6 3 关系图 8 7 6 4 图6 1 对应的对象亲缘图8 8 6 5 基于对象亲缘关系的快速滑动标记缩并算法8 9 6 6 年轻代的布局9 1 6 7 性能对比图9 2 6 8d t l b 失效率与c a c h e 失效率对比9 3 6 9 频繁c a c h e 失效的类型统计 9 4 6 1 0 频繁c a u c h e 失效类型引起的c a c h e 失效与标准运行下它们引起 的c a c h e 失效对比( 一) 9 5 6 1 1 频繁c a c h e 失效类型引起的c a c h e 失效与标准运行下它们引起 的c a c h e 失效对比( 二) 9 6 6 1 2 对象重排优化对预取优化的影响9 7 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 撕从 作者签名：刍至盗 渺年彦月厂日 第一章绪论 虚拟机的设计思想在上个世纪6 0 年代被i b m 公司应用在v m 3 7 0 操作系统。 后来，s m a l l t a u 【将虚拟机发扬光大。此外，很多公司如i n t e l 、s u n 等，都开始研 究并开发虚拟机。ja ：v a 语言的出现，使得虚拟机被进一步推广。通过使用虚拟 机，移植变得方便简洁，只需为不同的架构定制相应的虚拟机平台，而基于其上 的应用程序都不需更改。同时由于虚拟机的隔离作用，也使得基于虚拟机之上 的应用程序更加安全。 虚拟机提供了一个动态编译环境，和传统的静态编译的二进制代码相比， 它存在很多优势：代码的可移植性、安全性、自动化的内存管理和线程管理技 术、动态类加载等等。这些方便而又强大的功能大大提高程序员的t 作效率，因 此类新型语言被，“泛使用。但是，虚拟机中的这些动态特性使得一些传统的 静态编译技术不再适用，因此科学家们一直在探索新的编译技术，使得在虚拟 机上能够获得更好的性能。 由于缺乏运行时信息，静态编译采用较为复杂的全局分析而并不能得到理 想的结果。虚拟机的介入使得编译及优化发生在程序运行时，因此工业界一直 致力于发展自适应优化技术，希望能够利用程序运行时的动态信息来指导对程 序进行何种优化。在虚拟机迅速发展的三十年中，自适应优化技术可以分成四 大类： 1 ) 选择性优化技术：在何时对程序的何部分进行优化； 2 ) 反馈指导优化的p r 娟l i n g 技术：如何获得细粒度的p r 曲l i n g 信息； 3 ) 反馈指导的代码生成技术：如何利用p r o f i l i n g 信息使得动态编译器生成 具有合理布局的代码： 4 ) 其他的反馈指导优化技术：如何利用p r o f i l i n g 信息来提高程序的性能； 1 1自适应优化技术 自适应优化技术伴随软件业而产生，以下五代产品可以看作是它发展 过程中的里程碑：l i s p 解释器 m c c a r t h y 7 8 】、a d 印t i v e f 0 r t r a n 【h a n s e n 7 4 】、s m a u t a l k 【d e u t s c h 8 4 】、s e l f ( c h a m b e r s 9 1 1 h o l z l e 9 4 和j a v a 【a r n o l d 0 0 1 。 2 j a 、，a 虚拟机的自适应动态优化 l i s p 解释器是最早被推广的虚拟机，它支持自动内存管理、自动加载程序 等强大的功能。a d a p t i v ef o r t r a n 第一次深入地对动态的自适虑优化技术进行 探索，【h a n s e n 7 4 1 中详细地描述了自适应优化技术将要面临的种种挑战以及对 应的策略。1 9 8 4 年，d e u t s c h 和s c h i 珏m a n 提出他们设计的虚拟机s m a l l t a l k ，这是 第一个现代化的虚拟机，它不同于以前解释执行的虚拟机，而是采用先进的即 时编译技术。s e l f 继续s m a l l t a l k 未完成的事业，进一步开发出更先进的编译 技术，有很多技术仍被现在的虚拟机所使用。1 9 9 5 年s u n 公司提出j a v a 语言以 及j a v a 虚拟机，它继承了先驱们，诸如s m a l l t a l k 和s e l f 中优秀的技术，将虚拟 机推向主流市场，被t 业界广泛采用。随后微软公司也提出n e t 平台，再一次 将虚拟机技术推向巅峰。 1 1 1 选择性优化技术 由于虚拟机运行在动态环境下，对程序在何时进行何种优化显得尤为重要， 现有的选择性优化技术应用在解释器、即时编译器以及两者结合的系统中。 a 解释器( i n t e r p r e t e r ) 解释执行是最简单、直观的运行方式，最早为人所知的解释器有l i s p ，其 后又出现a p l f p e n f i e l d 7 5 1 、s n o b o l f g r i s 、 的l d 7 8 1 、b c p l f r i c h a r d s 7 7 1 和p a s c a l - p 【n o r i 7 5 1 。当今被广泛使用的脚本语言p e r l p e r l l 和p y t h o n p y t h o n l ，以及强大 的数学应用软件m a t l a b m a t l a b l 也都是基于解释执行之上。 解释器开发和测试难度比较低，易于编写、调试和移植，并且系统简单，代 码量少。在存储空间有限的设备中，解释器具有一定的优势。由于解释器逐条 对代码进行解释，导致程序性能很低，在由性能作为主导的产品中，解释器已经 不能再解决这些问题，因此人们提出即时编译器。 b 即时编译器( j u s t - i n - t i m ec o m p i l e r ) 即时编译技术指的是在程序运行之前对其进行编译，这种方式消除了解释 执行带来的额外开销，大大提高了程序运行的速度。即时编译器对所有的代码 都进行编译，冈此需要额外的空间来保存编译好的代码，同时编译在运行时进 行，这将导致运行时间的增加。尽管如此，即时编译器获得的性能大大优于解 释器的性能，冈此被大家j | 泛使用f d e u t s c h 8 4 1 f c h a m b e r s 9 0 1 。 很快研究者们发现对于大部分程序而言，只有2 0 的代码i 吁用大部分运行 时间，因此在运行时对另外8 0 代码进行优化并小总是有用。于是他们提出采 用解释器和即时编译器结合的系统f h o l z l e 9 6 1 。 第一章绪论 3 c 选择优化系统( s e l e c t i v eo p t i m i z a t i o ns y s t e m ) 该系统同时采用解释器和即时编译器，最开始采用解释执行的方式，随着 代码的执行发现某段代码被频繁执行，便唤醒即时编译器对它进行重新编译优 化。对于一个选择优化系统而言，它需具备以下三个组成部分： 1 ) 发现程序热点的p r o l i l i n g 部件； 2 1 对热点进行何种优化的决策部件； 3 ) 对热点进行优化的动态编译部件； 这些部件均在程序运行的过程中被执行，因此为了保证性能，必须将它们 的开销降至最低。 对于p r 0 6 l i n g 机制而言，人们往往有两种选择来获得粗粒度的p r o f i l i n g 信息： 计数器机制和采样机制( s a m p l i n g ) 。计数器机制即对应每个方法设置4 个相应 的计数器，并且用它们来记录相应方法被调用的次数，或者是方法中循环被执 行的遍数。采样机制则是周期性地中断程序的执行，同时记录调用栈顶的方法， 采样的周期通常采用外部时钟，这样能够使得开销足够的低，但是增加了采样 的不确定性，使调试变得困难。基于收集到的p r 曲l i n g 信息，决策部件决定对某 个方法或者是某段代码序列进行优化，有些系统采用不同的阈值来决定对应级 别的优化。 1 1 2 反馈指导优化的p r o n l i n g 技术 以往有很多研究通过离线的p r o 丘l e 信息来指导静态编译器进行编译 s m i t h o 0 1 ，静态编译无法根据程序的实际行为采用不同的优化策略，而虚拟机提供的 运行时系统使得自动化的反馈指导优化成为可能，它通过发掘运行时信息来克 服以往静态编译技术的不足，并且能够根据条件的变化动态地选择优化策略。 为了使反馈指导优化有效，研究者们面临着种种挑战【a r n o l d 0 5 】，比如：如何补 偿收集、处理p r o f i l i n g 信息，以及对程序进行优化带来的额外开销等等。下面将 要描述的是当今虚拟机中采用最多的p r o f i l i n g 技术。 a 硬件性能分析器( h 缸d w 龃ep e r f o r m a n c ea n a l l y z e r ) 许多微处理器都提供硬件工具来帮助程序员们获得处理器级别的事件，我 们称之为硬件性能分析器。它们功能强大，能够收集丰富的事件，但是却很少 被虚拟机技术所采用。硬件性能分析器之所以不被看好，因为将底层的事件映 4 j a 、，a 虚拟机的自适应动态优化 射到高级语言非常困难。如何合理地利用硬件性能分析器来帮助动态编译和优 化，这一工作对于虚拟机设计者而言是一个巨大的挑战。 b 采样法( s a m p l i n g ) 采样法定期地对某些事件进行统计，这使得它的开销能够被系统所容忍。 但是这也使得采样法只能收集到粗粒度的p r o f i l i n g 信息，对于某些优化而言，这 些粗粒度的信息已经足够，比如内联优化，它需要定期对调用栈顶进行采样，如 果发现某个方法在栈顶出现的次数超过阈值，那么便采用内联优化将其进行内 联 h o l z l e 9 6 【h a z e l w o o d 0 3 。 但是有更多的优化需要的是细粒度的p r o f i l i n g 信息，比如基本块执行频率 或者是历史值统计，采样法无法得到它们。 c 插桩法( i n s t r u m e r l t a t i o n ) 插桩法通过在程序中插入些代码来获得p r o f i l i n g 信息，它能够收集到很 多细粒度的p r o f i l i n g 信息。有很多研究者通过插桩法来获得离线的p r o f i l i n g 信息， 从而指导静态编译器进行编译优化 p e t t i s 9 0 】 c h a n 9 9 1 【h w u 9 3 “c o h n 0 0 】 m o c k 0 0 】 h a z e l w o o d 0 3 同时研究结果也表明插桩法将引入3 0 一1 0 0 0 0 的运行时开销， 如果要在虚拟机中使用插桩法，必须要降低它们的开销。 要降低插桩代码引起的开销，无非是减少它们运行的时间。有一些研 究者们选择对未优化的代码或者是解释执行的代码( 后面统称为未优化代 码1 进行插桩，一_ 日发现热点代码，便对它进行优化，插桩代码将不再被执 行f p a l e c z n y 0 1 1 s u g a n u m a 0 1 1 。这个技巧有如下优点：1 ) 对未优化的代码进行插 桩，插桩的开销相对而言不会那么大；2 ) 即时编译器根据p r o f l l i n g 信息能够进 行反馈指导优化；3 ) 工程实现简单。由于被优化的代码不再包含插桩的代码， 这将导致无法对代码进行进一步地优化。 d 采样插桩法( s a m p l i n ga n di n s t r u m e n t a t i o n ) 从上文中，我们看出采样法和插桩法有各自的优点和缺点，因此有些研究者 们提出将采样法和插桩法结合起来收集p r o f i l i n g 信息 a r n o l d 0 1 【h i r z e l 0 1 a r n o l d 0 2 】 c h i l i m b i 0 2 】，即为每个需要插桩的代码准备两份拷贝，一份为源代码，另一 份为插桩后的代码，这两份代码将被交替地执行。采样插桩法已经被一些商业 虚拟机采用。 第一章绪论5 1 1 3 反馈指导的代码生成技术 在本小节中，我们总结当今虚拟机中常用的反馈指导的代码生成技术，并 且更加关注的是即时编译器中使用的相关技术。反馈指导的代码生成技术主要 包括：内联、代码布局、指令调度、代码多版本等等。 a 内联 内联指的是在函数被调用处将函数体展开，多年的研究表明内联优 化是一种重要的编译优化技术，在面向对象的程序中更是如此。但是内 联优化会使得代码大小以及编译时间有所增加。研究者们在内联优化带 来的改进与其代价之间进行权衡，他们认为利用反馈信息驱动的内联优 化算法能够将大部分热点的函数调用进行内联，同时编译开销不会很大， 数据表明根据反馈信息进行的内联优化比普通的内联优化性能要好1 0 一1 7 【a r n o l d o o 】【c i e r n i a k o o 】【a r n o l d 0 2 】【s u g a n u m a 0 2 儿a d l - 7 r a b a t a b 出0 3 】。 基于以上结论，j i k e 8r v m 在代价利益( c o s t b e n 胡t ) 模型中增加内联优 化，对于热点调用处使用内联优化 a r n o l d 0 2 】。s u g a n u m 通过对热点方法进行 插桩从而获得动态调用图，并且根据它们来指导内联【s u g a n u m a 0 2 】。 b 代码布局 代码布局常用的代码生成技术，通过对代码进行蕈布局来改善代码块的局 部性，同时可以提高分支预测的效率。 p e t t i s 和h a n s e n 的研究首次证明了代码布局优化对程序性能具有定的影 响，良好的布局能够大大改善程序的性能【p e t t i s 9 0 】。【a r n o l d 0 2 】设计了一种自上 向下的代码布局方式，获得一定的性能提升。【a d l - t a b a t a b a i 0 3 】在a r n o l d 的基础 上，将代码分成热部分和冷部分，热部分依次放置，从而改善代码的局部性。 c 指令调度 指令调度优化通过调整指令之间的顺序来最大化每次可以同时发射的指 令数。i m p a c t 编译器利用离线得到的p r o f i l i n g 信息来指导指令调度，获得一 定的效果c h a n 9 9 1 1 c h e n 9 4 】。指令调度是否有效很大程度上取决于当前处理器 采用的体系结构及其实现。对于乱序执行的体系结构，指令的调度已经很不 错。而对于顺序执行的处理器而言，比如i t a n i u m ，指令调度仍有很大的优化空 间 d u l o n 9 9 8 】【i a 6 4 】。 d 代码多版本 6 j a 、，a 虚拟机的自适应动态优化 编译器有时会为段代码产生多个版本的二进制序列，并在运行时根据实 际情况选择运行哪个版本。 最早代码多版本是在静态编译中提出的，它们只能根据编译时得到的信息 来产生。f b y l e r 8 7 1 基于f o r t r a n 编译器进行修改，使得它可以为f o r t r a n 中的循环 产生多个版本，在运行过程中根据循环边界、循环变量的递增关系以及访问的 模式来选择最佳的版本。类似的技术也曾经运用在j a v a 编译器中，在j a v a 中，必 须保证数组的安全访问，冈此在循环中每次都需要对数组访问进行检查，开销 很大，f a r t i g a s 0 0 3 提出为循环生成两个版本，。1 个是安全版本，也就是说在该版 本中数组访问肯定不会越界，另个则是非安全版本，在安全版本中，编译器还 可以进行更加激进的优化。 随着虚拟机的发展，代码多版本优化逐渐被采用。最简单的做法就是在需 要多版本代码的地方实现动态打补丁机制( d y n a m i cp a t c h i n g ) ，在打入补丁之 前进行条件判断，根据判断的结果来决定执行哪个版本的代码，运行时检测会 有一定的开销。a r n o l d 则提出t h i ng u 盯d s 机制将条件判断简化，即用一些快速 的布尔法则替换原来昂贵的条件检测f a r n o l d 0 2 1 。 e 其他 随着自适应优化技术的发展，当今产品级的虚拟机中已经融汇了各种各样 的反馈指导优化技术，研究者利用运行时反馈的p r o f i l i n g 信息米指导各种优化。 但是大部分优化很可能是针对某类应用而设计的，而对其他不同种类的应用可 能没有任何效果。 除了前面提到的内联、代码重排等优化之外，a r n o l d 也曾经利用收集到的 循环刚边信息来指导循环展开优化，另外，他们也利用反馈信息来指导寄存器 分配优化，但是效果小太明显 a r n o l d 0 2 】。h o t s p o t 服务器端的编译器中也采用 类似的反馈指导优化，利用h o t s p o t 的解释器收集方法执行次数、l 口j 边执行次数 以及分支频率，并且利用这些信息来指导包括内联、全局代码重排在内的各种 优化。 在早期研究中，有很多利用离线( o m i n e ) 时收集到的p r 曲l e 信息来指导软 件预取 l u l ( 9 6 】 w u 0 2 】。而近年来，虚拟机研究者提出利用动态反馈的信息来 指导线上( o n l i n e ) 预取技术。i n a g a k i 提出一种低开销的p r o f i l e 机制来帮助循环 中的数据进行预取 i n a g a k i 0 3 】。a d l 一t a b a t a b a i 提出种机制来帮助链表中的 频繁c a c h e 失效数据进行预取，他们利用硬件性能计数器来收集频繁c a c h e 失 8j a 、，a 虚拟机的自适应动态优化 渐进垃圾收集不同，并发垃圾收集使用独立的收集线程和用户线程并发地执行。 这种垃圾收集通常被使用在拥有多处理器的系统中。通过并发的执行，垃圾收 集系统将不会中断用户程序的执行，垃圾收集和用户程序通过操作系统进行调 度。 过去研究者们都在单处理器上研究垃圾收集算法，随着现代处理器技术的 发展，多处理器的计算机被广