Optimizing Graphical User Interfaces

This project seeks to improve the implementation of two aspects of prototyping toolkits that are used for the development of graphical interfaces: (1) constraints and (2) structured graphics. Its research contribution is the development of compiler techniques that allow rapid prototyping environments to support custom graphics while simultaneously delivering excellent time and storage performance. More broadly, it seeks to put in place tools that advance the objectives of the National Information Infrastructure (NII).

The Problem

Currently constraints and structured graphics are not viable for large applications because they cannot project more than a few hundreds of objects on the screen. The reasons for this shortcoming are twofold:

Storage: The storage requirements of these two techniques are so great that they can support hundreds of objects, but not thousands or hundreds of thousands of objects. To support rapid prototyping, the structured graphics objects must be heavyweight objects that are (a) expressive (supporting tens of predefined properties), and (b) malleable (allowing users to dynamically add and delete new properties). Similarly, constraints require an inordinate amount of storage to represent formula objects and dependencies among formula objects.
Performance: The performance of these two techniques is adequate when there are tens of objects on the screen. However, our extrapolations of performance measurements using existing toolkits and our preliminary experience with applications involving hundreds of objects suggest that performance will be unacceptably impaired when applications necessitate thousands or even hundreds of thousands of objects on the screen. The problems arise from dynamic scheduling of formula evaluations, from overhead incurred in calling the functions that execute constraints, and from paging caused by toolkit applications that cannot be fit into memory due to their enormous storage requirements.

To ameliorate the difficulties posed by these two techniques in large applications, researchers have developed optimizations such as lightweight glyph objects, constraint plans, and constant propagation that eliminate constraints. However, these innovations sacrifice rapid prototyping by requiring a programmer to program at a low-level. Currently there are no compiler techniques for automatically translating an application written in a high-level protyping environment into a fast, lightweight application that employs these optimizations. A programmer must either reimplement the application in a faster, lower-level toolkit or must provide extensive static declarations as found in Garnet or ThingLab.

Research Strategy

Our research is developing compiler techniques that automatically optimize an application by using static and dynamic profiling strategies that have proven successful in both object-oriented computing and high-performance computing. The profile-based approach to compilation makes use of information that is obtained from the actual execution of a program on example inputs.

We are attempting to optimize interactive graphical applications by automatically instrumenting the code and gathering the required semantic information as the program executes. The semantic information will be used to optimize a program both statically and dynamically. More particularly, as a program executes, the semantic information will be used to:

Decrease the storage requirements of the most frequently occurring objects. This reduction can be achieved using a) glyph optimization (recomputing some values on demand rather than storing them with the object), and b) composite object folding (merging a collection of objects, such as the objects comprising a button, into a single object);
Eliminate constraints and dependencies among constraints. Constraints and dependencies will be eliminated by (a) using constant propagation and b) developing novel constraint-solving algorithms that can operate correctly without maintaining full information about constraints or dependencies among constraints.
Compute plans for each operation that evaluate predetermined sets of constraints. These plans can be reused when an operation is completed.

Funding

This project is being supported by the National Science Foundation under Grant No. CCR-9633624.

Undergraduate Students

Lawrence Karnowski

Graduate Students

Rick Halterman

Alumni

Scott Venckus (MS-1996)

Publications

``Optimizing Toolkit-Generated Graphical Interfaces'', 1994 ACM SIGGRAPH Symposium on User Interface Software and Technology, Marina del Rey, CA, November, 1994, pp. 157-166.

``An Empirical Study of Constraint Usage in Graphical Applications'', 1996 ACM SIGGRAPH Symposium on User Interface Software and Technology, Seattle, WA, November, 1996, pp. 137-146. With Scott Venckus.

``Compilation of Prototype Objects Using Profile Information'', Submitted to OOPSLA'98. With Lawrence J. Karnowski.

``Using Model Dependency Graphs to Reduce the Storage Requirements of Dataflow Constraints in Prototype-Instance Systems'', Submitted to OOPSLA'98. With Richard L. Halterman.

``Using Model Dataflow Graphs to Reduce the Storage Requirements of Constraints'', To appear in ACM Transactions on Computer Human Interaction. With Richard L. Halterman.

Software

Pam Interface Toolkit: Interactive, interpreted front-end to the Amulet graphical interface development environment that allows a programmer to rapidly prototype applications by creating graphical objects and callback procedures in Python. Pam is an outgrowth of the adaptive, profile-based compilation project and is used to help us prototype our optimization ideas.