Ungleichmäßige Tabling-Performance in BProlog 8.1

Question

Ich habe ein paar Experimente mit den Tabling-Fähigkeiten von b-prolog Version 8.1 und war ziemlich überrascht von der Leistung, die ich beobachtet habe.

Hier ist der Code, den ich verwendet habe. Es zählt die Anzahl der Collatz Schritte N erforderlich für eine positive ganze Zahl I bis 1 reduzieren:

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

:

%:- 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 
    ). 

Um die maximale Anzahl von Reduktionsschritten für alle ganzen Zahlen I0-I erforderlich zu bestimmen Wenn ich einige Abfragen ?- time(i0_i_maxSteps0_maxSteps(1,1000000,0,MaxSteps)). ohne und mit Tabling ausgeführt habe, beobachtete ich die folgenden Laufzeiten (in Sekunden):

• w/o Einreichungs: 6,784
• mit Einreichungs: 2.323, 19.78, 3.089, 3,084, 3,081

Durch das Hinzufügen :- table posInt_CollatzSteps/2. die Abfragen bekam 2x schneller. Dennoch bin ich verwirrt:

• Der 2. Lauf ist mehr als 5x langsamer als der erste. Anscheinend wird die meiste Zeit in GC verbracht. Ab dem 3. Lauf ist die Tabling-Variante wieder schnell.
• Warmläufe (3., 4., ...) sind merklich langsamer als der kalte (1.) Lauf.

Ich habe das nicht erwartet! Vergleichen Sie dies mit der Laufzeit, die ich mit xsb Version 3.6.0 beobachtet:

• w/o Einreichungs: 14,287
• mit Einreichungs: 1.829, 0,31, 0.308, 0,31, 0.333

Was kann ich tun? Gibt es Richtlinien oder Flags, die mir helfen, bessere Leistung mit BProlog zu erzielen? Ich benutze BProlog Version 8.1 64-Bit Edition mit Linux.

Answer 1

War gegen Jekejeke Prolog Tabling. Aber konnte nur gehen bis n = 100'000. Für B-Prolog der folgende Befehlszeile hat gut funktioniert an Fenstern:

bp -s 40000000 

Dies soll zu einem Stapel/Heap-Speicher von 160 MB betragen. Ich erhalte beide eingereicht und nicht eingereicht besser warme läuft als kalte Läufe:

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

Die Einreichungs Code für Jekejeke verwendet den Operator (< =)/2 von der hypo Modul . Sie müssen es manuell zu Ihrem Code hinzu:

Jekejeke Prolog/Minlog n = 100'000 in s:
w/o Einreichungs: 20,271, 18,920
mit Einreichungs: 3,352, 2,879, 2,300, 2,719

So gibt es noch Platz für Geschwindigkeitsverbesserungen in Jekejeke. In Bezug auf Ihre B-Prolog Frage: Wenn der Speicher zu eng ist, könnte dies einen zusätzlichen Druck auf GC ausüben, was zu Ihrem beobachteten Verhalten führen könnte.

Bye

P. S .: Das ist der Jekejeke Prolog der Einreichung von Code. Sie müssen Jekejeke Minlog installieren, damit das Modul hypo verfügbar ist. Beste ist die neueste Version zu installieren:

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