Performance of the built-in Prolog predicate (is)/2

Question

Update: 11.6.2016

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 way¹ of introducing beginners to deriving length/2:

[...] Also note that E needs 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 processors²:

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.}

Answer 1

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).