Re: GC [was Re: Lua 5.1 (work4) now available]

[skaller <skaller@...>]

On Fri, 2005-01-07 at 16:49, Mike Pall wrote:

> I wrote:
> > I patched luaC_step to print some stats after each call (see attachment).
> 
> Ok, so I tried this with the linked list example provided by John Skaller
> and got interesting results. I generated a graph including the total and
> estimated memory and the current threshold. See the attached images (compare
> them side by side).

> I think the problem is that the estimate is derived from the total memory
> consumption after the propagate phase. But it really should be derived
> from the total memory minus the memory (still) occupied by soon-to-be-dead
> objects. See the end of atomic() in lgc.c.

> Does this make sense?

This is a hard problem. See also Mark's comment: 
"a generational collector, you also need to throw in the issue of how
fast objects are getting tenured"

I have done a lot of work with phase locked loops.
This is basically the same problem -- you need to
keep a variable Y tracking some external variable X.

I am wondering if in calculating the amount of
'work' that needs to be done in each step, if
a quadratic polynomial wouldn't be useful.

Basically:

	X = reachable memory
	Y = total memory

Ideally, Y = X at all times, but this is expensive,
we will accept G = Y - X to be say 20% of X.

A first order solution:

	E0 = Y0 - X0
	Y1 = Y0 + E0

is too expensive, so we can try

	Y1 =  Y0 + k * E0

instead. If k = 1/n this means doing 1/n'th of the work
each cycle.

However this can easily loose track if X varies
too fast. So using a quadratic term:

	D = E1 - E0
	Y1 = Y0 + k * E1 + j * D^2

where D measures how fast our *error* estimate is changing,
(the error in the error). If D is small it has
no impact on the correction factor -- we just do linear
adjustments. But if our errors get out of hand, D takes
over, since D^2 rapidly becomes large.

So basically the idea is:

in a game, if you do something drastic like loading
a new level, or killing off the player, the quadratic
term rapidly dominates and forces heavy collection,
but it doesn't matter (real time performance is already
lost at that point anyhow, it's much more important
not to run out of memory)

However during 'normal' gameplay you'd start off
doing too many full collections to gain an estimate
of how fast garbage is generated, and gradually tune it down,
so that garbage is collected at the same rate it is generated
incrementally (since our estimate is now very good).

The quadratic correction formula will do all this
automatically, provided there is some way of using
the generated output to 'drive' the incremental
collector to do more or less work each cycle.

[Of course the constants k and j need to be chosen
carefully .. that's the hard part .. because the values
are application dependent .. :]

Hmm .. what I'm saying is that the 'zig-zag' pattern seen
in the graphs are symptomatic of an under-dampened feedback
circuit. It needs more damping, with a quadratic term
to make sure it never lags too far behind, in case some
memory changes are systematic rather than random.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net