The baffling performance discrepancy which I had observed with SICStus Prolog 4.3.2 has completely disappeared with the recently released SICStus Prolog 4.3.3. Kudos!
I updated the "runtimes" table below to include SICStus Prolog 4.3.3. Highlights include:
(is)/2 is up to 10x faster than before.val_of/2 has sped up tremendously, too, almost by 2x!MEGO;-)
When answering the question "Size Procedure in Prolog Language" SO-user @ThanosTintinidis proposed a conspicuously simple way1 of introducing beginners to deriving length/2:
[...] Also note that
Eneeds to be instantiated only because is is going to evaluate the expression. You could write something like this:size([], 0). size([_|Xs], 1+E) :- size(Xs, E).and if you call it:
?- size([_,_], E). E = 1+(1+0).Fun, isn't it? You might want to evaluate the last
E, i.e. call?- size([1,2], E), N is E. [...]
Fun? Big fun! A number of interesting experiments lay ahead:
Left-leaning vs right-leaning trees
list_sizL([], 0). % left-leaning list_sizL([_|Es], N+1) :- list_sizL(Es,N). list_sizR([], 0). % right-leaning list_sizR([_|Es], 1+N) :- list_sizR(Es,N).
built-in (is)/2 vs val_of/2
val_of(V, E) :- ( E = E1+E2 -> val_of(V1, E1), val_of(V2, E2), V is V1+V2
; number(E) -> V = E
).
To measure runtimes I ran go(2000000) using different Prolog processors2:
go(L) :- length(Xs, L), member(B_2, [list_sizL,list_sizR]), call(B_2, Xs, E), member(P_2, [is,val_of]), call_time(call(P_2,N,E), T), ( L = N -> writeq(B_2+P_2=T), nl ; throw(up) ).
On an Intel Core i7-4700MQ I observed the following runtimes with SICStus and SWI:
| SWI | SICStus | SICStus |
| 7.3.20 | 4.3.2 | 4.3.3 |
-------------------+--------+---------+---------|
list_sizL + (is) | 208 ms | 650 ms | 60 ms | 3.4x
list_sizL + val_of | 381 ms | 100 ms | 60 ms | 6.3x
-------------------+--------+---------+---------|
list_sizR + (is) | 88 ms | 660 ms | 70 ms | 1.2x
list_sizR + val_of | 346 ms | 100 ms | 60 ms | 5.7x
-------------------+--------+---------+---------|
I'm baffled by these (reproducible) results... Can somebody tell me what's going on?
Footnote 1: For the sake of brevity and readability, variable names were slightly adapted.
Footnote 2: Running SWI-Prolog 7.3.20 with suitable command-line arguments swipl -G2G -L2G -O.
I can confirm the surprising fact that, in SICStus Prolog, val_of/2 is much faster than is/2 when the expression is a large compound term, i.e. when is/2 is interpreting an expression.
In the current SICStus implementation compiled is/2 needs to escape to Prolog code when the argument to an arithmetic operator is not a number. When interpreting deep expressions this escaping happens for all arguments, recursively, which is much slower than what val_of/2 does, i.e. plain Prolog to Prolog calls.
I did a proof-of-concept fix for the underlying issue, it made the is/2 case in the program above about the same speed as val_of/2. This change has been included in the current release of SICStus Prolog (4.3.3).