"Garbage" questions

Help!
1

SWIP v 10.1.20, MacOS, Apple silicon

With the “exact” CPU profiler, I’ve been paying more attention to the impact of the garbage collector. My simple peg_parse BM is indicating 5-10% of the time is spent in GC. That was a bit of a surprise since I didn’t think this short BM (~25,000 inferences) produced much garbage to be collected.

Using a small predicate to output GC statistics:

get_garbage(G,GCs,CellsGained) :-
	garbage_collect,
	statistics(garbage_collection,[GC0,By0,_,_]),
	G,
	statistics(garbage_collection,[GC1,By1,_,_]),
	GCs is GC1-GC0,
	CellsGained is (By1-By0)/8.  % 8 bytes/cell

I get:

?- peg_grammar(_G), get_garbage(peg_parse(pPEG,_G,_T),GCs,Cells).
GCs = 2,
Cells = 35368.

For this small BM, it seems like a lot of memory recovered. (Intel Macs give a similar result but only 1 GC reported.) With all the available stack memory, why is GC even being activated (twice)? Is some of this tunable?

I generally assume that terms created would be freed on backtracking, and would not depend on the GC to free space.

Other than terms created through unification, other possible sources of garbage include =.. (univ) and string ops (e.g., substring). Since there should be no references to them upon backtracking, they shouldn’t be any different (?).

Are there any tools which would help to identify (unexpected) sources of garbage?

2

Yes. See set_prolog_stack/2. Brute force is ?- set_prolog_flag(gc, false). That causes it to simply expand the stack until it runs out.

Yes, but there are two exceptions: exceptions (throw/1) and nb_* predicates that set the value to a compound term, float, rational, big integer or string (anything that is allocated on the stack). Both freeze the global stack to just above the value that has been set. Backtracking than takes it back to this bar. Anything below the bar is left to GC. GC also figures out whether the freeze bar is still needed and resets or removes it if possible.

No. There is term_size/2 that can tell you how many cells are taken by some term and you already figured out statistics/2. I guess it would be possible to add to the profiler: take the amount of stack at call time and exit time and reduce by what has been garbage collected. Might be worth a try.

3

This:

A term containing diagnostic information about the highest point of failure was being kept in a global updated with nb_linkarg. I’ll have to rethink my design options.

Thanks.

4

I’ve also come to the conclusion that the default min_free values for the stacks are pretty low:

?- prolog_stack_property(S,min_free(F)).
S = local,
F = 1041 ;
S = global,
F = 256 ;
S = trail,
F = 256 ;
false.

which seems to result in excessive GC counts.

5

Yes, they are. That is because multi-threaded execution has always had a lot of attention and with many threads we want to keep them small. In most scenarios that is fine as GC cost is pretty much linear in the amount of non-garbage data (with a smaller component that is linear to the size of the stacks) on the Your \pm10\% is rather large. I’m not really sure why the system does not adjust the parameters. Normally, after GC takes over 5\% if I recall correctly, a hook is activated that reconsiders the parameters. Possibly the pattern resulting from the frozen stacks doesn’t cause it to kick in the right way.

A better approach might be to finally introduce incremental (generational?) GC. Notably full GC scans that scan the global stack below the frozen bar multiple times mainly cost time while gaining little.

6

We now have a memory (global stack) view in the profiler. See here

image
image1271×822 118 KB

This shows two things

  • The string and =../2 impact you suspected is minimal.
  • Backtracking works poorly as the summary says 29.4Kb is reclaimed by backtracking and 243.7Kb by GC.

Pretty much all garbage is collected by created compound terms and backtracking cannot reclaimed due to nb_linkarg/3.