Re: [Haskell-cafe] Traversing a graph in STM

On 9/19/06, Jan-Willem Maessen wrote:

On Sep 18, 2006, at 4:47 AM, Einar Karttunen wrote:

...

On 18.09 01:23, Josef Svenningsson wrote:

...

On 9/17/06, Jan-Willem Maessen wrote:

...

You can associate a unique name with each traversal, and store a set of traversals at each node (instead of a mark bit). But this set grows without bound unless you follow each traversal with a "cleaning traversal" which removes a traversal tag from the set. And you'd need some way to generate the unique names.

Well, if your set implementation used weak pointers there would be no need for a cleaning traversal. The garbage collector will take care of that. The only slightly tricky thing is to keep a live pointer to the unique traversal name during the entire of the traversal. But I don't think that should be a big problem.

This just amounts to saying "we can use the GC to implement the cleanup traversal on our behalf."

Indeed.

I'd be quite surprised if this were actually more efficient. It is a lot more efficient in the sense that the GC is already written. We don't have to implement a cleanup traversal ourselves.

But this is all a bit moot, as Einar observes:

...

This suffers from the problem that two traversals reading the same parts of the graph would have a good chance to make each other retry.

Any solution which stores traversal states in the nodes has this problem. Fundamentally you can't update the state of graph nodes in any way using STM and expect to run multiple traversals concurrently over the same subgraph.

Alas, yes. All the best, Josef