4.4 Optimization: Caching

 

The specification S can be broken into several pieces, based upon its dependence on x and y:

For example,

may be transformed into

with

This is a natural extension of common sub-expression elimination, present in optimizing compilers [3]. Applying common sub-expression elimination in conjunction with symbolic rewriting, the example is transformed into

with

Such transformations are useful when evaluating S many times, which occurs during rendering.

Let ; after evaluating

the evaluation of

is more efficient if

some sub-expressions need not be re-evaluated.

With aligned cuts, it is likely that

has sub-expressions that have been evaluated before. For example, with cuts aligned along a grid,

are each computed 32 times, instead of 1024 times, if sub-expressions are cached; these calculations assume that every grid cell contains one pixel cluster. Caching takes minimal memory, and aids computation considerably; with our previous example, it would be computed once, instead of 1024 times, if is cached.

A better estimate of cache utility may be made by considering the graph being rendered. For , consider vertical lines, as shown in the following figure:

In the example shown, most lines intersect G twice; it follows that is usually computed twice, for each possible value of . Interval evaluation may ``smear'' the graph, so that may be computed several times for each actual intersection.

Jeff Tupper

March 1996