garbage collection and keysort/2

[Jean-Luc-Picard-2021]

What does Killed mean here? Memory overflow? I don't find the same error for SWI-Prolog or Scryer-Prolog.

/* Trealla Prolog 2.51.11 */

?- start(X), time(best(X, [], [], [], L)).
Killed

?- goal(X), reverse(X,Y), time(best(Y, [], [], [], L)).
Killed

Source code:

eight2.p.log

[infradig]

The first query generates a solution using 5Gb of memory, the second query gets OOM-Killed on my 16GB system. I'll look into it.

On Wed, May 8, 2024 at 5:42 PM Jean-Luc-Picard-2021 < @.***> wrote:

What does Killed mean here? Memory overflow? I don't find the same error for SWI-Prolog or Scryer-Prolog.

/ Trealla Prolog 2.51.11 /

?- start(X), time(best(X, [], [], [], L)). Killed

?- goal(X), reverse(X,Y), time(best(Y, [], [], [], L)). Killed

Source code:

eight2.p.log https://github.com/trealla-prolog/trealla/files/15245463/eight2.p.log

— Reply to this email directly, view it on GitHub https://github.com/trealla-prolog/trealla/issues/539, or unsubscribe https://github.com/notifications/unsubscribe-auth/AFNKSETUT76ZOVGR6D3XINLZBHJOVAVCNFSM6AAAAABHMNSBFGVHI2DSMVQWIX3LMV43ASLTON2WKOZSGI4DIOJRHEYDENY . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[infradig]

It all seems to be used in the findall goal, not keysort.

[Jean-Luc-Picard-2021]

You can try this one, it has still findall/3 but no keysort/2, except for the keysort/2 in weight/2, but there is no more keysort/2 in best/5.

Trealla Prolog has no problem with it. So I doubt that it is findall/3.

/* Trealla Prolog 2.51.11 */

?- start(X), time(best(X, [], [], [], L)).
% Time elapsed 0.886s, 4227329 Inferences, 4.773 MLips

?- goal(X), reverse(X,Y), time(best(Y, [], [], [], L)).
% Time elapsed 1.752s, 8129415 Inferences, 4.640 MLips

Source code:

eight.p.log

[infradig]

Are you satisfed with this now?

[Jean-Luc-Picard-2021]

Don't know yet. I only noticed that Quicksort is a bad choice. If I am not mistaken SWI-Prolog uses a clever inline Mergesort.

What do you use? How does it perform now?

[infradig]

Well the original code works now.

On Mon, 13 May 2024, 00:13 Jean-Luc-Picard-2021, @.***> wrote:

Don't know yet. I only noticed that Quicksort is a bad choice. If I am not mistaken SWI-Prolog uses a clever inline Mergesort.

What do you use? How does it perform now?

— Reply to this email directly, view it on GitHub https://github.com/trealla-prolog/trealla/issues/539#issuecomment-2106260802, or unsubscribe https://github.com/notifications/unsubscribe-auth/AFNKSEWLKP24JH7MW3FHGQ3ZB52HJAVCNFSM6AAAAABHMNSBFGVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCMBWGI3DAOBQGI . You are receiving this because you commented.Message ID: @.***>

[infradig]

$ tpl eight2.pl
?- start(X), time(best(X, [], [], [], L)).
% Time elapsed 2.613s, 2981601 Inferences, 1.141 MLips
   X = [6,1,3,4,*,5,7,2,0], L = [down,down,right,up,left,up,right,down,down,left,up,right,up,left,down,down,right,up,left,up,right,down,left,up,right,down,right,up,left,left,down,right,up,right,down,left,up,right,down,left,up,left,down,right,right,up,left,left,down,right,up,right,down,left,left,up,right,down,right,up,left,left,down,right,right,up,left,down,left,up,right,right,down,left,left,up,right,down,right,up,left,left,down,down,right,up,left,up,right,right,down,left,up,left,down,right,right,up,left,left|...]
; 
?- goal(X), reverse(X,Y), time(best(Y, [], [], [], L)).
% Time elapsed 5.258s, 5971445 Inferences, 1.136 MLips
   X = [0,1,2,3,4,5,6,7,*], Y = [*,7,6,5,4,3,2,1,0], L = [down,down,right,up,left,up,right,down,down,left,up,right,up,left,down,down,right,up,left,up,right,down,left,up,right,down,right,up,left,left,down,right,up,right,down,left,up,right,down,left,up,left,down,right,right,up,left,left,down,right,up,right,down,left,left,up,right,down,right,up,left,left,down,right,right,up,left,down,left,up,right,right,down,left,left,up,right,down,right,up,left,left,down,down,right,up,left,up,right,right,down,left,up,left,down,right,right,up,left,left|...]
;
~/trealla (devel) $ 

[Jean-Luc-Picard-2021]

Thanks for sharing your testing results. More food for thought to investigate "sorting". Or maybe investigate library(heaps):

8 Puzzle Solution with Pairing Heap (right?) eight3.p.log

They are an itch faster than my hand rolled insert/4, but I don't know whether Trealla has library(heaps), the library is from SWI-Prolog.

Also I changed the problem a little bit so that it matches slago stackoverflow solution. My code had a bug in the goal state.

[infradig]

Nothing to stop you copying library/heaps.pl from SWI and trying to use it.

[infradig]

~/trealla (devel) $ swipl -q eight3.pl
?- empty_heap(H), start(X), time(best(X, [], H, [], L)), length(L, N).
% 76,842 inferences, 0.014 CPU in 0.014 seconds (100% CPU, 5588970 Lips)
H = heap(nil, 0),
X = [6, 1, 3, 4, -1, 5, 7, 2, 0],
L = [left, left, up, right, down, right, up, left, left|...],
N = 62 

/trealla (devel) $ cp ~/swipl-devel/library/heaps.pl library/

~/trealla (devel) $ tpl -q eight3.pl
?- empty_heap(H), start(X), time(best(X, [], H, [], L)), length(L, N).
% Time elapsed 0.022s, 60058 Inferences, 2.690 MLips
   H = heap(nil,0), X = [6,1,3,4,-1,5,7,2,0], L = [left,left,up,right,down,right,up,left,left,down,right,right,up,left,down,left,up,right,right,down,left,left,up,right,down,right,up,up,left,down,right,down,left,left,up,right,down,right,up,left,left,down,right,up,left,down,right,up,up,left,down,down,right,up,right,up,left,down,down,right,up,left], N = 62
;

[Jean-Luc-Picard-2021]

Was sort/2 also affected besides keysort/2 ? I didn't test sort/2. But one could replace all keysort/2 in eight2.p by sort/2 to get a tester.

[infradig]

Neither sort/2 nor msort/2 were affected.