I have a two rule that are variants of each other – I could combine then into one parameterized rule. I am however curious what the cost of binding a variable v.s. checking a match is …
For example:
rule1(mmm, aaa, yyy) :-
rule2(mmm, zzz, yyy) :-
Could be combined into:
rule12(mmm, X, ,yyy) :-
X == aaa ; X == zzz,
Would there be significant overhead in the second case, relative to the first one – or are they essentially the same – its possible that the first one matches on indexing while the other unifies and tests – which is more work to be done …
Edit:
Interestingly, Single Side Unification, does move binding to the body per definition – does this create somewhat more overhead?
Assuming you meant to write this (note that I’ve changed your ==/2 to =/2):
rule1(mmm, aaa, yyy).
rule1(mmm, zzz, yyy).
rule12(mmm, X, yyy) :-
X = aaa ; X = zzz.
you can see that the vm code is essentially the same for the first part of the “or” but is different for the second part (whether faster or slower, I don’t know). There are two major differences:
with the separate rules, there can be indexing on any of the arguments; but with the combined rule, there’s no indexing on the 2nd argument.
the “;” rule always leaves a choicepoint after the X=aaa part whereas for the separate rules, indexing could avoid the choicepoint.
But unless profiling shows that there’s a problem, I wouldn’t worry much about such micro-optimizations.
I am curious for later, when i start optimizing in earnest.
The code area that include these lines, are the most performance sensitive I have … if squeezing out cycles there doesn’t cut (no pun intended), I will have to go to C for those areas …
re: = vs. ==
I intentionally choose == over = thinking that it will test for equality of the bound atoms, while not bind the variable when not bound by the caller.
That is indeed the difference between (=)/2 and (==)/2. But if you have an atom in the head, that’s the equivalent of (=)/2; and the argument can also participate in indexing. I don’t think there’s a significant performance difference between (=)/2 and (==)/2 if the argument is bound; but the semantics are different and (==)/2 is “non-logical” – I mostly use (==)/2 in tests.
I now understand and it makes sense – i guess its non logical because == is aware of the variable – just like, say var/1 is.
So, i guess, to make this logical i have to factor out those arguments that can be left unbound and create predicates where they always do have values – when in use.
Perhaps you’re thinking procedurally when you should be thinking “logically”. There are predicates that don’t work when everything is a variable – e.g., there’s an infinite number of solutions to member(a,List) on backtracking, but there’s a finite number of solutions to length(List,5), member(a,List). And here’s one way of finding all permutations of [a,b,c]:
Having said that, because of Prolog’s execution strategy, you sometimes need to think procedurally,. to minimize backtracking or because certain predicates require their arguments to have a value. For example X is Y+Z, Y=2, Z=3 won’t work … but there’s a “logical” version if is/2 that does work: X #= Y + Z, Y=2, Z=3. So – where possible – it’s better to think of a program as solving a set of equations (using a rather simplistic execution strategy) rather than as a series of execution steps.
Thinking about your comment made me realize that what i am actually doing is playing with a decision tree.
My first approach was to create a completely flattened tree, so there is no backtracking, only one lookup.
I guess, now i am carefully, putting a structure back, which does introduce backtracking such as provided by the ‘;’ operator, and later a hierarchy of calls.
The more i “recreate” the tree, the more such unbound variables will disappear and become predicate cases in the tree structure.
But, all this has a performance cost, which will add up … so, i might stay with the flattened structure after all.
Edit:
And there is still some structuring possible, by having more general flat rules placed before the more specific ones.
Maybe, maybe. Show some results. This means reproducible code that anyone can run on their machine, example runs, your timings, properly done. Otherwise all we are doing is shooting the wind.
That is not really true, especially not when using (A == a -> ... ; ...). As ==/2 doesn’t change anything, the if-then-else is compiled into a much simpler form that does not create a normal choice point, but merely execute the test and continues in one of the two branches.
Indeed – right now i am eyeballing the speed of my unit test cases – and they provide a subjective indicator to me – i can see when things slow down and when they process swiftly
Since the whole idea here is to combine common outcomes into one rule.
But, this would then again introduce the choice point – but, i guess the cost to replicate in the code the outcome as above – would be the “cost” to remove the choice point.
My $0.01: keep it simple. The simple two clauses look by far the simplest. If the body is complex (not very likely with ground arguments), write a predicate that implements the body. That also gives you the opportunity to give a nice name to the (body) code. It is pretty unlikely any of these variations is significantly faster and even if this were the case it may be different the next release (or even when Prolog is compiled with a different C compiler).
If this is a bottle neck and there are only a handful clauses you may time some alternatives. If there are many clauses you may decide to use term_expansion/2 to rewrite the predicate. I’ve seen code transforming similar code like this:
rule1(mmm, A, yyy) :-
rule_mmm_yyy(A).
rule_mmm_yyy(aaa) :-
rule_mmm_yyy(bbb) :-
In one implementation i have several hundred such predicates – which were developed in a piece by piece manner, while characterizing a rather complex state space.
The benefit of the representation for exploration was in was simple and offered a table-like systematic exploration – which also often required adding columns.
All this has become very difficult to understand.
I am now systematically redoing this with an eye on abstraction – but, want to keep to a non-choice point generating representation.
I think this is a great analysis and very helpful.
I my case, the call is always ground i.e. mode(+,+,+) … (edited)
There is no case during the runtime of the system where a query will be submitted – a call with an unbound variable with the intent to bind it for further processing – i guess this makes it a functional relation – and i also don’t allow backtracking over it – so the call is wrapped in a once/1/
In cases, a variable is provided, then its meaning is Not Applicable, rather than retrieve it’s value – hence my use of == instead of =.
