Part of meta issue966.

We decided to merge this. The effect on total runtime is still OK, and the slowdown in some cases is limited to a pruning method we don't particularly care about. If not done yet, please add a changelog entry. It can be very brief given that this is a "for developers" change.

I tried to reproduce the increased pruning time locally but couldn't. I compared base to v3 on freecell/p03.pddl with sssimple. In the grid experiment, pruning time increased from 44.46 to 50.28 seconds (+5.82 seconds).

I ran both four times with the following timings:
base: 43.81s, 43.99s, 43.58s, 39.82s
v3:   43.42s, 42.20s, 41.28s, 40.96s

The fact that they got faster and faster suggests I might have some kind of speed-step functionality kicking in, making comparison difficult. But I ran that in an interleaved version and also changed the order (base, then v3; both at the same time; base, then v3; v3, then base), so if we average, it should be reasonably reliable.

That I cannot reproduce this could be due to compiler and hardware difference. From my casual look at the data, I think we mostly see negative effects on large tasks and in domains with lots of operators. This suggest to me that it could be cache-related; in the old code, some critical data structure were a bit more cache-friendly (perhaps just a bit smaller, perhaps because of allocation patterns), and this only shows for large tasks where cache becomes an issue. This could explain why I don't see this on my machine; it would depend on the specific cache characteristics.

Just speculation at this point.

I looked at the changes and they look fine to me. 

The pruning time (and with that, search time) for simple stubborn sets increase quite significantly across all domains in the experiments. Do you know why this happens only for that particular type of stubborn sets? It cannot really be explained by the additional indirection due to the new class ActionCentricStubbornSets, can it? I find the differences surprisingly large.

I rebased the branch to the current main branch and made some necessary adaptations. I also ran another round of experiments with 30 minutes time limit and 
measuring pruning time.

https://ai.dmi.unibas.ch/_tmp_files/roeger/issue1059-v3-issue1059-base-issue1059-v3-compare.html

The simple stubborn sets are most negatively affected in the absolute numbers but this does not translate into a similarly negative change of the scores!?

I'm OK with merging this, but there are some wild jumps in runtime, for example in scanalyzer-08-strips. I'm looking at this:

https://ai.dmi.unibas.ch/_tmp_files/roeger/issue1059-v2-issue1059-base-issue1059-v2-compare.html#total_time-scanalyzer-08-strips

In future experiments, I would recommend measuring the time spent inside the stubborn set computations to have a clearer picture. With our most recent changes, I think enabling this output requires setting verbose output for the pruning method, and then of course we need to make sure this is parsed and reported in lab.

https://ai.dmi.unibas.ch/_tmp_files/roeger/issue1059-v2-issue1059-base-issue1059-v2-compare.html

I have no idea why my links are always broken.

New experiment results after incorporating almost all feedback from the reviews: 
https://ai.dmi.unibas.ch/_tmp_files/roeger/issue1059-v2-issue1059-base-
issue1059-v2-compare.html
We sporadically lose and win an instance. I had a look at some of them and they 
were all solved briefly before the 5 minute time limit.

One remaining point from the reviews was whether we should move the function 
find_unsatisfied_condition from stubborn_set.h to class StubbornSet and into the 
implementation file. Malte and I agreed that exploring this is not worth it (it 
can only slow things down because it is probably no longer possible to inline 
it).

Silvan, do you think this can be merged? What about the changes you merged in 
the main branch? If I am not mistaken, these are orthogonal and there should be 
no need for another round of experiments?

Since the link is broken in Gabi's message, here it is: https://ai.dmi.unibas.ch/_tmp_files/roeger/issue1059-v1-issue1059-v1-issue1059-base-compare.html

Those segfaults stem from the translator running out of memory/crashing on too large tasks. (= This is standard behavior on organic-synthesis.)

Since Silvan anyway already shared my preliminary state, I can as well share 
preliminary experimental results. This look ok enough to me, so I will turn to 
the remaining changes.


https://ai.dmi.unibas.ch/_tmp_files/roeger/issue1059-v1-issue1059-v1-issue1059-
base-compare.htm
(I had the revisions in the wrong order, so red is good and green is bad.)


There are some segmentation faults in organic-synthesis-opt18-strips, also in 
the base version and without pruning. Has anyone observed this before?

Gabi already implemented changes which can be found at: https://github.com/aibasel/downward/pull/117/

Jendrik and I both left a few comments.

The StubbornSets parent class contains a lot of functionality that is only relevant 
for the operator-centric variants but not for the atom-centric implementation (e.g. 
all handling of the operator queue).

We should try to separate these (with an intermediate parent class for operator-
centric stubborn sets) and evaluate the impact on runtime.