I have a directed graph data structure used for audio signal processing (see http://audulus.com if you're curious).
I would like graph edges to be strong references, so in the absence of cycles, std::shared_ptr
would do the trick. Alas, there are potentially cycles in the graph.
So, I had this idea for a simple concurrent mark-sweep collector:
The mutator thread sends events to the collector thread. The collector thread maintains its own representation of the graph and does not traverse the mutator thread's graph. The collector thread just uses mark-sweep at regular intervals.
The events would be the following (in function call form):
AddRoot(Node*)
RemoveRoot(Node*)
AddEdge(Node*, Node*)
RemoveEdge(Node*, Node*)
Is this scheme correct? The collector thread has an older version of what the mutator thread sees. My intuition is that since a node that is unreachable at an earlier time will still be unreachable at a later time, the collector thread may delete an unreachable object as soon as it finds one.
Also, if it's correct for one mutator thread, would it work for multiple mutator threads?
UPDATE
I've released the code here: https://github.com/audulus/collector. The code is actually fairly general purpose. Use RootPtr<T>
to automatically keep track of root nodes. Links between nodes are managed using EdgePtr<T>
.
The collector seems to work for multiple mutator threads (both in my app and in unit tests), but I feel like a proof of correctness is needed.
PLEASE NOTE (in repsonse to @AaronGolden's comment below, judging from the comments below, people aren't reading this): The mutator thread is responsible for calling the collector functions in the correct order. For example, if the mutator thread calls RemoveEdge(a,b)
before assigning b
to a RootPtr
, the collector may intervene and collect b
.
UPDATE 2:
I've updated the code to my latest version and updated the link above. I've now used the code in my app for over a year and haven't attributed any bugs to it.
std::shared_ptr
doesn't suffice. When does an edge become obsolete, when do cycles, vertices?AddRoot
andRemoveRoot
events.n
unreachable and then adds a new edge makingn
reachable again, and your collection thread happens to freen
between those actions, you're going to have trouble. I think you'll need to lock your event queue to perform garbage collection, which means you're still going to have the possibility of intermittent reduced responsiveness due to garbage collection.