Re: how to suppress carefully a recursive tree

> Step 3 only involves a *single* mark and sweep. It begins by flagging
> all the roots as visited and pushing them on a stack. The mark phase
> involves popping a node from the stack and pushing adjacent nodes that
> haven't yet been visited, until the stack is empty. Note that it is
> best to mark nodes as visited as they are pushed onto the stack
> (rather than when they're popped). So at all times the stack only
> contains nodes that have been marked as visited. This makes it clear
> that the algorithm will never process a node more than once.
>
> Step 3 will typically be faster than step 1 even though it may start
> with multiple roots. The time taken by a trace has more to do with
> the total number of visited nodes than the initial number of roots,
> and step 3 always visits a subset of the nodes that were visited in
> step 1.

OK you are right. I did not realize that this algorithm was not fully recursive because one visit only non marked objects.

I have programmed it and it seems to work correctly. But I think that I will adopt the Python strategy :
- for deleting a tree or a branch, I just decrement the reference count of its root first and I delete it really (and sub-objects recursively) if the count is equal to zero. This can be done everywhere in my application but lost objects (those with recursion) may remain undeleted.
- from time to time, in a single thread part of the application, I can decide to call a garbage collector which examines all the container objects. This is possible because I always keep information (pointer) about all the created objects. The step 1 is even simplified because I don't need to go down the containers recursively : I know all the containers and I just have to examine container sub-objects at the first level. At the end of this step I know all the root containers (those which have been protected somewhere in increasing their reference count without storing them in a container). Then I start steps 2 and 3.

I have programmed this strategy and it seem to work ... on two simple examples with few nodes, from 6 (the example proposed) to 15000 (a short test case). I have now to test it in real conditions (in general about 1 million of containers for 5 to 10 millions of objects for a big test case) and measure performances.

Thank you very much for your help !

F. Jacq Received on Fri Jan 25 2008 - 04:37:19 CET