内置 Prolog 谓词 (is)/2 的性能

Question

更新：2016 年 6 月 11 日

我在 SICStus Prolog 4.3.2 中观察到的令人困惑的性能差异在最近发布的 SICStus Prolog 4.3.3 中完全消失了。 荣誉！

我更新了下面的 "runtimes" table 以包含 SICStus Prolog 4.3.3。亮点包括：

(is)/2 比以前快 10 倍。
val_of/2 也大大加快了速度，几乎快了 2 倍！

MEGO;-)

当 answering the question "Size Procedure in Prolog Language" SO-user @ThanosTintinidis 提出了一种非常简单的方法 ¹ 来向初学者介绍推导 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. [...]

好玩吗？很有趣！ 一些有趣的实验摆在面前：

左倾树 vs 右倾树

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

内置 (is)/2 对比 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
                ).

使用不同的 Prolog 处理器运行go(2000000)测量运行时间²:

go(L) :- 
   length(Xs, L),
   member(B_2, [list_sizL,list_sizR]),
   call(B_2, Xs, E),
   member(P_2, [is,val_of]), 
   (call(P_2,N,E), T),
   ( L = N -> writeq(B_2+P_2=T), nl ; throw(up) ).

在 Intel Core i7-4700MQ 上，我使用 SICStus 和 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
       -------------------+--------+---------+---------|

~~我对这些（可重现的）结果感到困惑...有人能告诉我发生了什么事吗？~~

^{脚注 1：为了简洁和可读性，对变量名称进行了一些改动。

脚注 2：运行带有 suitable 命令行参数的 SWI-Prolog 7.3.20 swipl -G2G -L2G -O。}

Answer 1

简单地说，我认为 SWI-Prolog 对算法进行了更多的优化，而 SICStus 对一般控制流的代码生成更好。

也许可以通过 Partial Evaluation, that is very well introduced by Pereira-Shieber in chapter 6 of Prolog and Natural-Language Analysis 从 SWI-Prolog 获得更好的性能。

您还应该给 YAP 一个机会：据报道，它是最快的基于 WAM 的 Prolog。我记得 Jan Wielemaker 在 SWI-Prolog 列表上指出，大部分 YAP 速度是通过大量重写获得的——比方说，内联。我认为它建立在（当然实施得很好）部分评估的基础上。

Answer 2

您正在比较 (is)/2 的两个截然不同的实现。 SWI 在实际评估之前检测实例化错误和循环表达式。 SICStus 没有。试试这个：

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

SWI 产生一个实例化错误和一个类型错误（因为无限树），而 SICStus 总是评估 1/0 并在这两种情况下产生评估错误。并且（至少对于这个例子），两者都是符合的。

两种树结构的评估速度差异是由于SWI中ground/1和acyclic_term/1中的尾递归优化。当前算法使用堆栈并从左到右访问参数。因此，嵌套在右边的树需要常量辅助 space，因此速度要快得多。

SICStus 对 acyclic_term/1 和 ground/1 使用 Deutsch-Schorr-Waite，因此没有显式堆栈，因此没有 TRO。至少，左右速度差不多。

Answer 3

我可以确认一个令人惊讶的事实，即在 SICStus Prolog 中，当表达式是一个大的复合项时，val_of/2 比 is/2 快得多，即当 is/2 正在解释一个表达式。

在当前的 SICStus 实现中，当算术运算符的参数不是数字时，is/2 需要转义到 Prolog 代码。当解释深层表达式时，这种转义会递归地发生在所有参数上，这比 val_of/2 所做的要慢得多，即普通的 Prolog 到 Prolog 调用。

我针对潜在问题进行了概念验证修复，它使上述程序中的 is/2 案例与 val_of/2 的速度大致相同。此更改已包含在当前版本的 SICStus Prolog (4.3.3) 中。

内置 Prolog 谓词 (is)/2 的性能

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

prolog

swi-prolog

sicstus-prolog

更新：2016 年 6 月 11 日