Summary I: Attributed Data
The overhead of matching CHR rules is alleviated by constraint store indexing. Attributed variables provide an efficient means of indexing on logical variables. Existing indexing strategies for ground terms, based on hash tables, incur considerable performance overhead, especially when frequently computing hash values for large terms.
In this paper we (1) propose attributed data, a new data representation for ground terms inspired by attributed variables, that avoids the overhead of hash-table indexing, (2) describe program analysis and transformation techniques that make attributed data more effective, and (3) provide experimental results that establish the usefulness of our approach.
Attributed Data Benchmarks
| name | source file | benchmark driver |
|---|---|---|
| chrg | chrg.pl | |
| flat_ram | ram.pl | bench_ram_op.pl |
| mergesort | mergesort.pl | |
| reverse | reverse.pl | |
| uf_opt | uf_opt.pl | |
| turing | turing.pl | |
| wfs | wfs.pl | |
| fib | fib.pl | |
| fib2 | fib2.pl | |
| dijkstra | fib_heap.pl | dijkstra_bench.pl, dijkstra_bench.pl |
Summary II: Flattening
Multi-headed rules are essential for the expressiveness of CHR, but incur considerable performance overhead. Current indexing techniques are often unable to address this problem. They are effective only when matchings have a particular form, or offer good run-time complexity rather than good absolute figures.
We describe two lightweight techniques for improving the effectiveness of existing CHR indexing techniques: two program transformations based on term flattening. With a complimentary set of post-processing program transformations the flattening overhead is considerably reduced.
We compare these techniques with the current state of the art in CHR compilation, and measure their efficacy in K.U.Leuven CHR and CHRd.
Flattening Transformations
Generic Flattening
- K.U.Leuven CHR (SWI-Prolog)
Download the sources, unpack them and run make flattener. With flattener in.pl out.pl you can transform a CHR program in file in.pl into a flattened program in file out.pl.
Benchmarks:
and auxiliary timing file.name original flattened benchmark driver gamma gamma.pl gamma.pl listdom listdom.pl listdom.pl mergesort mergesort.pl mergesort.pl ram ram.pl ram.pl ram_op.pl,ram_prog.pl zebra zebra.pl zebra.pl - CHRd (SWI-Prolog)
Download the sources, unpack them and run:
- ftrans(Option,Module) to translate CHR module Module into SWI Prolog with flattening, with Option being either +pp to enable post-processing, or -pp to disable post-processing (disabled by default)
- trans(Module) to translate CHR module Module into SWI Prolog without flattening
Benchmarks:
and auxiliary timing file.name original flattened gamma gamma.chr gamma.chr listdom listdom.chr listdom.chr mergesort mergesort.chr mergesort.chr ram ram.pl ram.pl zebra zebra.pl zebra.pl
Constraint Symbol Specialization
- K.U.Leuven CHR (SWI-Prolog)
Download the sources, unpack them and run make flattener. With flattener in.pl out.pl you can transform a CHR program in file in.pl into a flattened program in file out.pl. The flattener program has the following options:
- -nopp disables post-processing (enabled by default)
- -nofix disables flattening fixedpoint (enabled by default)
- -nolimits disables heuristic for restricting code growth (enabled by default)
Benchmarks:
name original flattened benchmark driver gamma gamma.pl gamma.pl listdom listdom.pl listdom.pl manners manners.pl manners.pl manners_64.pl mergesort mergesort.pl mergesort.pl ram ram.pl ram.pl ram_op.pl,ram_prog.pl zebra (1 iteration) zebra.pl zebra.pl zebra (2 iterations) zebra2.pl zebra2.pl - CHRd (SWI-Prolog)
Benchmarks (translated into SWI Prolog):
name original flattened benchmark driver gamma gamma.pl gamma.pl listdom listdom.pl listdom.pl manners manners.pl manners.pl manners_64.pl mergesort mergesort.pl mergesort.pl ram ram.pl ram.pl ram_op.pl,ram_prog.pl zebra (1 iteration) zebra.pl zebra.pl zebra (2 iterations) zebra2.pl zebra2.pl
Technical Report: Preliminary Ideas
Multi-headed rules are essential for the expressiveness of CHR, but incur a considerable performance penalty. Current indexing techniques are often unable to address this problem. They are effective only when matchings have a particular form, or offer good run-time complexity rather than good absolute figures. In this paper we describe three advanced indexing techniques: (1) two program transformations that make other indexing techniques more effective, (2) an index for ground terms more efficient than hash tables, and (3) a post-processing program transformation that eliminates runtime overhead of (1) and (2). We compare these techniques with the current state of the art, and give measurements of their effectiveness in K.U.Leuven CHR and CHRd. [Get it here]