5

更新：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 倍！

美高;-)

在回答“ Prolog 语言中的大小程序”问题时， SO 用户 @ThanosTintinidis提出了一种非常简单的方法1，将初学者介绍给deriving length/2：

[...] 另请注意，E仅需要实例化它是因为 is 将评估表达式。你可以这样写：

大小（[]，0）。
大小（[_|Xs]，1+E）：- 大小（Xs，E）。

如果你称之为：

?- 大小（[_，_]，E）。
E = 1+(1+0)。

有趣，不是吗？您可能想要评估最后一个E，即 call ?- size([1,2], E), N is E。[...]

乐趣？ 大乐趣！ 许多有趣的实验摆在面前：

  • 左倾树与右倾树

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

list_siz R ([], 0)。%右倾_
list_sizR([_|Es], 1+N) :- list_sizR(Es,N)。

  • 内置(is)/2vsval_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运行的运行时间：

去（左）：-
   长度（Xs，L），
   成员（B_2，[list_sizL，list_sizR]），
   呼叫（B_2，Xs，E），
   成员（P_2，[是，val_of]），
   call_time (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 毫秒 | 650 毫秒 |   60 毫秒| 3.4 倍
       list_sizL + val_of | 381 毫秒 | 100 毫秒 | 60 毫秒 | 6.3 倍
       -------------------+--------+---------+---------|
       list_sizR + (is) | 88 毫秒 | 660 毫秒 |   70 毫秒| 1.2x
       list_sizR + val_of | 346 毫秒 | 100 毫秒 | 60 毫秒 | 5.7 倍
       -------------------+--------+---------+---------|

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

脚注 1：为了简洁和可读性，变量名称稍作修改。
脚注 2：使用合适的命令行参数运行 SWI-Prolog 7.3.20 swipl -G2G -L2G -O。

4

3 回答 3

7

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

于 2016-05-12T12:00:48.773 回答
4

您正在比较(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当前算法使用堆栈并从左到右访问参数。因此，嵌套在右侧的树需要恒定的辅助空间，因此速度要快得多。

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

于 2016-05-12T07:23:52.753 回答
2

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

也许通过Partial Evaluation可以从 SWI-Prolog 获得更好的性能，Pereira-Shieber 在Prolog 和 Natural-Language Analysis的第 6 章中很好地介绍了这一点。

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

于 2016-05-11T21:45:54.637 回答