Title M&S refactoring part 2: get rid of LabelEquivalenceRelation and use label mappings local to TransitionSystem instead
Priority feature Status reviewing
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.

Part of issue567, and to some extent follow-up of issue851.
msg9343 (view) Author: silvan Date: 2020-06-09.09:30:59
I evaluated the current implementation (with all improvements together) after merging from default:
msg9332 (view) Author: silvan Date: 2020-05-24.16:00:21
I looked into this again today but couldn't actually find anything else I would like to do in this issue. So now, with an unnecessary delay of 8 months :-), I'd like to ask for a review. Or, as a first step, for ideas of how to simplify reviewing in this case. The pull request list the following changes:

+0 -59
M src/search/algorithms/
+64 -1
M src/search/algorithms/equivalence_relation.h
+3 -7
M src/search/merge_and_shrink/
+8 -9
M src/search/merge_and_shrink/
+5 -5
M src/search/merge_and_shrink/factored_transition_system.h
+69 -47
M src/search/merge_and_shrink/
+72 -0
A src/search/merge_and_shrink/
+47 -0
A src/search/merge_and_shrink/global_labels.h
+0 -134
D src/search/merge_and_shrink/
+0 -122
D src/search/merge_and_shrink/label_equivalence_relation.h
+3 -4
M src/search/merge_and_shrink/
+0 -62
D src/search/merge_and_shrink/
+0 -46
D src/search/merge_and_shrink/labels.h
+4 -1
M src/search/merge_and_shrink/
+1 -2
M src/search/merge_and_shrink/
+1 -3
M src/search/merge_and_shrink/
+270 -129
M src/search/merge_and_shrink/
+50 -52
M src/search/merge_and_shrink/transition_system.h 

The files labels.* and global_labels.* should be reviewed next to each other (the new class is a bit simpler) and some of the logic of what used to be in label_equivalence_relation is now part of transition_system (and fts_factory, which creates transition systems), however also modified as described below. The change to equivalence_relation is due to making refine being a templated method (therefore in the header). The rest are only small changes required to adapt to the changed interface of transition systems.
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:
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:
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.

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:
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.
Date User Action Args
2020-06-09 09:30:59silvansetstatus: in-progress -> reviewing
messages: + msg9343
2020-05-24 16:00:22silvansetmessages: + msg9332
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