Reengineering a complex application using a scalable data structure compiler

ABSTRACT

P2 is a scalable compiler for collection data structures. High-level abstractions insulate P2 users from data structure implementation details. By specifying a target data structure as a composition of components from a reuse library, the P2 compiler replaces abstract operations with their concrete implementations.LEAPS is a production system compiler that produces the fastest sequential executables of OPS5 rule sets. LEAPS is a hand-written, highly-tuned, performance-driven application that relies on complex data structures. Reengineering LEAPS using P2 was an acid test to evaluate P2's scalability, productivity benefits, and generated code performance.In this paper, we present some of our experimental results and experience in this reengineering exercise. We show that P2 scaled to this complex application, substantially increased productivity, and provided unexpected performance gains.

REFERENCES

• ACM91: Association for Computing Machinery, "Next Generation Database Systems", Communications of the ACM, October 1991.
• Bat88: D. S. Batory , J. R. Barnett , J. F. Garza , K. P. Smith , K. Tsukuda , C. Twichell , T. E. Wise, GENESIS: An Extensible Database Management System, IEEE Transactions on Software Engineering, v.14 n.11, p.1711-1730, November 1988 [doi>10.1109/32.9057]
• Bat92: Don Batory , Sean O'Malley, The design and implementation of hierarchical software systems with reusable components, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.4, p.355-398, Oct. 1992 [doi>10.1145/136586.136587]
• Bat93: Don Batory , Vivek Singhal , Marty Sirkin , Jeff Thomas, Scalable software libraries, Proceedings of the 1st ACM SIGSOFT symposium on Foundations of software engineering, p.191-199, December 08-10, 1993, Los Angeles, California, United States
• Bat94a: Don Batory, The LEAPS Algorithm, University of Texas at Austin, Austin, TX, 1994
• Bat94b: Don Batory , Vivek Singhal , Jeff Thomas , Sankar Dasari , Bart Geraci , Marty Sirkin, The GenVoca Model of Software-System Generators, IEEE Software, v.11 n.5, p.89-94, September 1994 [doi>10.1109/52.311067]
• Big94: T. BiggerStaff. "The Library Scaling Problem and the Limits of Concrete Component Reuse", IEEE International Conference on Software Reuse, November 1994.
• Bra91: David A. Brant , Timothy Grose , Bernie Lofaso , Daniel P. Miranker, Effects of Database Size on Rule System Performance: Five Case Studies, Proceedings of the 17th International Conference on Very Large Data Bases, p.287-296, September 03-06, 1991
• Bra93: David A. Brant , Daniel P. Miranker, Index support for rule activation, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.42-48, May 25-28, 1993, Washington, D.C., United States
• Bro94: J. Browne, et al. "A New Approach to Modularity in Rule-Based Programming", Department of Computer Sciences, University of Texas at Austin, April 1994.
• Cog93: L. Coglianese and R. Szymanski, "DSSA-ADAGE: An Environment for Architecture-based Avionics Development", Proc. AGARD, 1993. Also, Technical Report ADAGE-IBM-93-04, IBM Owego, New York, May 1993.
• For81: C. Forgy, OPS5 User's Manual, Technical Report CMU-CS-81-135, Carnegie Mellon University, 1981.
• Hei93: John S. Heidemann , Gerald J. Popek, File-system development with stackable layers, ACM Transactions on Computer Systems (TOCS), v.12 n.1, p.58-89, Feb. 1994 [doi>10.1145/174613.174616]
• Hut91: Norman C. Hutchinson , Larry L. Peterson, The X-Kernel: An Architecture for Implementing Network Protocols, IEEE Transactions on Software Engineering, v.17 n.1, p.64-76, January 1991 [doi>10.1109/32.67579]
• McD78: J. McDermott, A. Newall, and J. Moore, "The Efficiency of Certain Production Systems", Pattern Directed Inference Systems, Waterman, Hayes, Roth (ed), Academic Press, New York, 1978.
• Mir90: D. Miranker, D. Brant, B. Lofaso, and D. Gadbois, "On the Performance of Lazy Matching in Production Systems", Proc. National Conference on Artificial Intelligence, 1990.
• Mir91: D. P. Miranker , B. J. Lofaso, The Organization and Performance of a TREAT-Based Production System Compiler, IEEE Transactions on Knowledge and Data Engineering, v.3 n.1, p.3-10, March 1991 [doi>10.1109/69.75882]
• Sir93: Marty Sirkin , Don Batory , Vivek Singhal, Software components in a data structure precompiler, Proceedings of the 15th international conference on Software Engineering, p.437-446, May 17-21, 1993, Baltimore, Maryland, United States
• Sir94: Martin Jay Sirkin, A software system generator for data structures, University of Washington, Seattle, WA, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Measurement, Performance, Theory