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).
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
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
- 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.
This project is being supported by the
Science Foundation under Grant No. CCR-9633624.
``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
``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.
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.