Optimizing deterministic code - directive to creating compiled code without choice points

Help!
1

Hi,

I have labored this question before, but am now wondering about it from a different angle.

I notice that much code i write is deterministic. I, indeed wrap sequences of predicates into once/1.

I also noticed that test code i write is essentially determinstic – i.e. if one predicate in a test fails then the test should fail without further backtracking.

I imagine that use of once/1, essentially creates a choice point upon call of a predicate, and then removes (prunes) the choice point, when encountering a cut.

Assuming this is correct, wouldn’t it be much more performant if code sections could be declared as deterministic, so that a compiler generates code without creating choice points.

I am further assuming that choice point creation is quite an overhead beyond “simple” calls.

any thoughts are much appreciated,

Dan

1 Like
2

In the future it would be appreciated if you you include a link to your earlier related topics with title of topic as link name so that we don’t have to hunt it down. :smiley:

Series of “procedural” predicates – removing choice points

3

thanks for looking it up :slight_smile:

i guess the :- rdet(p1/0) directive, mentioned in that thread, doesn’t remove choice point code in the compiled version, just generate on the fly the right boilerplate code to make predicates behave deterministically.

Dan

4

If you write deterministic code correctly, choice points aren’t created. Or, more precisely, there are no choice points after exiting a correctly written deterministic predicate. (Choice points aren’t bad per se … they’re a vital part of the Prolog engine and aren’t expensive in themselves.)

rdet/1 doesn’t detect non-deterministic predicates — it simply catches failures and forces non-failure to be deterministic. This is not ideal … I’ve long wanted an easy way of wrapping predicates in something that throws an error on either failure or on “dangling” choice points (if I think I’ve written a deterministic predicate, but there’s a choice point, then I haven’t written it correctly and there’s probably a latent bug). Perhaps the newly proposed wrapper functionality can help with that.

1 Like
5

Hi Peter,

Can you show me an example how deterministic code looks like that does not create choice points.

thanks,

Dan

6

Hi Dan,

I suspect that we have been through this exact cycle before. Creating and removing a choice point is more work than not creating a choice point (yes, yes, I know, that’s a truism). If you want to not create choice points, write the code accordingly.

There is a lot of information scattered all over the place on how to do that. If you cannot find it yourself, you can show a particular piece of code that is not deterministic when it should be and you will probably get useful advice.

7

PS: “But why are you not just telling me how to write deterministic code? This is why I keep asking and I never get a straight answer!”

well, there are so many different approaches depending on the specific case. Off the top of my head, in no particular order, not exhaustive and probably wrong:

  • first argument indexing
  • but since some time also indexing on other arguments
  • but then again, tabling
  • the [] vs [H|T] thing for lists
  • using built-ins that have better determinism (like compare for comparing)
  • compile-time re-writing to generate the too-tedious-to-write-manually deterministic code
  • other assorted clever tricks.

and so on.

8

Hi Boris,

Thank you :slight_smile:

But, i still don’t understand.

When I have code such as so:

goal(X, Y) :-
  pred1(X),
  pred2(Y),   
  pred3(X, Y).

each, of pred1, pred2, pred3 will create a choice point – even if its not needed,

Presumably, one way to avoid it is to write:

goal(X, Y) :-
  pred1(X), !,
  pred2(Y),  !, 
  pred3(X, Y), !.

But, this would create and the prune a choice point – i guess.

I am currently doing this:

goal(X, Y) :-
  once(pred1(X)),
  once(pred2(Y)),   
  once(pred3(X, Y)).

Which, i don’t think is any better …

Ideally, I would like to see this – in an imaginary prolog implementation

goal(X, Y) :-
 no_choice(
  pred1(X),
  pred2(Y),   
  pred3(X, Y)
).

where no_choice is a kind of compiler directive that at compile time commits to each predx as if a cut has been written after it.

and, then there are the choice points you are referring to – which i will need to analyze to understand well.

thank you,

Dan

p.s. BTW, in the “Craft of Prolog” book, O’Keefe explains that the compiler tries to guess which goals are deterministic and which not, and creates choice points accordingly. And, that one can assist in that guessing by how the code is written …

Is this the case with swi-prolog as well …

9

Not to my knowledge. If pred1/1 and pred2/1 and pred3/2 are all deterministic, they will not create choice points (I am killing it with the truisms today. I will try a tautology and an oxymoron next, to mix it up a bit).

If you indeed have code like this, then you should ask yourself: “Why is pred1/1 not deterministic? Does it need to be? Can I re-write it to make it deterministic? Is there a better predicate for this slot that is deterministic?” and so on.

Another random piece of wisdom: there are different kinds of unnecessary non-determinism.

You have Type I non-determinism like here:

?- member(b, [a, b, c]).
true ;
false.

You have Type II non-determinism like here:

?- member(a, [a, a, a]).
true ;
true ;
true.

And then you have the Type III non-determinism that I have observed mostly in my own shitty code. For example, Boris (talking about himself in the third person all of a sudden) tries to define a predicate length_leq_3/1 that succeeds when the argument is a list of length up to or equal to 3:

length_leq_3(L) :-
    length(L, N),
    N =< 3.

He then proceeds to test this predicate with the proverbial “most general query”:

?- length_leq_3(X).

This is just one example of Type III non-determinism. Sometimes it does something even more sinister. For example:

?- list_max([1,2,3,1,2,3], Max).
Max = 3 ;
Max = 1;
Max = 2;
% and so on

(True story!)

10

Hi Boris,

That is very helpful.

I am still missing one piece in the puzzle.

Taking my example as template. can you show me one example of deterministic code.

How would pred1(X) look like?

And, how does the compiler know that it is deterministic without execution.

I recall that in Mercury one must explicitly declared predicates deterministic or otherwise – perhaps, to make such optimizations i have in mind.

thanks,

Dan

11

No, I cannot. I don’t know what it is supposed to do. I am not an academic (I tried to be and failed dramatically).

But we are now on the same merry-go-round all of a sudden. I need to get off and move on; good luck!

12

re: merry go round

I would call it recursive descent … since it will eventually bottom out (with an example, of course) :slight_smile:

Dan

13

Most of these are in the end about indexing. Note that currently indexes on other arguments are lazily created for avoiding long searches, not to avoid non-determinism. This means for example that if it created an index for the 3th argument and now has a call with args 3&4 instantiated it will first check whether the existing index on the 3th argument is `pretty good’. If so, it will use it, despite the possibility of a perfect index on the 4th argument.

Tabling is a bit of an outlier as it produces all answers and then gets these from a table.

The general story is simple:

  • If a predicate has more than one clause there are two ways to make it (semi-)det:
    • Make sure argument indexing does it for you. This basically means the first argument
      should be instantiated on call and each clause should have a different value. Reliably
      indexable are only atoms, compounds on name/arity and small integers (up to the Prolog
      flag max_tagged_integer. For objects such as large integers, strings or floats the
      system computes a hash key and can thus be subject to collisions.
    • Consider each clause as Head :- Guard, !, Action. Here, the combination of the
      head matching and the Guard do the clause selection and Action is (for writing
      det predicates) supposed to be deterministic on its own. If the (Head,Guard) pairs
      for all clauses are logically mutually exclusive the cuts are green, which implies
      they do not modify the semantics.
      And yes, this creates a choice point and destroys it. That isn’t expensive. It
      only gets expensive if choice points live long as such choice points avoid last-call
      optimization and leave a lot of data --at least theoretically-- accessible. This slows
      down GC and makes it far less effective.
2 Likes
14

Hi Jan,

Thank you.

“And yes, this creates a choice point and destroys it. That isn’t expensive.”

Could I ask you to quantify this …

What is really the (little bit of) expense here … how much data is allocated and then destroyed and how long does it typically take.

Very broadly speaking, I am sort of wondering if an embedded swi-prolog version makes sense – where one has more control over low level performance related implementation choices.

thank you,

Daniel

15

Hi Jan,

thank you for taking the time to comment on my hastily written thoughts. This was a useful summary. Does it exist in this form somewhere in the manual/documentation? This section of the manual:

http://www.swi-prolog.org/pldoc/man?section=jitindex

… contains most of what you wrote (right?)

Another somewhat related page:

http://www.swi-prolog.org/pldoc/man?section=modes

A small part of the “problem” as I have experienced it is that it is not immediately obvious to a novice what will be indexed and how. But the real problem for me personally was (is) that it wasn’t (isn’t) immediately obvious how is non-determinism useful and when is it a nuisance and when is it just wrong. The one place where those questions are discussed in a fashion is “The Craft of Prolog”. Then, at some point, on Stackoverflow, “correctly” deterministic predicates were “hot” but I don’t know if this is still the case. I suspect it culminated in this paper:

If I knew more and weren’t so lazy I’d write a 10-page treatise on the topic, with a decent review of the literature, pointers to the relevant documentation, and profiled examples. So, it’s not happening :wink:

EDIT: if this has been written already and I just don’t know about it, please share a link/citation!

16

No. Look into the source and/or do your timing/measurements. I’d have to do the same, but my guestimate it simply that it isn’t worth the trouble. A choice point is a small structure allocated on the local stack with a couple of pointers. Committing it is generally really cheap and just changes the global pointer for the most recent choice point.

17

“The Craft of Prolog” is probably the most relevant text on this. Surely some stuff is outdated as JIT indexing and constraints were not available (or at least not in Quintus, which was the main target of this book).

Non-determinism is typically useful if you want to solve problems stated in a purely logical form and you want Prolog to do the logical resolution. The whole purity movement of which is paper is an example is an attempt to solve a larger class of problems based on constraints/coroutining this way. There is some elegance in that as it is way simpler to reason about pure programs, they are generally concise and their semantics is clear. A lot of code doesn’t fall into this category though and thus involve simple deterministic transformations. Surely you can use these techniques (at least to some extend), but the techniques from e.g., The Craft of Prolog" are IMHO easier to grasp for these problems.

Tabling, and in particular the XSB and now also SWI-Prolog stuff including sound negation, is a strong competitor for solving problems from a pure logical specification. It is also a competitor for Answer Set Programing (ASP). The exact relation between all these formalisms is not entirely clear to me. They are all three (close to) declarative. They all have their own pitfalls and strengths and there is some overlap.

You also use non-determinism for all sorts of smaller and larger generate-and-test algorithms. Sometimes you use constraints as part of these, but often it is easy enough to make sure everything is instantiated before you do the test and you can simply use \== rather than dif/2. Only of the best ordering of subgoals is unclear, the code is generated from some knowledge base or constraints can do better than generate-and-test by using e.g., interval reasoning you should seriously consider constraints.

3 Likes
18

Hi Jan,

Looking at: (https://github.com/SWI-Prolog/swipl-devel/blob/6bde2c0bb4f1aec2385d5899544e74b1c86c26f0/src/pl-wam.c), i notice that there is quite a bit going on when calling a goal and various concerns are dealt with such as exception, debugging, etc.

The creation and freeing of a choice point is only one small part of this … so, its effect isn’t much significant.

Dan

19

Sure. Most of this is normally not executed though :slight_smile: There is LD->alerted as a general flag that puts the VM in an alerted state, meaning it must watch all these things. Normally this is false and all the checking for debugging, profiling, signals, etc. is skipped.

Still, a short lived choice point doesn’t have much impact. Notably those that prohibit last-call optimization in deep recursion do.

20

This is a side note off the main thread, and I can’t recall if I dropped this link to you before so forgive me if I have, but many years ago when I wanted/needed to learn more about how choice-points were made/worked instead of taking the route of examining how existing code worked, I started from the basement and learned how to write a Prolog interpreter. I didn’t say ground level because the basic interpreter was already written.

While there are many implementations on the web and many in GitHub alone, at the time I was living in functional languages and used this one (miniprolog) based on OCaml. While it can do inferencing and create choice points, as it notes, it lacks cut and even the ability to do list, but it helped me greatly in understanding how choice-points were created and worked.

If you choose to go down the path of building a Prolog interpreter from the basement up and want to use a different set of code than noted, validate that the code does inferencing correctly as many of these example code drops will fail basic inferencing test and thus will do more harm than good.