以控制樣式分析物件導向程式之行為

Abstract

物件導向(object-oriented, OO)程式設計已成為軟體發展的主流方式。比起傳統的程序導向方法，其設計出的程式較具擴充性、易管理及高再利用性，但卻面臨執行效率不彰與程式動態行為複雜，不易了解動態執行程序等困境。為改善或減輕此困境，進而提供更準確效能測量及提昇程式執行效能，程式分析扮演重要的角色。目前程式分析方法如靜態及動態分析不足以了解程式執行時的行為樣式，同時也未有將行為樣式量化的文獻或報告。對程式語言而言，程式碼樣式(code patterns)是靜態重複的結構，可在軟體設計時加入以解決特定的問題。相對於程式碼樣式，控制樣式(control pattern)是在程式執行時動態產生的重複結構，可應用於設計測量程式(benchmark)及了解程式執行的行為(runtime behavior)，並對執行程式最佳化有幫助。 在論文中，我們分析Java程式多種度量方式(metric)與物件方法呼叫序列(method invocation sequence)，我們提出以控制樣式為基礎的動態分析工具(profiler)，控制樣式包含一個有向圖(directed graph)及兩個函數，限制輸出函數(constraint output function)，限制布林函數(constraint Boolean function)，可將程式執行的軌跡(run-time trace)以有向圖(directed graph)表示，限制輸出函數及限制布林函數來說明程式執行真正的路徑。藉由此分析，希望能更了解Java程式執行時的行為。首先，我們修改了昇陽公司的模擬Java虛擬機器軟體(Java virtual machine)，藉此得到Java程式動態執行時的資訊。然後設計與實作一個控制樣式探索工具(control pattern mining tool)來分析所得到的動態執行資訊。同時，我們收集了18個Java程式做為控制樣式分析實驗程式。 物件導向程式的執行是藉由訊息呼叫(message invocation)而導致物件的產生與消滅(lifetime)，控制樣式敘述了物件之間控制權的轉移。本論文藉由實驗結果說明了控制樣式的存在及提供量化分析，控制樣式包括複雜的控制樣式(complex control pattern)、複合式的控制樣式(compound control pattern)和簡單的控制樣式(simple control pattern)在實驗程式中佔有不同的比例，且並非所有的程式都擁有這三類控制樣式，但大部分的程式也都含有高比例不尋常的控制樣式(nontrivial control pattern)。在此研究中，我們特別說明控制樣式可應用於物件導向測量程式建構，建議一個以控制樣式為基礎的物件導向測量程式建構方法，另一方面，控制樣式也可以提供給程式設計師設計較有效率的物件導向程式，同時，為了更容易了解，論文中使用許多範例來解釋控制樣式的應用方法。

Object-Oriented (OO) programming has played a major role in program design and implementation due to the fact that it is more extensible, maintainable, and reusable in the software system construction. Experiences of using Object-Oriented programming have indicated that there exist disadvantages with respect to its execution inefficiency and complicated runtime behaviors. Program analysis is essential for performance measurement and improvement. Current static and dynamic analysis using OO programming cannot characterize runtime behavior well and are also hard to quantify the measured results. In this dissertation, research work was performed to analyze several Java program metrics and method invocation sequence. The results not only provide us a better understanding of the runtime behavior but also present more information for different application domains. Code-patterns are statically recurring structure specifically related to a programming language. It can be used in parallel to help designing software systems for solving particular problems. In opposition to code-patterns’ role in assisting compilation, control-patterns are dynamically recurring structures invoked during program execution time. It can be used to understand the run-time behaviors of OO-programs for the underlying architecture such as Java-VM. We have proposed a run-time profiler based on control patterns to show that all run-time trace can be represented by a directed graph, a constrained output function, and a constraint Boolean function. It is known that the progress of program is the lifetime of objects by message invocation. Control pattern describes the model of control transfer among objects in OO program execution. In this research, several control patterns are proposed and discussed. Particularly, we have analyzed and collected several control patterns over several Java program corpora. The experimental results show that control pattern does exist and provide quantitative analysis. Simple pattern, compound pattern and complex pattern have different ratio respectively, according to a variety of different source programs. Not all benchmark programs contain all three kinds of patterns. There are high percentages of programs with nontrivial behaviors. Application of control patterns are addressed in this study specifically since control patterns can be used to design an OO benchmark for understanding the execution behaviors of OO systems. An OO benchmark design methodology is proposed for implementing such application. Also, control pattern can be used to provide guidelines for OO programmers to write more effective OO program. To make it clear, examples are also used to illustrate the applicability of these control patterns.