GrGen is a new generative programming system for graph rewriting.
Description
It features an expressive specification language and implements a modification of the theoretically well-founded SPO approach to graph rewriting.
The generated program code executes very fast and is easy to invoke through a comfortable interface.
According to a benchmark introduced by Varró the performance of rewriting, especially of the potentially costly pattern matching, is at least one order of magnitude faster than of any other known system.
We achieve this by using special tailored data structures and by a dynamically optimizing approach to sub graph matching, which means that the optimization can be done at runtime depending on the actual present host graph.
In this context we use the concept of search plans to represent different matching strategies.
By stating a cost model we understand the generation of good search plans as an optimization problem, which we solve heuristically.
This benchmark was introduced by Gergely Varró. The benchmark itself is described in a tech report a more high-level description as well as runtimes for several graph rewrite systems are given in a paper by Gergely Varró, Andy Schürr, and Daniel Varró.
Extensive benchmark results can be found on a website maintained by Gergely Varró.
Runtimes for the mutex benchmark of the GrGen SearchPlan graph engine.
Detailed numbers can be found in a
table.
Runtime per rule application for the mutex benchmark of the GrGen SearchPlan graph engine, i.e. all runtimes for the whole benchmark are divided by the size of the benchmark (which is proportional to the number of rule applications in this benchmark).
Detailed numbers can be found in a
table.
Runtimes for the mutex benchmark of the GrGen SearchPlan graph engine compared with major tools.
Note the logarithmic scaling of the time axis.
The benchmark was conducted using the SearchPlan graph engine on an AMD Athlon(tm) XP 3000+ running SuSE Linux 9.3 with kernel version 2.6.11.4-21.11-default.
The runtime displayed includes the whole rule applications that include: matching, rewriting, cleanup, and the overhead executing the rewrite sequences (detailed numbers can be found in a table).
The graph analysis (for the computation of the costs of the possible search plan operations) remains under 2 ms for benchmark sizes upto 1000. For sizes up to 10000 it remains under 15 ms.
The runtime for the heuristic determination of searchplans was always below timer resolution (1ms).
Questions, suggestions, bugs? Feel free to contact the maintainer and main author: Rubino Geiss
