Prolog - Big speed difference between styles?

Author

Big speed difference between styles?

roschler

2006-09-16, 3:58 am

I want to know what the performance difference is between the three
following styles of writing a predicate where I want to restrict the
domain of one of the arguments.

Suppose I have a predicate and I only want to accept three particular
values for the first argument. I could do the following:

% CASE 1 - use clause head unification
pred(value_one) :-
pred_aux(value_one).
pred(value_two) :-
pred_aux(value_one).
pred(value_three) :-
pred_aux(value_one).

pred_aux(X) :-
% do some more stuff with X
....

Or I could do:

% CASE 2 - use term comparison with disjunctions.
pred(X) :-
(X == value_one ; X == value_two; X == value_three),
% do some more stuff with X
...

Or I could do:

% CASE 3 - use the member function with a list of items.
pred(X) :-
member(X, [value_one, value_two, value_three]),
% do some more stuff with X

I'm guessing that CASE 2 and CASE 3 are slower than CASE 1 since
Prolog can't do a simple unification but has to examine rules or a list
instead. But how much slower? Sometimes it's much more convenient,
especially during prototyping, to just tweak a list of disjunctions or
a list used in a member/2 call, then to have to create extra predicate
clauses to control the domain of an argument.

Is the performance hit, if there is one, really worth worrying about?

Thanks.

Jan Wielemaker

2006-09-16, 7:01 pm

On 2006-09-16, roschler <robert.oschler@gmail.com> wrote:
> I want to know what the performance difference is between the three
> following styles of writing a predicate where I want to restrict the
> domain of one of the arguments.
>
> Suppose I have a predicate and I only want to accept three particular
> values for the first argument. I could do the following:
>
> % CASE 1 - use clause head unification
> pred(value_one) :-
> pred_aux(value_one).
> pred(value_two) :-
> pred_aux(value_one).
> pred(value_three) :-
> pred_aux(value_one).
>
> pred_aux(X) :-
> % do some more stuff with X
> ....
>
> Or I could do:
>
> % CASE 2 - use term comparison with disjunctions.
> pred(X) :-
> (X == value_one ; X == value_two; X == value_three),
> % do some more stuff with X
> ...
>
> Or I could do:
>
> % CASE 3 - use the member function with a list of items.
> pred(X) :-
> member(X, [value_one, value_two, value_three]),
> % do some more stuff with X
>
> I'm guessing that CASE 2 and CASE 3 are slower than CASE 1 since
> Prolog can't do a simple unification but has to examine rules or a list
> instead. But how much slower? Sometimes it's much more convenient,
> especially during prototyping, to just tweak a list of disjunctions or
> a list used in a member/2 call, then to have to create extra predicate
> clauses to control the domain of an argument.

You miss one option:

pred(X) :-
ok_for_aux(X),
pred_aux(value_one).

ok_for_aux(value_one).
ok_for_aux(value_two).
ok_for_aux(value_three).

This -in my opinion- is the best option. It is efficient (only very
slightly less than CASE 1), it avoids rewriting _and_ it gives you the
opportunity to give the test on X a name (ok_for_aux here).

> Is the performance hit, if there is one, really worth worrying about?

Depends what you are doing. In general I'd advice to write using the
style you consider most readable. If the program gets too slot, run the
profiler to find the performance bottleneck and consider optimizing
there. Read "The Craft of Prolog" with many invaluable tips to keep your
code both readable and fast. In many cases these things do not bite in
Prolog. In cases where they do you can consider source rewriting using
term_expansion/2. That shouldn't be your first worry, but it is good to
know that if readability asks for a different representation than
performance you can opt for automatic transformation.

Cheers --- Jan

bart demoen

2006-09-18, 7:01 pm

On Sat, 16 Sep 2006 03:46:06 -0700, roschler wrote:

> I want to know what the performance difference is between the three
> following styles of writing a predicate where I want to restrict the
> domain of one of the arguments.

When you want to know something, and be (reasonably) sure you know
that you know something, it is worth conducting the experiment yourself.
Here is a program you can execute on your favourite Prolog system, and see
for yourself ...
The query is ?- t(1000000).
I will post results in different Prolog systems later. But only after you
have posted your results, and commented on them: do ut des.

Cheers

Bart Demoen

pred1(value_one).
pred1(value_two).
pred1(value_three).

pred2(X) :- (X == value_one ; X == value_two; X == value_three), !.

pred3(X) :- mmember(X, [value_one, value_two, value_three]), !.

pred4(_).

mmember(X,[X|_]).
mmember(X,[_|R]) :- mmember(X,R).

t(N) :-
statistics(runtime,[T1|_]),
do1(N),
statistics(runtime,[T2|_]),
T is T2 - T1,
write(method1 = T), nl, fail.
t(N) :-
statistics(runtime,[T1|_]),
do2(N),
statistics(runtime,[T2|_]),
T is T2 - T1,
write(method2 = T), nl, fail.
t(N) :-
statistics(runtime,[T1|_]),
do3(N),
statistics(runtime,[T2|_]),
T is T2 - T1,
write(method3 = T), nl, fail.
t(N) :-
statistics(runtime,[T1|_]),
do4(N),
statistics(runtime,[T2|_]),
T is T2 - T1,
write(dummy=T), nl, fail.

do1(N) :-
(N > 0 ->
pred1(value_one),
pred1(value_two),
pred1(value_three),
M is N - 1,
do1(M)
;
true
).

do2(N) :-
(N > 0 ->
pred2(value_one),
pred2(value_two),
pred2(value_three),
M is N - 1,
do2(M)
;
true
).

do3(N) :-
(N > 0 ->
pred3(value_one),
pred3(value_two),
pred3(value_three),
M is N - 1,
do3(M)
;
true
).

do4(N) :-
(N > 0 ->
pred4(value_one),
pred4(value_two),
pred4(value_three),
M is N - 1,
do4(M)
;
true
).

Sponsored Links