Memory scalability in constraint-based multimedia style sheet systems

Multimedia style sheet systems uniformly use a constraint-based model of layout. Constraints provide a uniform mechanism for all aspects of style managementand layout and are better-suited to non-textual media than flow models. We have developed a prototype style sheet system, Proteus, and have used it with a variety of document types, including program source code. This work has exposed a critical performance problem in constraint-based style sheet runtime systems: memory usage. Existing constraint systems treat cached attribute values and constraints as first-class objects, each with its own storage. Program syntax trees are very large and the constraint data for a medium-sized source file can easily consume tens of megabytes of main memory. This scalability problem would be exposed by any document of any type containing thousands of objects. We present here a new constraint-based runtime system that is substantially faster and dramatically more space-efficient than its predecessor, which had first-class constraint objects. The improved performance is the result of exploiting important common cases and a sophisticated constraint representation that allows considerable sharing of information between individual constraints.