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 倍になりました。

MEGO;-)

「プロローグ言語のサイズ手順」という質問に答えると、 SOユーザー@TanosTintinidisは、初心者に導出を紹介する非常に簡単な方法1を提案しました。length/2

[...]またE、式を評価しようとしているという理由だけでインスタンス化する必要があることに注意してください。次のように書くことができます。

サイズ([], 0)。
size([_|Xs], 1+E) :- size(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)/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)、
   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 + (である) | 208 ミリ秒 | 650 ミリ秒 |   60 ミリ秒| 3.4倍
       list_sizL + val_of | 381 ミリ秒 | 100 ミリ秒 | 60 ミリ秒 | 6.3倍
       -------+--------+---------+---------|
       list_sizR + (である) | 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。

4

3 に答える 3

7

SICStus Prolog では、式が大きな複合項の場合、つまりが式を解釈する場合val_of/2よりもはるかに高速であるという驚くべき事実を確認できます。is/2is/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

の 2 つの非常に異なる実装を比較してい(is)/2ます。SWI は、実際の評価の前にインスタンス化エラーと循環式を検出します。SICStus はそうではありません。これを試してください：

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

SWI はインスタンス化エラーと型エラーを生成しますが (無限ツリーのため)、SICStus は常に 1/0 を評価し、どちらの場合も評価エラーを生成します。そして（少なくともこの例では）、両方とも適合しています。

2 つのツリー構造の評価速度の違いは、SWIground/1とacyclic_term/1SWI の末尾再帰の最適化によるものです。現在のアルゴリズムはスタックを使用し、左から右に引数を参照します。したがって、右にネストされたツリーは一定の補助スペースを必要とするため、はるかに高速です。

SICStus は と に Deutsch-Schorr-Waite を使用するためacyclic_term/1、ground/1明示的なスタックがなく、したがって TRO もありません。少なくとも、どちらも左右でほぼ同じ速度です。

于 2016-05-12T07:23:52.753 に答える
2

簡単に言えば、SWI-Prolog は算術演算の最適化に専念しているのに対し、SICStus は一般的な制御フローのコード生成が優れていると思います。

おそらく、 Prolog and Natural-Language Analysisの第 6 章で Pereira-Sieber によって非常によく紹介されているPartial Evaluationによって、SWI-Prolog からより良いパフォーマンスが得られる可能性があります。

また、YAP にもチャンスを与える必要があります。これは、最速の WAM ベースの Prolog として報告されています。Jan Wielemaker が SWI-Prolog のリストで、YAP の速度のほとんどは大規模な書き換え (インライン化など) によって得られたと述べたのを覚えています。（もちろん、うまく実装されています）部分的な評価に基づいていると思います。

于 2016-05-11T21:45:54.637 に答える