Optimizing toolkit-generated graphical interfaces

ABSTRACT

Researchers have developed a variety of toolkits that support the development of highly interactive, graphical, direct manipulation applications such as animations, process monitoring tools, drawing packages, visual programming languages, games, and data and program visualization systems. These toolkits contain many useful features such as 1) structured graphics, 2) automatic display management, 3) constraints, and 4) high-level input-handling models. Despite a number of optimizations that have been described in the literature, most toolkit-generated applications run in a predominantly interpreted mode at runtime: they dynamically determine the set of constraints and objects that must be redisplayed, which requires the use of time consuming algorithms and data structures. The optimizations that do exist rely on semantic information that applies globally to all operations in an application. In this paper we identify a number of optimizations that require local, operation-specific semantic information about an application. For each operation, these optimizations pre-compute update plans that minimize the number of objects that are examined for redisplay, and pre-compute constraint plans that minimize the amount of dynamic scheduling and method dispatching that is performed for constraint satisfaction. We present performance measurements that suggest that these optimizations can significantly improve the performance of an application. We also discuss how a compiler might obtain from a programmer the information required to implement these optimizations.

REFERENCES

• 1: Paul S. Barth, An object-oriented approach to graphical interfaces, ACM Transactions on Graphics (TOG), v.5 n.2, p.142-172, April 1986 [doi>10.1145/22949.22951]
• 2: Alan Hamilton Borning, Thinglab--a constraint-oriented simulation laboratory., 1979
• 3: Alan Borning , Robert Duisberg, Constraint-based tools for building user interfaces, ACM Transactions on Graphics (TOG), v.5 n.4, p.345-374, Oct. 1986 [doi>10.1145/27623.29354]
• 4: Marc H. Brown, Exploring Algorithms Using Balsa-II, Computer, v.21 n.5, p.14-36, May 1988 [doi>10.1109/2.56]
• 5: Paul R. Calder , Mark A. Linton, Glyphs: flyweight objects for user interfaces, Proceedings of the 3rd annual ACM SIGGRAPH symposium on User interface software and technology, p.92-101, October 03-05, 1990, Snowbird, Utah, United States [doi>10.1145/97924.97935]
• 6: B. N. Freeman-Benson, A module mechanism for constraints in Smalltalk, ACM SIGPLAN Notices, v.24 n.10, p.389-396, Oct. 1989
• 7: Tyson R. Henry , Scott E. Hudson, Using active data in a UIMS, Proceedings of the 1st annual ACM SIGGRAPH symposium on User Interface Software, p.167-178, October 17-19, 1988, Alberta, Canada [doi>10.1145/62402.62429]
• 8: Ralph D. Hill, Languages for the construction of multi-user multi-media synchronous (MUMMS) applications, Languages for developing user interfaces, A. K. Peters, Ltd., Natick, MA, 1992
• 9: Ralph D. Hill, The Rendezvous constraint maintenance system, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.225-234, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168665]
• 10: Scott E. Hudson. A System for Efficient and Flexible One-Way Constraint Evaluation in C++. Tech. Rept. 93-15, Graphics Visualizaton and Usability Center, College of Computing, Georgia Institute of Technology, April, 1993.
• 11: David Kosbie, Brad Vander Zanden, Brad A. Myers, and Dario Giuse. Automatic Graphical Output Management. In Brad A. Myers, Ed., The Garnet Compendium: Collected Papers, 1989-1990, Carnegie Mellon University Computer Science Department, Technical Report CMU-CS-90-154, 1990.
• 12: J. Moloney , A. Borning , B. Freeman-Benson, Constraint technology for user-interface construction in ThingLab II, ACM SIGPLAN Notices, v.24 n.10, p.381-388, Oct. 1989
• 13: John Harold Maloney. Using Constraints for User Interface Construction. Ph.D. Th., Department of Computer Science & Engineering, University of Washington, Seattle, Washington 98195, 1991.
• 14: Brad A. Myers , Dario A. Giuse , Roger B. Dannenberg , David S. Kosbie , Edward Pervin , Andrew Mickish , Brad Vander Zanden , Philippe Marchal, Garnet: Comprehensive Support for Graphical, Highly Interactive User Interfaces, Computer, v.23 n.11, p.71-85, November 1990 [doi>10.1109/2.60882]
• 15: Brad A. Myers , Dario A. Giuse , Andrew Mickish , David S. Kosbie, Making Structured Graphics and Constraints Practical for Large-Scale Applications, Carnegie Mellon University, Pittsburgh, PA, 1994
• 16: Michael Sannella. The SkyBlue Constraint Solver. Tech. Rept. 92-07-02, Computer Science Department, University of Washington, July, 1992.
• 17: Bradley T. Vander Zanden, Incremental constraint satisfaction and its application to graphical interfaces, 1989
• 18: Brad Vander Zanden , Brad A. Myers , Dario A. Giuse , Pedro Szekely, Integrating pointer variables into one-way constraint models, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.2, p.161-213, June 1994 [doi>10.1145/180171.180174]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: User interface management systems (UIMS)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
automatic redisplay, constraints, development tools, optimization, structured graphics