Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


Garbage collection algorithim


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 King Mir   Members   -  Reputation: 2032

Like
0Likes
Like

Posted 15 July 2012 - 06:34 PM

I'm looking for a garbage collection algorithim that would behave like the following psudo code example specifies.
Class Foo {
  int id;
  GraphNodePtr<Foo> next //defaultly null
  Foo(int theID):id(theID){}
};


GraphNodePtr<Foo> graph(0);
{
  GraphNodePtr<Foo> node1(1);
  GraphNodePtr<Foo> node2(2);
  GraphNodePtr<Foo> node3(3);
  node1->next = node2;
  node2->next = node3;
  node3->next = node1; //circular loop
  graph->next = node1;
}
graph.next.release()//nodes 1, 2, and 3 are immediately deleted here

That is, you have a a single pointer type that can detect orphaned loops. And the garbage collection needs to guarantee that orphaned objects are released once they are orphaned.

Edited by King Mir, 16 July 2012 - 10:28 AM.


Sponsor:

#2 Mussi   Crossbones+   -  Reputation: 2057

Like
0Likes
Like

Posted 15 July 2012 - 08:34 PM

I'm not sure if a single pointer type exists/fits here. You could go for weak_ptr<> and shared_ptr<>, but I'm guessing that's not what you want?

#3 ApochPiQ   Moderators   -  Reputation: 16064

Like
1Likes
Like

Posted 15 July 2012 - 08:34 PM

Mark and sweep can generally do this, provided you have access to the stack and any other root nodes possible in the program. Can you provide more details about what you're trying to do?

#4 King Mir   Members   -  Reputation: 2032

Like
0Likes
Like

Posted 15 July 2012 - 09:38 PM

Mark and sweep can generally do this, provided you have access to the stack and any other root nodes possible in the program. Can you provide more details about what you're trying to do?

Mark and sweep would work, but then you would have to call it every time a node is deleted or released, and it would run through unrelated code to look for links to this graph. Is there an algorithm that would take advantage of the fact that releasing node 1 can only release nodes pointed to by node 1, or that can detect the loop when it is made without unmanageable overhead?

I'm not trying to do anything besides learn about general purpose garbage collection.

#5 Krohm   Crossbones+   -  Reputation: 3171

Like
0Likes
Like

Posted 16 July 2012 - 01:08 AM

Mark and sweep would work, but then you would have to call it every time a node is deleted or released, and it would run through unrelated code to look for links to this graph.

Mh, no.

I'm not trying to do anything besides learn about general purpose garbage collection.

No problem! It's just like learning "general purpose sorting"!
int array[SOME_REALLY_BIG_NUMBER];
Init(array, SOME_REALLY_BIG_NUMBER);
GeneralPurposeSort(array); // O(1), stable, online
But in the real world, things are a bit different. You don't learn something by marking existing algorithms as "not interesting to me".

#6 King Mir   Members   -  Reputation: 2032

Like
0Likes
Like

Posted 16 July 2012 - 02:07 AM


Mark and sweep would work, but then you would have to call it every time a node is deleted or released, and it would run through unrelated code to look for links to this graph.

Mh, no.

I'm not trying to do anything besides learn about general purpose garbage collection.

No problem! It's just like learning "general purpose sorting"!
int array[SOME_REALLY_BIG_NUMBER];
Init(array, SOME_REALLY_BIG_NUMBER);
GeneralPurposeSort(array); // O(1), stable, online
But in the real world, things are a bit different. You don't learn something by marking existing algorithms as "not interesting to me".

I didn't say Mark and sweep wasn't interesting. I just commented that it doesn't take advantage of some additional information that appears to be present in the example.

Also to be clear, deleting nodes immediately when they become unreachable is part of the requirements of the question. It's of some advantage to have resources released as soon as possible, and I want to know the costs of doing so.

#7 Krohm   Crossbones+   -  Reputation: 3171

Like
1Likes
Like

Posted 16 July 2012 - 07:14 AM

The information you want to exploit is, in general, not available. This is the reason for which GC is run every once in a while rather than every time something goes out of "scope". The cost of deleting objects "immediately" is untolerable for anything beyond trivial examples: no GC methods I recall (as used in major programming languages) allowed immediate, deterministic deletion of garbage, albeit some allowed some cooperation with escape analysis. In general I'd say the largest amount of papers I've consulted appeared to take for granted GC is too costly to not use it to delete high amounts of garbage (in terms of graph nodes).

What question are you talking about? Your original question does not seem to imply immediate destruction.

Note GC typically does not care in detecting loops but rather in isolating islands of unused objects.

#8 King Mir   Members   -  Reputation: 2032

Like
0Likes
Like

Posted 16 July 2012 - 10:49 AM

The information you want to exploit is, in general, not available. This is the reason for which GC is run every once in a while rather than every time something goes out of "scope". The cost of deleting objects "immediately" is untolerable for anything beyond trivial examples: no GC methods I recall (as used in major programming languages) allowed immediate, deterministic deletion of garbage, albeit some allowed some cooperation with escape analysis. In general I'd say the largest amount of papers I've consulted appeared to take for granted GC is too costly to not use it to delete high amounts of garbage (in terms of graph nodes).

What question are you talking about? Your original question does not seem to imply immediate destruction.

Note GC typically does not care in detecting loops but rather in isolating islands of unused objects.

I did say the nodes should be deleted here at the last line, but I'll edit the post to be clearer.

I realize that it is indeed costly to do it every release, but how costly? What algorithm would I use if it's really really needed?

#9 ApochPiQ   Moderators   -  Reputation: 16064

Like
0Likes
Like

Posted 16 July 2012 - 11:15 AM

AFAIK there is no known general-purpose algorithm to do what you describe. Of course, my knowledge of garbage collection is largely academic and definitely a few years out of date, so there may be more modern tricks that I do not know about.

In general, if you want deterministic destruction, you use reference counting. If you want circular reference detection, you use true garbage collection algorithms or you use weak references. All of these options are incompatible with your request from the OP.

#10 King Mir   Members   -  Reputation: 2032

Like
0Likes
Like

Posted 22 July 2012 - 08:25 PM

I've had some luck researching this, and this paper explains a decent way to take advantage of locality. See the sequential algorithm there.

It's reference counting, with additional cycle detection. From what I understand, the idea is that when you want to check for cycles (it's still expensive despite locality), for each reference counted object that has been decremented at least once, but is still in scope, see if decrementing all branches one more time leads to anything going down to 0. If it does, remove that loop. For anything not released, restore the reference count.

Edited by King Mir, 22 July 2012 - 08:30 PM.


#11 jwezorek   Crossbones+   -  Reputation: 1919

Like
0Likes
Like

Posted 22 July 2012 - 08:59 PM

Take a look at this old thread by me. I believe I'm talking about what you want; although I never actually implemented it.

Edited by jwezorek, 22 July 2012 - 09:00 PM.


#12 King Mir   Members   -  Reputation: 2032

Like
0Likes
Like

Posted 22 July 2012 - 11:38 PM

Yeah that's the same thing. I'm interested in how it would be done though. ie:

1) when to check for cycles
2) how to check for cycles
3) what information can be stored to make cheeking for cycles easier
4) What simple analysis could be done to mark a branch cycle free

#13 jwezorek   Crossbones+   -  Reputation: 1919

Like
0Likes
Like

Posted 23 July 2012 - 05:28 PM

Yeah that's the same thing. I'm interested in how it would be done though. ie:

1) when to check for cycles
2) how to check for cycles
3) what information can be stored to make cheeking for cycles easier
4) What simple analysis could be done to mark a branch cycle free


1. could be a policy class of the smart pointer. I was saying in the old thread to just check any time an a smart pointer goes out of scope and the raw pointer associated with it gets freed but that might be too aggressive.

2. Don't think in terms of checking for cycles; think in terms of whether removing a node from the graph has now left the graph such that it has connected components that are no longer attached to any live pointers. In other words, 2. can be done by the general graph algorithm get connected components. Another way to think about it is when you remove an edge from the graph, are you removing a bridge?

3. and 4. you can use a "disjoint-set" data structure to maintain the set of connected components very efficiently I believe,

Edited by jwezorek, 23 July 2012 - 05:28 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS