利用事先預算表格與系統合約來提升程式碼效能

Unit Code Performance Improvement by Pre-computed Table and Contracts

楊家瑋(Chia-Wei Yang)

指導教授 ： 鄭永斌

國立臺灣師範大學/教育學院/資訊教育學系/碩士(2004年)

摘要

程式通常可以使用兩個方法來改善它的效能。一種是先找出程式可以改進的地方，然後再利用比較好的演算法和資料結構來改善。另外一種是讓編譯器(compiler)來將程式碼最佳化(code optimization)。然而實際上，在許多應用軟體裡，仍然存在著一些在程式裡的函式(function)無法用這兩種方法來改進，而且，很不幸的，這些函式有時候是提升效能的瓶頸。為了要改善程式的效能，有許多有經驗的程式設計師會利用一些特殊的技巧手動的來寫改寫程式，像論文[10]裡面所敘述的技巧一樣。
在這一篇論文裡，我們著重在利用表格查尋(tabular search)來取代原來要執行的函式這樣的技巧。那就是將函式裡要回傳的值預先計算好，並且把它們儲存在一個表格裡。然後當這個函式被呼叫時，函式要回傳的值可以立即的從表格裡取得。這個技巧主要在於加快函式的執行速度，但是這個技巧卻必需程式設計師自己手動完成，而且寫完的程式碼也變得不容易讓人了解。
在這一篇論文裡，我們提出利用程式碼自動轉換的系統來將這些造成程式效能瓶頸的函式給取代掉。很不幸的，假如我們盲目地自動化產生事先運算的表格(pre-computed table)，這個表格所需要的空間會非常的大。所以，在使用我們的系統時，程式設計師可以先利用系統合約(contracts)來標記這個函式的規格。系統合約是一種可以指出函式的限制的標記語言，並且它可以被解譯(parse)用來提供程式碼轉換(code transformation)時一些重要的資訊。除此之外，為了找出會影響這個函式執行結果的變數，我們利用程式碼切片的技巧(program slicing techniques)來分析它。這些變數是要用來查尋表格時所要用的索引(index)。

關鍵字

表格查尋 ； 事先運算的表格 ； 系統合約

並列摘要

Performance of a program is usually improved in roughly two ways. One is to seek improvements by adopting better data structure or algorithms. The other is using the code optimization built inside the compiler. However, in many practical applications, there are some functions of a program which may not be improved further by these two approaches and unfortunately, these functions could be the bottleneck of performance in a program. In order to improve program performance, many experienced programmers write the code by using specific techniques of programming manually, as in [10].
In this thesis, we focus on a trick which replaces the execution of functions by a tabular search. That is, one can pre-compute all the returned values of a function and store them in a table. Then, when the function is called, the result value is returned from the table immediately. This trick can accelerate function execution significantly but can only be done manually and the source code becomes difficult to understand.
In this thesis, we propose a code transformation system to replace the bottleneck function automatically. Unfortunately, in practice, the table can be very large if we produce the table blindly or brute-forcedly. So, to use our system, programmers may use contract to annotate functions. Contracts are annotations which specify the constraints (preconditions, postcondition, invariants, etc.) of a function. The contract can be parsed to provide important information for our code transformation. Besides, the target functions are analyzed by program slicing techniques to find out variables which affect the function execution. These variables will be used as indices for looking up the return value in the table.

並列關鍵字

tabular search ； pre-computed table ； contracts