Merged and pushed. 

Reusing evaluation contexts is issue675.

Thanks! I had a look at how often the base config outperforms the new config in
terms of the number of expansions on a per-task basis. With the null hypothesis
that they are both equally likely to outperform each other in terms of
expansions, there is no very strong statistical evidence against.

The most extreme result is the one for seed 2, where the advantage of the old
config in terms of expansions would only occur randomly around 5.8% of the times
(comparing only on the ones solved by both). That might indicate that there is a
significant difference, but it is not highly significant.

There is no doubt that it's getting worse in terms of total time, but perhaps
this is something we can look into later on as we eventually streamline the data
structures used for this. For example, we could try to accomplish using the same
data structure for the set of preferred operators throughout the search rather
than creating lots of new ordered sets all the time.

As I said earlier, I think it could move into the evaluation context, and we
could reuse evaluation contexts rather than creating new ones all the time. If
there isn't an issue for that yet, we might want to open one.

I'm fine with merging this.

Sure, here you go:

~/projects/jendrik-downward/experiments/issue535/data/issue535-v7-randomized-eval/properties

Thanks! If only the last column wasn't there...

Can you let me know where I can find the properties file on maia? (The path in
your home directory suffices, assuming that you haven't disabled read access for
our group.)

As discussed I ran the last configuration again with three different random seeds:

http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v7-randomized-issue535-base-issue535-v7-compare.html

(The table still uses the old way of aggregating score values.)

Here is a scatter plot showing the number of expansions for the configuration in question:

http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-base-lazy-ff-pref-True-randomize-True-vs-issue535-v7-lazy-ff-pref-True-randomize-True-expansions.png

Here is the same plot, but zoomed in (omitting all points > 10x and < 0.1x):

http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-base-lazy-ff-pref-True-randomize-True-vs-issue535-v7-lazy-ff-pref-True-randomize-True-expansions-censored10x.png

score_expansions also reduces by a lot in this config. There are three reasons
why it can change:

(1) random noise
(2) lower coverage due to slow-down or similar things
(3) a change in behaviour that leads to more expansions

Regarding (2): this cannot explain the size of the effect, as coverage only
decreases by 5, but score_expansions decreases by 19.03.

Regarding (1): I counted in how many domains score_expansions increases (18) vs.
the number where it decreases (42). The probability of observing such a bad
result randomly are less than 0.15%.

So at the moment I cannot see another explanation than (3), although I also
don't see where or how the behaviour in this case should have changed. Anyone
got any further ideas for getting to the bottom of this?

Note also that most of the left half of the scatter plot -- everything where
runtimes are below 1 second -- doesn't actually influence score_total_time. The
score_total_time value is identical for all runtimes below 1 second. So the big
increase cannot be explained by what happens on small tasks.

> Although the total time score decreases, the corresponding total_time scatter
> plot shows a negative trend, i.e., less runtime for long-running tasks.

I don't think so -- I think you may be getting distracted by the (few) extreme
outliers. Also for long runtime, there seem to be many, many tasks where runtime
increases by a factor of 1.1 or so, which is quite massive for something like
shuffling the preferred operators that should be low overhead compared to
heuristic evaluation.

Although the total time score decreases, the corresponding total_time scatter 
plot shows a negative trend, i.e., less runtime for long-running tasks.

I have looked at the diff again, focusing on the relevant code path, but 
couldn't spot any difference in behavior.

I'd attribute the dispersed results to the randomization.

The effect in the last column, where total time score reduces by ~50, is rather
severe. Did we change the behaviour there, or can this just be increased
overhead due to the use of OrderedSet?

The effect on total_evaluations etc. for this configuration is also quite
severe, given that the overall behaviour should also be the same (although of
course it is randomized).

The other configurations look acceptable.

Here are the results:

http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v7-issue535-base-issue535-v7-compare.html
http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v7-scatter-plots.tar.gz

The tables don't look too good on first sight, but the plots show favorable trends, I think.

OK, no further comments on Bitbucket. I'm glad we'll finally be able to get rid
of this hack soon.

1) I don't think so.

2) I just started an experiment testing the various flags of lazy search.

I had another look. I have no further comments beyond what I wrote on the
tracker, but have two questions:

1) Since the last experiments, did we make further changes that warrant a new
round of experiments?

2) Did we test the various flags in lazy search that affect successor generation
(such as preferred first and randomization)?

I agree on EHC. I'd like to have another look at the code, but I'm not sure how
soon I'll have the opportunity. If you don't hear from me again by Tuesday, some
nagging might speed things up. ;-)

Given that EHC is not one of our main algorithms, the relative changes in runtime 
are small and the fact that we shouldn't expect to perform better than using 
GlobalOperator::marked, I'd say this is not a deal-breaker.

> I tested ehc() for all combinations of preferred_usage and use_preferred:
>
> http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v6-issue535-base-issue535-v6-compare.html

Looks like the effect on time is consistently negative for some domains.
  elevators-sat08-strips
  openstacks-sat08-adl
  openstacks-sat08-strips
  optical-telegraphs
  parcprinter-08-strips
  parcprinter-sat11-strips
  philosophers
  transport-sat14-strips
The effects are mostly small, though.

> Also, as I wrote in msg5659, lazy_search wasn't reviewed in detail yet.
I looked at it in my review (msg5664, msg5666).

The following link should show the diff between the last revision you reviewed and the 
branch tip:

https://bitbucket.org/jendrikseipp/downward/branches/compare/1e259bb..4c74355#diff

Sorry, for not answering your comments. I liked and made all your proposed changes.

Is there a good way to see what you changed in the parts of the code that we
commented on, other than by doing a new code review from scratch? With no
answers to the questions and no obvious way to find out how the code was
changed, it is hard to sign off on the changes. (Also, as I wrote in msg5659,
lazy_search wasn't reviewed in detail yet.)

I tested ehc() for all combinations of preferred_usage and use_preferred:

http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v6-issue535-base-issue535-v6-compare.html

No changes in the number of expanded, evaluated and generated states. Looks fine to me.

I'm also done handling the code comments. Can this be merged?

I'm done with this round of comments.

I'll try to have a look at the pull request today.

OK, I've run that one a few times on my desktop at home, and the differences
between the two versions were negligible. Runtime varied between 788 and 1065
seconds depending on the load of the machine, but there was no noticeable
difference between the base and v5 versions.

There are a few data points that I would like to find out a bit more about, such
as parking-sat11-strips/pfile10-039.pddl with lazy_greedy_ff, where runtime
increases from 346.97 seconds to 645.32 seconds (no change in number of
evaluated states). If that's just random noise (or rather, related to the load
on maia), there's no problem, but if the code changes actually add 300 seconds
to the runtime, we need to look into them.

Here are the results for an experiment comparing the default branch with the latest issue branch revision:

http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v5-issue535-base-issue535-v5-compare.html

http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v5-issue535-base-issue535-v5-total_time-lazy_greedy_ff.png
http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v5-issue535-base-issue535-v5-total_time-eager_greedy_ff.png
http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v5-issue535-base-issue535-v5-total_time-ehc_ff.png
http://ai.cs.unibas.ch/_tmp_files/seipp/issue535-v5-issue535-base-issue535-v5-total_time-lama-first.png

Overall the total_time score goes down a little bit, but I don't think this is a dealbreaker.

I made some comments. I skipped enforced hill-climbing and would appreciate if
someone else could check it, and I mostly skipped lazy search because there is a
more general comment to address there first. The other files look fine to me
apart from the comments I made (the collection of preferred operators might be
much slower than before because of the "one-by-one" implementation we have now,
but let's wait for the experiments before rushing to change that), but perhaps
it would be good for someone else to have another look.

I have updated the pull request to reflect or offline discussion. Can one of you 
have a look again, please?

I'm done with my comments.

> Related to our recent discussion of directories, I think this belongs in the
> "algorithms" subdirectory, not "utils". Right?
It would be great, if we had some kind of documentation, what goes where. ;-)

I made a few more comments, but did not look at everything. If Florian does a
round of reviewing, this could speed things up.

Related to our recent discussion of directories, I think this belongs in the
"algorithms" subdirectory, not "utils". Right?

Thanks again for the comments Malte. 

The code now uses OrderedSet for lazy search and EHC as well. Retrieving the 
individual ordered and unordered collections from the OrderedSet makes for a 
little cumbersome code, but it avoids copying the data.

While I was at it, I used OrderedDict in eager search as well.

Malte, could you have another look at the code? Or should I ask Florian?

Florian and I agreed that this issue should be resolved before we continue the discussion about 
whether to keep GlobalOperator (see issue509).

I have made a pull request at https://bitbucket.org/jendrikseipp/downward/pull-requests/58

Could you have a look at the code please, Florian?

I have already run some experiments for ["--heuristic", "h=ff()", "--search", "lazy_greedy(h, 
preferred=h)"]. It seems the runtime is dominated by the heuristic computation (which is probably 
true for most heuristics marking preferred operators), so I'd say we wait with running further 
experiments until we're all fine with the code.

The flag is currently used for marking preferred operators. It should be removed to allow for 
cleaner code.