21

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.

23
  • I don't see why std::shared_ptr doesn't suffice. When does an edge become obsolete, when do cycles, vertices?
    – stefan
    Jun 14, 2013 at 19:52
  • 1
    Hey @stefan, thanks for your reply! The issue is the old cycle problem with reference counting. See en.wikipedia.org/wiki/…
    – Taylor
    Jun 14, 2013 at 20:07
  • What about breaking the cycle through resetting an edge? You didn't actually answer my question which is "When does a cycle become obsolete"
    – stefan
    Jun 14, 2013 at 20:09
  • 1
    @Casey, right (though they're not signal sources). The root set seen by the collector would be controlled with the AddRoot and RemoveRoot events.
    – Taylor
    Jun 14, 2013 at 20:28
  • 6
    If your mutator thread removes an edge making node n unreachable and then adds a new edge making n reachable again, and your collection thread happens to free n 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. Jun 17, 2013 at 19:46

2 Answers 2

1

One argument I think is somewhat persuasive (though I would hesitate to call it proof) that this scheme works is that in the absence of cycles, the scheme is equivalent to reference counting with atomic reference counts.

In the absence of cycles, AddRoot and AddEdge map to incrementing a reference count and RemoveRoot and RemoveEdge map to decrementing. Pushing an event onto the queue (I use boost::lockfree::queue) is an atomic operation just like the updating reference counts.

So then the remaining question is: how do cycles change the picture in terms of correctness? To wave hands a bit, cycles are a property of the connectivity of the graph, but don't have an effect on the atomicity of the operations or the ability of one thread to know something earlier than it would otherwise (causing a potential bad ordering of operations).

This would suggest that if there's a counterexample for the scheme, it will involve playing some game with cycles.

1
  • Thanks for the interesting read, and for sharing the code, I'm hopeful my current project will be going in a direction where I need something like this and can dig in more.
    – moodboom
    Jun 26, 2013 at 14:16
0

Is this scheme correct?

I'm concerned that you don't have any concept of safe points. In particular, can an update require more than one of your actions to be executed atomically? Perhaps it is ok because you can always add all vertices and edges in a batch before removing.

Also, if it's correct for one mutator thread, would it work for multiple mutator threads?

If one thread drops a root to a subgraph just after another picks up a root to the same subgraph then you must make sure you get the messages in-order which means you cannot use per-mutator queues. And a global queue is likely to kill scalability.

One of my constraints is that the GC has to be lock-free because of my real-time DSP thread

  1. Is the allocator lock-free?
  2. What if the GC cannot keep up with mutator(s)?

Also, I would recommend considering:

  1. Forking and collecting in a child process.
  2. Incremental mark-sweep with Dijkstra's tricolor marking sceme.
  3. Baker's treadmill.
  4. VCGC.
  5. Separate per-thread heaps with deep copying of messages.
3
  • Thanks for your help! I don't believe any of the updates require multiple actions to be executed atomically. I think this scheme doesn't need safe points because the mutator is notifying the collector, rather than the collector pausing things briefly to determine roots. I'm not sure I understand safe points though.
    – Taylor
    Jul 5, 2013 at 22:40
  • Right, I need a single global queue, which is somewhat unfortunate. In my app though, I only have two threads involved, so its not that bad.
    – Taylor
    Jul 5, 2013 at 22:42
  • The allocator (malloc) isn't lock free, but I'm careful to only allocate in the non-realtime thread and then pass the object to the DSP thread. If the GC can't keep up, then the queue has to allocate more space, which is a problem -- I just use a sufficiently large queue so that's unlikely.
    – Taylor
    Jul 5, 2013 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.