On 13.09 08:48, Chris Kuklewicz wrote:

And the concurrent searches are isolated from each other? Or are you performing a single search using many threads?

Isolated from each other. Mainly dreaming of the per-transaction variables attached to the nodes :-) - Einar Karttunen

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

On Sep 13, 2006, at 3:37 AM, Einar Karttunen wrote:

...

Hello

Is there an elegant way of traversing a directed graph in STM?

type Node nt et = TVar (NodeT nt et) type Edge et = TVar et data NodeT nt et = NodeT nt [(Node nt et, Edge et)]

type MyGraph = Node String Int

When implementing a simple depth first search we need a way to mark nodes (= TVars) as visited. In addition multiple concurrent searches should be possible.

Is it possible to avoid passing around an explicit Set of visited nodes?

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. Cheers, Josef

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." I'd be quite surprised if this were actually more efficient. 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.

I am thinking of going the StableName route. But as this happens inside STM Data.HashTable does not help much (without using unsafeIOToSTM and dealing with retries).

I'd like to make an STM version of Data.HashTable, but it requires implementing some sort of STMArray, or using an array of TVars and slowing the hashtable implementation to a crawl. Without access to the internals of STM, implementing some form of STMArray turns out to be awfully difficult (I understand the implementation techniques, but the ones I understand involve adding frobs to the STM implementation itself or degenerating to maps). This would also address the lack of a concurrent hash table (the other alternatives for which are to run into a similar set of shortcomings for IOArrays or STArrays, where I'd want to have a CAS operation or some sort of compact array of MVars). I'm always a little conflicted about making StableNames for keys into a hash table. Internally GHC creates a giant invisible hash table of StableNames, just so we can look things up in it and then use the result to insert stuff into our user-visible hashtable.

If StableNames were in Ord using Set (StableName T) would be nice. But in the current implementation one has to resort to IntSet Int [StableName T] which is not pretty at all.

I agree. I wish StableNames were ordered. -Jan-Willem Maessen [PS - Does the StableName-internal hash table use the same hash function as the old Data.HashTable did? The comments in Data.HashTable suggested it might. If so, it might be a good idea to switch to something like the multiplicative hash function in my Data.HashTable code; this gets much of the benefit of switching hash table implementations at pretty low cost. It's not the best hash by a long stretch, but it's much better than what was there.]

- Einar Karttunen

On 9/19/06, Bulat Ziganshin wrote:

Hello Jan-Willem,

Tuesday, September 19, 2006, 5:47:15 PM, you wrote:

...

I'd like to make an STM version of Data.HashTable, but it requires implementing some sort of STMArray, or using an array of TVars and

are we not have TArray already?

The current TArray is implemented as an array of TVars IIRC. There was some discussion about possibly using a more efficient implementation in the future, but AFAIK it hasn't been done yet. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862