Constraint systems have been used for some time to implement various components of a user interface. High level support for flexible screen layout has been among the more important uses; layout constraints in a user interface toolkit provide a declarative mechanism for controlling the size and position of objects in an interactive display, along with an efficient update mechanism for maintaining display layouts automatically in the face of dynamic changes. This paper describes a new technique for implementing one-way layout constraints which overcomes a substantial limitation of previous systems. In particular, it allows constraints to be implemented in an extremely small amount of space &emdash; as little as 17 bits per constraint &emdash; and still maintain the level of performance needed for good interactive response. These ultra-lightweight constraints, while not handling all cases, cover most relationships used for layout, and allow conventional constraints to be applied when needed. This paper will consider both a general technique for ultra-lightweight layout constraints and its specific implementation in a new Java™-based user interface toolkit.
Keywords: User Interface Toolkits, User Interface Layout, One-Way Constraint Systems, Lazy and Incremental Update, Space Optimization, Java™.
Constraint systems of various sorts have been applied to a number of user interface implementation tasks such as screen layout, semantic feedback, and synchronization of multiple views (for examples see [1-3, 6-9, 11-16, 20, 24, 25, 29-32, 34]). These systems allow relationships to be declared between objects, and provide a mechanism for automatically maintaining those relationships in the face of changes. For this paper we will be concerned with screen layout, so for example, a display object might be declared to be 5 pixels to the right of the previous object in a layout, or to fill the horizontal space provided by its parent object except for a 10 pixel border. These declarations are normally done with constraint equations such as:
x = prev.x + prev.w + 5;
x = parent.x + 10;
w = parent.w - 20;
Based on these equations, a constraint update or evaluation system would then be responsible for maintaining those relationships. Updates would be performed whenever the size or position of other objects changed, or for example, whenever the user changed the size of a window.
Because of their declarative nature and automatic update, constraint systems offer a number of advantages for expressing user interface layouts. In particular, they offer a powerful but convenient formalism for expressing flexible and dynamic layouts. Further, they can be directly connected to application objects to provide rich feedback, and very efficient incremental update algorithms have been developed for the types of constraints typically used in user interface applications (i.e., local propagation constraints typically used in one-way or multi-way form [28]).
However, as more experience has been gained with using constraints in user interface toolkits, practical problems have been uncovered. While most systems seem to perform quickly enough to provide excellent response time (due to their use of very efficient incremental update algorithms), the use of constraints at a relatively fine grain has caused significant space problems for practical applications. For example, it is reported in [33] that in Garnet [27] (the most widely used constraint-based system) a scrollbar consumes over 19K bytes, while a labeled rectangle uses over 4K bytes. Although this is perhaps an egregious example, if constraint-based toolkits are to be practical for building a wide range of different applications, a mechanism will be needed that is not vastly more expensive than other techniques. This paper provides such a solution. It describes a general technique for ultra-lightweight layout constraints &emdash; what we will call µconstraints &emdash; which can use as little as 17 bits per constraint (the implemented system described here uses 18 bits per constraint, and we are currently working on an expanded system using 35 bits).
µconstraints are designed to support layout tasks in a user interface toolkit &emdash; that is to control the size and position of interactive objects that appear on the screen, and to automatically update those positions when interface objects or windows change size or position. Because they are so small, they can be applied even for very large interfaces without fear of space efficiency problems. (For discussion of another important, but unrelated, space saving technique in user interface toolkits, see [4].)
In order to maintain their exceedingly small size µconstraints limit the set of relationships that can be expressed between objects and use a slightly less efficient update algorithm than our previous systems [17, 18]. However, the system provides good real-time response even in interpreted Java-based interfaces, and the class of relationships that can be expressed are designed to cover what our experience leads us to believe are most cases in actual layouts. For layout constraints that cannot be expressed, traditional (heavyweight) constraints can be easily applied instead (with roughly the same speed as the remaining µconstraints, and space utilization comparable to traditional constraints).
In the next section, a discussion of the constraint update algorithm used here will be provided. Then a discussion of the unique concepts of µconstraints will be provided, followed by a discussion of specifics of constraint encoding in our prototype implementation. Next extensions to the system will be considered, followed by discussion of early experience with the system. Finally discussion of some performance simple tests and a conclusion will be provided.
Figure 1. Simple Interface Requiring Both Top-Down and Bottom-Up Layout Strategies
Layout is the process of sizing and positioning objects that appear in a user interface display. In most modern toolkits, interactive objects (or simply interactors) are organized hierarchically with a parent object grouping together a series of subordinate child objects, which may in turn serve as a parent object, and so on recursively. In a hierarchical setting, most layout computations can be seen as either bottom-up &emdash; where child characteristics (e.g., size) determine parent characteristics &emdash; local &emdash; where characteristics are derived from the object itself or its siblings &emdash; or top-down &emdash; where child characteristics are determined by those of the parent (these layout strategies can also be thought of as inside-out, local, and outside-in respectively).
Each of these basic forms of layout can be carried out within a simple bottom-up or top-down pass over the interactor tree. Unfortunately, used alone, none of these forms of layout is typically sufficient. For example, Figure 1 shows a simple interface built with our system which requires several layout strategies simultaneously. Here we can see that even within a single object, such as the column object organizing the palette on the left, both bottom-up and top-down layouts may be needed. In this case the width of the palette is determined by the size of the buttons within it, while the height expands to fill the space provided by the parent object.
As a result, although some systems use a single top-down or bottom-up strategy (for example [5]), most must use a more complex multi-pass strategy. For example the Xt toolkit [26] uses a very complex negotiation process which can in the worst case take O(n2) time.
Rather than use a fixed structure of passes over the interactor tree, constraint-based layout typically allows each of the overall layout strategies to be employed wherever it is needed. Specific layout computations are then done in an order that matches whatever specification is made. This order is a dependency-based order. If a value A needs some value B in order to be computed, we say that A is dependent on B, and insure that B is computed before A.
Local propagation-based constraint update algorithms typically use a dependency graph internally to express the dependencies between various values that control a layout (i.e., values that store the position and size of each interactor object). If a constraint such as x = (parent.w - w)/2 is declared in a system, the one-way constraint algorithms used in this paper would establish dependency edges from the attributes parent.w and w to the attribute x as shown in Figure 2. This indicates that information flows from parent.w and w to x and hence x must be computed after they have been given valid values. (In contrast a multi-way algorithm would typically begin with a related undirected graph, then in a planning step choose a direction for each edge, after which the resulting one-way problem would typically be solved whenever parent.w or w were changed.)
Figure 2. Part of a Simple Dependency Graph
The constraint evaluation algorithm used in the work described here is a simple, but relatively efficient one. It is a simplification of the lazy update algorithm described in [17]. It works in two phases: when attribute values change (for example, when an object's size changes or it is reparented), any attributes which are directly or indirectly dependent upon the changed values are marked as out-of-date. These attributes are found by simply traversing the dependency graph forwards from the point(s) of change, marking all reachable attributes. Whenever an attribute value is requested, its out-of-date mark is examined. If the attribute is marked, then it may be out of date with respect to its defining equation and an evaluation of its constraint is done. This evaluation removes the out-of-date mark , recursively requests any attribute values needed to compute the constraint, and then executes the function associated with the constraint to obtain a new value. Attributes which are not directly or indirectly requested remain out-of-date until they are needed (hence this is a lazy update algorithm).
This algorithm, although not optimal (it does not do the early quiescence optimizations found in [17]), is fairly efficient, and has the property that it only requires one bit of bookkeeping information for each attribute (for the out-of-date mark). It also shares a property with essentially all other update algorithms: it must traverse portions of the dependency graph both forwards and backwards. The dependency graph is traversed forwards in the mark out-of-date phase and backwards during the evaluation phase. As a result, a straightforward implementation of the algorithm would need to keep dependency edge pointers in both directions (in data flow terms both the outgoing and incoming edges). Storage of these dependency edges is one of the larger uses of bookkeeping space [35], and elimination of this storage is key to the result presented here. Note that while the set of incoming edges is bounded by the number of values mentioned in the constraint equation, the number of outgoing edges is not bounded. As a result, more expensive variable sized data structures are typically needed if constraints can be attached and detached dynamically.
In order to minimize the space used for constraint bookkeeping, several important observations can be made. First, since they are only used during actual evaluation and do not change unless the constraint changes, incoming dependency edges can be implicitly maintained within the code used for constraint function evaluation and do not need to be explicitly stored (this approach is also taken in several other existing systems including [18]). Second, for layout constraints, the vast majority of constraints reference only the local neighborhood of an object, that is the parent, children, or siblings of an object. As a result, most outgoing dependency edges go only to attributes in this local neighborhood. Further, regardless of the use of constraints, a typical toolkit must maintain data structures that allow access to these same parent child, and sibling objects. Finally, we can note that many layout constraints come from a small set of operations, most commonly equality or copy constraints, and constant offset constraints (which typically place objects a fixed distance apart or with a fixed margin).
Using these observations, we can create a limited form of constraint that does not need to store any dependency edges. It does this by limiting its domain to the local neighborhood of a given object (specifically, itself, its parent, its children, and its next and previous sibling), by taking all constraints from a limited set, and by dynamically inferring the existence of the edges as needed.
Figure 3. Edge Inference Example
(a) Interactor Hierarchy with Constraints
(b) Inferred Dependency Edges
Each constraint from the limited set implies a particular set of incoming dependency edges, and as in other systems, these are not explicitly stored. The key to the µconstraint technique involves outgoing dependency edges. When operations need to traverse outgoing edges &emdash; in the case of the algorithm used here to propagate an out-of-date mark &emdash; each of the potentially dependent neighbor attributes is consulted. Each attribute in turn consults the constraint attached to it to determine which incoming dependency edges are implied by the constraint. If an incoming edge from the inquiring attribute is implied, then the corresponding outgoing edge also exists, and the operation across that edge (i.e., marking out-of-date) is performed. Otherwise, the operation is simply ignored.
Figure 3 illustrates an example of this process. Figure 3(a) shows part of an interactor hierarchy and the constraint equations applied to it. In this case we have constraints suitable for a centered column layout. Each child object centers itself horizontally with respect to the parent object, and the parent sets its width to cover the maximum width of its children. (The subArctic toolkit in fact supplies a column interactor which applies exactly these constraints). Note that no dependency edges are stored, only an encoding of the constraint equations.
Let us suppose that the width of child[1] changes. In response to this, the µconstraint system needs to infer the outgoing edges from child[1].w and mark all other attributes that directly or indirectly depend on it out-of-date. To do this, it attempts to propagate out-of-date marks to all neighbors of child[1] &emdash; in this case, parent, child[0] and child[2]. The constraint attached to each horizontally oriented attribute belonging to those objects is consulted to determine if there is an implicit incoming edge from child[1].w to that attribute. In this case, none of the sibling attributes have an implied incoming edge, so the mark out-of-date operation for them is ignored. However, parent.w depends upon the widths of all of its children so an edge from child[1].w to parent.w is inferred and parent.w is marked out-of-date.
Marking parent.w out-of-date causes additional out-of-date marks to be propagated. Again, out-of-date propagation is attempted for all the neighboring objects. In this case, the child objects each have a constraint which implies an edge from parent.w to child[i].x. Consequently each of these attributes is marked out-of-date, while other objects ignore the out-of-date propagation. Figure 3(b) shows the dependency edges that were inferred by this process along with final out-of-date marks (shown with gray shading).
This scheme represents a speed for space tradeoff. We use an indirect encoding scheme which requires polling a small set of local neighbors in order to avoid storage of dependency edges. This increases run-time by consulting attributes which are not actually dependents during the mark out-of-date phase of the algorithm. This does not change worst case behavior of the algorithm (which is still bounded by O(N+E) where N is the number of attributes and E is the number of dependency edges). However, it can reduce the savings normally gained by incremental update in some cases (particularly when large numbers of children must be consulted). Based on our performance tests (below) and experience with our implementation thus far, we believe this tradeoff is a good one.
An implementation of the µconstraint approach has been constructed within subArctic, an experimental new toolkit written in Java (this toolkit is a successor to the Artkit toolkit described in [10, 19]).
The subArctic implementation of µconstraints encode constraints in 16 bits and use two additional bits of bookkeeping per constraint. There are four layout attributes per object: x, y, width, and height resulting in a total overhead for layout constraints of 9 bytes per object .
Each constraint in this system either comes from a fixed set of 6 functions (listed below), or invokes a "hook" to use a conventional heavyweight constraint. Further, each constraint is limited to referring to one or two other attributes within its local neighborhood plus in some cases a fixed attribute of itself. Within these limitations, each constraint is encoded in four parts as indicated below:
Like many modern toolkits, the subArctic toolkit uses hierarchical coordinates where each object introduces a new coordinate system with its top-left corner at 0,0. To make the best use of hierarchical coordinates, position values are transformed before use in constraint equations (width and height values are coordinate system independent and hence are not transformed).
Each position value from a parent or sibling is transformed to be in the coordinate system of the parent of the object being constrained (the same coordinate system that the x, y position of that object is expressed in). As a result, the parent.left and parent.top values are always zero. Each position value from a child object is transformed into the coordinate system of the constrained object. Because of the hierarchical coordinates which place the constrained object's top left at 0,0, this allows the positions of child objects to be safely used to compute the size of the parent object (e.g., the width of a parent can be derived from the right edge of the last child as expressed in the parent's coordinate system).
Finally, note that the "none" and "external" evaluation functions ignore the attribute encoding of the first part of the constraint and do not request a value. The "none" function is used to denote that the attribute in question is not constrained. This is required since the 16 bit constraint encoding is always present.
The "external" function represents a "hook" for invoking an externally defined constraint when the µconstraint system is not expressive enough. When this value is coded, the object refers to a global hash table to find a constraint object associated with the interactor and attribute in question. This heavyweight constraint may refer to any values and may use any constraint function the user wishes to code. This allows attributes to be "bridged" across neighborhood boundaries and also provides a convenient interface to allow application objects to be connected to the layout constraints. Further this can be done at only a slight penalty over what traditional heavyweight constraints would cost anyway.
|
Name |
Equation |
Use |
|
plus_offset |
value+parm |
Positive offset from another value |
|
minus_offset |
value-parm |
Negative offset from another value |
|
centered |
(value-wh)/2+parm |
Typically used with parent.wh to perform centering |
|
plus_far_off |
value-wh-parm |
Positive offset from the right or bottom edge |
|
minus_far_off |
value-wh+parm |
Negative offset from the right or bottom edge |
|
fill |
next_sibling.xy - value - parm |
Distance from given position to left or top of next sibling |
|
external |
-- |
Constraint is an "external" (heavyweight) constraint |
|
none |
-- |
No constraint is applied to the attribute |
Table 1. Available Constraint Functions
In addition to the 16 bit constraint encoding, two other bits are stored for each attribute in the subArctic implementation. One bit is used for the out-of-date mark associated with the attribute. The second bit indicates whether there are any external constraints that depend upon the attribute (i.e., whether there are outgoing edges from this attribute to an external constraint). Whenever an attribute is marked as out-of-date, this bit is consulted. If it indicates the existence of external outgoing edges, a global hash table that maintains external edge lists is consulted, and out-of-date marks are propagated to each attribute or external object found there. Note that this bit represents a speed optimization and is not strictly necessary since the hash table could simply be consulted on every mark out-of-date operation.
The initial subArctic implementation of µconstraints was designed to explore the question of just how small constraints could be and still cover nearly all cases needed for layout. In addition to a larger encoding with more functions (see below), there are also several other possible techniques not currently implemented by the system that could be applied to increase the functionality of µconstraints.
First, since the "none" and "external" functions do not use the encoding for a dependent value or parameter, the encoding for these functions is redundant (i.e., 13 bits are unused). By recognizing these functions in only one encoded form (e.g., with the remaining 13 bits set to zero), this would leave 16,382 constraint encodings unused. These additional encodings could be used with a table of application specific constraints and/or a table of application specific indirect attributes to extend the functionality of the system with little additional space or time cost.
In addition, it is possible to use conventional subclass specialization to create objects which have a custom set of evaluation functions, replacing any or all of the six standard functions with other specialized computations. For example, the standard evaluation functions cannot directly implement the boxes-and-glue model employed for layout in the Interviews toolkit [22, 23]. However, it would be a relatively simple matter to create an interactor subclass which changed the interpretation of the three function encoding bits in order to implement the constraints needed for boxes-and-glue layout.
Finally, it is important to point out that it may be possible to use the basic µconstraint technique to support other forms of constraints, in particular to support eagerly evaluated one-way constraints, or even multi-way constraints. This is because the central technique of avoiding dependency edge storage can be applied essentially regardless of the update algorithm. The only real questions for these other algorithms will regard how small the other bookkeeping used by the algorithm can be made.
Although the subArctic toolkit using µconstraints has only been in use for a short time, we do have some preliminary experience with it. At this point we are only able to report anecdotal evidence from a small group of users. However, the system has been used by people outside our University to build several real applications including a resizeable newspaper-style layout using µconstraints, a "graphics editor", and a hierarchical data visualization system which produces tree layouts with µconstraints.
We found in our initial use that the vast majority of layout constraints could be expressed within the lightweight system. In fact, no heavyweight constraints were for layout in any applications built outside our own development group. This was partially affected by the fact that heavyweight constraints were not documented as well as µconstraints in the initial release of the system, and at that time, typically required construction of a new subclass for the constraint. However, it clearly indicates that common layout needs can normally be covered within the system.
We did find that the limit of an 8 bit constant parameter was a problem in a few cases. Further, although almost all things we wished to express were in fact covered by our 6 operations, a few more operations would be useful in certain circumstances.
In addition, we found that the learning curve for constraint-based layout was slightly steeper than expected (although this is an issue related to constraints in general, not µconstraints in particular).
Finally, although it was useful to validate that so few bits could be employed successfully, it is clear that we could afford a few more bytes per object even for large applications. As a result, we are currently implementing another version of the µconstraint encoding that uses 35 bits per constraint. This system will encode constraints in 32 bits (including a 16 bit constant) and use 3 bookkeeping bits (including an extra bit for cycle detection). In addition, µconstraints will also be applied to the visibility and enable status of each object. This new system will support many more operations, as well as operations with multiple parameter values. The algorithm and concept of this system, however, will remain the same.
In order to test the runtime performance of our existing µconstraint implementation, a small benchmark was constructed. This benchmark creates a long chain of interactor objects whose x position is each constrained to be 20 pixels to the right of its previous sibling's x position. Although this benchmark is quite limited in scope, similar benchmarks have been used for other systems (see for example [17, 18, 28, 34]), and it does provide some overall assessment of practicality. (Note that the subArctic implementation of µconstraints has not yet been optimized for runtime performance.)
1 parent = new min_parent_interactor(0,0);
2 for (int i = 0; i < 1000; i++)
3 {
4 child = new bench_interactor(10,10);
5 if (i != 0)
6 child.set_x_constraint(new constraint(PREV_SIBLING,LEFT,PLUS_OFFSET,20));
7 parent.add_child(child);
8 }
Figure 4. Code for Constructing Chain Benchmark
The code for constructing these objects is shown in Figure 4. In line 6 of this code we can see the basic interface for creating and attaching constraints to objects. Note that the constraint object created here is only temporary. The actual constraint is encoded in a 16 bit short integer stored inside the interactor object itself. Constraint objects are used at this level in order to provide a uniform interface for both µconstraints and conventional heavyweight constraints, both of which can be declared using subclasses of the constraint class and manipulated in the same manner.
For this benchmark, chains of 1000 attributes were constructed. A set of 100 trials were conducted where each trial consisted of changing the x position of the first interactor object, and then requesting the x position of the last interactor. To help isolate attribute evaluation from other runtime actions, a special subclass of interactor object was used. This subclass disables a number of features such as screen damage tracking that are normally provided "behind the scenes" by the subArctic toolkit.
Using this test setup an average rate of 3907 attributes evaluations per second was obtained on a lightly loaded 167 MHz Sun Ultra 1 170E processor (rated at 341 MIPS and 252 SPECint) running interpreted Java code under the Sun Java Development Kit version 1.0. In a separate 100 trial test isolating the mark out-of-date phase from the actual evaluation, an average of 4906 attributes per second were marked out-of-date, while evaluation alone occurred at an average rate of 19279 attributes per second.
These results indicate that µconstraints offer sufficient runtime performance to provide good interactive response for most applications. For example, if we desire response from each mouse movement to occur within 100 msec and (arbitrarily) assume 50 msec are spent on actual screen update, then about 195 objects could be repositioned (in one dimension) after each movement event. While this does not meet the needs of all applications (see for example the star-field display applications described in [21]), it should handle the needs of most moderately interactive user interfaces. This is particularly true since the update algorithm is incremental, and does not update attributes which are not affected by a particular interaction.
Further, we can expect a substantial improvement in the interpreted Java system in the near future when native code compilers become available. Although at the time of this writing, no Java compilers are sufficiently robust to handle the full subArctic system, benchmarks indicate that as much as a factor of 10 improvement over interpreted Java code can be expected. If this improvement materializes, then we can expect to be able to handle about 1950 attributes within response time goals (50 msec). In the presence of incremental evaluation this should be sufficient for nearly all needs.
This paper has presented the µconstraint ultra-lightweight constraint technique and described its implementation in the subArctic toolkit. The µconstraint approach allows layout constraints to be implemented in very little space &emdash; a small as 17 bits per constraint. This allows layout constraints to be used in a wide variety of applications &emdash; even for very fine grained layout &emdash; without fear of a space explosion. Although µconstraints limit the set of constraints that can be expressed, they still cover most common layout constraints, and provide a simple and transparent mechanism for falling back on conventional heavyweight constraints in the few cases where they are too restrictive. In addition, while µconstraints are typically somewhat slower than traditional constraint techniques, they still provide the level of performance needed to maintain good interactive response time in most applications.
This work was supported in part by a grant from the Intel Corporation, and in part by the National Science Foundation under grants IRI-9500942 and CDA-9501637.