Re: [Haskell-cafe] Traversing a graph in STM
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 [EMAIL PROTECTED] 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 smime.p7s Description: S/MIME cryptographic signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Traversing a graph in STM
On 9/19/06, Jan-Willem Maessen [EMAIL PROTECTED] 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 [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Traversing a graph in STM
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. If you're performing no side effects or accesses to TVars (which you aren't, as your graph representation requires reading TVars all over the place), you can in principle use the following horrid kludge: 1) keep a TVar indicating visited at each node. 2) within an atomic, perform your traversal in the usual sequential way, setting the TVar each time a node is visited. 3) when you're done, package up your desired result in an exception and throw it. All your marking work will be un-done and your result will emerge. 4) catch the exception outside the atomic and extract the result again. However, this will still preclude two simultaneous traversals of overlapping portions of the graph. Really, you're just asking the STM mechanism to maintain the hash table on your behalf; in practice you will be better off doing it yourself. Really, there's no such thing as a free lunch here, I'm afraid. If you want to concurrently traverse a graph, you need to keep separate cycle-avoidance state for each traversal. Using TVars doesn't change that basic algorithmic detail. And is there a better way of getting TVar identity than StableNames? Would that there were! -Jan-Willem Maessen - Einar Karttunen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe smime.p7s Description: S/MIME cryptographic signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Traversing a graph in STM
On 9/17/06, Jan-Willem Maessen [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Traversing a graph in STM
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. And the concurrent searches are isolated from each other? Or are you performing a single search using many threads? Is it possible to avoid passing around an explicit Set of visited nodes? And is there a better way of getting TVar identity than StableNames? - Einar Karttunen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Traversing a graph in STM
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
