| Initial Rete Network Construction [message #1832981] |
Wed, 30 September 2020 10:15  |
 Hans van der Laan
Messages: 34
Registered: February 2020 |
Member |
|
|
Hey,
Are there any optimizations being performed under-the hood when the model is loaded and the Rete networks are constructed? Or is loading a model equivalent to instantiating an empty model, adding each element one-by-one and propagating the changes through the rete networks?
I'm currently working a performance evaluation of a VIATRA-based solution. I use VIATRA to verify model properties, which are specified as graph patterns. I want to give an impression of the efficacy gain by performing the verification incrementally instead of in batch. I want to do this in a similar fashion as the train benchmark [1].
However, some of the graph patterns are recursive. Therefore, I cannot use the local search engine to verify the model properties. I'm thinking about using the incremental engine as a "stand-in" batch-engine. To simulate batch checking, I want to rerun the incremental engine from scratch. However, I'm curious as to how representative using the incremental engine as a "stand-in" batch-engine is. From the Train Benchmark, it looks as the initial read/check phase take roughly the same time with the local search and incremental engine. I'm looking to better understand what happens under the hood, therefore my question.
Kind regards,
Hans
[1] The Train Benchmark: cross-technology performance evaluation of continuous model queries
|
|
|
| Re: Initial Rete Network Construction [message #1833068 is a reply to message #1832981] |
Thu, 01 October 2020 16:34  |
Zoltan Ujhelyi
Messages: 392
Registered: July 2015 |
Senior Member |
|
|
Hi Hans,
there are some minor differences whether Rete is constructed before or after the model is loaded, mainly because of two reasons:
(1) If you initialize Rete after the model is loaded, the model has to be traversed again to fill out the indexes VIATRA uses; while if VIATRA is set up before the model is loaded, this indexing happens right as the elements are added to the containment hierarchy.
(2) If i recall correctly, there are a few cases Rete tries to optimize the Rete structure based on the model contents, e.g. based on the number of elements of a given type. To be honest, I am not sure whether I am remembering the discussions about optimizations to implement or some case that are already included, but the engine is allowed to take into account what it knows about the instance models to create the plan. The local search-based algorithm greatly relies on these bits of information to provide efficient search plans.
Our experience with using Rete as a "batch" engine is that it works surprisingly effective in this regard for a wide range of queries, before we had the local search engine we have provided a functionality called "run-once" query engine [1]: a query engine that does not listen to model changes (and thus works as expected with derived features as well). However, you have to be careful, as freeing up the indexes and then rebuilding them might easily result in a lot of objects created, thus increasing the load on the garbage collector (that can result in performance issues on its own). We had some experiments with combining local search and Rete based searches since 2010 [2, 3], and in general we have some ideas which is better for which cases:
1. You can choose between lower memory consumption and faster search times (with some additional time required for setting up the indexes).
2. For most queries, the sum of initialization and search times are comparable, but there are queries that greatly prefer one or the other approach. The more times you have to execute the queries, the greater the index-based approaches overall execution times becomes better.
3. Rete is often better for "global queries": queries where you are interested in all the matches of the model, while search-based approaches can handle "local" queries where you bind some parameters (provide some context) and you are only interested in results related to these parameter values.
In other words, you can use Rete as a "batch" engine, but it has some pitfalls for measurement results. If you really have to go that way, I recommend measuring not two but three cases: (1) incremental Rete; (2) batch Rete and (3) local search, and for the cases with recursive patterns you simply state that these are not supported with local search, but for the other patterns case (2) provides a comparison what you can expect for your set of queries.
Hope this was helpful,
Zoltán
[1] https://www.eclipse.org/viatra/documentation/query-api.html#_run_once_query_engine
[2] https://link.springer.com/article/10.1007/s10009-010-0149-7
[3] https://ieeexplore.ieee.org/document/6747181?arnumber=6747181
|
|
|
|
Powered by
FUDForum. Page generated in 0.02895 seconds
] 
Search
Help
Register
Login
Home
