Sorry for answering so late... On 6/8/05, Leopold Toetsch <[EMAIL PROTECTED]> wrote: > jerry gay wrote: > > i'm no gc expert, but here's my comments after discussions with > > alexandre on #parrot. > > > > On 6/8/05, Alexandre Buisse <[EMAIL PROTECTED]> wrote: > > > since threading issues haven't been mentioned here, i thought i'd make > > sure they get discussed. now, if someone could say something > > intelligent about threading issues with this gc scheme, we can start > > the discussion :-) > > A thread has typically some objects in it's local memory arena and may > refer to shared objects, located in some other arena. We now have two cases: > > 1) a local GC run in the threads arena > 2) GC of the shared arena > > Case 1) is simple as it's fully private to the thread. A non-shared > object can not be referenced by a shared one, therefore all local > garbage can be identified.
Does that mean that we have a gc structure in each arena (which, as far as I understand parrot design, is similar to a process memory space) ? Or is a gc rather attached to a thread or a shared arena ? (My question could be restated in : "are we sure that a thread only uses one arena for its local storage ?"). > For the shared case 2) things get more complicated. Something like this > might happen: > > - a "global GC start event" is triggered > - all threads must meet at a rendevous point > - all threads start a mark phase, shared items are marked either inside > a mutex lock or faster with an atomic BTS or CAS [1] > - threads can continue to run code or run a private GC too (as the mark > is already done) > - the owner of the shared arena waits for all threads to finish mark > - the owner of the shared arena collects garbage This seems the simplest way to perform it. I am not sure I understand why threads must meet at a rendezvous point, though. Couldn't they just stop what they were doing, mark their shared items and go on ? There is also something else about the locks (but it may be what you call BTS or CAS) : it is the gc of the owner of the arena that should have all the locks, and release them when he's done with the compaction phase (because we know objects won't move anymore). And then we'd need all the threads to meet at a rendezvous point, but only _after_ the marking phase. They wait for the gc to have said "I have all the locks" and then go on. Of course, if they want access of the objects before the gc is done, they will have to sleep, which makes this part really critical for the system speed and safety. > >>We then use a generational, incremental mark-and-sweep algorithm, such > >>as described by http://citeseer.csail.mit.edu/armstrong95one.html > >> > >>We have different generations (in fact queues) of objects, from 1 to > >>n-1 (the value of n could be tuned dynamically). We also have two > > > > "tuned dynamically", as in at run-time? alexandre mentioned this may > > be possible on #parrot, but there may be trouble with decreasing the > > generation count. i don't know if run-time tuning of the generation > > count is necessary, but if so, i imagine that decreasing the count at > > run-time could be achieved by merging generations. > > Yep. We'd have usually 3 generations: constant / old / new. But if a > scope emit's code that it need timely destruction it seems best to just > make this scope one generation. On scope exit all remaining objects get > merged with the previous generation. I was thinking about the possible advantages of using more generations. One could be that it allows more fine-tuning of memory we allocate. I think we won't be malloc/freeing our generations all the time, but only malloc the overhead when needed, and never free it. If we want the generation to be a whole, we have to copy everything in it (which costs much), if not, we have an array splitted in many parts, which can be imho better described by several generations. So allocating more space is adding a generation. And if we see that we have many empty generations, we can just delete them and free the unused memory. > > if this gc is tunable at build-time, it should be configurable such > > that timely destruction can be disabled. after all, most languages > > just don't need it, so why should they have the overhead? > > You don't disable timely destruction. In the absence of some special > scope_enter / scope_exit opcodes, there is no timely destruction. It > only depends on the code that parrot executes. > > > good start! and since the gc is modular, it should be straightforward > > to implement this without affecting the existing gc--that should make > > it easier to develop and test. > > At the beginning GC is modular, yes. But if this concepts works and > works fast, then we have the opportunity to use variable-sized PMC > bodies. This simplifies e.g. objects vastly. An object is then just an > attribute count + a fixed sized piece of memory w/o any indirection > (plus the usual PMC stuff). I will begin to dig into parrot source, and hope I will be able to start coding soon, if everyone is ok with the current design. Regards Alexandre PS: sorry, I had forgotten to Cc: perl6-internals
