4

バージョン 8.1のテーブル機能でいくつかの実験を行い、 観察したパフォーマンスに非常に驚きました。

これが私が使用したコードです。正の整数を に減らすために必要なコラッツステップの数をカウントします。NI1

%:- table posInt_CollatzSteps/2.               % remove comment to enable tabling
posInt_CollatzSteps(I,N) :-
   (  I == 1
   -> N = 0                                                % base case
   ;  1 is I /\ 1 
   -> I0 is I*3+1, posInt_CollatzSteps(I0,N0), N is N0+1   % odd
   ;  I0 is I>>1,  posInt_CollatzSteps(I0,N0), N is N0+1   % even
   ).

から までのすべての整数に必要なリダクション ステップの最大数を決定するには、次のI0ようにしIます。

i0_i_maxSteps0_maxSteps(I0,I,M0,M) :-
   (  I0 > I
   -> M0 = M
   ;  posInt_CollatzSteps(I0,N0),
      I1 is I0+1,
      M1 is max(M0,N0),
      i0_i_maxSteps0_maxSteps(I1,I,M1,M)
   ).

テーブルを使用しない場合と使用する場合のいくつかのクエリ?- time(i0_i_maxSteps0_maxSteps(1,1000000,0,MaxSteps)).を実行すると、次のランタイム (秒) が観察されました。

  • テーブルなし: 6.784
  • テーブル付き: 2.323、19.78、3.089、3.084、3.081 _ _ _ _

クエリを追加すること:- table posInt_CollatzSteps/2.で、2 倍速くなりました。それでも、私は困惑しています：

  • 2 回目の実行は、1 回目の実行よりも 5 倍以上遅くなります。どうやらほとんどの時間はGCに費やされています。3 回目以降、テーブル バリアントは再び高速になります。
  • ウォーム実行 (3 回目、4 回目、...) は、コールド (1 回目) 実行よりも著しく遅くなります。

私はこれを期待していませんでした！バージョン 3.6.0で観察したランタイムと比較してください。

  • テーブルなし: 14.287
  • テーブル付き: 1.829、0.31、0.308、0.31、0.333 _ _ _ _

私に何ができる？BProlog のパフォーマンスを向上させるためのディレクティブやフラグはありますか? Linux で BProlog バージョン 8.1 64 ビット版を使用しています。

4

1 に答える 1

2

Jekejeke Prolog Trailed memoing と照合していました。n = 100'000 になるだけでした。B-Prolog の場合、次のコマンド ラインは Windows で正常に機能しました。

bp -s 40000000

これは、160MB のスタック/ヒープ スペースになると言われています。コールドランよりも、テーブル化されたものとテーブル化されていないものの両方で、ウォームランの方が優れています。

B-Prolog n=100'000 in s:
テーブルなし: 14.276, 12.229 テーブル
付き: 0.419, 0.143, 0.127, 0.152

Jekejeke のメモコードは、モジュール hypo の述語 assumez/2 を使用します。B-Prolog テーブル作成とは対照的に、追跡メモ作成は呼び出しごとにすべてを再計算します。コードに手動で追加する必要があります。

Jekejeke Prolog/Minlog n=100'000 in s:
メモなし: 4.521, 3.893 メモあり: 0.724,
0.573, 0.585, 0.555

したがって、Jekejeke にはまだ速度改善の余地があります。B-Prolog の質問について: メモリが不足している場合、不規則に GC に追加の圧力がかかり、観察された動作が発生する可能性があります。

さよなら

PS: これは Jekejeke Prolog のメモ用コードです。モジュールhypoを利用できるようにするには、Jekejeke Minlogをインストールする必要があります。最善の方法は、最新のリリースをインストールすることです:

:- thread_local posInt_CollatzStepsm/2.

mposInt_CollatzSteps(I,N) :-
   (  I == 1
   -> N = 0                                                % base case
   ;  posInt_CollatzStepsm(I,N) %%% memo check
   -> true
   ;  1 is I /\ 1
   -> I0 is I*3+1, mposInt_CollatzSteps(I0,N0), N is N0+1,   % odd
      assumez(posInt_CollatzStepsm(I,N)) %%% memo add
   ;  I0 is I>>1,  mposInt_CollatzSteps(I0,N0), N is N0+1,   % even
      assumez(posInt_CollatzStepsm(I,N)) %%% memo add
   ).

?- time(mi0_i_maxSteps0_maxSteps(1, 100000, 0, R)).
% Up 724 ms, GC 71 ms, Thread Cpu 640 ms (Current 06/20/19 09:43:24)
R = 350

?- time(mi0_i_maxSteps0_maxSteps(1, 100000, 0, R)).
% Up 573 ms, GC 69 ms, Thread Cpu 500 ms (Current 06/20/19 09:43:27)
R = 350
于 2016-05-15T20:51:39.420 に答える