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

Question

更新:2016年6月11日

我在SICStus Prolog 4.3.2中观察到的令人困惑的性能差异已经完全消失,最近发布的SICStus Prolog 4.3.3.奖励!

我更新了下面的"运行时"表,包括SICStus Prolog 4.3.3.亮点包括:

• (is)/2是快达10倍比以前.
• val_of/2也加速了,差不多快了2倍!

MEGO ;-)

---

当回答 "这个问题在序言语言大小程序 " SO-用户@ThanosTintinidis提出了一个显着简单的方法¹介绍初学者获得的length/2:

[...]另请注意,E仅需要实例化因为是要评估表达式.你可以写这样的东西:

size([], 0).
size([_|Xs], 1+E) :- size(Xs, E).

如果你打电话给它:

?- size([_,_], E).
E = 1+(1+0).

好玩,不是吗？您可能想要评估最后一次E,即通话?- size([1,2], E), N is E.[...]

好玩吗？ 好玩! 未来将进行一些有趣的实验:

• 左倾与右倾树木

  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)/2vs.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
                  ).
  

为了测量运行时间,我运行了go(2000000)不同的Prolog处理器²:

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

在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:使用合适的命令行参数运行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)中.