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

Lynn

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

Fork

.. and what about adopting acyclic_term/1 and ground/1 to support TRO? At least in SWI, this produces a speedup of 2-3. – Belle

Perfect! I updated the benchmark table in my question accordingly... Kudos, again! – Lynn

Answer 2

You are comparing two very different implementations of (is)/2. SWI detects instantiation errors and cyclic expressions prior to actual evaluation. SICStus doesn't. Try this out with:

?- E=(1/0)+_, X is E.
?- E=(1/0)+E, X is E.

SWI produces an instantiation error and a type error (because of the infinite tree), whereas SICStus always evaluates 1/0 and produces an evaluation error in both cases. And (at least for this very example), both are conforming.

The difference in speed between evaluating the two tree structures is due to the tail recursion optimization in ground/1 and acyclic_term/1 in SWI. The current algorithm uses a stack and visits arguments left-to-right. Thus, the tree nested to the right requires constant auxiliary space and is thus much faster.

SICStus uses Deutsch-Schorr-Waite for acyclic_term/1 and ground/1, and thus has no explicit stack and thus no TRO. At least, both are about the same speed for left and right.

Belle

Interesting! Still I can't wrap my head around it. The main advantage of Deutsch-Schorr-Waite is low(er) memory use for the tree traversal, right? So then, why is SICStus (is)/2 (essentially) running out of memory with L is 10^7, go(L)? That does not make sense to me. – Lynn

@repeat: SICStus does not use DSW for expression evaluation. In this example, it neither uses ground/1 nor acyclic_term/1. So something else is responsible for the overflow. – Belle

Thanks for Deutsch-Schorr-Waite. awesome – Inception

Answer 3

Simply stated, I think that SWI-Prolog devotes more optimization to arithmetic, while SICStus has better code generation for general control flow.

Maybe some better performance could be obtained from SWI-Prolog by means of Partial Evaluation, that is very well introduced by Pereira-Shieber in chapter 6 of Prolog and Natural-Language Analysis.

You should also give a chance to YAP: it has been reported as the fastest WAM based Prolog. I remember Jan Wielemaker noting on SWI-Prolog list that most of YAP speed was obtained by massive rewriting - let's say, inlining. Something I think it's founded on (well implemented, of course) partial evaluation.

Inception

yap version 6.2.2 ("stable"), which comes with 64-bit Linux Mint 17, crashed instantly. Current versions may be better but I haven't tried anything newer (yet)... – Lynn

YAP has become very difficult to install. At least I am unable to install it, since it uses cmake. – Belle

The cmake package in Linux Mint 17 didn't work -- too old. Fetching and compiling cmake.org/files/v3.5/cmake-3.5.2.tar.gz OTOH did work with yap-devel. – Lynn

Bleeding edge technology – Belle