RE: GC "survey"

["Alberto Demichelis" <alberto@...>]

Hi this is a summary of our game:

Size of the problem: 
	11ms+ with our memory manager, 23ms+ with the Win memory manager
	the collector is called once per second. I think with a generational GC
	0.5ms calling the GC every frame would be perfect.
Size of out data:
	for an average size game level

	protos=3179 closures=4601 tables=7660 udatas=4684 strings=5018

	about 1000 tables collected per cycle, this will be drastically optimized but
	because of our mem allocator this is not the bottleneck.
Profile of the GC:
	I made some tests and I saw that mark & sweep are the bottle neck.
	We are using a very fast mem allocator and our malloc() and free() are
	almost "for free".
Generational friendly considerations:
	90% of the dynamic data die in 1 GC cycle
Constant data:
	except tables 30% of the tables and few strings
	the rest of the data is static.
Considerations:
	A generational GC would probably be a big improvement, especially being able
	to specify the percentage of data to be processed (or something similar).
	The most important thing is being able to avoid hiccups in the frame rate
	also if this involve some slowdown.
	BTW probably ref counting would be better AFFAIR we don't have any cycle ref.
LAU version:
	4.1 alpha I added a field in the table obi to store a pointer
	and a pointer in the lua_State. I also removed all implicit GC calls
	and I call the GC explicitly.

ciao
Alberto

-------------------------
Alberto Demichelis
alberto@crytek.de
Crytek studios GmbH
www.crytek.com

-----Original Message-----
From: Roberto Ierusalimschy [mailto:roberto@inf.puc-rio.br]
Sent: Friday, August 23, 2002 2:36 PM
To: Multiple recipients of list
Subject: GC "survey"


As lhf wrote, we are thinking about a generational collector. The
problem is not how to implement it, but whether it would do any good.
For some applications, a generational collector can be a real booster,
for others it can make no difference from mark & sweep.

To try to improve garbage collection in Lua, we need data about it in
real programs. So, if you think you can have problems with it, please
consider taking some time to tell us about your problems. If you prefer,
send the data directly to us [lua at tecgraf...]; we will keep it
confidential. We cannot promise anything, but such data will certainly
increase the chances.

What we want to know?

* the "size" of your problem (e.g. it should run in Xms but it takes
10Xms);

* the "size" of your data (how many tables? typical size of tables?
how many closures? etc.)

* do you know the time profile of the GC in your program? Where does
it take most time? (mark, sweep, traverse of tables, sweep of strings,
actually freeing memory, etc.)

* does your program respect the "generational hypothesis"? (that is,
most objects die young, before 2-5 GC cycles?)

* does your program have lots of constant data (such as tables that you
set up once, and after that never [or seldom] change again.)? How much?
(This is very important; mainly, those are the data a generational GC
can avoid visiting, and so is the source of its improvements.)

* feel free to tell anything else you think is relevant;

* don't forget to tell which version of Lua you are using, and whether
you modified it in any way that may affect the GC.

-- Roberto