Dogelog Player: Heap Pressure for Garbage Collection
Dogelog Player is a Prolog system for the JavaScript, Python and Java targets. It is mostly written in 100% Prolog. Our garbage collector already used GC frequency autotuning via user_time. We added a GC generation choice autotuning feature using user_memory.
Metronome Collector
A prominent source for advanced garbage collection concerning the WAM are the SICStus Prolog papers by Matt Carlsson et al. from the 80s. Dogelog Player borrowed the trail sweep and compaction. But otherwise delegates to the host programming language garbage collector.
In its early stage, Dogelog Player had a single generation mark & sweep garbage collector, that was user_time and user_memory agnostic. The heuristic was to measure the trail length, since this is what our garbage collector reduces, before the host programming language takes over.
Meanwhile Dogelog Player abandoned measuring the trail length, and went for a metronome garbage collector, together with an incremental minor garbage collection phase, which decides which nursery Prolog logical variables are either removed or land in the old generation.
###
# Old policy:
# - Regular major GC based on metronome tock
# - Otherwise perform minor GC
##
def gc_run():
if gc_enter >= gc_tock:
gc_major()
gc_tock += 3600*gc_maxinfs
else:
gc_minor()gc_run() is called from the Prolog solver based on the logical inference counter. Since RAM and CPU speeds varies, logical inferences per second (LIPS) also varies. The current version autotunes the GC frequency via user_time so that gc_run() is called every second.
Remembered Sets
The GC generation is decided in gc_run(). The current policy is such that a major mark & sweep is called every 60 seconds, otherwise the remaining 59 times, a minor generational mark & sweep is called. Old generation Prolog logical variables that get bound again form a remembered set.
During the next minor generational mark & sweep, the remembered set will be used as additional marking roots. Unfortunately, this extends the old generation. For certain programs this old generation can indefinitely grow, and will only be reclaimed if there is a major mark & sweep.
This runaway effect can for example be observed here:
test :-
T = [_,_,_,_,_],
loop(T).
loop(T) :-
maplist(snoc, T, R, _),
loop(R).
snoc(X, T, H) :-
X = [H|T].For Dogelog Player 2.3.2 all targets fail the test case:
/* Java */
?- time(call_with_time_limit(120000, test)).
% Zeit 75626.377 ms, Benutzer 100 %, Lips 1602 k
🚨 Fehler: Ausführung wegen aufgebrauchtem Speicherplatz abgebrochen.
user auf 2
/* JavaScript */
?- time(call_with_time_limit(120000, test)).
<--- Last few GCs --->
/* Python */
?- time(call_with_time_limit(120000, test)).
RPython traceback:Ulrich Neumerkel’s paper about Precise Garbage Collection in Prolog from 2008 shows similar test cases. The corresponding stress tests consist of an indefinitely running tail recursive program. In the following we will show how to address the major mark & sweep timing problem.
Used Memory
The potpourri of the Precise Garbage Collection paper shows examples beyond the major mark & sweep timing problem in loop/1. These extended examples are based on problems with choice points or attributed variables. The SICStus Prolog papers show according refinements.
To solve the major mark & sweep timing problem we aim at measuring heap pressure and then drop the minor generational mark & sweep in favor of a major mark & sweep. The idea is to measure the used memory and compare it to a soft limit derived from max memory.
Get Dogelog Player’s stories in your inbox
Join Medium for free to get updates from this writer.
We had a “used” statistics, could extend it to PyPy:
def used_memory():
if platform.python_implementation() == "PyPy":
stats = gc._get_stats()
return (stats.total_gc_memory+
stats.total_memory_pressure+
stats.jit_backend_used)
else:
return 0A new “maxmem“ statistics was introduced, again for PyPy:
def max_memory():
if platform.python_implementation() == "PyPy":
maxstr = os.environ.get("PYPY_GC_MAX", None)
if maxstr is None:
return 0
maxstr = maxstr.upper()
if maxstr.endswith("B"):
maxstr = maxstr[:-1]
i = 0
mult = 1
while i < 3:
if maxstr.endswith("KMG"[i]):
mult = 1024**(i+1)
maxstr = maxstr[:-1]
break
i += 1
return int(float(maxstr)*mult)
else:
return 0Our code base now offers similar implementations for JavaScript and Java besides the above Python code. In all cases the value 0 means that the corresponding “statistics” is not available. Dogelog Player can still fall back to the metronome collector, use program options or default values.
Heap Pressure
To avoid repeated CPU-intensive max_memory() we store the value in variable gc_maxmem. The current heuristic is to use 75% of gc_maxmem as a soft limit to trigger an emergency major mark & sweep. The corresponding Python code reads as follows:
###
# New policy:
# - Regular major GC based on metronome tock
# - Emergency major GC based on soft limit
# - Otherwise perform minor GC
##
def gc_run():
if gc_enter >= gc_tock:
gc_major()
gc_tock += 3600*gc_maxinfs
elif (gc_maxmem != 0 and
used_memory() > gc_maxmem * 3 / 4):
gc_major()
gc_tock += 60*gc_maxinfs
else:
gc_minor()To analyse the problem we used JConsole live view of GC from JDK 26 and tapped into the running Dogelog Player 2.3.2 for Java. We saw that the Java old generation continuously grew, mirroring the old generation of Prolog logical variables and Prolog compounds that were clogging.
With the regular-only policy the timing was indeed the culprit:
/* regular-only */
?- time(call_with_time_limit(120000, test)).
min min min min min min min min min min
% Zeit 76844.937 ms, Benutzer 100 %, Lips 1570 k
🚨 Fehler: Ausführung wegen aufgebrauchtem Speicherplatz abgebrochen.
user auf 2
With the regular-and-emergency policy the problem disappears:
/* regular-and-emergency */
?- time(call_with_time_limit(120000, test)).
min min
maj min
maj
maj min min
maj
maj min min min Etc..Benchmark Results
We implemented the new policy for all targets JavaScript, Python and Java. On the upside the test case now passes, the Prolog system can run loop/1 indefinitely. On the downside the logical inferences per second (LIPS) drop considerably, since major mark & sweep is costly.
The downside is well known, it has a couple of negative side effects such as noticeable pauses and/or memory thrashing. More disturbingly, repeated major mark & sweep do traverse the same roots redundantly. Remedies are additional generations and/or incremental major mark & sweep.
The above diagram shows a LIPS comparison, higher is better. The testing campaign included all of our budget AI laptops, with CPUs such as a Ryzen AI 7 350 (Ryzen), Intel(R) Core(TM) Ultra 7 258V (Yoga), Snapdragon(R) X — X126100 (Think) and Apple A18 Pro (Neo), without virtual memory.
The degradation is not observed for SWI-Prolog, even with set_prolog_flag( stack_limit, 2147483648) it stays around 45 MLips for the Ryzen CPU without and with pressure. While our own Prolog system drops from 30 to 10 MLips for the Ryzen CPU and the Java target.
The results for Think show a problem in the availability of host language compilers resp. virtual machines. SWI-Prolog suffers in that their Windows cross-compilation for ARM64 drops the baseline from 45 to 20 MLips. We are similarly unlucky with the Microsoft JDK for ARM64.
Conclusions
The heuristic is to use 75% of max_memory as a limit for user_memory to trigger an emergency major mark & sweep. The Dogelog Player can now run loop/1 indefinitely. Less welcome is the performance drop from 30 to 10 MLips. SWI-Prolog does not show the same degradation.
See also:
Precise Garbage Collection in Prolog
https://www.complang.tuwien.ac.at/ulrich/papers/PDF/2008-ciclops.pdf
