個體導向（Object-Oriented, OO）軟體系統常面臨執行效率不彰的
問題，諸如太多的間接存取（Indirect Access)，頻繁之物件產生和消除
的動作，以及大量多型性訊息傳送（Polymorphic Message Sending）.這
些都是個體導向系統執行環境所面臨最嚴重之問題. 為了提昇整體效率，
不容刻緩的就是降低間接存取動作，設計有效率的記憶體配置器（或無用
記憶體收集器，Garbage Collector）及使用更好的訊息分派方法（
Method Dispatch），使適用於各種不同之語言環境如靜態型別的 C++ 和
Eiffel，及動態型別的 Smalltalk 和 SELF. 我們的研究焦點在動態訊息
分派及間接存取之問題，並設法調查影響軟體執行各種行為的因素，進而
改善幾種現有建立快取查詢器之技術. 各種應用領域及程式碼樣式既存在
有極大差異，其相關之最佳化自應針對特殊之領域或樣式. 所提出之 OO
環境幾項特別的性質，如類別資訊(Class),物體個體(Object Instance),
變數繫結種類(Variable Binding),訊息名(Message Selector),以及對應
執行體(Method Body). 這些角色都參與控制權的轉移. 我們所要最佳化
的就是使最常參與之主角更快，並適時儲存需要之資訊. 不同之應用領域
所醞含之特殊樣式將呈現不同的控制模式，而其參與者也將扮演不同角色
，具不確定性之影響力. 在處理動態訊息分派的問題上，我們有幾項考慮
，如繫結之限制(Binding Constraint),編譯時所花之時間及中間過程所
用空間,執行時間之存取效率及空間大小,及所設計之方法是否容許動態選
取訊息名稱，以解決多重繼承(MultipleInheritance) 所延伸之名稱互相
衝突之問題(Name Conflict). 基本上所設計之快取器是在找尋最大可能
之空間壓縮，並達成有效率的存取. 在設計上以考慮過前述實際應用將面
臨之問題，並與傳統方法做各方面的比較.

Object-oriented(OO) software systems suffer from poor
execution efficiency due to larger number of indirect accesses.
Frequent object creation and destruction, and lots of
polymorphic message sendings.These are central issues in therun-
time environment of OO systems. To improve the overall
efficiency,it is crucial to reduce indirect access,
designefficient memory allocator (or garbage collector) and use
a betterstrategy for message dispatch adapting to various
language implementationsincluding statically typed languages
such as C++ and Eiffel,and dynamicallytyped environment like
Smalltalk and SELF. In our research, we focus on theissues of
dynamic message sending and in behavior and improve several
existing techniques for constructing fast lookup cache for
method search. Since the run time behaviors differ substantially
for various application domains and code patterns, the
optimization should be domain or patternspecific. The proposed
concept of control cache tries to capture the difference between
data access and control transfer and preserve special traitsin
OO environment like class information, object instance, binding
type of variable, message selector and method body. These are
all "subjects" attending in a transfer of control. What we want
to optimize is to make frequently accessed "subject" fast and
store necessary informationin appropriate time. Different code
patterns for specific applications will have different roles in
an uncertain extent. For dealing with the problems of dynamic
method dispatch, we must consider several issues, including
biding constraint, time and intermediate space for table
construction in compile time, table access efficiency and table
size during execution time and whether the designated schema
allow dynamic resolution of message selectors for name conflict
in multiple inheritance. The basic idea behind the proposed
schema for constructing lookup cache is to explore maximum space
reduction for dispatch table and achieve efficient table access.
Practical issues such as name conflict problems inmultiple
inheritance and error detection for unknown messages are
discussed and implemented. Comparisons aremade with conventional
method resolutions of offset, name and dispatch function in
terms of time of schema construction, table space overhead and
dispatch efficiency.

COVER
中文摘要
ABSTRACT
ACKNOWLEDGMENTS
TABLE OF CONTENTS
LIST OF FIGURES
LIST OF TABLES
1. INTRODUCTION
1.1 PROBLEMS IN RUN-TIME ENVIRONMENT
1.1.1 Dynamic Message Sending
1.1.2 Indirect Access
1.1.3 Object Storage Management
1.2 PROPERTIES OF MESSAGE PATTERNS
1.2.1 General Form of Message Patterns
1.2.2 Class Variant and Selector Invariant
1.2.3 Class Variant and Selector Variant
1.3 METHOD DISPATCH STRUCTURE AND TYPES OF METHOD RESOLUTION
1.3.1 Types of Method Resolution
1.3.2 Dispatch Structures
1.3.3 Inheritance Tree Topolgies
1.4 TYPES OF VARIABLE BINDING AND ATTENDING SUBJECTS IN A CONTROL TANSFER
1.4.1 On Variable Binding
1.4.2 Attending Subjects
1.5 OVERVIEW
2. RELATED WORKS
2.1 MONE-METHOD AND MULTI-METHOD DISPATCH
2.2 STATIC OPTIMIZATION
2.3 LOOKUP CACHE APPROACH
2.3.1 Inline Cache and Polymorphic Inline Cache
2.3.2 Lookup Cache and Objective-C Messager
2.4 LOOKUP CACHE SPACE OPTIMIZATION
2.4.1 Dispatch Table Search (DTS) and Selector Table Index (STI)
2.4.2 Coloring Indes Table (CIT)
2.4.3 Two-Directional Record Layout Approach (TDR)
2.4.4 Incremental Coloring for Message Tables
2.5 SUMMARY OF PREVIOUS RELATED WORK AND MOTIVATION FOR OUR APPROACH
3. TWO-WAY MERGE INDEXED TABLE SCHEMA AND DISPATCH
3.1 TABLE ROW AND COLUMN MERGE
3.2 MAXIMUM COMPATIBLE CLASS
3.3 COMPATIBLE TABLE CONSTRUCTION
3.3.1 Codeword Support for List Construction
3.4 UNKNOWN MESSAGE DETECTION
3.5 ASSESSMENT OF TWO-WAY MERGE
4. IMPLEMENTATION OF TWM: INVERSE DISPATCH TABLE CACHE (IDT CACEN) AND VALIDATION CACHE (V CACHE)
4.1 INTRODUCTION
4.2 CONSTRUCTION OF THE INVERSE DTS TABLE AND THE IDT MESSAGE CACHE TABLE
4.2.1 Separation of Vcache and IDT Cache
4.2.2 Cluster Venification
4.2.3 Group Merging
4.3 DISPATCH ALGORITHM AND ERROR DETECTION
4.3.1 Dispatch Verification
4.4 RESULTS OF RANDOM TESTS
4.5 DISCUSSION
5. DISPATCH FUNCTION FOR NAME CONFLICT RESOLUTION AND MULTI-METHOD DISPATCH
5.1 INTRODUCTION
5.1.1 Dynamic Resolution and the Independence Principle
5.2 POINT OF VIEW RESOLUTION
5.3 DISPATCH ALGORITHM AND ERROR DETECTION
5.4 RESULTS OF RANDOM TESTS
5.4.1 Considerations for Strongly Typed Languages
6. UNKNOWN MESSAGE DETECTION AND PROBLEMS IN PHYSICAL IMPLEMENTATIONS
6.1 INTRODUCTION
6.2 THREE TYPES OF MESSAGE ERRORS
6.2.1 Class Alias Error
6.2.2 Selector Alias Error
6.2.3 Class Dependency Alias Error
6.3 INCREMENTAL DEVELOPMENT AND INCREMENTAL COLORING FOR DYNAMIC TRANSITION SYSTEMS
6.3.1 Compilative Language Systems
6.3.2 Dynamic Transition Systems
6.3.3 Incremental Process to Two-Way Merge
7.THE CONCEPT OF CONTROL CACHE
7.1 INTRODUCTION
7.1.1 The Features of a Control Cache
7.1.2 The Control Cache Lift Time
7.1.3 The Types of Control Cache
7.2 MAKING FREQUENTLY USED SUBJECTS FAST
7.3 CODE PATTERN OPTIMIZATION
7.3.1 Selector Intensive Scope
7.3.2 Class Intensive Block
7.3.3 Binding Type Specific Patterms
7.4 RUN TIME RECONFIGURATION FOR DISPATCH TABLE
7.4.1 The Control State
7.4.2 The Control Strategy
7.5 MEASUREMENT OF REUSABILITY
7.5.1 Interface Non-Conflict and Class Compatible
7.5.2 IDT Lookup Cache Compresion Rate and Software Compatibility
8. CONCLUSIONS AND FURTHER WORK
8.1 FURTHER WORK
9. REFERENCES
VITA
PUBLICATIONS