
| Benchmark                 | time %   |           |        |
|---------------------------|----------|-----------|--------|
| All-Interval (50)         | 102.48   |           |        |
| All-Interval (100)        | 101.17   |           |        |
| Golomb Rulers (Bnd, 10)   | 100.51   |           |        |
| Golomb Rulers (Dom, 10)   | 128.98   |           |        |
| Graph Coloring            | 144.58   |           |        |
| Magic Sequence (GCC, 500) | 103.56   |           |        |
| Queens (Dom, 10)          | 187.36   |           |        |
| Queens (Dom, 100)         | 155.62   | Benchmark | time % |
| Social Golfers (8-4-9)    | 522.62   |           |        |
| Social Golfers (5-3-7)    | 450.15   |           |        |
| Hamming Codes (20-3-32)   | 297.38   |           |        |
| Steiner Triples (9)       | 304.97   |           |        |
| Sudoku (Set, 1)           | 459.85   |           |        |
| Sudoku (Set, 4)           | 483.27   |           |        |
| Sudoku (Set, 5)           | 436.92   |           |        |

## 7.4 Iterators Versus Temporary Data Structures

The following experiments show that using range iterators improves the efficiency of propagators, compared to the use of explicit set data structures for temporary results.

For the experiments, temporary data structures have been emulated by wrapping all iterators in a cache iterator as described in Section 5.4. Table 7 shows the results. For integer propagators that perform the safe iterator-based domain operations introduced in Section 5.4, computing with temporary data structures results in 28% to 87% overhead (*Golomb Rulers Dom, Graph Coloring, Queens Dom*). For set propagators, which make much more use of iterators than integer propagators, the overhead becomes prohibitive, resulting in up to 4.8 times the runtime. The memory consumption does not increase, because iterators are not stored, and only few iterators are active at a time.

## 8 Conclusion

The paper has developed views for deriving propagator variants. Such variants are ubiquitous, and the paper has shown how to systematically derive propagators using different types of views, corresponding to techniques such as transformation, generalization, specialization, and type conversion.

Based on a formal, implementation independent model of propagators and views, the paper has identified fundamental properties of views that result in *perfect* derived propagators. The paper has shown that a derived propagator inherits correctness and domain completeness from its original propagator, and bounds completeness given additional properties of the used views.

The paper has presented an implementation architecture for views based on *parametricity*. The propagator implementation is kept parametric over the type of view that is used, so that deriving a propagator amounts to instantiating a parametric propagator with the proper views. This implementation architecture is an orthogonal layer of abstraction that can be implemented on top of any constraint solver.

An empirical evaluation has shown that views have proven invaluable for the implementation of Gecode, saving huge amounts of code to be written and maintained.

Furthermore, deriving propagators using templates in C++ has been shown to yield competitive (in most cases optimal) performance compared to dedicated handwritten propagators. The experiments have also clarified that deriving propagators is vastly superior to decomposing the constraints into additional variables and simple propagators. Acknowledgments. We thank Mikael Lagerkvist, Gert Smolka, and Thibaut Feydy for fruitful discussions. Christian Schulte has been partially funded by the Swedish