TODOs:

1. Run experiments.
2. Split successor generator code into three files.
3. Perhaps get rid of code duplication in factory; use internal operator
representation.
4. Update derived classes of GeneratorBase in light of new factory algorithm. 
In
particular, try replacing the 2-way GeneratorFork with a k-way GeneratorChain.
There may be other classes that can go away or be simplified.
5. Add high-level documentation for factory algorithm.
6. See TODOs in the code regarding possible algorithmic improvements.
7. Reconsider where and how nullptr is permitted/used for a GeneratorBase.
8. Remove trailing underscores in parameters in
successor_generator_internals.cc.
9. Update code comments in successor_generator_internals.cc in light of the 
new
implementation.

After talking to Florian, I've merged this without further review. Of course,
everybody is still very welcome to complain about the code and request changes. :-)

Thanks, Jendrik! So the results look good, and the remaining question is whether
someone wants to review the code before merging.

Here are the results for v7:

http://ai.cs.unibas.ch/_tmp_files/seipp/compare-all-tags.html
http://ai.cs.unibas.ch/_tmp_files/seipp/issue732-v7-debug-issue732-base-issue732-v7-compare.html

Thanks, Jendrik!

The results so far look very nice. Successor generator creation is now roughly
20x faster, and memory usage has also gone down a bit. The whole-planner
experiment also looks good, and all intermediate steps seem to have gone in the
right direction.

So if there are no issues with v7 (which should give essentially identical
results to v6) and if you (plural) are happy with the code, we can merge.

The experiments for v6 were already finished (I ran the fetch and report steps manually):

http://ai.cs.unibas.ch/_tmp_files/seipp/issue732-compare-all-tags.html
http://ai.cs.unibas.ch/_tmp_files/seipp/issue732-v6-debug-issue732-base-issue732-v6-compare.html

Experiments for v7 are queued.

After some discussion with Florian, I made some small modifications to the
estimate_..._size methods (now called estimate_..._bytes) and tagged a new
version issue732-v7.

Jendrik, could you update the experiments accordingly (adding v7 to the first
one and replacing v6 with v7 in the second one) and restart them? Sorry for the
hassle!

Thanks, Jendrik!

The experiments are queued.

Sounds like a plan :-) I'll prepare the experiments.

I've dealt with the remaining TODOs and tagged two more revisions, issue732-v5
and issue732-v6.

I am now happy with the code, and I think we can move on to experiments and code
review. Can someone again help me out with the experiments?

There are three questions I'd like to consider in the experiments:

1. What is the effect of the new code on the performance (runtime and memory) of
successor generator construction?

2. Is the code correct, i.e., does it actually produce the successor generators
it is supposed to?

3. How does the new code affect the performance of the search in general, in
particular as it creates slightly different successor generators than previously?

For question 1, I think we should run an experiment with all seven tags (base,
v1, v2, v3, v4, v5, v6) since some of the changes between the tags involve data
structure decisions that can be good in some domains and bad in others. I
suggest running the experiment on the complete suite of benchmarks, but without
search ("--search astar(const(infinity))"), so that it completes reasonably
quickly. The experiment should include attributes for the two new lines of
output regarding the construction time and memory usage for the root successor
generator.

For questions 2 and 3, I suggest running a second experiment with the base and
v6 tags in debug and release mode (four configurations total) on all benchmarks
using a single reasonable planner configuration, such as lama-first. I think
this should be sufficient. This is under the assumption that the previous
experiment shows v6 to be the version we want to use. Depending on what is
easier, we can either submit both experiments immediately, or run the first one
first and only run the second one if/once we're happy with the first one.

Does this make sense?

I dealt with some more TODOs and tagged issue732-v3 and issue732-v4.

I've dealt with item 3., which was the bulk of the remaining work. The factory
code is now a bit longer, but I think it's much easier to understand and much
nicer. I also expect it to be faster, but more experiments are needed for this.

I've also updated the list of remaining TODOs, adding some new ones. It may look
like little progress because the list has become much longer, but most new
entries are quite small action items.

I've tagged a new version (issue732-v2).

Experimental results available here (thanks, Florian!):

http://ai.cs.unibas.ch/_tmp_files/helmert/issue732-v1.html

No changes in coverage. The search time scores drops marginally (from 780.99 to
780.69), which may be noise or due to the slightly less efficient successor
generator structure (I'm not using nodes that combine "immediate operators" with
"forking" any more). The new code suggests new "multi-fork" nodes which should
help with performance, but I think we'll see very little change there either way.

There are some errors in debug builds for tasks with no operators due to an
over-eager assertion. This is already fixed in the issue branch.

Regarding what the issue is about: successor generation time drops significantly
from a total of 378.17 seconds over all instances to a total of 31.31 seconds
over all instances.

So this seems to do its job. Next, I'll see if I can still make this a bit
faster and get rid of the current code duplication.

Done splitting the successor generator code into multiple files.

This will make reviewing harder, of course, but I think the new factory code is
so different from the old code in any case that it probably doesn't help to see
the old code next to it.

For the other parts (successor_generator and successor_generator_internals),
there were no significant changes before the split, so a diff comparing the
after-split revision to whatever final version we will have should suffice.

PS: To be on the safe side, I think it would also be useful to have an
additional experiment with the same two configurations in debug mode.

I've added output on time taken for successor generator creation to globals.cc
on the default branch (outside of an issue since it's such a simple change) so
that we have reference numbers. I've also merged this change into the issue732 code.

Warning: I slightly changed the wording of the successor generator peak memory
difference to make it explicit that this is about the root generator, so lab
patterns need to be adapted. (But I think this isn't one of our default patterns?)

BTW, I was thinking about adding options to the planner that facilitate
experiments that quit after creating the successor generator, so that we can do
simple experiments with the successor generator (or other "preprocessing" tasks)
quickly without spending time on a search we don't care about. But then I
realized we can already do this by using "astar(const(infinity))" as the search
engine. (Other algorithms can be used in place of A*, of course.)

I have tagged issue732-base and issue732-v1. Can you run experiments for
astar(const(infinity)) and astar(blind()) on all benchmarks (not just the
optimal planning set) for these, or help me run them myself? I would defer
experiments with other planner configurations until the issue is close to
converging.

Next, I'll split the successor generator into three files (using "internals"
instead of "details"), leaving it in task_utils. This shouldn't affect the
experiments, so no need to wait for this to be pushed. (Not sure when I'll get
to it.)

I'll probably hold off with the other changes until we have more experiments,
since they would benefit from an experimental comparison to v1 (except for the
documentation, but it probably makes sense to wait with adding high-level
documentation until the algorithm has stabilized).

> Our current code doesn't show the time to produce the successor generator.
> Should we change that?
We could add this to the part of code that measures the peak memory increase
(globals.cc). This would only measure the time for the root successor generator
but I think that is fine.

> 1. Run experiments.
I can do that. What configurations do you want? Only blind search or should I
start with a full experiment of blind, LM-cut, ipdb, cegar, and lama-first?

> 2. Split the successor generator code into three files.
The LP solver also does this and calls the files with implementation details
"lp_internals.{h,cc}". Both leaving it in task_utils and moving it to a new
namespace seems ok to me. I slightly prefer leaving it in task_utils.


To comment on the other points, I should have a look at the code first.

I've cleaned up the code somewhat, and it's now closer to something that can be
merged. What I would like to do before merging (not necessarily in this order):

1. Run experiments.

2. Split the successor generator code into three files: successor_generator (for
the actual successor generator class), successor_generator_details (for
GeneratorBase and its derived classes) and successor_generator_factory (for the
factory code).

Do you think this make sense? Does this mean we should add the successor
generator to its own directory (and namespace), outside of task_utils, or should
it still stay where it is?

3. Optionally get rid of the remaining code duplication in the factory. It's not
that easy, though. One way to do facilitate it is to follow the TODO in the code
about using a different internal operator representation within the factory,
which would probably help with cache locality, allow some further optimizations
and perhaps cleaner code, and allow us to use a sentinel in the main
construction loop to get rid of the duplication. It would lead to a bit more
code, though.

4. In light of the new algorithm, reconsider some details of the derived classes
of GeneratorBase. For example, the current fork class should perhaps be replaced
by a class with a list or vector of child classes (rather than just two), and
the "immediate" classes that combine forks with leaves are no longer needed.

5. The main ideas of the new factory algorithm should be documented in
high-level documentation.

Thoughts?

The code is on my bitbucket repository, and I have created a pull request:

https://bitbucket.org/malte/downward/pull-requests/7/issue732/diff

The code is not yet ready to review, but I think it's ready for some experiments.

I would be interested in running an experiment to check that this is correct and
compare the successor generator creation time to our current code. However, our
current code doesn't show the time to produce the successor generator. Should we
change that?

Copied from msg6445 for issue705:

I've played around a bit with the algorithm for creating the successor
generators, and the initial results look quite promising.

I tested on the last tetris-sat14 task, since the scatter plot suggested this
might be a challenging domain for our current algorithm. The experimental new
implementation creates the successor generator in 0.06 seconds, more than 100
times faster than our current code (8.52 seconds). Without more experiments, I'm
not convinced that the algorithm is implemented correctly, but at least every
operator seems to show up in the resulting successor generator exactly once,
which is a good property to have. :-)