Part of issue987.

Depends on issue1036.

I saw the recent update and overlooked that this is already resolved, so I did another code review. ;-)

I don't have much to add. The memory usage of our hash set could probably be improved by making the underlying bucket data structure a deque-like data structure like we do for the state registry. It probably wouldn't be too much work to try this out. If someone is interested in this, let me know.

I investigated the memory increase. First off, I could not reproduce it on my laptop, but I could reproduce it on the grid. I observed that big chunks of memory are allocated when the IntHashSet for StateIDs is enlarged. Running the v1 version of lm_hm on mystery/prob30, there were two large jumps: from 291'268KB to 315'844KB, and then from 315'844KB to 381'384KB.

In the code, there are two places where enlarge() is called:
 (i) the number of entries exceeds the capacity
 (ii) When the bucket of the new key is too far away from the ideal bucket of the key and it could not be swapped (? Sorry, I don't understand the details here.)

I assume that case (i) should behave the same in both base and v1, but (ii) sounds like this could happen non-deterministically and we were just unlucky in v1.


In summary, the memory increase does not have anything to do with this issue. I don't really know enough about the IntHasher to judge whether or not we are ok with this behavior, but I assume that we can't really do any better.

Merged.

I have removed obedient-reasonable orderings and ran some experiments to verify nothing bad happens. First, here's a link to the pull requrest: https://github.com/aibasel/downward/pull/168. Salomé already left some comments, thank you.

Second, here are links to the experiment reports (timeout of 5 minutes):
https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1089/data/issue1089-v1-satisficing-eval/issue1089-v1-satisficing-issue1089-base-issue1089-v1-compare.html
https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1089/data/issue1089-v1-optimal-eval/issue1089-v1-optimal-issue1089-base-issue1089-v1-compare.html
Everything is pretty much as expected:
- Number of orderings decreases.
- Landmark graph generation time tends to go down (although it is surprisingly noisy sometimes, especially for lm_hm with m=2).
- The number of state evaluations, expansions, and generations stays exactly the same.
- Coverage does not vary by more than 1 per configuration.

The only slightly concerning observation is the increase in memory usage despite the reduced number of orderings. An extreme case of this is in the optimal configuration with lm_hm and mystery/prob30.pddl. There, memory increases by 30MB! However, I could not reproduce this locally... We assume it has nothing to do with this issue and decided to proceed and merge. Salomé will look into this a bit more, though.

I'm optimistic that issue1036 will soon be integrated in the main branch. If we don't deviate from the current plans, that issue will lead to obedient-reasonable orderings no longer be considered when progressing landmark information during search. This is mainly because the semantics of obedient-reasonable orderings are somewhat convoluted and not necessarily intuitive. Moreover, we have observed experimentally that they have little effect on the search behaviour of LAMA, which is the only algorithm that exploits them. Therefore, we suggest to disallow creating obedient-reasonable orderings in the first place (msg11105), i.e., remove the ordering type from the code.