Goal Evaluation with Timeouts

Help!
1

Hello,

My question has two parts. In the first part, I would like to inquire about best logic-programming practices related to coding a specific portion of my program. In the second part, I have more direct programming-related questions.

Part I: My program evaluates goals with different strategies, and has the following blueprint.

% TimeOut is set to some value

program(Goal):-
attempt_strategy_1(Goal);
attempt_strategy_2(Goal);
...
attempt_strategy_n(Goal);

attempt_strategy_k(Goal):-
time_out(strategy_k(Goal), TimeOut, Result),
Result \== time_out.

From problem-domain knowledge, I know that there is almost always a strategy that will solve the problem in less than TimeOut milliseconds ; it’s just not possible to know apriori which one is going to be.

For this reason, I envelop the evaluation of strategies in a time_out/3 predicate as a way of saying “If strategy i is not able to solve the problem in Timeout milliseconds, then move to strategy i+1, and keep doing this because eventually one strategy will solve the problem within TimeOut milliseconds”.

This saves me a great amount of evaluation time as I do not have to exhaustively search all the space of a given strategy if I know that it should have found a solution by now – if it was the right strategy to pursue.

My question: Is there a better way of dealing with this other than using timeouts?

Part II: I overindulged in using timeouts to the point where I started using timeouts within timeouts. I noticed that for the following case:
p1(G):- time_out(p2(G), TimeOut1, Result1).
p2(G):- time_out(G, TimeOut2, Result2).

If TimeOut2 > TimeOut1, say TimeOut1=10000 and TimeOut2=50000, the evaluation of p2(G) will continue past TimeOut1=10000 and up to TimeOut2=50000 if a solution has not been found by then.

My Question: Is this expected, or am I doing something very wrong and convoluted?

Before posting this cry for help, I searched the topics in this forum looking for similar issues; and found that there is a more SWI-like predicate for timeouts namely call_with_time_limit/2.

My Question: Should I be using this latter instead for my timeouts?

Many thanks,
Amine.

2

I find your current idea to be quite intuitive and practical.

Off the top of my head I can think of only 4 additional ways to make this better.

  1. Make use of tabling if you are not already. (Note I have not used this personally but would do so if presented this problem).
  2. Make use of symbolic execution to calculate Big O, or do it by hand, then compare the Big O for each method.
  3. Use computation graph simplification if possible. See “Deep Learning” by Ian Goodfellow, Yoshua Bengio and Aaron Courville (WorldCat) (Chapter 6 PDF) (site) in section: 6.5.1 Computaional Graphs. Theano has Graph optimization
  4. If you are not after exact results but close enough then change closed world (Prolog) to open world (Neural Network), e.g. train a neural network and then use that. Also read the book as there are many other concepts in the book that might apply, e.g. Structured Probabilistic Models

I would use call_with_inference_limit/3 as it should be immune to CPU load changes AFAIK.

EDIT

The ideas listed above basically look at the algorithm as a computation graph and looks for ways to find the best algorithm using Big O, optimize the exiting algorithm, or reuse previously computed parts.

Another ideas is to look at the data for additional constraints that can be added. For example when parsing data as DCGs and looking at the input data with print_term/2 on slower running parts I can sometimes see a pattern in the data that lead to an added clause that speeds up the parsing. Most of the time the parsing with DCGs should be deterministic and the code that is not running as fast as desired is not running deterministic. By adding the additional clause(s) it becomes deterministic and thus much faster.

In other words an algorithm that is not the best may be one more constraints away from being the best algorithm, but if you don’t check you won’t known.

While I have not tried this with Prolog, it seems using a fuzzer would help with this concept.

4

First of all your second part. I reproduced this using

:- use_module(library(dialect/sicstus/timeout)).

test :-
    p1((repeat,fail)).

p1(G) :-
    time_out(p2(G), 100, Result1),
    writeln(1:Result1).

p2(G) :-
    time_out(G, 1000, Result2),
    writeln(2:Result2).

After which we get

103 ?- time(test).
2:time_out
1:success
% 2,611,875 inferences, 0.100 CPU in 0.100 seconds (100% CPU, 26145854 Lips)
true.

This is fairly easy to understand. Both schedule an alarm that throws a time_out exception. This will trigger after 0.1 sec in the inner loop, causing this to fail with Result2=time_out. Now the outer alarm scheduler is finished and the inner one got a timeout and killed its alarm. p1/1 now runs to completion (there are no active alarms). As p2/1 succeeds, p1/1 reports success and removes the activated, but still present alarm.

For short, the current implementation doesn’t nest well. A solution is to use a different exception, for example by including the frame reference in the exception. Just tested that. Works fine, so I’ll push that shortly.

As @EricGT says, the fact that this monitors wall time rather than CPU time might be killing, i.e., you may kill the correct strategy because wall time limit kills it although it didn’t use much CPU.

Back to your first question:

SWI’s native support for this is first_solution/3, which exploits multiple threads, using the answer of the first one to complete.

2 Likes
5

Related, an example using competitive-or parallelism that uses different algorithms to find the root of a function:

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/threads/functions

In this case, instead of using a timeout, the first algorithm that succeeds results in the termination of the other ones (hence the word “competitive”). Depending on the function, some algorithms converge quickly, some converge slowly, and others diverge. If you’re sure that a problem is always solvable using one of the algorithms, even if you don’t know which one, this may be a better solution than relying in possibly arbitrary timeouts.

6

Wow, I did not know about tabling; I have very entangled parts in my code to memorise proved goals and unprovable goals to speed up the search for goal. I will definitely look into this as it looks very clean and does things transparently without cluttering the code. Cheers!

7

Thanks a lot, I will be looking into more efficient ways that are based on concurrency.

8

Be aware that Jan has been adding/updating the tabling code over the last few months so if something doesn’t work as expected, don’t assume you made a mistake. At present it would be best to post it here so Jan can look it over and let you know if you found a bug in the SWI-Prolog tabling code or something. :smiley:

9

Does first_solution/3 create separate knowledge-base spaces for the different strategies during the concurrent evaluation?

I have asserts and retracts inside the strategies, and they are applied to the same predicates e.g.
strategy_1(Goal):-
% assert(some_info_about(X))
% Strategy 1 Stuff
% retract(some_info_about(X))

strategy_2(Goal):-
% assert(some_info_about(X))
% Strategy 2 Stuff
% retract(some_info_about(X))

So if they share the same knowledge base, data gets corrupted.

P.S. How do you format the code in your answers? I can only use the “</>” button that says “pre-formatted code” which gives me an output that does not even begin to look half as nice as yours.

10

Check the documentation of the thread_local/1 directive.

11

Thanks, I finally got it working :slight_smile:

1 Like
12

Hello,

I post my question in this thread because it’s somewhat related to the question posted by aminemarref a few years ago and it’s the closest I found in the forum.

I’m simplifying the problem we have as much as I can.

We have a solver (called setlog) that can be called from Prolog as follows:

setlog([p1,p2],goal,60000,Res)

where [p1,p2] is a list of configuration options, goal is the goal to be solved, 60000 is a timeout and Res is the answer computed by setlog (either success, when goal is satisfiable; or failure when it isn’t).

Let’s say so far we have two configuration options (p1 and p2) that can be turned on and off independently of each other. Each option makes setlog to apply different sets of rewrite rules. So we have 4 different configurations under which setlog can operate.

setlog([],goal,60000,Res)
setlog([p1],goal,60000,Res)
setlog([p2],goal,60000,Res)
setlog([p1,p2],goal,60000,Res)

Under any configuration setlog is complete; the only difference from configuration to configuration is that one of them may solve a given goal faster than the others. The timeout is still necessary because setlog may take an unpractical time to solve some goals, under all configurations. Since it’s hard to predict which configuration is the best for a given goal we want to run all the four calls above in parallel. Then we use first_solution (since we’re looking for the fastest answer) as follows :

?- consult('setlog.pl').

?- first_solution(
     Res,
     [setlog([],goal,60000,Res),
      setlog([p1],goal,60000,Res),
      setlog([p2],goal,60000,Res),
      setlog([p1,p2],goal,60000,Res)],
     []
   ).

The problem we have is that we have found a particular goal for which, in spite that every single call to setlog always returns failure, the call to first_solution sometimes returns failure and sometimes returns success.

We don’t know where the problem is. We believe it might lay in how setlog is programmed causing threads to mix something up in the wrong way. In particular configuration options are manged with global variables; for instance:

nb_setval(p1,on)
................
nb_getval(p1,on)

Can this be the cause of the problem? Are there other Prolog features we should look at before calling setlog from first_solution? Can setlog non-determinism be the problem? Can it be the interaction with time_out/3? What Prolog features could make threads created by first_solution mix things up thus making the call to it to work wrong?

setlog doesn’t use concurrency at all; this would be the first attempt to use concurrency to speed it up. So far setlog is a 10 KLOC program using fairly simple SWI-Prolog features (https://www.clpset.unipr.it/setlog.Home.html).

Any tip would help.

Thanks in advance!

13

Success with some answer? If that is the case it seems some setlog/4 call produced that answer, no?

That should be ok as global variables are thread-specific, each solver runs in its own thread and, if I understand this right, the global variables are set by the setlog call at the start.

If you do get a successful run while single threaded you don’t, it does suggest some thread interaction. The rough story is

  • Each thread starts without global variables. This means that if you created some while loading the program, a thread running the program has no global variables. There is a hook (exception/3) that may be used to create global variables lazily with an initial value in threads.
  • Dynamic predicates are shared. It is safe to access them from multiple predicates. The logical update view applies: a call to a dynamic predicate enumerates over all clauses as they are at the call time. Modifications (assert/retract) by the same thread or or other thread are invisible. There is one exception: retract/1 cannot retract the same clause in two threads, i.e., the first one wins and the second thread skips this clause despite the fact it may have been visible when the retract/1 call started.
  • Thread-local predicates start without clauses in a new thread. Any left over clauses are destroyed on thread exit.
  • Prolog flags use copy semantics: they are copied to a new thread. The implementation uses copy-on-write for efficiency.

[we may have to move this to a new topic; we’ll see where it goes]

14

Thanks for the quick answer

Yes, with some answer. I simplified that part of the description. The real call to setlog looks like more like this one:

setlog([p1,p2],goal(X,Y,Z),60000,Res)

so the call to first_solution is as follows:

first_solution(
     [X,Y,Z,Res],
     [setlog([],goal(X,Y,Z),60000,Res),
      setlog([p1],goal(X,Y,Z),60000,Res),
      setlog([p2],goal(X,Y,Z),60000,Res),
      setlog([p1,p2],goal(X,Y,Z),60000,Res)],
     []
   ).

What I mean is that setlog non only computes a value for Res but also values for goal’s variables when goal is satisfiable.

We’re checking all the tips you mentioned in your answer. I’ll come back to you as soon as we have some new information.

15

You may try

?- trace(setlog/4).

To print the port traversals of the setlog calls. But I suspect some thread interaction. I’d first check for dynamic predicates. When designing the thread system I think that the default for dynamic predicates should have been thread-local.

Some ways to find things:

?- predicate_property(M:Head, dynamic).

?- explain(assert/1).   % and asserta/assertz/retract/retractall.
1 Like
16

Hello,

As you predicted the problem were a few dynamic predicates (in the form of Boolean variables) that we used to govern some aspects of the solving algorithm. So, after moving them to global variables (i.e. managed through nb_setval/nb_getval) the erratic behavior disappeared.

Thanks you very much for your help, Jan.