Issue 350 Dominance pruning in canonical heuristic

Issue 350 Dominance pruning in canonical heuristic

[Florian, 2012-10-02 08:24:20]

Changes in Makefile are not checked in.

http://codereview.appspot.com/6590058/diff/1/src/search/Makefile
File src/search/Makefile (right):

http://codereview.appspot.com/6590058/diff/1/src/search/Makefile#newcode209
src/search/Makefile:209: CCOPT_DEBUG    = -O0
Not checked in, only done locally for debugging.

http://codereview.appspot.com/6590058/diff/1/src/search/Makefile#newcode230
src/search/Makefile:230: LINKOPT_DEBUG  += -Wl,--no-as-needed -lrt
Not checked in, only done locally for debugging.

[malte.helmert, 2012-10-04 00:56:49]

Hi Florian,

no substantial comments, really. I'd prefer to have the big method taken into
parts, as indicated in one of the comments. Everything else are very small
things.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
File src/search/pdbs/canonical_pdbs_heuristic.cc (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:18: #include
<boost/functional/hash.hpp>
This adds a dependency on boost which we currently don't have. Hence needs
discussion.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:115: // Patters are copied and
sorted for the superset test to avoid changing the
typo: patters

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:121: }
I *think* all our patterns are already guaranteed to be sorted. However, this
doesn't seem to be verified in the constructor of PDBHeuristic currently, which
it should be.

I suggest adding such verification there, which could use a new function
assert_sorted (if done via assertions) or verify_sorted (if done via if/abort())
in ../utilities.h. This functionality would be useful in other parts of the
code, too, which currently assert sortedness manually.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:134: 
Does the code do the right thing if the same pattern appears twice? (Maybe this
is impossible; not sure.)

Does the code do the right thing if the same clique appears twice? (That should
definitely be impossible, but if it would cause problems and could be verified
with a simple assertions, it might be worth it.)

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:162: break;
Six nesting levels are too many, I think. There should be a function for an
individual dominance test. I guess this may be awkward because of the need to
pass superset_relation around, requiring writing its type in multiple places
etc. A good solution for that is to wrap the algorithm into a small class which
has the superset_relation as an attribute.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:185: if
(remaining_heuristics.find(pattern_databases[i]) == remaining_heuristics.end())
{
Membership in associative containers is most easily and equally efficiently
tested with count:

if (!remaining_heuristics.count(pattern_databases[i]))

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:188: }
Is there a method to recompute size from scratch? Should there be one? Feels
like something that should be encapsulated somewhere, e.g. in a method that sets
the PDBs.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:197: cout << "Dominance Pruning took
" << timer << endl;
"pruning" should be lower-case.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
File src/search/pdbs/canonical_pdbs_heuristic.h (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.h:45: another clique. */
Can we make the pruning condition a bit more mathematically precise? (It's not
clear here that "another" must always be the same one.)

Like: "Prune pattern set P = {P_1, ..., P_k} if there exists another pattern set
Q = {Q_1, ..., Q_l} where each P_i is a subset of some Q_j: this implies h^P <=
h^Q for all states."

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/pattern_generati...
File src/search/pdbs/pattern_generation_haslum.cc (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/pattern_generati...
src/search/pdbs/pattern_generation_haslum.cc:228:
current_heuristic->dominance_pruning();
We kind of have a proliferation of TODOs that we will realistically never get
to, so unless we really want to do this, I'd suggest marking this as "Possible
improvement:" or similar. IIRC, we already compute the cliques incrementally to
some extent (right?), so it would fit to do the dominance pruning in the same
place -- if there is actually an easy and correct way to do it incrementally
(but I don't see why not):

[Florian, 2012-10-05 15:11:27]

Patch set 2 now addresses most of you issues

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
File src/search/pdbs/canonical_pdbs_heuristic.cc (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:115: // Patters are copied and
sorted for the superset test to avoid changing the
On 2012/10/04 00:56:49, malte.helmert wrote:
> typo: patters

Done.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:121: }
On 2012/10/04 00:56:49, malte.helmert wrote:
> I *think* all our patterns are already guaranteed to be sorted. However, this
> doesn't seem to be verified in the constructor of PDBHeuristic currently,
which
> it should be.
> 
> I suggest adding such verification there, which could use a new function
> assert_sorted (if done via assertions) or verify_sorted (if done via
if/abort())
> in ../utilities.h. This functionality would be useful in other parts of the
> code, too, which currently assert sortedness manually.

Done. I found one more occurrence in max_cliques.cc. Are there any more that you
know of?

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:134: 
I'm not sure if either of those cases can occur but it is probably better to
keep the code robust enough to handle them anyway.

On 2012/10/04 00:56:49, malte.helmert wrote:
> Does the code do the right thing if the same pattern appears twice? (Maybe
this
> is impossible; not sure.)

There might be a problem if two PDBs with the same pattern occur in singleton
cliques. I added code to check for this case in the loop that calculates the
superset relation. On adding P <= Q this test if Q <= P was already added. If it
was, it just replaces Q with P in all cliques. Q will then be removed by
pruning.

> 
> Does the code do the right thing if the same clique appears twice? (That
should
> definitely be impossible, but if it would cause problems and could be verified
> with a simple assertions, it might be worth it.)

I added a vector that keeps track of what cliques we already excluded and skips
those in the search for a dominating clique. That should work in case there are
duplicate cliques.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:162: break;
On 2012/10/04 00:56:49, malte.helmert wrote:
> Six nesting levels are too many, I think. There should be a function for an
> individual dominance test. I guess this may be awkward because of the need to
> pass superset_relation around, requiring writing its type in multiple places
> etc. A good solution for that is to wrap the algorithm into a small class
which
> has the superset_relation as an attribute.

Done. I uploaded a second change set with this.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:185: if
(remaining_heuristics.find(pattern_databases[i]) == remaining_heuristics.end())
{
On 2012/10/04 00:56:49, malte.helmert wrote:
> Membership in associative containers is most easily and equally efficiently
> tested with count:
> 
> if (!remaining_heuristics.count(pattern_databases[i]))

Done.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:188: }
On 2012/10/04 00:56:49, malte.helmert wrote:
> Is there a method to recompute size from scratch? Should there be one? Feels
> like something that should be encapsulated somewhere, e.g. in a method that
sets
> the PDBs.

Done. There is no such method right now. Patterns were never removed before, so
the size was just increased for every new pattern. I changed it to be computed
from scratch here (without encapsulating it) which makes a lot more sense than
searching through remaining_heuristics every time. I don't think we need to
encapsulate it at the moment, because this is the only place it is needed.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:197: cout << "Dominance Pruning took
" << timer << endl;
On 2012/10/04 00:56:49, malte.helmert wrote:
> "pruning" should be lower-case.

Done.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
File src/search/pdbs/canonical_pdbs_heuristic.h (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.h:45: another clique. */
On 2012/10/04 00:56:49, malte.helmert wrote:
> Can we make the pruning condition a bit more mathematically precise? (It's not
> clear here that "another" must always be the same one.)
> 
> Like: "Prune pattern set P = {P_1, ..., P_k} if there exists another pattern
set
> Q = {Q_1, ..., Q_l} where each P_i is a subset of some Q_j: this implies h^P
<=
> h^Q for all states."

Done.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/pattern_generati...
File src/search/pdbs/pattern_generation_haslum.cc (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/pattern_generati...
src/search/pdbs/pattern_generation_haslum.cc:228:
current_heuristic->dominance_pruning();
On 2012/10/04 00:56:49, malte.helmert wrote:
> We kind of have a proliferation of TODOs that we will realistically never get
> to, so unless we really want to do this, I'd suggest marking this as "Possible
> improvement:" or similar. IIRC, we already compute the cliques incrementally
to
> some extent (right?), so it would fit to do the dominance pruning in the same
> place -- if there is actually an easy and correct way to do it incrementally
> (but I don't see why not):

Done.
I included dominance pruning during the incremental computation at first, but
this meant that the improvement of patterns changed and different patterns were
selected. For example, if we have patterns P_1 and P_2 already in the collection
with P_1 <= P_2 and try to add a new pattern Q that is additive with P_1 but not
with P_2. With dominance pruning P_1 would have been removed after the last
iteration and the clique {P_1, Q} would not have been tested.
I tried this in one instance and the pattern discovery was much faster (because
fewer patterns were generated) but the search also expanded more nodes.
With this comment I was thinking more about the pattern candidates that are
discarded during search because they would take up too much memory. Maybe we
could collect those discarded patterns and try them again after dominance
pruning cleared up some memory.
I changed it to "Possible improvement" for now.

http://codereview.appspot.com/6590058/diff/7001/src/search/landmarks/landmark...
File src/search/landmarks/landmark_types.h (left):

http://codereview.appspot.com/6590058/diff/7001/src/search/landmarks/landmark...
src/search/landmarks/landmark_types.h:10: class hash_pointer {
I moved this to ../utilities.h

[malte.helmert, 2012-10-05 15:25:00]

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
File src/search/pdbs/canonical_pdbs_heuristic.cc (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:121: }
On 2012/10/05 15:11:27, Florian wrote:
> On 2012/10/04 00:56:49, malte.helmert wrote:
> > I *think* all our patterns are already guaranteed to be sorted. However,
this
> > doesn't seem to be verified in the constructor of PDBHeuristic currently,
> which
> > it should be.
> > 
> > I suggest adding such verification there, which could use a new function
> > assert_sorted (if done via assertions) or verify_sorted (if done via
> if/abort())
> > in ../utilities.h. This functionality would be useful in other parts of the
> > code, too, which currently assert sortedness manually.
> 
> Done. I found one more occurrence in max_cliques.cc. Are there any more that
you
> know of?

The only one I know off-hand is in partial order reduction code that is not yet
pulled into the master repository.

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/pattern_generati...
File src/search/pdbs/pattern_generation_haslum.cc (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/pattern_generati...
src/search/pdbs/pattern_generation_haslum.cc:228:
current_heuristic->dominance_pruning();
Right, we have to be careful: we should not throw away a pattern that is
currently unneeded, because it might become needed later.

I didn't try to think of an example, but probably for the same reason we should
also keep around dominated *cliques*, right?

Maybe it would be a good idea to add a comment line where the dominance pruning
is called observing that dominance pruning should not be done incremental
because patterns and/or cliques that are currently dominated can become
non-dominated after more patterns are added? Then we won't feel the temptation
to "optimize" this later.

> With this comment I was thinking more about the pattern
> candidates that are discarded during search because they
> would take up too much memory. Maybe we could collect
> those discarded patterns and try them again after
> dominance pruning cleared up some memory.

I think it's not worth the code complication. We rarely hit the memory limit,
and when we do it's generally caused by the *large* PDBs, i.e., those with the
highest number of variables. By definition, dominated PDBs are never maximal
among PDBs w.r.t. subset exclusion, so reclaiming them can only give us a
fraction of the memory that its dominators use.

In other words, I wouldn't expect significant space savings from dominance
pruning, only savings in time.

[Florian, 2012-10-08 09:02:36]

The way I see it, this feature is complete enough to run some tests now, or did
one of you want to comment on the second patch set before I start the tests?

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
File src/search/pdbs/canonical_pdbs_heuristic.cc (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/canonical_pdbs_h...
src/search/pdbs/canonical_pdbs_heuristic.cc:18: #include
<boost/functional/hash.hpp>
On 2012/10/04 00:56:49, malte.helmert wrote:
> This adds a dependency on boost which we currently don't have. Hence needs
> discussion.
Done. The code for hashing pointers and pairs was already implemented for the
landmarks heuristic. I pulled it out and combined it in the general utilities.cc
(see second patch set).

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/pattern_generati...
File src/search/pdbs/pattern_generation_haslum.cc (right):

http://codereview.appspot.com/6590058/diff/1/src/search/pdbs/pattern_generati...
src/search/pdbs/pattern_generation_haslum.cc:228:
current_heuristic->dominance_pruning();
On 2012/10/05 15:25:00, malte.helmert wrote:
> Right, we have to be careful: we should not throw away a pattern that is
> currently unneeded, because it might become needed later.
> 
> I didn't try to think of an example, but probably for the same reason we
should
> also keep around dominated *cliques*, right?
> 
> Maybe it would be a good idea to add a comment line where the dominance
pruning
> is called observing that dominance pruning should not be done incremental
> because patterns and/or cliques that are currently dominated can become
> non-dominated after more patterns are added? Then we won't feel the temptation
> to "optimize" this later.
> 
> > With this comment I was thinking more about the pattern
> > candidates that are discarded during search because they
> > would take up too much memory. Maybe we could collect
> > those discarded patterns and try them again after
> > dominance pruning cleared up some memory.
> 
> I think it's not worth the code complication. We rarely hit the memory limit,
> and when we do it's generally caused by the *large* PDBs, i.e., those with the
> highest number of variables. By definition, dominated PDBs are never maximal
> among PDBs w.r.t. subset exclusion, so reclaiming them can only give us a
> fraction of the memory that its dominators use.
> 
> In other words, I wouldn't expect significant space savings from dominance
> pruning, only savings in time.

Done. I removed the TODO completely and replaced it with warning explaining
this.