簡易檢索 / 詳目顯示

回結果列表
研究生： 楊家瑋
Chia-Wei Yang
論文名稱： 利用事先預算表格與系統合約來提升程式碼效能
Unit Code Performance Improvement by Pre-computed Table and Contracts
指導教授： 鄭永斌
Cheng, Yung-Pin
學位類別： 碩士
Master
系所名稱： 資訊教育研究所
Graduate Institute of Information and Computer Education
論文出版年： 2004
畢業學年度： 93
語文別： 英文
論文頁數： 144
中文關鍵詞： 表格查尋 、事先運算的表格 、系統合約
英文關鍵詞： tabular search, pre-computed table, contracts
論文種類： 學術論文
相關次數： 點閱：177  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 程式通常可以使用兩個方法來改善它的效能。一種是先找出程式可以改進的地方，然後再利用比較好的演算法和資料結構來改善。另外一種是讓編譯器(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.

    List of Figures vi Chapter 1 Introduction 1 Chapter 2 Background 6 2.1 Code optimization in compiler 6 2.1.1 An idealized optimizing compiler structure 7 2.1.2 Flow graph 9 2.1.3 The principle of data flow analysis 11 2.2 Program slicing 16 2.2.1 Static slicing 16 2.2.2 Dynamic slicing 20 2.3 Assertions 21 2.4 Design by contract 23 2.4.1 The notion of contract and contracting for software by assertions 23 2.4.2 Contract definition rule in object oriented code 25 2.5 Java compiler compiler tool 27 2.5.1 Using parser generators 27 2.5.2 AST from JJTree in JavaCC 32 Chapter 3 Code Transformation for Accelerating Function Execution 36 3.1 An overview 36 3.2 A Java parser 43 3.3 Getting table-lookup variables by program slicing 43 3.4 Contract analysis in a contract parser 44 3.5 A table generator 46 3.6 Code translator 48 Chapter 4 Code Analysis Using Program Slicing 51 4.1 Generating a control flow graph from source code 51 4.2 Program slicing 54 4.2.1 Data dependence and control dependence in CFG 54 4.2.2 Slicing control flow graphs 55 4.3 Obtaining table-lookup variables by program slicing 61 4.3.1 Def-use analysis using program slicing techniques 62 4.3.2 Side-effect analysis using program slicing techniques 64 4.3.3 Defining all variables in function for the table generator 67 Chapter 5 Using Contract as an Aid to Reduce Table Size 70 5.1 Analyzing the contract 71 5.2 The contract syntax and constructs 71 5.2.1 The construct of the contract 72 5.2.2 The contract expressed by assertions 72 5.3 Generating a tabular search function depending on the contract 74 5.3.1 A precondition by assertions 75 5.3.2 The value used in a range frequently by assertions 76 5.3.3 The priority in assertions 78 Chapter 6 A Case Study 80 Chapter 7 Conclusions and Future Works 89 7.1 A summary 89 7.2 Future works 90 Appendix (A) A JavaCC Garmmar in Java1.4 92 Appendix (B) A JavaCC Garmmar in VCL 122 Appendix (C) Driver Class Generator in Java 134 Appendix (D) Table Code Generator in Java 139 References 141

    References
    [1] H. Agrawal. and R. A. DeMIllo. Dynamic slicing in the presence of unconstrained pointers. Proceedings 5th ACM Symposium on Test and Validation, October 1991.
    [2] H. Agrawal. and J. Horgan. Dynamic program slicing. Technical Report SERC-TR-56-P, Purdue University, 1989.
    [3] H. Agrawal. and J. Horgan Dynamic program slicing. In Proceedings of the ACM SIGPLAN'90 Conference, 1990.
    [4] J. P. Banning An efficient way to and the side effects of procedure calls and the aliases of variables. In Conference Record of the Sixth ACM Symposium on Principles of Programming Languages, (San Antonio, TX, Jan. 29-31, 1979), 1979.
    [5] J. F. Bergeretti and B. Carr Information-flow and data-flow analysis of while-programs. ACM Transactions on Programming Languages and Systems, 7(1):37-61, January 1985.
    [6] L. C. Briand, Y. Labiche and H. Sun, “Investigating the Use of Analysis Contracts to Improve the Testability of Object Oriented Code,” Carleton University, Technical Report SCE-01-10, 2001.
    [7] D. Binkley and K. Gallagher, Program Slicing, In Advances in Computers, Volume 43, 1996.
    [8] J. Ferrante, K. Ottenstein, and J. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987.
    [9] T. Frank. A survey of program slicing techniques. Technical Report: CS-R9438 1994.
    [10] K. B. Gallagher. Using program slicing to eliminate the need for regression testing. In Eighth International Conference on Testing Computer Software, May 1991.
    [11] K. B. Gallagher and J. R. Lyle. Using program slicing in software maintenance. IEEE Transactions on Software Engineering, 17(8):751-761, August 1991.
    [12] K. B. Gallagher and J. R. Lyle. Program slicing and software safety. In Proceedings of the Eighth Annual Conference on Computer Assurance, pages 71-80, June 1993. COMPASS'93
    [13] M. C. Glen. Thirty ways to improve the performance of your JavaTM programs, http://www.glenmccl.com/jperf/index.htm, October 1999.
    [14] P. Hausler. Denotational program slicing. In Proceedings of the 22nd Hawaii International Conference on System Sciences, pages 486-494, January 1989. Volume II, Software Track.
    [15] JavaCCTM, Java Parser Generator, https://javacc.dev.java.net/ , 2002.
    [16] JContract, “Using Design by Contract to Automate Java Software and Component Testing,” ParaSoft Corporation,
    www.parasoft.com/products/jtest/papers/tech_dbc.htm.
    [17] M. Kamkar. Interprocedural Dynamic Slicing with Applications to Debugging and Testing. PhD thesis, Linkoping University, S-581 83 Linkoping, Sweeden, 1993.
    [18] M. Kamkar, P. Fritzson, and N. Shahmehri. Interprocedural dynamic slicing applied to interprocedural data flow testing. In Proceeding of the Conference on Software Maintenance 93, pages 386-395, 1993.
    [19] K. Kennedy. A survey of data flow analysis techniques. In Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis: Theory and Applications. Prentice-Hall, Englewood Cliffs, New Jersey, 1981.
    [20] B. Korel and J. Laski. Dynamic program slicing. Information Processing Letters, 29(3):155-163, October 1988.
    [21] B. Korel and J. Laski. Dynamic slicing of computer programs. Journal of Systems and Software, pages 198-195, 1990.
    [22] Bixin Li, Analyzing information-flow in java program based on slicing technique, ACM SIGSOFT Software Engineering Notes, v.27 n.5, p.98-103, September 2002.
    [23] B. Meyer, “Design by Contracts,” IEEE Computer, vol. 25 (10), pp. 40-52, 1992.
    [24] J. H. Mary and L. S. Mary. Efficient computation of interprocedural definition-use chains. ACM Transactions on Programming Languages and Systems, 16(2):175-204, March 1994.
    [25] OCL, “Object Constraint Language,” Object Management Group, V1.4, 2001.
    [26] K. Ottenstein and L. Ottenstein. The program dependence graph in software development environments. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, pages 177-184, May 1984. L.Ottenstein is now known as L. Ott.
    [27] H. Pande, W. Landi, and B. G. Ryder. Interprocedural def-use associations in C programs. IEEE Trans. on Software Engineering, vol. 20(5):385–403, May 1994.
    [28] D. Rosenblum, “A Practical Approach to Programming with Assertions,” IEEE Trans. on Software Engineering, vol. 21 (11), pp. 19-31, 1995.
    [29] Amie L. Souter and Lori L. Pollock. Contextual def-use associations for object aggregation. In Proceedings of the ACM Workshop on Program Analysis for Software Tools and Engineering, 2001.
    [30] Amie L. Souter, Lori L. Pollock, and Dixie Hisley. Inter-class def-use analysis with partial class representations. In Proceedings of the ACM Workshop on Program Analysis for Software Tools and Engineering, 1999.
    [31] J. Warmer and A. Kleppe, The Object Constraint Language, Addison-Wesley, 1999.
    [32] M. Weiser. Program Slicing: Formal, Psychological and Practical Investigations of an Automatic Program Abstraction Method. PhD thesis, The University of Michigan, Ann Arbor, Michigan, 1979.
    [33] M.Weiser. Program slicing. In Proceeding of the Fifth International Conference on Software Engineering, pages 439-449, May 1981.
    [34] M. Weiser. Programmers use slices when debugging. CACM, 25(7):446-452, July 1982.
    [35] M. Weiser. Program slicing. IEEE Transactions on Software Engineering, 10:352-357, July 1984.

    QR CODE