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

Once merged: remove manual implementations of operator!= throughout the code that do the same thing as the automatically available implementation in C++20. (Note that we also don't need to write operator!= ... = default. It is available without doing anything.)

> Just to be clear: we're comparing the code before and after this commit?
> 
> https://github.com/aibasel/downward/pull/260/commits/1a7b484613cfb6bca06c04805aaee617c4d0db9b

Yes, in msg12030 and msg12031 this was the evaluated change.

The hope was that the performance would improve and then the next step would have been to compare the improved performance to the main branch, but since the performance got worse, I never got to this step. I'm only mentioning this here to not lose track of the fact that investigating the performance before and after changing the equality operators was not the performance difference we were originally investigating.

Something I learned while looking into this: C++20 added default implementations of operator!= based on operator==. I think we should remove the manual implementations of operator!= that we have in a bunch of places (I counted 16 such functions).

Many of these are unrelated to this issue, so I wouldn't include it here, and I'd also wouldn't want to do it while we're actively working on this to avoid unnecessary merge conflicts. So I've added this as a potential follow-up TODO to the summary.

Just to be clear: we're comparing the code before and after this commit?

https://github.com/aibasel/downward/pull/260/commits/1a7b484613cfb6bca06c04805aaee617c4d0db9b

The profile on the binary compiled on the grid also had close to identical numbers for before and after switching the equality operator. Running the same task 1000 times showed that the performance variation is much higher than the size of the effect we are trying to measure. The runtime of the task ranges from 2 to 10 seconds and we are looking for a difference of about 5%. Running a full planner experiment seems to be a reliable way to detect a difference at least but it doesn't help with finding what causes the difference.

I like the suggestion, but I'd like to first get a handle on the performance.

Malte and I profiled a task and had a closer look at the code. One thing we noticed in both the diff and the profile was that the old version compared proxy iterators by comparing the index they were pointing at and only used an assertion to check that the collection was the same. The new implementation instead used "= default" for the equality operator which would be implemented to compare both the index and the pointer to the collection. In the profile we saw that this caused additional effort and indeed when we changed the implementation back to comparing only one pointer, the profiles of the two versions looked close to identical.

Strangely though, the change had the opposite effect in an experiment on the grid: the code comparing only one pointer actually was slower. I re-ran the experiment 5 times and measured the difference in time score (negative numbers mean that the code got slower by switching back to comparing a single pointer).

A: -4.51
B: -2.3
C: -4.11
D: -2.2
E: -1.22

The results are not exactly stable but all 5 repetitions agree that the change made it worse instead of going back to the performance in the main branch.

My next step would be to compile a version of the planner on the grid, and use that for profiling, as well as setting up an experiment that just repeats a single task for 1000 times, to hopefully get more consistent measurements.

The PR changes lots of code from something like

    state[atom.var].get_value()
== atom.value;

to 

    return state[atom.var] == atom.value;

To make this
even more readable, I suggest to add a method State::contains(const FactPair
&fact) and instead write

    return state.contains(atom);

Of course, the
method signature should later use the name "atom" instead of "fact". And we
could pass the atom by value instead of by reference, if you prefer.

Usually,
I'd use a separate issue for such a change, but the current PR makes it easy to
find the sites where the new method could be used.

Sure.

I also think this looks different than the changes we have seen in the past. I would prefer to find a solution for this but as I said, I have no idea how we can figure out what the problem is. Malte, do you think it would help to look at this together? Perhaps in a Fast Downward meeting?

Florian, do you agree?

Compared to these other issues, the order of magnitude here seems on a different scale. +5% overall planner runtime because of a change to something that you wouldn't normally expect to be a bottleneck is a bit tough to swallow. But if you both agree I won't object.

Given that we've seen "unexplainable" speed differences in the landmark code for many issue patches, I suggest we chalk this up as just another one of those and merge this pull request. What do you think?

The change in the landmark code was not caused by switching the iterator to a range. I undid the change an repeated the experiment. The next thing I had in mind was that the landmark code called the FactPair constructor. I thought that maybe the old code inlined this call and the new code didn't, so I switched that code back to the old method of getting a FactProxy and getting a FactPair from it. Now the change in the landmark code looks really similar to the change in all other classes where we didn't see a performance impact.

Despite all of this, all version above show the same ~5% performance decrease and the time score drop of ~3 compared to the main branch. This is only on lama first and not on the other configs. The change also is relatively small, so it will be hard to reproduce and analyze with a profiler. I don't know how to continue from here.

I ran experiments comparing the current state of the pull request (299ddd4d) to the main branch (89b3d973) on configurations affected by the diff.

Optimal configurations look good: besides the usual noise there are not a lot of changes. Time scores go up minimally for merge&shrink (+0.67) and cegar (+0.17), and they roughly stay the same for blind search with stubborn set pruning (+- 0) and h^seq (-0.06). There are roughly 10 tasks per config with a runtime of over 1 second were the runtime decreased by more than 5% but this is balanced by a larger number of tasks were the performance increased by more than 5%. I would attribute all of this to noise and see no problem with these configurations.

https://ai.dmi.unibas.ch/_experiments/ai/downward/issue997/data/issue997-v1-opt-eval/issue997-v1-opt-89b3d973cdd1559f239302a446d3aba702a6af49-299ddd4db326c02777f90cf558ff75e72f909a7b-compare.html

https://ai.dmi.unibas.ch/_visualizer/?c=eJxdkFtuAyEMRbcS8TkqkGejZCtRVDmD1SAxQDHzaKPZe_G0RFX_fK_t4ys_xICJbPDivBJbtRYvK5EwsjyU0kCGUj5EnxxP3HOOdNYarDKdVb23NyDV3vUbThGT7dBnKl1twuhHSEZboh5Pp6Nm1FPJYSNDzBIHcDqmUHazRVIZkpq-OAQ4S8vlNd_1OMqbs95IaIm4v6l2i--Q2NlWp4NlYlc14QfrPevgzD_QodpP0Gt1fkHHqhk0zz8fWrJNkHMq1W5fzM-_AiKnv1xEwwkaxjSMaMT1ugD4nTn1OM_f-_dz8A%3D%3D

For the satisficing configurations, the configuration running h^cea and h^cg looks similar to the configs above: more tasks run faster then the tasks that run slower and the changes look like the typical noise.

https://ai.dmi.unibas.ch/_experiments/ai/downward/issue997/data/issue997-v1-sat-eval/issue997-v1-sat-89b3d973cdd1559f239302a446d3aba702a6af49-299ddd4db326c02777f90cf558ff75e72f909a7b-compare.html#summary

https://ai.dmi.unibas.ch/_visualizer/?c=eJxVUO1uwjAMfBWU32tSQGiCV0EIeY0ZkdI0st2PDfXdFxcx4N_d-XyX-GYGJA5dMoeV2djafKwMYVa6K9CDQIE301NUx1Uk88E5CNa3wfYpfAHb5urOOGWk0GISLlPnuzGNQN4F5h73-0-nUf-sGtYVg1Q4QHSZurIrAdkKkJ1-9REQAy_NtfYmHKsILVwCseh4_VCb7wZBlY0qXfTvvu1Dvfvm-f6_JXkCESpoWxfx55VA1u7j8b3hGXM6LTF6EqEe5_kPl4tmWw%3D%3D

There is a small but significant negative effect for lama-first, though: the search time score drops by 3.31, coverage drops by 1, 1168 tasks run slower compared to 394 that run faster.

https://ai.dmi.unibas.ch/_visualizer/?c=eJxlUO1uwjAMfBWU32tSQAjBqyCEvMaMSGka2e7Hhvrui4uYQPt3dz7fJb6bAYlDl8xxZTa2Nh8rQ5iV7gr0IFDg3fQU1XETyXx0DoL1bbB9Cp_Atrm5C04ZKbSYhMvU-W5MI5B3gbnHw2HvNOqPVcO6YpAKB4guU1d2JSBbAbLTjz4CYuCludbehGMVoYVrIBYdr59q89UgqLJRpYv-3bd9qg_fPD_-tyRPIEIFbesifr8SyNp9Ov3vfS84n5c4PY1Qj_P8C_ZEafs%3D


There are not many changes in the landmark code that are not used in the other heuristics as well. One candidate would be switching an iterator to a range.

https://github.com/aibasel/downward/pull/260/files#diff-a0a42b16e39576ec3e60d2ff316805d74cd017efe025a701aa5a6868adc6acfcR37-R40

We discussed this in a Fast Downward meeting and decided the ProxyIterator should be opt-in. I re-added the ItemType nested type in the containers and used it as a way to opt in to using the ProxyIterator, i.e., it is only enabled for classes that have this nested type (as before).

Instead of template specialization for the state iterator, State now just doesn't opt in to the the Proxy iterator and instead has its own iterator class like FactsProxy (the class we use to iterate over all facts of a task).

The pull request is up to date and ready for a review.

It's been a while but I had another look at this. Since we now support c++-20 concepts, they could be used to make the code a bit nicer and solve the problem mentioned below in a different way:

Instead of proxy classes advertising the class that they iterate over with a typedef `ItemType`, there now is a concept `indexable` that ensures that a class supports `c.size()` and `c[i]`. This is all we need to implement the iterator and the begin/end methods. One potential downside is that our iterator returns everything by value, not by reference. This is fine for our proxy classes where the returned values that we iterate over are light-weight proxies themselves. It could become an issue if ProxyIterator is used for a non-proxy class. For example, imagine ProxyIterator being used for a vector containing expensive-to-copy objects. Then a for loop over this vector would copy all objects into the loop variable. This doesn't happen because vector has its own begin/end methods that are preferred over ours, but it could be a danger with custom container classes. We could adapt the concept to only allow classes where operator[] returns by value anyway. What do you think?

Another snag is the uncrustify configuration. Uncrustify doesn't support C++-20 features yet, so the code formatting of the concepts has several mistakes that we cannot write in a nicer way. The option mod_remove_extra_semicolon also removes a non-optional semicolon from the concept, breaking the build. In the PR, this option is disabled but the remaining options are left as they were.

Finally, the issue with State, mentioned before, is that State now does have a size method and an index operator with integers, so it does technically satisfy the concept `indexable`. With our ProxyIterator, this now automatically generates begin/end methods that return a proxy iterator. Unfortunately this uses ints so it would only work in for loops like `for (int value : state)` which is not what we want. We want a different iterator that works in loops like  `for (FactProxy fact : state)` but we cannot overload `begin(const State &)` to return two different iterators. This is solved now with a template specialization `ProxyIterator<State>` that uses variable proxies internally. Another option would have been to implement the iterator as a stand-alone class, not related to ProxyIterator and just disable ProxyIterator<State>. I'm not sure what is better here. We also have `VariablesProxy.get_facts()` which returns a `FactsProxy`, a class that is only there to allow iteration and doesn't match our new concept. All of this is a bit messy and I'd appreciate some feedback on it.

I also like the change. 

Regarding looping over the facts in a state: usually when I need to loop over facts (in a state, precondition or the goal), I would prefer to get a FactPair instead of a FactProxy. The latter always leads to unwieldy code like "myfunc(fact.get_variable().get_id(), fact.get_value())" instead of the simple "myfunc(fact.var, fact.value)".

I like the change

If we need it, adding something like

for (FactProxy fact : state.facts()) {
    ...
}

where facts() behaves like an iterator in Python doesn't sound too terrible to implement. (Famous last words.)

Currently, states return a FactProxy that is created in the subscript operator and returned. Most receivers immediately call get_value() on the proxy to get to the value. One case where this is not the case queries the state for a facto proxy just to create a VariableProxy from it. A better solution for this case would probably be to ask the state for a TaskProxy and create the VariableProxy from there.

The main complication is that ProxyIterator<State> enables code like
  for (FactProxy fact : state) {...}
This could be handled by another iterator but I found it complicated to avoid the begin/end functions of ProxyIterator even if more specific functions for State iterators are available.

As a preview, here is a diff showing the changes (although this is from a temporary branch in issue348 which might be deleted at some point):
https://github.com/FlorianPommerening/downward/compare/issue348-version2...issue348-debug-no-fact-proxy

To discuss the actual changes we should make a real pull request in the correct branch but it might be worth waiting for issue348 with this.