Nierówna wydajność przy stołowaniu w BProlog 8.1

Question

Zrobiłem kilka eksperymentów z możliwościami stołu b-prolog wersja 8.1 i byłem bardzo zaskoczony występem, który zaobserwowałem.

Oto kod, którego użyłem. Liczy liczbę Collatz krokach N wymagany dla zmniejszenia pewną liczbą całkowitą dodatnią I do 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 
    ). 

Aby określić maksymalną liczbę etapów redukcji wymaganych dla wszystkich liczb całkowitych od I0 do 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) 
    ). 

Po uruchomieniu niektórych zapytań ?- time(i0_i_maxSteps0_maxSteps(1,1000000,0,MaxSteps)). bez i z tabling, obserwowałem następujące czasy działania (w sekundach):

• W/O składanie: 6,784
• z składania: 2,323, 19,78, 3,089, 3.084, 3,081

Dodając :- table posInt_CollatzSteps/2. zapytania dostaje 2x szybciej. Mimo to jestem zaskoczony:

• Drugi przebieg jest więcej niż 5 razy wolniejszy niż pierwszy. Najwyraźniej większość czasu spędza się w GC. Od trzeciego biegu wariant na stole jest szybki.
• Ciepłe biegi (3, 4, ...) są zauważalnie wolniejsze niż zimny (pierwszy) przebieg.

Nie spodziewałem się tego! Inaczej jest z wykonywania że obserwowanego xsb wersja 3.6.0:

• W/O składanie: 14,287
• z składania: 1,829, 0,31, 0,308, 0,31, 0,333

Co mogę zrobić? Czy istnieją jakieś dyrektywy lub flagi, które pomogą mi uzyskać lepszą wydajność w BProlog? Używam wersji 64-bitowej BProlog wersji 8.1 z systemem Linux.

Answer 1

Sprawdzałam przed Jekejeke Prolog tabling. Ale może przejść tylko do n = 100'000. Dla B-Prolog następujące polecenie działało dobrze na oknach:

bp -s 40000000 

To powiedział, aby wynieść przestrzeni stos/Sterta 160 MB. Uzyskać zarówno złożone i nie zgłoszone działa lepiej niż ciepłe zimno seriach:

B Prologa n = 100'000 ws:
W/O składanie: 14,276 12.229
z składania: 0,419, 0,143, 0,127, 0,152

Kod składanie do Jekejeke używa operatora (< =)/2 z modułu hipoglikemii. Trzeba ręcznie dodać go do swojego kodu:

Jekejeke Prolog/Minlog n = 100'000 w S:
w/o składanie dokumentów: 20,271, 18,920
ze składania: 3.352, 2.879, 2.300, 2.719

W Jekejeke jest jeszcze miejsce na ulepszenia prędkości. W odniesieniu do pytania B-Prolog: gdy pamięć jest zbyt mocno zamknięta, może to nieregularnie wywierać dodatkową presję na GC, co może skutkować zaobserwowanym zachowaniem.

Bye

P.S .: Jest to kod składania Jekejeke Prolog. Musisz zainstalować Jekejeke Minlog, aby moduł hypo był dostępny. Najlepiej należy zainstalować najnowszą wersję:

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