title: Garbage collector : data structure of the object graph
body: <p>I read many resources on garbage collecting where they explained different algorithm. However, I didn't find any explaining the representation of the graph object.</p>
  
  <p>My idea is quite simple : an oriented graph where vertex represent allocated memory block (on heap) and the edges the owner relationship. Example : Consider 2 memory blocks m1 and m2, if m1 contains reference to a block inside m2 then add an edge (m1, m2). These edges are weighted with the number of references to m2 that m1 contains (here just 1). Finally I've got a "virtual" memory vertex representing the stack, call it M0. Every Mi reachable from M0 mustn't be garbage collected.</p>
  
  <p>Okay, now consider you want to add a memory block to the graph. If we keep the vertices inside a set, then the complexity of adding a memory block should be of O(log(n)).
  First question : Can we do better ?</p>
  
  <p>Idem for deleting.</p>
  
  <p>Now, I'm asked to use this algorithm with a reference counting mechanism in C++ (shared_ptr). Firstly, is the reference counter isn't redundant with the in-degree of a vertex ?</p>
  
  <p>Secondly, the key idea is to use the best of the reference counter (O(1) deleting/adding) with the best of the garbage collector algorithm (cleaning reference cycles), but is the overhead of adding/deleting each node in the object graph isn't a bit non-efficient ?</p>
  
  <p>What are the complexities of adding/removing in known garbage collector (java / C# / …) ?</p>
  
  <p>Thanks !</p>