Prestazioni di tabulazione non uniformi in BProlog 8.1

Question

Ho fatto alcuni esperimenti con le funzionalità di tabulazione di b-prolog versione 8.1 ed è stato piuttosto sorpreso dalle prestazioni osservate.

Ecco il codice che ho usato. Conta il numero di Collatz passi N necessaria per ridurre un po 'intero positivo I verso il basso per 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 
    ). 

Per determinare il numero massimo di passi di riduzione necessari per tutti gli interi 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) 
    ). 

Quando ho eseguito alcune query ?- time(i0_i_maxSteps0_maxSteps(1,1000000,0,MaxSteps)). senza e con la presentazione, ho osservato i seguenti runtime (in secondi):

• w/o presentazione: 6,784
• con presentazione: 2.323, 19.78, 3.089, 3.084, 3,081

Aggiungendo :- table posInt_CollatzSteps/2. le query ottenuto 2x più veloce. Tuttavia, sono perplesso:

• La seconda corsa è più di 5 volte più lenta della prima. Apparentemente la maggior parte del tempo è spesa in GC. Dalla terza esecuzione in poi, la variante di tablatura è di nuovo veloce.
• Le corse calde (3a, 4a, ...) sono notevolmente più lenta rispetto alla corsa fredda (1a).

Non me l'aspettavo! In contrasto con il runtime che ho osservato con xsb versione 3.6.0:

• w/o presentazione: 14,287
• con presentazione: 1.829, 0,31, 0,308, 0,31, 0.333

Cosa posso fare? Ci sono delle direttive o delle bandiere per aiutarmi a ottenere prestazioni migliori con BProlog? Uso BProlog versione 8.1 64-bit con Linux.

Answer 1

Stavo verificando contro Jekejeke Prolog su carta. Ma poteva andare solo da a n = 100'000. Per B-Prolog il seguente comando funzionava bene sulle finestre:

bp -s 40000000 

Questo si dice ammontare a uno spazio pila/mucchio di 160MB. Ottengo sia presentati e non presentati funziona meglio caldi di piste fredde:

B-Prolog n = 100'000 in s:
w/o presentazione: 14,276, 12.229
con presentazione: 0,419, 0,143, 0,127, 0,152

Il codice presentazione per Jekejeke utilizza l'operatore (< =)/2 dal modulo ipo. È necessario aggiungere manualmente al codice:

Jekejeke Prolog/Minlog n = 100'000 in s:
w/o presentazione: 20,271, 18,920
con presentazione: 3.352, 2.879, 2.300, 2.719

Quindi c'è ancora spazio per miglioramenti della velocità a Jekejeke. Per quanto riguarda la domanda B-Prolog: quando la memoria è troppo stretta , ciò potrebbe causare un'ulteriore pressione aggiuntiva su un GC , causando probabilmente il comportamento osservato.

Bye

P.S .: Questo è il codice presentazione Jekejeke Prolog. È necessario installareJekejeke Minlog per avere il modulo hypo disponibile. Il migliore è quello di installare l'ultima versione:

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