Issue927

Title M&S refactoring part 2: get rid of LabelEquivalenceRelation and use label mappings local to TransitionSystem instead
Priority feature Status in-progress
Superseder Nosy List atorralba, jendrik, malte, silvan
Assigned To silvan Keywords
Optional summary
Part of issue567, and to some extent follow-up of issue851.

Created on 2019-09-18.15:34:48 by silvan, last changed by silvan.

Summary
Part of issue567, and to some extent follow-up of issue851.
Messages
msg8967 (view) Author: silvan Date: 2019-09-26.14:32:44
Added link to meta issue567.

I just found that issue851 can be seen as a predecessor of this issue. To quote its summary: 
Possible further improvements: do not store information for all labels in each
transition system, but only for the relevant ones. This requires either a
concept of local label numbers and a mapping between global and local labels,
or using hash maps instead of vectors whenever storing information per label,
leaving out irrelevant labels.
msg8964 (view) Author: silvan Date: 2019-09-21.17:35:43
I'll you know, yes.

In step 3, after reducing labels and shrinking, we always make sure that there are no gaps in vector<vector<Transition>>, i.e., we have a contiguous "numbering" of "local labels". 

The effect can be both negative or positive, especially in large instances, sometimes reducing memory and speed, sometimes trading the former for the latter: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v3-issue927-v2-issue927-v3-compare.html
msg8963 (view) Author: malte Date: 2019-09-20.21:36:42
Hi Silvan, I'm curious, but lack the time, so I'll stay quiet for the time being.  But sounds exciting! Let us know when something needs to be done in terms of reviewing etc.
msg8962 (view) Author: silvan Date: 2019-09-19.11:41:38
In a small second step, I did some more minor refactoring to avoid having a global label mapping from global to local labels, but instead having it individually for each transition system. No large changes: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v2-issue927-v1-issue927-v2-compare.html
msg8961 (view) Author: silvan Date: 2019-09-18.22:04:06
The results of the first step are in. The only change is to replace LabelEquivalenceRelation (which uses a hash map to map global labels to local label group ids and a list for said groups) by a combination of global to local and local to global label mappings in each transition system, only using vectors.

https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v1-issue927-base-issue927-v1-compare.html

There is a clear positive performance trend and we can finish the computation of atomic FTS and the whole heuristic in more cases than before. (The attributes ms_out_of_memory and ms_out_of_time were not correctly parsed as of this writing; the report will be updated tomorrow.)

Here's a pull request if someone is already curious: https://bitbucket.org/SilvanS/fd-dev/pull-requests/54/issue927/diff
msg8960 (view) Author: silvan Date: 2019-09-18.15:34:48
In a recent discussion with Álvaro, we came to the conclusion that it would be worth trying to change the representation of transition systems. In particular, getting rid of LabelEquivalenceRelation and its underlying data structure of using a hash map from labels to local label group ids, and using lists for label groups. Using the notion of "local labels" and vector<int> to store both a mapping from "global" to local labels and vice versa could not only help simplify the code greatly, but also potentially improve performance.

In a first step, we will replace LabelEquivalenceRelation by appropriate mappings (vector<int>) as just described. Later, we could also try to always keep local and/or global label numbers contiguous and thereby get rid of the need for testing if a global label number is valid or not (because it has been reduced). In principle, we could also attempt the same thing for transition systems in factored transition systems. Finally, what is up for debate is whether we want to not store transitions of irrelevant labels, like it was the case years ago before the introduction of generalized label reduction.
History
Date User Action Args
2019-09-26 14:32:44silvansettitle: M&S: get rid of LabelEquivalenceRelation and use label mappings local to TransitionSystem instead -> M&S refactoring part 2: get rid of LabelEquivalenceRelation and use label mappings local to TransitionSystem instead
messages: + msg8967
summary: Part of issue567, and to some extent follow-up of issue851.
2019-09-21 17:35:43silvansetmessages: + msg8964
2019-09-20 21:36:42maltesetmessages: + msg8963
2019-09-19 11:41:38silvansetmessages: + msg8962
2019-09-19 09:40:57jendriksetnosy: + jendrik
2019-09-18 22:04:06silvansetmessages: + msg8961
2019-09-18 15:34:48silvancreate