[Haskell-cafe] Traversing a graph in STM

[Josef Svenningsson]

On 9/19/06, Jan-Willem Maessen <jmaessen at alum.mit.edu> 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 <jmaessen at alum.mit.edu> 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