Safe,multiphase bounds check elimination in Java

As part of its type‐safety regime, Java's semantics require precise exceptions at runtime when programs attempt out‐of‐bound array accesses. This paper describes a Java implementation that utilizes a multiphase approach to identifying safe array accesses. This approach reduces runtime overhead by spreading the out‐of‐bounds checking effort across multiple phases of compilation and execution: production of mobile code from source code, just‐in‐time (JIT) compilation in the virtual machine, application method invocations, and the execution of individual array accesses. The code producer uses multiple passes (including common subexpression elimination, load elimination, induction variable substitution, speculation of dynamically verified invariants, and inequality constraint analysis) to identify unnecessary bounds checks and prove their redundancy. During class‐loading and JIT compilation, the virtual machine verifies the proofs, inserts code to dynamically validate speculated invariants, and generates code specialized under the assumption that the speculated invariants hold. During each runtime method invocation, the method parameters and other inputs are checked against the speculated invariants, and execution reverts to unoptimized code if the speculated invariants do not hold. The combined effect of the multiple phases is to shift the effort associated with bounds‐checking array access to phases that are executed earlier and less frequently, thus, reducing runtime overhead. Experimental results show that this approach is able to eliminate more bounds checks than prior approaches with minimal overhead during JIT compilation. These results also show the contribution of each of the passes to the overall elimination. Furthermore, this approach increased the speed at which the benchmarks executed by up to 16%. Copyright © 2010 John Wiley & Sons, Ltd.     

面向Fork/Join框架的软件重构及性能分析

针对目前对于Fork/Join框架应用和性能分析的相关工作还不多的现状,以JGF基准测试程序套件为基础,对其中的series、crypt、sparsematmult和sor等程序使用Fork/Join框架进行重构,并以series程序为例,详细地说明了重构的过程.在实验中,首先,测试了每个程序在不同阈值下使用Fork/Join框架分别递归1、2、3次执行程序的时间,进而选择相对较好的阈值;然后,对每个程序使用Fork/Join框架和使用Thread的执行时间进行了对比;此外,测试了重构后的程序在执行过程中任务窃取的情况.实验结果表明,Fork/Join框架执行时间与多线程执行时间相比,平均降低了14.2%;对于series程序,当数据大小为sizeC且线程个数为2时,Fork/Join框架执行时间比多线程执行时间降低高达40%,可见,在多核处理器平台上应用Fork/Join框架比使用多线程将获得更好的性能.     

Java程序中数组越界和空指针错误的静态分析

介绍了静态分析的相关背景知识,对Java程序中数组越界和空指针错误的常见表现形式进行了归类,并通过实验评估了现有的Java静态分析工具功能,指出了其在跨过程分析中的不足,并对如何改进进行了讨论。     

Evaluation and optimization of method calls in Java

Recent advances in Virtual Machine's technology have led to the diffusion of Java execution environments which provide performance levels comparable to those of traditional languages such as C/C++ and Fortran. This paper's focus is on method calls, a well researched area of compilers' optimization. In particular, we evaluate the impact on the performance of the Java virtual call mechanism and the advantages which can be obtained through the inlining optimization. Moreover, we propose a new heuristic methodology which allows us to consider whole sequences of methods for the inlining decision and not only simple couples of caller–callee methods. The proposed methodology operates at bytecode level and is applicable only to the calls that can be resolved at compile time. Thus, we execute a devirtualization algorithm before the inlining decision, in order to enlarge the basis for the optimization. We made empirical measures on three major platforms (Unix, Windows and Linux) by using the SPEC JVM98 benchmark suite. Results reveal an average performance improvement of 1.9% with devirtualization and 5.5% with inlining. We discuss the different behaviour of single benchmarks and virtual machines, arguing that dynamic compilers are not yet able to fully exploit the wider scope for intra‐procedural optimization offered by eliminating the calls. Finally, we show that taking into consideration whole sequences of calls—instead of single calls—is effective only on a few benchmarks where hotspots of execution involve cycles of nested methods. Copyright © 2003 John Wiley & Sons, Ltd.     

Worst‐case execution time analysis for a Java processor

In this paper, we propose a solution for a worst‐case execution time (WCET) analyzable Java system: a combination of a time‐predictable Java processor and a tool that performs WCET analysis at Java bytecode level. We present a Java processor, called JOP, designed for time‐predictable execution of real‐time tasks. The execution time of bytecodes, the instructions of the Java virtual machine, is known to cycle accuracy for JOP. Therefore, JOP simplifies the low‐level WCET analysis. A method cache, which fills whole Java methods into the cache, simplifies cache analysis. The WCET analysis tool is based on integer linear programming. The tool performs the low‐level analysis at the bytecode level and integrates the method cache analysis. An integrated data‐flow analysis performs receiver‐type analysis for dynamic method dispatches and loop‐bound analysis. Furthermore, a model checking approach to WCET analysis is presented where the method cache can be exactly simulated. The combination of the time‐predictable Java processor and the WCET analysis tool is evaluated with standard WCET benchmarks and three real‐time applications. The WCET friendly architecture of JOP and the integrated method cache analysis yield tight WCET bounds. Comparing the exact, but expensive, model checking‐based analysis of the method cache with the static approach demonstrates that the static approximation of the method cache is sufficiently tight for practical purposes. Copyright © 2010 John Wiley & Sons, Ltd.     

互模拟准局部验证算法的扩展与实现

互模拟是并发系统的分析和验证的一个重要概念。本文主要扩展了一种由Du和Deng提出的准局部算法,使其更加适用于一般的标记迁移系统。我们用Java实现扩展后的准局部算法与Fernandez和Mounier提出的局部算法。我们以VLTS为实验数据基准,进行大量的实验,发现在大多数情况下,前者的性能比后者更好。同时,我们修改了算法使其能够验证模拟关系。最后,我们用Java实现对标记迁移系统进行转换,使算法同时可以验证弱互模拟关系。     

An effective processor allocation strategy for multiprogrammedshared-memory multiprocessors

Existing techniques for sharing the processing resources in multiprogrammed shared-memory multiprocessors, such as time-sharing, space-sharing, and gang-scheduling, typically sacrifice the performance of individual parallel applications to improve overall system utilization. We present a new processor allocation technique called Loop-Level Process Control (LLPC) that dynamically adjusts the number of processors an application is allowed to use for the execution of each parallel section of code, based on the current system load. This approach exploits the maximum parallelism possible for each application without overloading the system. We implement our scheme on a Silicon Graphics Challenge multiprocessor system and evaluate its performance using applications from the Perfect Club benchmark suite and synthetic benchmarks. Our approach shows significant improvements over traditional time-sharing and gang-scheduling. It has performance comparable to, or slightly better than, static space-sharing, but our strategy is more robust since, unlike static space-sharing, it does not require a priori knowledge of the applications' parallelism characteristics     

Statically safe program generation with SafeGen

SafeGen is a meta-programming language for writing statically safe generators of Java programs. If a program generator written in SafeGen passes the checks of the SafeGen compiler, then the generator will only generate well-formed Java programs, for any generator input. In other words, statically checking the generator guarantees the correctness of any generated program, with respect to static checks commonly performed by a conventional compiler (including type safety, existence of a superclass, etc.). To achieve this guarantee, SafeGen supports only language primitives for reflection over an existing well-formed Java program, primitives for creating program fragments, and a restricted set of constructs for iteration, conditional actions, and name generation. SafeGen’s static checking algorithm is a combination of traditional type checking for Java, and a series of calls to a theorem prover to check the validity of first-order logical sentences, constructed to represent well-formedness properties of the generated program under all inputs. The approach has worked quite well in our tests, providing proofs for correct generators or pointing out interesting bugs.     

Efficient data race detection for async-finish parallelism

A major productivity hurdle for parallel programming is the presence of data races. Data races can lead to all kinds of harmful program behaviors, including determinism violations and corrupted memory. However, runtime overheads of current dynamic data race detectors are still prohibitively large (often incurring slowdowns of 10× or more) for use in mainstream software development. In this paper, we present an efficient dynamic race detection algorithm that handles both the async-finish task-parallel programming model used in languages such as X10 and Habanero Java (HJ) and the spawn-sync constructs used in Cilk. We have implemented our algorithm in a tool called TaskChecker and evaluated it on a suite of 12 benchmarks. To reduce overhead of the dynamic analysis, we have also implemented various static optimizations in the tool. Our experimental results indicate that our approach performs well in practice, incurring an average slowdown of 3.05× compared to a serial execution in the optimized case.     

基于污点分析的数组越界缺陷的静态检测方法

随着移动计算、物联网、云计算、人工智能等领域的飞速发展,也涌现出了很多新的编程语言和编译器,但是C/C++语言依旧是最受欢迎的编程语言之一,而数组是C语言最重要的数据结构之一.当在程序中通过数组下标访问数组元素时,必须确保该下标在该数组的边界之内,否则就会导致数组越界.程序中的数组越界缺陷会使得程序在运行时导致系统崩溃,甚至使攻击者可以截取控制流以执行任意恶意代码.当前针对数组越界的静态检查方法无法达到高精度的分析,尤其是无法处理复杂约束和表达式,过多的误报额外增加了开发者的负担.因此,提出了一种基于污点分析的数组越界的静态检测方法.首先,提出流敏感、上下文敏感的按需指针分析方法,实现数组长度区间分析.然后,提出按需污点分析方法,实现数组下标和数组长度污染情况的计算.最后,定义数组越界缺陷判定规则,提出使用后向数据流分析方法,检测数组下标是否越界.在进行数组越界检测的过程中,为了处理程序中的复杂约束和表达式,在分析过程中将调用约束求解器来判断约束的可满足性.如果没有发现相应的语句,则报告数组越界缺陷警报.同时,实现了自动静态分析工具Carraybound,并通过实验展示了方法的有效性.     

Using abstract interpretation to add type checking for interfaces in Java bytecode verification

Java interface types support multiple inheritance. Because of this, the standard bytecode verifier ignores them, since it is not able to model the class hierarchy as a lattice. Thus, type checks on interfaces are performed at run time. We propose a verification methodology that removes the need for run-time checks. The methodology consists of: (1) an augmented verifier that is very similar to the standard one, but is also able to check for interface types in most cases; (2) for all other cases, a set of additional simpler verifiers, each one specialized for a single interface type. We obtain these verifiers in a systematic way by using abstract interpretation techniques. Finally, we describe an implementation of the methodology and evaluate it on a large set of benchmarks.     

基于PageRank和基准测试的异构集群节点性能评价算法研究

为了提高集群效率,需要根据集群节点的性能来进行集群的数据部署和任务调度。在异构集群中,节点性能存在很大差异,如何评价节点的性能非常具有挑战性。可以使用基准测试来评价节点的性能,而不同的基准测试对节点评价的角度不尽相同。PageRank算法被谷歌用来对网站进行排名,现在它也被应用于评价书籍的影响力或用户行为等等。提出一种新颖的基于PageRank的节点性能评价算法,以充分利用不同基准测试的评价结果。首先对每个节点使用LINPACK、NPB、IOzone等主流基准测试进行评价;然后采用PageRank算法处理每个基准测试的执行结果,从而得到节点的性能。为了使用PageRank算法,建立了1个图模型,并计算了性能向量和概率转移矩阵。该算法具有计算复杂度低、综合评价效果好等优点。     

SPEC CPU2000: measuring CPU performance in the New Millennium

As computers and software have become more powerful, it seems almost human nature to want the biggest and fastest toy you can afford. But how do you know if your toy is tops? Even if your application never does any I/O, it's not just the speed of the CPU that dictates performance. Cache, main memory, and compilers also play a role. Software applications also have differing performance requirements. So whom do you trust to provide this information? The Standard Performance Evaluation Corporation (SPEC) is a nonprofit consortium whose members include hardware vendors, software vendors, universities, customers, and consultants. SPEC's mission is to develop technically credible and objective component- and system-level benchmarks for multiple operating systems and environments, including high-performance numeric computing, Web servers, and graphical subsystems. On 30 June 2000, SPEC retired the CPU95 benchmark suite. Its replacement is CPU2000, a new CPU benchmark suite with 19 applications that have never before been in a SPEC CPU suite. The article discusses how SPEC developed this benchmark suite and what the benchmarks do     

一种混合式内存泄漏静态检测方法

内存泄漏是导致系统性能降低的重要问题.提出一种基于模型检测算法的内存泄漏静态检查方法TMC.该方法依据程序的控制流图构建对应于程序执行的有限状态自动机,进而在此基础上应用模型检测算法分析程序中可能存在的内存泄漏.论文利用几个典型的程序实例详细说明了TMC的工作原理,并通过基于内存操作密集的测试程序集PtrDist的实验对TMC进行了验证.实验结果表明,TMC能够显著提升内存泄漏分析的精度.     

Characterizing and optimizing Java-based HPC applications on Intel many-core architecture

The increasing demand for performance has stimulated the wide adoption of many-core accelerators like Intel^® Xeon Phi^TM Coprocessor, which is based on Intel’s Many Integrated Core architecture. While many HPC applications running in native mode have been tuned to run efficiently on Xeon Phi, it is still unclear how a managed runtime like JVM performs on such an architecture. In this paper, we present the first measurement study of a set of Java HPC applications on Xeon Phi under JVM. One key obstacle to the study is that there is currently little support of Java for Xeon Phi. This paper presents the result based on the first porting of OpenJDK platform to Xeon Phi, in which the HotSpot virtual machine acts as the kernel execution engine. The main difficulty includes the incompatibility between Xeon Phi ISA and the assembly library of Hotspot VM. By evaluating the multithreaded Java Grande benchmark suite and our ported Java Phoenix benchmarks, we quantitatively study the performance and scalability issues of JVM on Xeon Phi and draw several conclusions from the study. To fully utilize the vector computing capability and hide the significant memory access latency on the coprocessor, we present a semi-automatic vectorization scheme and software prefetching model in HotSpot. Together with 60 physical cores and tuning, our optimized JVM achieves averagely 2.7x and 3.5x speedup compared to Xeon CPU processor by using vectorization and prefetching accordingly. Our study also indicates that it is viable and potentially performance-beneficial to run applications written for such a managed runtime like JVM on Xeon Phi.     

Java指令集结构的研究

1 引言 Java是一种编程语言,用其编写的程序具有安全、模块化和可移植等特点。当前Java在Internet有广泛应用,在网站主页的HTML代码中嵌入Java类文件,可以增强界面的动画效果,这种类文件称为小程序(Applet),它是Java源程序的可执行代码。当浏览器访问包含小程序的主页时,相应的类文件从服务器传送到在客户机上运行的Java虚拟机(JVM)上,由JVM生成相应的类对象,并执行相应的方法。Netscape浏览器中就包含这种JVM。     

Static Checking of Array Index Out-of-Bounds Defects in C Programs Based on Taint Analysis

During the rapid development of mobile computing, IoT, cloud computing, artificial intelligence, etc., many new programming languages and compilers are emerging. Nevertheless, C/C++ is still one of the most popular languages, and the array is one of the most important data structures of C language. It is necessary to check whether the index is within the boundary of the array when it is used to access the element of an array in a program. Otherwise, array index out-of-bounds will happen unexpectedly. When array index out-of-bounds defects are in programs, some serious errors may occur during execution, such as system crash. It is even worse that array index out-of-bounds defects open the doors for attackers to take control of the server and execute arbitrary malicious codes by carefully constructing input and intercepting the control flow of the programs. Existing static methods for array boundary checking cannot achieve high accuracy and deal with complex constraints and expressions, leading to massive false positives. In addition, it will increase the burden of developers. In this study, a static checking method is proposed based on taint analysis. First, a flow-sensitive, context-sensitive, and on-demand pointer analysis is proposed to analyze the range of array length. Then, an on-demand taint analysis is performed for all array indices and array length expressions. Finally, the rules are defined for checking array index out-of-bounds defects and the checking is realized based on backward data flow analysis. During the analysis, in light of complex constraints and expressions, it is proposed to check the satisfiability of the conditions by invoking the constraint solver. If none statement for avoiding array index out-of-bounds is found in the program, an array index out-of-bound warning will be reported. An automatic static analysis tool, Carraybound, has been implemented, and the experimental results show that Carraybound can work effectively and efficiently.     

面向对象程序设计语言的绑定时间分析技术

为了实现面向对象语言的部分求值,提出了一种绑定时间分析技术.该技术通过针对引用类型变量和指针变量的上下文敏感分析,能够比较精确地分析面向对象语言中诸如对象元素、数组元素等复杂数据结构元素的绑定时间,进而扩大了部分求值的作用范围.这种方法采用两层BTA环境来保存静态变量和局部变量的BTA状态,设置一种专用句柄来表示不同程序点创建的对象,进而采用这种句柄的集合表示引用类型变量的BTA状态.在为面向对象语言程序标注绑定时间信息的过程中,采用一个正向分析和一个反向分析过程,借助于BTA环境来跟踪和设定各种变量、对象和引用变量的绑定时间.该技术已经用于实现Java程序的绑定时间分析,能够有效地分析大多数单线程的Java程序,为实现高性能Java程序部分求值提供了必要的手段.     

Static verification of dynamically detected program invariants: Integrating Daikon and ESC/Java

This paper shows how to integrate two complementary techniques for manipulating program invariants: dynamic detection and static verification. Dynamic detection proposes likely invariants based on program executions, but the resulting properties are not guaranteed to be true over all possible executions. Static verification checks that properties are always true, but it can be difficult and tedious to select a goal and to annotate programs for input to a static checker. Combining these techniques overcomes the weaknesses of each: dynamically detected invariants can annotate a program or provide goals for static verification, and static verification can confirm properties proposed by a dynamic tool.We have integrated a tool for dynamically detecting likely program invariants, Daikon, with a tool for statically verifying program properties, ESC/Java. Daikon examines run-time values of program variables; it looks for patterns and relationships in those values, and it reports properties that are never falsified during test runs and that satisfy certain other conditions, such as being statistically justified. ESC/Java takes as input a Java program annotated with preconditions, postconditions, and other assertions, and it reports which annotations cannot be statically verified and also warns of potential runtime errors, such as null dereferences and out-of-bounds array indices.Our prototype system runs Daikon, inserts its output into code as ESC/Java annotations, and then runs ESC/Java, which reports unverifiable annotations. The entire process is completely automatic, though users may provide guidance in order to improve results if desired. In preliminary experiments, ESC/Java verified all or most of the invariants proposed by Daikon.     

The Runabout

This paper presents a variation of the visitor pattern which allows programmers to write visitor‐like code in a concise way. The Runabout is a library extension that adds a limited form of multi‐dispatch to Java. While the Runabout is not as expressive as a general multiple dispatching facility, the Runabout can be significantly faster than existing implementations of multiple dispatch for Java, such as MultiJava. Unlike MultiJava, the Runabout does not require changes to the syntax and the compiler. This paper illustrates how to use the Runabout, details its implementation and provides benchmarks comparing its performance with other approaches. Furthermore, the effect of an automatic static program transformation tool that translates bytecode using the Runabout to equivalent bytecode is evaluated. The tool uses double dispatch and runtime‐type checks to achieve the same semantics that the Runabout has. The performance comparisons on large benchmarks that make extensive use of multiple dispatch show that using the Runabout does not result in a significant loss of performance for realistic applications and that, depending on the application and platform, small performance gains are also possible. Copyright © 2008 John Wiley & Sons, Ltd.