Path: ...!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.prolog
Subject: Re: Ulrich Neumerkel is like Ozzy Osbourne
Date: Thu, 5 Dec 2024 11:41:41 +0100
Message-ID: <vis014$raku$1@solani.org>
References: <virv4c$eoih$1@solani.org> <virvig$raf2$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 5 Dec 2024 10:41:40 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="895646"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.19
Cancel-Lock: sha1:PhPM2Ji4S406HVq4SzyarX17z0w=
In-Reply-To: <virvig$raf2$1@solani.org>
X-User-ID: eJwFwQkRwAAIAzBLPKUdcnYM/EtYUknnCCyiri5finGlG+ahXQh19oc3Fsgwr2WhehQyswl3Kfex061+GnYTxQ==
Bytes: 4580
Lines: 118

Hi,

A further test case with choice points is this test case:

run5(Z) :- p(_,_,Z).
p(X,Y,Z) :- (Z > 0-> f(X), g(Y), dummy ; g(Y), f(X), dummy).
g([g|X]) :- g(X).
dummy.

But the choice points go away, if Z > 0 the then (->)/2 will
cut away any choice point. And if not Z > 0 the usual
optimization is anyway to have no choice point.

So we are back to the problem of minor garbage collection.
If we attack the problems with major garbage collection,
we can run all examples indefinitely. We only need to

find a high enough major garbage collection frequency.
Our usual setting is Period: 60, Dirty: 60. With changing
the setting to Period: 15, Dirty: 15 we can run the

viable test cases for straight 5 minutes long:

?- suite.
% Zeit 300966 ms, GC 51595 ms, Lips 2026565, Uhr 04.12.2024 12:01
% Zeit 300622 ms, GC 59049 ms, Lips 1929996, Uhr 04.12.2024 12:06
% Zeit 301023 ms, GC 62909 ms, Lips 1911479, Uhr 04.12.2024 12:11
% Zeit 300192 ms, GC 58244 ms, Lips 1925432, Uhr 04.12.2024 12:16
% Zeit 300065 ms, GC 52253 ms, Lips 1944909, Uhr 04.12.2024 12:21
true.

The test code was:

suite :-
    time(sys_trap(time_out(run1, 300000), _, true)),
    time(sys_trap(time_out(run2, 300000), _, true)),
    time(sys_trap(time_out(run3, 300000), _, true)),
    time(sys_trap(time_out(run5(0), 300000), _, true)),
    time(sys_trap(time_out(run5(1), 300000), _, true)).

Bye

Mild Shock schrieb:
> Hi,
> 
> This test case is also extremly cringe.
> In our Prolog system it conflicts with another
> optimization, that is in place to reduce the
> 
> length of instantiation chains.
> 
> run4 :- run(_).
> run(X) :- f(X).
> run(X) :- X == [].
> 
> Our Prolog system doesn't create a variable
> at all for the first clause of run. It speculates
> that return value variables are passed around and
> 
> thus resulting in no extra instantiation chains.
> So it passes the anonymous variable from run4
> to the call of f/1. But since the anonymous variable
> 
> is from the run(_) call site, and since there is
> a choice point. The anonymous variable is always
> reachable never carbage collected, similarly chains
> 
> _=[f,..,f|T] will never get garbage collected.
> In as far the test case fails after a while with
> memory overflow.
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> Ulrich Neumerkel is like Ozzy Osbourne.
>> He is making me paranoid. Especially this
>> F.U.D. here stole one week of my life.
>>
>> Precise Garbage Collection in Prolog
>> https://www.swi-prolog.org/download/publications/lifegc.pdf
>>
>> The test cases make no sense at all!
>> Take this test case run1, similar to run2
>> and run3:
>>
>> run1 :- f(_).
>> f([f|X]) :- f(X).
>>
>> You will never find this in real world.
>> Perpetual processes usually have a different
>> pattern of loop state transition.
>>
>> Also its virtually impossible to garbage collect
>> via minor incremental garbage collection. We
>> might find a chain X=[f,..,f,Y] and collect
>>
>> it. But Xn is then colored as old. And instantiation
>> of an old variable gets on the changed list, and
>> so a new chain Y=[f,..,f,Z] will not be reclaimed,
>>
>> so that the beast can be only reclaimed via
>> major garbage collection.
>>
>> Bye
>>
>> P.S.: Maybe there is a chance to solve it
>> nevertheless via minor garbage collection, but
>> its very difficult. I had something in
>>
>> formerly Jekejeke Prolog via reference counting.
>> But not sure how to bring it to a Prolog
>> system without reference counting.
>>
>>
>>
>