個體導向程式系統執行行為最佳化的探討

Abstract

個體導向（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.