Issue732

Title speed up creation of the successor generator
Priority feature Status chatting
Superseder Nosy List florian, haz, jendrik, malte
Assigned To malte Keywords
Optional summary
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.
5. Add high-level documentation for factory algorithm.
6. See TODOs in the code regarding possible algorithmic improvements.

Created on 2017-07-14.15:36:05 by malte, last changed by jendrik.

Summary
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.
5. Add high-level documentation for factory algorithm.
6. See TODOs in the code regarding possible algorithmic improvements.
Messages
msg6456 (view) Author: malte Date: 2017-07-16.20:55:36
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.
msg6455 (view) Author: malte Date: 2017-07-15.17:44:35
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.
msg6454 (view) Author: malte Date: 2017-07-15.15:39:53
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.
msg6453 (view) Author: malte Date: 2017-07-15.15:25:45
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).
msg6451 (view) Author: florian Date: 2017-07-15.08:56:34
> 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.
msg6449 (view) Author: malte Date: 2017-07-14.17:07:41
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?
msg6448 (view) Author: malte Date: 2017-07-14.15:53:25
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?
msg6446 (view) Author: malte Date: 2017-07-14.15:36:05
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. :-)
History
Date User Action Args
2017-07-17 09:24:30jendriksetnosy: + jendrik
2017-07-16 20:55:37maltesetmessages: + msg6456
summary: 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. 5. Add high-level documentation for factory algorithm. 6. See TODOs in the code regarding possible algorithmic improvements. -> 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. 5. Add high-level documentation for factory algorithm. 6. See TODOs in the code regarding possible algorithmic improvements.
2017-07-15 17:45:30maltesetsummary: 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. 5. Add high-level documentation for factory algorithm. -> 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. 5. Add high-level documentation for factory algorithm. 6. See TODOs in the code regarding possible algorithmic improvements.
2017-07-15 17:44:35maltesetmessages: + msg6455
summary: 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. 5. Add high-level documentation for factory algorithm. -> 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. 5. Add high-level documentation for factory algorithm.
2017-07-15 15:39:53maltesetmessages: + msg6454
2017-07-15 15:25:45maltesetmessages: + msg6453
2017-07-15 08:56:34floriansetmessages: + msg6451
2017-07-14 17:09:17hazsetnosy: + haz
2017-07-14 17:07:41maltesetmessages: + msg6449
summary: 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. 5. Add high-level documentation for factory algorithm.
2017-07-14 15:53:25maltesetmessages: + msg6448
2017-07-14 15:36:05maltecreate