incremental GC

classic Classic list List threaded Threaded
3 messages Options
pau
Reply | Threaded
Open this post in threaded view
|

incremental GC

pau
With my GC problem getting really serious (refering to my earlier post)
and the const patch still not solving my issues, I had to dug into the
Lua source and make my own incremental patch.

I implemented thri-color with write barrier, and it seems to become
stable after a week's debugging... but I still have some worries about
collection speed falling behind garbage generation speed.

The current L->GCthreshold v.s. L->blocks does not seem to be a good 
measurement in calculating the gc cycles to be performed. Sometimes it
collects too often, and sometimes it fails to catch up with the garbages.

Also doubling the threshold doesn't seem to be a very good idea in 
incrememtal GC either, since it isn't truely reflecting how much memory
is really available. If the collection speed falls behind, I actually
ended up doubling the threshold again and again until memory-full.

Would anybody shed some light on the two issues? I'd love to make my
patch available if I didn't code it too wrong :P

Regards,
.paul.

Reply | Threaded
Open this post in threaded view
|

Re: incremental GC

Thatcher Ulrich
On Mar 26, 2002 at 10:51 +0800, [hidden email] wrote:
> With my GC problem getting really serious (refering to my earlier post)
> and the const patch still not solving my issues, I had to dug into the
> Lua source and make my own incremental patch.
> 
> I implemented thri-color with write barrier, and it seems to become
> stable after a week's debugging... but I still have some worries about
> collection speed falling behind garbage generation speed.
> 
> The current L->GCthreshold v.s. L->blocks does not seem to be a good 
> measurement in calculating the gc cycles to be performed. Sometimes it
> collects too often, and sometimes it fails to catch up with the garbages.
> 
> Also doubling the threshold doesn't seem to be a very good idea in 
> incrememtal GC either, since it isn't truely reflecting how much memory
> is really available. If the collection speed falls behind, I actually
> ended up doubling the threshold again and again until memory-full.
> 
> Would anybody shed some light on the two issues? I'd love to make my
> patch available if I didn't code it too wrong :P

Hey, this is very exciting!

My plan for controlling an incremental collector was going to be an
explicit call from the app, something like:

LUA_API void	  lua_dogcincrement (lua_State* L, int count);

where count would specify the number of objects to mark and/or sweep.
If the app never called lua_dogcincrement() then the collector would
just act like the current non-incremental collector.

For a game, you would just put lua_dogcincrement(gc_count) in the main
loop.  You'd experiment with gc_count to find a value that consumes
less than a couple milliseconds; or, you'd do something like:

     ...
     while (time_until_vblank() > 1.5)	/* time in milliseconds */
     {
	lua_dogcincrement(500);	/* or some other count that always takes < 1 ms */
     }
     swap_buffers();

You get the idea -- put the increment explicitly in the hands of the
app.  If the incremental gc can't keep up, eventually you would get a
blocking gc.

I hope your gc works out!  I'm definitely interested to try it!

-- 
Thatcher Ulrich <[hidden email]>
http://tulrich.com

pau
Reply | Threaded
Open this post in threaded view
|

Re: incremental GC

pau
Thanks for the idea! This was actually the first attempt I made
to the API, i.e., to let application programmer control the GC
steps. But your idea of making it behave like non-incremental
collector when it cannot keep up is new to me :) I'll definitely
give it a try!

My current attempt is to follow the collection/allocation ratio
of (M - L)/2L (refering to 3.8.2 from the paper: Uniprocessor 
Garbage Collection Techniques by Paul R. Wilson). It actually
advances a few steps whenever checkGC is called, the number of
collecting steps is proportional to recent mem allocation rate.
The advantage of this method is that application programmer does
not have to worry much about the GC in background. The idea
of controlling GC by a fixed step may not work well when the
number of objects in Lua grows/shrink drastically.

But I have to make it very conservative otherwise it easily goes 
out of control (memory full). So the problem I have now is that
it does GC too often, and eventually forced me to set a threshold
on how many milliseconds it is allowed spend on GC per rendering 
frame. Again, since there isn't any precise way to do the timing 
(as I cannot check timer in every GC step), it still ends up 
spending too much time in GC.

Anyway, I'll give it another try and see how is the result.

Regards,
.paul.

On Tue, Mar 26, 2002 at 03:32:04PM -0500, Thatcher Ulrich wrote:
> 
> Hey, this is very exciting!
> 
> My plan for controlling an incremental collector was going to be an
> explicit call from the app, something like:
> 
> LUA_API void	  lua_dogcincrement (lua_State* L, int count);
> 
> where count would specify the number of objects to mark and/or sweep.
> If the app never called lua_dogcincrement() then the collector would
> just act like the current non-incremental collector.
> 
> For a game, you would just put lua_dogcincrement(gc_count) in the main
> loop.  You'd experiment with gc_count to find a value that consumes
> less than a couple milliseconds; or, you'd do something like:
> 
>      ...
>      while (time_until_vblank() > 1.5)	/* time in milliseconds */
>      {
> 	lua_dogcincrement(500);	/* or some other count that always takes < 1 ms */
>      }
>      swap_buffers();
> 
> You get the idea -- put the increment explicitly in the hands of the
> app.  If the incremental gc can't keep up, eventually you would get a
> blocking gc.
> 
> I hope your gc works out!  I'm definitely interested to try it!
> 
> -- 
> Thatcher Ulrich <[hidden email]>
> http://tulrich.com