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.
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.
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.
| Sysop: | DaiTengu |
|---|---|
| Location: | Appleton, WI |
| Users: | 1,015 |
| Nodes: | 10 (0 / 10) |
| Uptime: | 57:23:27 |
| Calls: | 13,252 |
| Calls today: | 1 |
| Files: | 186,574 |
| D/L today: |
4,445 files (1,145M bytes) |
| Messages: | 3,335,122 |