Неравномерная производительность таблиц в BProlog 8.1

Question

Я провел несколько экспериментов с возможностями табулирования в b-prolog версии 8.1 и был весьма удивлен наблюдаемой производительностью.

Вот код, который я использовал. Подсчитывает количество шагов Коллатца N требуется для уменьшения некоторого натурального числа I до 1:

%:- 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,332, 19,78, 3,089, 3,084, 3,081

Добавляя :- table posInt_CollatzSteps/2. запросы стали в 2 раза быстрее. Тем не менее, я озадачен:

• Второй прогон более чем в 5 раз медленнее первого. Видимо, большую часть времени проводят в GC. Начиная с 3-го запуска, вариант табуляции снова быстрый.
• Теплые пробеги (3-й, 4-й,...) заметно медленнее, чем холодные (1-й).

I wasn't expecting this! Contrast this with the runtime that I observed with xsb version 3.6.0:

• w/o tabling: 14.287
• with tabling: 1.829, 0.31, 0.308, 0.31, 0.333

Что я могу сделать? Are there any directives or flags to help me get better performance with BProlog? I use BProlog version 8.1 64-bit edition with Linux.

Answer 1

Проверял против табуляции Jekejeke Prolog. Но можно было перейти только к n=100'000. Для B-Prolog следующая командная строка отлично работала в Windows:

bp -s 40000000

Говорят, что это составляет пространство стека / кучи 160 МБ. Я получаю как теплые, так и не ставимые столами, чем холодные:

B-Пролог n = 100'000 в с:
без табуляции: 14.276, 12.229
с табулированием: 0,419, 0,143, 0,127, 0,152

Код табуляции для Jekejeke использует оператор (<=)/2 из модуля hypo. Вам необходимо вручную добавить его в свой код:

Jekejeke Пролог /Minlog n=100'000 в с:
без таблицы: 20,271, 18,920
с табулированием: 3,352, 2,879, 2,300, 2,719

Так что в Jekejeke еще есть возможности для улучшения скорости. Относительно вашего вопроса B-Prolog: Когда память слишком тесная, это может нерегулярно оказывать дополнительное давление на GC, что может привести к вашему наблюдаемому поведению.

до свидания

PS: Это код табуляции Jekejeke Prolog. Вам нужно установить Jekejeke Minlog, чтобы модуль Hypo был доступен. Лучше всего установить последнюю версию:

/* with memoization */
:- thread_local posInt_CollatzStepsm/2.

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