After discussing this with Silvan: merged and pushed.

There are some points mentioned in the discussion here that we should add to the
meta-issue issue567, I think. I'll take care of this next.

Experimental results for the difference between v4 and v5 are in:

http://ai.cs.unibas.ch/_tmp_files/helmert/issue561-v5-issue561-v4-issue561-v5-compare.html

They look surprisingly good. :-) I suggest we merge this version.

The results look fine indeed -- we can use some of the speed gains from v4 for
the expected slowdown in v5 :-)

Experimental results for the difference between v3 and v4 are in:

http://ai.cs.unibas.ch/_tmp_files/helmert/issue561-v4-issue561-v3-issue561-v4-compare.html

Things seem to be a little bit faster overall, and at a quick glance I see no
problems.

I have also started experiments with a new tag v5, which cleans up the ugliness
in TransitionSystem::apply_abstraction w.r.t. distance computation. I expect
this to slow things down somewhat -- let's hope it's not too bad.

I've tagged a new revision issue561-v4, where the main change is that the atomic
transition systems are created by a factory function. To facilitate this and
avoid giving the factory access to private attributes of TransitionSystem, the
old "two-shot" construction of atomic transition systems is now gone: their
constructor now leaves them in their complete final state.

More work needs to be done on that front, but the code change was already
disruptive enough that it seems wise to run experiments with the current
version. There are some unnecessary allocations and movements there at the
moment, so we might see a bit of a performance penalty.

I've started an experiment that compares v3 to v4.

I've changed the title of this issue to reflect what it is really about now.

The "minor changes" are things like introducing smart pointers in various places
and using make_shared/make_unique.

> I'd usually go with 1), but an additional complication is that we have issue520
> already for taking TransitionSystem apart.

Thanks for pointing that one out! I was looking for this discussion but couldn't
find it. That issue so far has no code, so I think it's not a big deal to close
it and refer here. I'll go ahead and do that, and then rededicate this issue.

Regarding the experiments:
 - base-v1 seems totally fine.
 - v1-v2: for some of the f-preserving shrinking strategies, there is already a
slight decrease in score_search_time - Sum, but not for Average, so this is also
fine, I guess.
 - v2-v3: as you pointed out, the loss in runtime is not negligible, but with
your patch, I agree
   that it is fine, even if we did not recover all of it later on.

Regarding mss4462:

> Silvan, did I read the code correctly?

Yes, I think so. 1) should not be a problem for our usual benchmarks, I think,
but still, this has never been tested. 2) definitely seems to waste a lot of
effort, but as you pointed out, we never tested this part of the code in our
paper experiments (was only used for IPC14).

Quoting from msg4446:

> Some options:
> 1) We can rededicate this issue to taking TransitionSystem apart and open a new
> issue for what this issue was originally apart. This would requires some copying
> of comments in the tracker, but we could leave the current issue561 branch as is.

> 2) We can open a new issue for taking TransitionSystem apart and rebase the
> issue561 branch in Silvan's repository (and my local clones) to belong to that
> new issue instead.

> 3) We can do everything in issue561.

> Silvan, which one do you like best?

I'd usually go with 1), but an additional complication is that we have issue520
already for taking TransitionSystem apart. So we can either go with 2), which
would require copying all the comments and experiments related to this to
issue520, and worse, taking out part of the patch of this issue and recreate the
history on a different branch (which may need to become a side branch of this
issue, and which definitely would require differently named issue tags and issue
experiments). The easier solution therefore seems to use this issue here for
taking apart TransitionSystem, to extract all comments related to other things
to a new issue (should not be too many of those), and to close issue520,
pointing to this new issue. The cleaner solution would be 1), however. I am
definitely against 3), and probably would go with 1), given that 2) comes with
re-basing or better re-creating an issue branch, starting from a not merged
different issue branch. What do you think?

> If you think it's worth it, I can start a small experiment with a modified
> version of v3 that allows inlining again, so that we have some more data on
> whether or not this can explain the performance difference.

I did a tiny test locally with one configuration and three instances whose
runtime was adversely affected by v3: inlining the two method did not eliminated
the loss of performance, but it reduced it by a factor of three. If we can
extrapolate from this, we'd get a typical -0.01 on average speed, which perhaps
we might recover by getting rid of the additional indirection in the shrink
strategies (asking Distances for the distances directly rather than asking the
transition system to ask Distances). I suggest we let this be for now; it
doesn't seem large enough to worry about.

[Deleted previous message because of wrong link. This one should be correct.]

Experimental results for the difference between v2 and v3 are in:

http://ai.cs.unibas.ch/_tmp_files/helmert/issue561-v3-issue561-v2-issue561-v3-compare.html

There is a slight decrease in speed this time (typically around -0.03 on average
in score_total_speed).

My best guess is that this is because TransitionSystem::get_init_distance() and
TransitionSystem::get_goal_distance() cannot be inlined with the current code
(because they defer to the Distances object, and we don't want
transition_system.h to include distances.h if we can avoid it), and hence access
to the distances has become a bit more expensive. We should be able to improve
this again once we've decoupled things further.

My hope is that after the refactoring is complete, code that needs the distances
would be able to ask a Distances object directly rather than asking the
transition system. Then I see no reason why we couldn't be back to the old speed.

If you think it's worth it, I can start a small experiment with a modified
version of v3 that allows inlining again, so that we have some more data on
whether or not this can explain the performance difference.

Experimental results for the difference between base and v1 are in:

http://ai.cs.unibas.ch/_tmp_files/helmert/issue561-v1-issue561-base-issue561-v1-compare.html

They also look benign to me. What do you think?

v3 should be done later this afternoon.

Experimental results for the difference between v1 and v2 are in:

http://ai.cs.unibas.ch/_tmp_files/helmert/issue561-v2-issue561-v1-issue561-v2-compare.html

They look benign to me. What do you think?

(Unfortunately, we don't have results for the difference between base and v1
yet, as mentioned in a previous comment. They are on their way.)

While refactoring the code that generates the atomic transition systems, I
noticed two things:

1. In the atomic transition system for variable v, it looks like we
   generate self-loops for each value of v and each operator o that does not
   mention v. So if there are N values and M irrelevant operators, this will
   take time and space O(NM). I assume that the self-loops for the different
   irrelevant operators are then combined into one in label normalization,
   reducing the representation to O(N). It might be worth checking out if we
   can get a performance boost from avoiding the O(NM) intermediate
   representation, instead generating a "normalized" representation for the
   irrelevant operators from the start.

2. If we have conditional effects, then we might get more transitions than
   necessary because each conditional effect is considered in isolation.
   Let's consider a variable with domain {0, 1, 2} and an operator with
   no preconditions and three conditional effects:
   if v = 0, then v := 1
   if v = 1, then v := 2
   if v = 2, then v := 0
   We would like this to only generate three transitions: 0->1, 1->2 and
   2->0. But because we consider each effect in isolation, we will also
   get 0->0 (from the second and third effect), 1->1 (from the first and
   third) and 2->2 (from the first and second). This is a bit of a pity,
   and it can also lead to a severe blowup in representation before
   normalization takes place: if we have M values in the domain, then
   *each* effect can generate O(M) self-loops, so with K effect, we have
   an intermediate size of O(MK), even though the many parallel self-loops
   will disappear after normalization. Bearing in mind that some tasks have
   tens of thousands of conditional effects in a single operator, this can
   be a problem.

Silvan, did I read the code correctly?

I don't think we need to act on these two points immediately, but I wanted to
record them while I still understand this part of the code, which is quite nasty
(a single 126-line function in master; in the branch, it's split up into smaller
parts, but the largest function there still has 71 lines).

If we should decide to act on these later, no. #2 in particular will very likely
have no effect on our standard M&S benchmark suite (which has no conditional
effects, I think), and it's very easy to mess the conditional effect code up if
we don't test the right domains.

I've started some experiments on the first three sets of changes in this issue.
The first experiment broke and I have to restart it, so it looks like we'll get
results for part #2 first, then part #1, and then part #3. (Assuming no further
breakage.)

I'm now leaning towards using this issue for the "take transition_system.cc
apart" thing and adding a separate one for laundry-list changes that aren't
incorporated yet. But I suggest to wait for the outcome of the experiments
before doing that. I assume they will be ready tomorrow.

One item for the laundry list of smaller changes: we should introduce a
namespace for merge and shrink. Currently we're using up quite generic words,
such as "Transition", by having everything in the global namespace.

> For now, the idea is to incorporate all smallish fixes and
> improvements in this issue and use separate issues for larger changes.

We have worked on the code a bit and started to break TransitionSystem into
smaller pieces.
That is a large enough change that it should perhaps be an issue of its own?
Some options:
1) We can rededicate this issue to taking TransitionSystem apart and open a new
issue for what this issue was originally apart. This would requires some copying
of comments in the tracker, but we could leave the current issue561 branch as is.

2) We can open a new issue for taking TransitionSystem apart and rebase the
issue561 branch in Silvan's repository (and my local clones) to belong to that
new issue instead.

3) We can do everything in issue561.

Silvan, which one do you like best?

The default value "-1" there does not mean infinity. Unfortunately, it's not
possible to pick a single default value from the usual range of these variables
(a number or infinity) that would match the current default behaviour. The
rationale behind the current behaviour is that we want to permit the user to set
any of

1) max_states
2) max_states_before_merge
3) both
4) neither

and get somewhat reasonable behaviour. Infinity wouldn't satisfy this, as the
default behaviour (case 4) would be very poor.

I'm not sure what a good solution that avoids the current "special" value could be.

One thing that should be addressed (maybe even directly in the default branch) is 
that the shrink strategies still use the option value "-1" for specifying "no 
limit". This should probably be changed to "infinity".

This is part of meta issue432.

The title is very generic, admittedly, but as I don't know what we will be
finding while progressing with the code review, I could not find anything more
suitable. For now, the idea is to incorporate all smallish fixes and
improvements in this issue and use separate issues for larger changes.