Hybrid java compilation of Just-in-Time compilation and Ahead-of-Time compilation for embedded systems

다국어 초록 (Multilingual Abstract)

Many embedded Java software platforms execute two types of Java classes: those installed statically on the client device and those downloaded dynamically from service providers at runtime. For higher performance, it would be desirable to compile static Java classes by ahead-of-time compiler (AOTC) and to handle dynamically downloaded classes by just-in-time compiler (JITC), providing a hybrid compilation environment. We propose a hybrid Java compilation approach and performs an initial case study with a hybrid environment, which is constructed simply by merging an existing AOTC and a JITC for the same JVM. Contrary to our expectations, the hybrid environment does not deliver a performance, in-between of full-JITC’s and full-AOTC’s. In fact, its performance is even lower than full-JITC’s for many benchmarks. We analyzed the result and found that a naive merge of JITC and AOTC may result in inefficiencies, especially due to calls between JITC methods and AOTC methods. We also observed that the distribution of JITC methods and AOTC methods is also important, and experimented with various distributions to understand when a hybrid environment can deliver a desired performance.
The Android Java is to be executed by the Dalvik virtual machine (VM), which is quite different from the traditional Java VM such as Oracle’s HotSpot VM. That is, Dalvik employs register-based bytecode while HotSpot employs stack-based bytecode, requiring a different way of interpretation. Also, Dalvik uses trace-based just-in-time compilation (JITC), while HotSpot uses method-based JITC. Therefore, it is questioned how the Dalvik VM performs compared the HotSpot VM. Unfortunately, there has been little comparative evaluation of both VMs, so the performance of the Dalvik VM is not well understood. More importantly, it is also not well understood how the performance of the Dalvik VM affects the overall performance of the Android applications (apps). We make an attempt to evaluate the Dalvik VM. We install both VMs on the same board and compare the performance using EEMBC benchmark. In the JITC mode, Dakvik is slower than HotSpot by more than 2.9 times and its generated code size is not smaller than HotSpot’s due to its worse code quality and trace-chaining code. We also investigated how real Android apps are different from Java benchmarks, to understand why the slow Dalvik VM does not affect the performance of the Android apps seriously.
We proposes a bytecode-to-C ahead-of-time compilation (AOTC) for the DVM to accelerate pre-installed apps. We translated the bytecode of some of the hot methods used by these apps to C code, which is then compiled together with the DVM source code. AOTC-generated code works with the existing Android zygote mechanism, with correct garbage collection and exception handling. Due to off-line, method-based compilation using existing compiler with full optimizations and Java-specific optimizations, AOTC can generate quality code while obviating runtime compilation overhead. For benchmarks, AOTC can improve the performance by 65%. When we compare with the recently-introduced ART, which also performs ahead-of-time compilation, our AOTC performs better.
We cannot AOTC all middleware and framework methods in DTV and android device for hybrid compilation. By case study on DTV, we found that we need to adopt AOTC enough methods and reduce method call overhead. We propose AOTC method selection heuristic using method call chain. We select hot methods and call chain methods using profile data. Our heuristic based on method call chain get better performance than other heuristics.

목차 (Table of Contents)

• Chapter 1 Introduction 1
• 1.1 The need of hybrid compilation 1
• 1.2 Outline of the Dissertation 2
• Chapter 2 Hybrid Compilation for Java Virtual Machine 3
• 2.1 The Approach of Hybrid Compilation 3
• 2.2 The JITC and AOTC 6
• 2.2.1 JVM and the Interpreter 7
• 2.2.2 The JITC 8
• 2.2.3 The AOTC 9
• 2.3 Hybrid Compilation Environment 11
• 2.4 Analysis of the Hybrid Environment 14
• 2.4.1 Call Behavior of Benchmarks 14
• 2.4.2 Call Overhead 15
• 2.4.3 Application Methods and Library Methods 18
• 2.4.4 Improving hybrid performance 20
• 2.4.4.1 Reducing the JITC-to-AOTC call overhead 20
• 2.4.4.2 Performance impact of the distribution of JITC methods and AOTC methods 21
• Chapter 3 Evaluation of Dalvik Virtual Machine 23
• 3.1 Android Platform 23
• 3.2 Java VM and Dalvik VM 24
• 3.2.1 Bytecode ISA 25
• 3.2.3 Just-in-Time Compilation (JITC) 27
• 3.3 Experimental Results 32
• 3.3.1 Experimental Environment 33
• 3.3.2 Interpreter Performance 34
• 3.3.3 JITC Performance 37
• 3.3.4 Trace Extension 43
• 3.4 Behavior of Real Android Apps 44
• Chapter 4 Ahead-of-Time Compilation for Dalvik Virtual Machine 51
• 4.1 Android and Dalvik VM Execution 51
• 4.1.1 Android Execution Model 51
• 4.1.2 Dalvik VM 51
• 4.1.3 Dexopt and JITC in the Dalvik VM 53
• 4.2 AOTC Architecture 54
• 4.3 Design and Implementation of AOTC 56
• 4.3.1 Dexopt and Code Generation 56
• 4.3.2 C Code Generation 56
• 4.3.3 AOTC Method Call 58
• 4.3.4 Garbage Collection 61
• 4.3.5 Exception Handling 62
• 4.3.6 AOTC Method Linking 63
• 4.4 AOTC Code Optimization 64
• 4.4.1 Method Inlining 64
• 4.4.2 Spill Optimization 64
• 4.4.3 Elimination of Redundant Code 65
• 4.5 Experimental Result 65
• 4.5.1 Experimental Environment 66
• 4.5.2 AOTC Target Methods 66
• 4.5.3 Performance Impact of AOTC 67
• 4.5.4 DVM AOTC vs. ART 68
• Chapter 5 Selecting Ahead-of-Time Compilation Target Methods for Hybrid Compilation 70
• 5.1 Hybrid Compilation on DTV 70
• 5.2 Hybrid Compilation on Android Device 72
• 5.3 AOTC for Hybrid Compilation 74
• 5.3.1 AOTC Target Methods 74
• 5.3.2 Case Study: Selecting on DTV 75
• 5.4 Method Selection Using Call Chain 77
• 5.5 Experimental Result 77
• 5.5.1 Experimental Environment 78
• 5.5.2 Performance Impact 79
• Chapter 6 Related Works 81
• Chapter 7 Conclusion 84
• Bibliography 86