Part of meta issue567

PR: https://github.com/aibasel/downward/pull/158

Merged.

Looks good to me. I left a question for the pull request; I assume the answer is "yes" after I saw a bunch of similar changes in other files.

I focused on architecture/where the code lives etc., not the code itself. If you want someone to vouch for this, I suggest finding a second reviewer.

Experiment results after the latest changes: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1092/data/issue1092-v2-eval/issue1092-v2-compare.html

M&S construction time score still greatly increases, but the baseline in this experiment is slightly better than in the previous one, presumably because there is no more computation of "merge candidate structs" when not using caching. Still an overall very beneficial change.

I'd be happy for another round of review; the diff is pretty small now.

We discussed this further. A clean solution of a general caching mechanism would require to broaden the scope of this issue significantly. In particular, the merge-and-shrink algorithm should notify merge strategies (and others?) of each transformation it does, so that the merge strategy can determine if their cache information on merge candidates is still valid or not.

To keep the scope of this issue small, I decided to implement the caching option only for the expensive-to-compute MIASM scoring function. I added text to the option that explains that caching only works as long as the merge-and-shrink algorithm works in the way it currently does: no (non-exact) shrinking on factors other than those being merged and no non-exact label reduction.

We discussed this a bit, focusing on three points:

- Avoid shared_ptr to make it possible for entries to be empty; use optional instead.
- If the caching functionality is added by the base class, its implementation should also live in the base class.
- The change makes the previously logically immutable scoring function classes mutable, which will lead to complications once we move to builders.

I'm OK to merge this, but these points should be addressed in followup issues. In particular, it looks like we add an option for caching to all scoring functions, but if you use it for anything other than MIASM, it leads to an error. If the option must not be used, this perhaps should be mentioned in the documentation as well (and then it's perhaps easier to either add it just to MIASM or support it for all from the start).

The new change also imposes new requirements on scoring functions, i.e., that they don't change in a way that would invalidate the caching. I think it would be good for this to be clearly documented in our code, i.e., what is the contract for scoring functions.

I had a look at the code and would like to discuss one or two things.

I created a pull request: https://github.com/aibasel/downward/pull/158

Experiments look good: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1092/data/issue1092-v1-eval/issue1092-v1-compare.html

I'm now looking for a reviewer.

I recently noticed that the "score-based selector", used as a merge strategy, repeatedly computes the scores for identical merge candidates in subsequent iterations. With the standard M&S algorithm, merge candidates are mostly not changed between iterations. (Label reduction applies to all factors and this could influence the scores computed by the DFP scoring function.) In particular for expensive scoring functions such as MIASM which computes the products for all merge candidates, it would make sense to allow reusing previously computed values. Preliminary experiments show that this greatly decreases the M&S construction time for that particular merge strategy. I would therefore like to introduce a caching option for all scoring functions.