Cyclic reference counting by typed reference fields

Reference counting strategy is a natural choice for real-time garbage collection, but the cycle collection phase which is required to ensure the correctness for reference counting algorithms can introduce heavy scanning overheads. This degrades the efficiency and inflates the pause time required for garbage collection. In this paper, we present two schemes to improve the efficiency of reference counting algorithms. First, in order to make better use of the semantics of a given program, we introduce a novel classification model to predict the behavior of objects precisely. Second, in order to reduce the scanning overheads, we propose an enhancement for cyclic reference counting algorithms by utilizing strongly-typed reference features of the Java language. We implement our proposed algorithm in Jikes RVM and measure the performance over various Java benchmarks. Our results show that the number of scanned objects can be reduced by an average of 37.9% during cycle collection phase.     

Jikes RVM动态编译技术分析与性能评测

随着Java语言的广泛应用,Java虚拟机的性能越来越受到人们重视,而虚拟机的动态编译技术是影响其性能的重要因素.Jikes RVM使用Java语言实现了一个Java虚拟机.首先分析了Jikes RVM的3个主要动态编译器的结构及其涉及的关键编译技术,包括基线编译、优化编译和自适应编译,然后利用SPECjvm Client98对Jikes RVM和Sun JVM的动态编译性能进行了测试和比较.测试结果显示,Jikes RVM的性能和Sun JVM性能基本相同,最后针对Jikes RVM的不足提出了改进Jikes RVM 编译器的方法.     

Efficiently Adapting Java Binaries in Limited Memory Contexts

This paper presents a compilation framework that allows executable code to be shared across different Java Virtual Machine (JVM) instances. Current compliant JVMs for servers are burdened with large memory footprints (because of the size of the increasingly complicated compilers) and high startup costs, while compliant JVMs for embedded devices typically rely on interpretation. This paper describes a quasi-static approach that allows execution of a read-only version of the code, enabling compiled Java binaries to be embedded in ROM in an embedded environment or shared across multiple applications in a server environment. We have implemented this approach in the Quicksilver quasi-static compiler for the Jikes RVM (Jikes Research Virtual Machine). On the SPECjvm98 benchmark suite, our approach gives writable memory space savings of between 82–89% over that of our previous (non-sharable, non-ROMable) quasi-static approach, while delivering performance that is typically within 1–7% of that approach, and is competitive with the performance of the Jikes RVM adaptive optimization system.     

Yama: a scalable generational garbage collector for Java in multiprocessor systems

The current state-of-the-art generational garbage collector pauses all the program threads when it performs young and old generation garbage collection. As the number of program threads increases, the delay due to garbage collection also increases, thus restricting the scalability of the collector. In order to improve the scalability and reduce the pause time, an on-the-fly generational garbage collector called Yama is proposed for multiprocessor systems. This uses the on-the-fly deferred reference counting in the young generation and the DLG (Doligez Leroy Gonthier) on-the-fly mark and sweep garbage collector in the old generation. We have proposed and experimented with two novel variations of the on-the-fly deferred reference counting called Chitragupt1 and Chitragupt2 in the young generation. Yama does not pause all the application threads simultaneously. An adaptive tenuring policy based on object reference count and survival rate is also proposed. Yama has been implemented in the IBM Jikes RVM (research virtual machine). The above claims are supported with experimental results for standard benchmark programs. The results show that Yama has an extremely low pause time in both the young and the old generation. The pause time reduction results in better response times for the user programs.     

Quantifying the Benefits of SSA-Based Mobile Code

High-performance just-in-time compilers for Java need to invest considerable effort before actual code generation can commence. This is in part due to the very nature of the Java Virtual Machine, which is not well matched to the requirements of optimizing code generators. Alternative transportation formats based on Static Single Assignment form should theoretically be superior to virtual machines, but this claim has not previously been validated in practice. This paper revisits the topic and attempts to quantify the effect of using an SSA-based mobile code representation (IR) instead of a virtual-machine based one.To this end, we have integrated full support for a verifiable SSA-based IR into Jikes RVM, an existing Java execution environment. The resulting system is capable of loading and executing Java programs represented in either format, traditional JVM bytecode as well as the SSA-based representation, and it can even execute programs made up of a mixture of the two formats. In our implementation, the two alternative just-in-time compilation pipelines share a common low-level code generator.Performance results are encouraging and show simultaneous improvements in both compilation time and code quality relative to Jikes RVM's standard optimizing compiler for JVM class files. They support the hypothesis that SSA-based intermediate representations offer advantages in the context of just-in-time compilation.     

基于Java实现移动Agent强迁移的方法

对比分析了常见的移动Agent强迁移与弱迁移,提出一种基于Java实现移动Agent强迁移的方法.该方法基于IBMJikesRvm(Jikes research virtual machine(RVM))提供的RVM,利用OSR(on-stack replacement)捕捉运行堆栈的状态,实现了移动Agent强迁移.该方法不需要对源代码或字节码进行预处理,也不需要改变JVNI,具有很好的系统扩展性.     

基于插桩分析的Java虚拟机自适应预取优化框架

对堆上数据的频繁访问是Java程序的主要开销,为此,研究者们通过虚拟机收集堆上数据访问的信息,而后采用预取或垃圾收集来改进内存性能.常用的收集方法有采样法和插桩法,但二者无法同时满足细粒度和低开销的要求.针对这两个要求,提出基于插桩分析的虚拟机自适应预取框架,该框架通过插桩收集信息,并根据程序运行时的反馈自适应地调整插桩并进行预取优化.实验结果表明,自适应预取优化在Pentium 4上对SPEC JVM98和Dacapo有不同程度的提高,最高的达到了18.1%,而开销控制在4.0%以内.     

Integrating generations with advanced reference counting garbage collectors

We propose the use of generations with modern reference counting. A reference counting collector is well suited to collect the old generation, containing a large fraction of live objects that are modified infrequently. Such a collector can be combined with a tracing collector to collect the young generation, typically containing a small fraction of live objects. We have designed such a collector appropriate for running on a multiprocessor. As our building blocks, we used the sliding‐views on‐the‐fly collectors. We have implemented the new collector on the Jikes Research Java Virtual Machine (Jikes RVM) and compared it with the concurrent reference counting collector supplied with the Jikes RVM package. Our measurements demonstrate short pause times, retaining those of the original on‐the‐fly collectors and a gain in application throughput time. It turns out that a modern reference counting collector may benefit from the use of generations. Copyright © 2006 John Wiley & Sons, Ltd.     

无用内存单元自动回收过程的实时性问题研究

自动垃圾回收技术是Java的核心技术之一。垃圾回收耗时的不确定性阻碍了Java在实时过程中的应用。基于最大响应时间分析方法，利用Petri网分析了垃圾回收过程。通过Java虚拟机内部堆空间的合理划分和采用多线程同步技术可以降低垃圾回收中的停滞现象，提高Java程序的执行速度和实时性。     

Visualizing trace of Java collection APIs by dynamic bytecode instrumentation

Object-oriented languages are widely used in software development to help the developer in using dynamic data structures which evolve during program execution. However, the task of program comprehension and performance analysis necessitates the understanding of data structures used in a program. Particularly, in understanding which application programming interface (API) objects are used during runtime of a program. The objective of this work is to give a compact view of the complete program code information at a single glance and to provide the user with an interactive environment to explore details of a given program. This work presents a novel interactive visualization tool for collection framework usage, in a Java program, based on hierarchical treemap. A given program is instrumented during execution time and data recorded into a log file. The log file is then converted to extensible markup language (XML)-based tree format which proceeds to the visualization component. The visualization provides a global view to the usage of collection API objects at different locations during program execution. We conduct an empirical study to evaluate the impact of the proposed visualization in program comprehension. The experimental group (having the proposed tool support), on average, completes the tasks in 45% less time as compared to the control group (not provided with the proposed tool). Results show that the proposed tool enables to comprehend more information with less effort and time. We have also evaluated the performance of the proposed tool using 20 benchmark software tools. The proposed tool is anticipated to help the developer in understanding Java programs and assist in program comprehension and maintenance by identifying APIs usage and their patterns.     

Mobile JikesRVM: A framework to support transparent Java thread migration

Today’s complex applications must face the distribution of data and code among different network nodes. Computation in distributed contexts is demanding increasingly powerful languages and execution environments, able to provide programmers with appropriate abstractions and tools. Java is a wide-spread language that allows developers to build complex software, even distributed, but it cannot handle the migration of computations (i.e. threads), due to intrinsic limitations of many traditional JVMs. After analyzing the approaches in the literature, this paper presents our thread migration framework (called Mobile JikesRVM), implemented on top of the IBM Jikes Research Virtual Machine (RVM): exploiting some of the innovative techniques in the JikesRVM, we implemented an extension of its scheduler that allows applications to easily capture the state of a running thread and makes it possible to restore it elsewhere (i.e. on a different hardware architecture or operating system), but still with a version of the framework installed). Our thread serialization mechanism provides support for both proactive and reactive migration, available also for multi-threaded Java applications, and tools to deal with the problems of resource relocation management. With respect to previous approaches, we implemented Mobile JikesRVM without recompiling its JVM (Java Virtual Machine) source code, but simply extending JikesRVM functionalities with a full Java package to be imported when thread migration is needed.     

The case for Java as a programming language

Java code is organised around objects and classes rather than just functions, which enables the reuse of code in a very structured manner. Although Java syntax is similar to C++, it has not suffered from feature overload and is much less complex. In addition, some Java features, like garbage collection, are not entirely new but were pioneered by languages such as Lisp and Smalltalk. The paper discusses Java language features such as: inheritance, robustness, type safety, access modifiers, null pointer checking, array bounds checking, memory management, multithreading, garbage collection and security     

Platform‐independent profiling in a virtual execution environment

Virtual execution environments, such as the Java virtual machine, promote platform‐independent software development. However, when it comes to analyzing algorithm complexity and performance bottlenecks, available tools focus on platform‐specific metrics, such as the CPU time consumption on a particular system. Other drawbacks of many prevailing profiling tools are high overhead, significant measurement perturbation, as well as reduced portability of profiling tools, which are often implemented in platform‐dependent native code. This article presents a novel profiling approach, which is entirely based on program transformation techniques, in order to build a profiling data structure that provides calling‐context‐sensitive program execution statistics. We explore the use of platform‐independent profiling metrics in order to make the instrumentation entirely portable and to generate reproducible profiles. We implemented these ideas within a Java‐based profiling tool called JP. A significant novelty is that this tool achieves complete bytecode coverage by statically instrumenting the core runtime libraries and dynamically instrumenting the rest of the code. JP provides a small and flexible API to write customized profiling agents in pure Java, which are periodically activated to process the collected profiling information. Performance measurements point out that, despite the presence of dynamic instrumentation, JP causes significantly less overhead than a prevailing tool for the profiling of Java code. Copyright © 2008 John Wiley & Sons, Ltd.     

适用于分布式静态检测的Java代码依赖性分析技术

为满足Java静态分布式检测系统对Java程序源代码解耦分包的需求,解决代码检测单节点单进程运行耗时过长问题,实现分布式检测系统单任务多节点并行运行的目的,本文提出了Java源代码文件间依赖性分析方法.该方法以生成源代码文件抽象语法树的方式抽取文件文本信息,遍历分析抽象语法树,获取文件与其他源代码文件类依赖关系,再通过定位类所在的文件方式得到文件与文件之间依赖关系.同时,以无入边顶点的带环有向图表示文件间依赖关系图,本文提出的方法基于该图进行了文件间解耦的分析.最后,通过对示例程序逐步剖析的实验以及对数个开源工具源代码解耦拆分的实验,验证了本文提出的文件间依赖性分析方法的可行性.     

Unifying program slicing and concept assignment for higher-level executable source code extraction

Program slicing and concept assignment have both been proposed as source code extraction techniques. Unfortunately, each has a weakness that prevents wider application. For slicing, the extraction criterion is expressed at a very low level; constructing a slicing criterion requires detailed code knowledge which is often unavailable. The concept assignment extraction criterion is expressed at the domain level. However, unlike a slice, the extracted code is not executable as a separate subprogram in its own right. This paper introduces a unification of slicing and concept assignment which exploits their combined advantages, while overcoming these two individual weaknesses. Our ‘concept slices’ are executable programs extracted using high-level criteria. The paper introduces four techniques that combine slicing and concept assignment and algorithms for each. These algorithms were implemented in two separate tools used to illustrate the application of the concept slicing algorithms in two very different case studies. The first is a commercially-written COBOL module from a large financial organization, the second is an open source utility program written in C. Copyright © 2005 John Wiley & Sons, Ltd.     

FLSP:一个高效的系统级垃圾收集算法

垃圾收集是Java操作系统的核心功能,它直接影响到整个系统效率。现代Java操作系统中使用的垃圾收集算法普遍还是沿用应用程序级的垃圾收集算法。应用程序级垃圾收集算法的优化主要面向于普通的Java虚拟机。而Ja-va操作系统与Java虚拟机相比有更高的操作权限和更灵活的资源管理策略,如何利用这些特点和权限来提高垃圾收集算法的效率是以前的垃圾收集算法所没有考虑的。本文分析了操作系统下内存管理和垃圾收集的特点,在JUnicorn操作系统上,利用操作系统平台提供的便利,设计并实现了一个高效的系统级垃圾收集算法FLSP。测试数据表明,在操作系统级别,这种垃圾收集算法能够提高13%的系统性能,并且使垃圾收集的停顿时间缩短50%。     

A Tree-Based Alternative to Java Byte-Codes

Despite the apparent success of the Java Virtual Machine, its lackluster performance makes it ill-suited for many speed-critical applications. Although the latest just-in-time compilers and dedicated Java processors try to remedy this situation, optimized code compiled directly from a C program source is still considerably faster than software transported via Java byte-codes. This is true even if the Java byte-codes are subsequently further translated into native code. In this paper, we claim that these performance penalties are not a necessary consequence of machine-independence, but related to Java's particular intermediate representation and runtime architecture. We have constructed a prototype and are further developing a software transportability scheme founded on a tree-based alternative to Java byte-codes. This tree-based intermediate representation is not only twice as compact as Java byte-codes, but also contains more high-level information, some of which is critical for advanced code optimizations. Our architecture not only provides on-the-fly code generation from this intermediate representation, but also continuous re-optimization of the existing code-base by a low-priority background process. The re-optimization process is guided by up-to-the-minute profiling data, leading to superior runtime performance.     

一种改进的增量式JVM垃圾收集算法

非增量式Java虚拟机(JVM)垃圾回收算法的内存开销较大。为此,提出一种基于栈式分配策略的JVM增量式垃圾收集算法。对Java栈帧进行改造使其支持存储对象,改进增量式收集器中堆空间的划分、引用跟踪方式,以减少垃圾收集带来的不确定性暂停。实验结果表明,该算法能有效减少暂停的频率和时长,提高运行速度。     

UML模型和Java代码之间的一致性检测方法

针对代码与模型之间的不一致性问题,提出了一种基于UML模型和Java代码之间的一致性检测方法.首先,对UML类图和时序图进行形式化描述,并提出时序调用图(SD-CG)这一概念,在此基础上完成类的关联关系到关联属性的转换以及UML时序图到时序调用图SD-CG的转换;其次,通过方法调用图CG来表达类方法之间的调用关系,从而反映代码动态行为,由此通过对Java源代码的词法分析与语法分析,可获得类的信息及方法调用图CG;然后设计了UML模型与Java源代码间一致性检测算法,包括对类间静态信息以及时序调用图SD-CG与方法调用图CG间的一致性检测;最后,通过开发UML模型与Java源代码一致性检测工具,验证了所提出的方法是可行有效的.     

Exact and Portable Profiling for the JVM Using Bytecode Instruction Counting

This paper presents a novel profiling approach, which is entirely based on program transformation techniques in order to enable exact profiling, preserving complete call stacks, method invocation counters, and bytecode instruction counters. We exploit the number of executed bytecode instructions as profiling metric, which has several advantages, such as making the instrumentation entirely portable and generating reproducible profiles. These ideas have been implemented as the JP tool. It provides a small and flexible API to write portable profiling agents in pure Java, which are periodically activated to process the collected profiling information. Performance measurements point out that JP causes significantly less overhead than a prevailing tool for the exact profiling of Java code.