EinsteinUTest taking too long

[linas]

Normally, EinsteinUTest runs in 10 seconds, but it is currently running in 300 seconds. This is due to some pattern matcher bug .. this has happened before, and bisection should reveal what the problem is.

[jswiergo]

This is caused by commit fb41305 (issue #76). If you revert this change the EinsteinUTest ends in less then 10 seconds but PatternCrashUTest crashes. I am still analyzing how to fix both problems.

Short summary after analyzing the code:
I have found out that after fixing #76 as a side effect you fixed calculation of undead variables in the procedure that select next untried clause. There was a bug before. I printed this undead variables out after and before the change. So this means that #76 change enabled "optimization" that choose a clause with minimum number of ungrounded variables.

Moreover seems like disabling this "optimization" helps much in that case of "elimination-rule" query in EinsteinUTest. (or there is other side effect of this change that helps and I am not aware of, is there?). When I trace the log of clauses and joiners chosen during search I see big difference. For example it looks like it is more lucky to select good joiner e.g. attr=German instead of predicate=Nationality, so it cuts longer branches in the search tree earlier.

Does above makes sense? What are your thought about following optimization strategies? Are they worth to experiment or it is not so important for real situations?

1. I have read the comment about choosing clause with smallest incoming set instead of counting variables. Indeed seems that counting does not help much.
2. In the case of "elimination-rule" that uses "c++:exclusive" predicate it is extremely poor strategy to choose this clause as a last one. What about the strategy that permits "black" clauses when their all variables are already grounded? Maybe that kind of predicates should have some additional "hint" attribute to help pattern matcher distinguish if the predicate is cheap to evaluate or not. Evaluating "c++:exclusive" just after grounding all attributes (attr_*) could prune very large part of the search tree.

[linas]

Csesc,

On Sat, Jul 4, 2015 at 3:12 AM, Jacek Świergocki [email protected]
wrote:

Does above makes sense?

Yes!

What are your thought about following optimization strategies? Are they
worth to experiment or it is not so important for real situations?

We don't have many "real situations". Both seem like good fixes,
especially the second one.

1. I have read the comment about choosing clause with smallest incoming
   set instead of counting variables. Indeed seems that counting does not help
   much.
2. In the case of "elimination-rule" that uses "c++:exclusive" predicate
   it is extremely poor strategy to choose this clause as a last one. What
   about the strategy that permits "black" clauses when their all variables
   are already grounded? Maybe that kind of predicates should have some
   additional "hint" attribute to help pattern matcher distinguish if the
   predicate is cheap to evaluate or not. Evaluating "c++:exclusive" just
   after grounding all attributes (attr_*) could prune very large part of the
   search tree.

This seems like a good idea... exclusion is very good at pruning. It
should run early/earlier. The best solution is probably to create a new
link type: UniqueLink or ExclusiveLink, so that it is true only if all the
elements are unique, else false. I like this for several reasons:

1. This turns a "black box" into a "clear box": the idea of uniqueness is
   well-defined in the algebraic sense, and so logical reasoning could be
   performed on it, if needed.

2. By turning it into a "clear box", it should automatically move this to
   an earlier stage of pattern matching, and thus the pruning should happen
   much earlier.

I hope this is enough to fix the problem; if not, then ...well, you now see
some of the algorithmic issues in the pattern matcher ... many of which are
hard.

[jswiergo]

The first optimisation decreased running time to previous level (~5 sek in my machine). I have sent PR #141.

[linas]

This appears to be fixed, and, if I understand the problem, its fixed in a way that the bug probably won't recur by accident. Closing.