Java的延伸式逃脫分析

Extended Escape Analysis for Java

洪資涵(Tzu-Han Hung)

指導教授 ： 陳俊良

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00526

摘要

Java是一個逐漸普及的程式語言。Java的特色之一為其物件導向(object-oriented)的觀念：物件是程式員所操作的基本單位。對Java執行時期(runtime system)而言，物件是依程式員的需求來配置，但是Java並沒有提供任何方式來讓程式員自行清除已配置的物件。事實上，Java依賴執行時期的垃圾收集器(garbage collector)來進行空間的回收。

為了克服垃圾收集演算法的高代價，有兩項重要的技術已經被討論過。首先是對於物件進行分類與分離，也就是說，物件可依其生存期(lifetime)來做分類，並且對不同類的物件分開使用不同的配置與回收規則。其次是記憶體管理的協同運作方法，也就是說，一個靜態或是動態的編譯器可先對程式碼進行分析，產生關於由程式配置出來的物件資訊，執行時期便可依此資訊來對記憶體進行更好的利用。

這篇論文利用了前述的兩項技術，並且延伸了已經被研究過的逃脫分析(escape analysis)。目前既有的逃脫分析皆試著分辨出方法局部(method-local)的物件與非方法局部(method-nonlocal)的物件，並將方法局部的物件配置在堆疊(stack)上，因為它們的生存期是被配置它們的方法所限制住的。我們進一步提出延伸式逃脫分析(extended escape analysis)，試著決定部份非方法局部物件的生存期上限，而且同樣地將之配置於堆疊上。其中關鍵的想法在於，我們找出一個物件究竟能逃脫到多遠，並依此來確定它的生存期上限。這些工作都是由一個靜態的編譯器來完成。對於執行時期而言，它能將這些已預先判斷好生存期上限的物件配置於堆疊而非於累堆(heap)，如此便能減輕垃圾收集器的負擔，因為這些物件會按照堆疊順序，也就是先進後出(first-in-last-out)的規則，來達成配置與回收的效果，而不需要垃圾收集器的介入。

關鍵字

延伸式逃脫分析 ； 爪哇

並列摘要

Java is a programming language with increasing popularity. Being object-oriented, objects are the basic elements that a programmer can manipulate. For the runtime system, objects can be allocated on demand by programmers, but there is no way that one can explicitly deallocate objects on the heap. In fact, Java depends on the runtime garbage collection to handle space reclamation.

To cope with the costly garbage collection problem, two essential techniques are discussed. One is the classification/separation of objects, i.e., objects are classified according to their lifetimes and are separated with different allocation/deallocation policies. The other is the cooperative approach for memory management, i.e., a compiler (either static-time or dynamic-time) analyzes program code and produces information about objects generated in the program, and then the runtime system can use the information to make better use of heap memory space.

This thesis exploits the previous two techniques and extends the escape analysis that has been studied before. All existing escape analyses try to separate method-local objects from method-nonlocal ones, and stack-allocate method-local objects since their lifetimes are bounded by their allocating methods. We further propose the extended version of escape analysis; it tries to determine the upper bound of lifetime for some method-nonlocal objects and still stack-allocates them. The key idea is that we find how far an object can escape and how long it can be reachable; these are done by a static-time compiler. For the runtime system, it allocates objects with pre-determined lifetime on stack rather than on heap, and this can lessen the burden of garbage collector since those objects can be allocated/deallocated in the stack manner (first-in-last-out) without the intervention of garbage collector.

並列關鍵字

Extended Escape Analysis ； Java

參考文獻

[3] Ken Arnold, James Gosling, and David Holmes. The Java Programming Language, third edition. Addison-Wesley, June 2000.

[5] Bruno Blanchet. Escape Analysis for Object Oriented Languages: Application to Java. In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 20-34, June 1999.

[7] Jong-Deok Choi, et al. Escape Analysis for Java. In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 1-19, June 1999.

[8] Jong-Deok Choi, et al. Stack Allocation and Synchronization Optimizations for Java using Escape Analysis. In ACM Transactions on Programming Languages and Systems, volume 25, issue 6, pages 876-910, November 2003.

[11] Robert Fitzgerald, et al. Marmot: An Optimizing Compiler for Java. Technical Report MSR-TR-99-33, June 1999.