Matt Fowles <[EMAIL PROTECTED]> wrote: > Leo~ > On Fri, 20 Aug 2004 16:26:33 +0200, Leopold Toetsch <[EMAIL PROTECTED]> wrote: >> And yes, I'm really thinking of inserting these A* nodes. Freezing an >> object does need it. DOD of course not really.
> How is space going to be made for these? DOD probably does not want > to allocate the dummy spaces to refer back to previous elements (since > it might be called in low memory situations), but without them the > subtree assertion might not hold. Good question. 1) I'm thinking of allocating these place holders in aggregates only, or better in "old" aggregates. 2) While it of course takes up resources, it doesn't impose a problem for low memory situation. The incremental collector isn't triggered by low memory (which actually isn't low memory at all - resource shortage, empty free list is the trigger in our old DOD system). Incremental DOD is triggered by allocations. For A allocations k.A work is done in the collector. The throttle factor k defines the memory usage vs speed behavior of the collector. With low k values memory usage can go up significantly, with high k values space wastage is minimal but it takes much more time to just do more cleanup. 3) So while that extra placeholder of course is a valuable resource it would save a lot of time to help preserving the object graph or at least to rebuild big chunks of the graph quickly as needed by the generational GC scheme and by object freezing. > Thus your subtree assertion would only be true with dummies in place. Yep. That's true. > But we cannot tell how many dummies an object graph would generate > ahead of time. No, we can't. But we can gather statistics during a DOD run. And we can reuse these numbers in the next DOD run, when visiting the same aggregate again. It doesn't make sense to do that for a small tuple of course, But scanning an array with 100.000 items could be vastly improved with some meta-information for that aggregate. Basically a bit "old_generation" and a word "skip N words to skip my graph" would suffice. > ... In fact, the root could be a dummy after every single > other object if they all referenced it. Thus I don't know how we > could get around allocating dummies dynamically... I'd rather not consider all of the root set for constructing the full object graph in the first place. I'm thinking of something like this: - mark the long-lived part of the root set (globals, interpreter internals, deeply buried lexicals ...) - trace children of that partial root set - immediately before sweep: stop-the-world now - mark volatile root set (Parrot registers, top lexicals, C stack) - reorder graph by hanging in already scanned old generation - sweep, then start over While that scheme doesn't really guarantee real time (i.e fixed bounded) operation, it ought to be soft real time. The fast moving part of the root set get scanned last. All intermediate temporaries aren't even looked at. The write barrier assures that the already scanned graphs (the old generation) isn't changed, or better, if it got changed, it gets rescheduled for a re-scan or updated immediately to reflect that change. So allocating these dummy placeholders would be done basically in the old generation only. The probably high count of multiple references in the volatile root set is ignored for garbage collection. For freezing the whole interpreter it would need consideration though. Summary: - the old generation graph is always uptodate - on massive changes to such an old object it's taken out of old - the young generation's graph is created last and dynamically That's what is crawling around in my head since quite a time. I dunno if it's really doable. But I think it could work. > Matt leo
