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

Question

更新:11.6.2016

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

我更新了下面的“运行时”表以包含 SICStus Prolog 4.3.3。亮点包括:

(is)/2是 速度提高 10 倍 比以前。

val_of/2也大大加快了速度，几乎是 2 倍 !

梅高;-)

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

乐趣？ 大乐趣!
许多有趣的实验摆在面前:

左倾树与右倾树

list_sizL([], 0)。 % 左倾
list_sizL([_|Es], N+1) :- list_sizL(Es,N)。

list_sizR([], 0)。 % 右倾
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 是 V1+V2
;数字(E) -> V = E
)。

为了测量运行时间，我运行了 go(2000000)使用不同的 Prolog 处理器2:

去(L) :-
长度(Xs，L)，
成员(B_2，[list_sizL，list_sizR])，
调用(B_2，Xs，E)，
成员(P_2, [is,val_of]),
call_time (调用(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 毫秒 | 650 毫秒 | 60 毫秒 | 3.4 倍
list_sizL + val_of | 381 毫秒 | 100 毫秒 | 60 毫秒 | 6.3 倍
-----------+--------+---------+---------|
list_sizR + (is) | 88 毫秒 | 660 毫秒 | 70 毫秒 | 1.2 倍
list_sizR + val_of | 346 毫秒 | 100 毫秒 | 60 毫秒 | 5.7 倍
-----------+--------+---------+---------|

我对这些(可重复的)结果感到困惑......有人可以告诉我发生了什么吗？

脚注 1:为了简洁和可读性，变量名称略有调整。
脚注 2:使用合适的命令行参数运行 SWI-Prolog 7.3.20 swipl -G2G -L2G -O .

Answer 1

我可以确认一个令人惊讶的事实，即在 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) 的当前版本中。