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

Question

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

Вот код, который я использовал. Он подсчитывает количество Collatz шагов 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,323, 19,78, 3,089, 3,084, 3,081

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

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

Я этого не ожидал! Сравните это со средой выполнения, что я наблюдал с xsb версии 3.6.0:

• ж/о карниз: 14,287
• с: 1.829 столами, 0,31, 0,308, 0,31, 0,333

Что я могу сделать? Существуют ли какие-либо директивы или флаги, которые помогут мне повысить эффективность работы с BProlog? Я использую 64-битную версию BProlog версии 8.1 с Linux.

Answer 1

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

bp -s 40000000 

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

В-Пролог п = 100'000 в секундах:
без столов: 14,276, 12.229
с: 0,419 столами, 0,143, 0,127, 0,152

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

Jekejeke Prolog/Minlog п = 100'000 в с:
без карниз: 20,271, 18,920
с: 3.352 столами, 2.879, 2.300, 2.719

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

Bye

P.S .: Это код Jekejeke столами Пролог. Вам необходимо: установить 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) 
    ).