On 13 December 2005 13:11, Sebastian Sylvan wrote:
On 12/13/05, Tomasz Zielonka <tomasz.zielonka@gmail.com> wrote:
On Tue, Dec 13, 2005 at 01:32:46PM +0100, Sebastian Sylvan wrote:
Are there plans to include a mutable array for use in the STM monad, or a good reason for why this is not needed? Also, an unboxed version would be nice.
Why not use an (Array idx (TVar a)) ?
Ah.. Good thinking! This should work for in the STM monad for anything you would IOArray for in the IO monad, if you write proper instances for MArray of course...
It's a bit inefficient, an extra indirection (compared to a primitive implementation) but that shouldn't matter too much for the general case. And the TVars themselves introduces some extra overhead, I would suppose (which could be per-array rather than per-element, without losing the property that only writes to the same element causes retries). It gets even trickier if you want an unboxed mutable array in the STM monad.
But still, it's useful and I think a mutable array for the STM monad should be in the libraries. It could be implemented as an Array at first, and perhaps later switch to a more efficient representation.
In the past I have used arrays of TVars, as Thomasz suggested. It would indeed be better to have a primitive STM array, the only problem with this is the extra complexity. One simplifying assumption is that it should consider changes at the level of the whole array, rather than per-element (otherwise you'd use an array of TVars). Cheers, Simon
On Dec 13, 2005, at 8:46 AM, Simon Marlow wrote:
[In response to another plea for TArrays]
In the past I have used arrays of TVars, as Thomasz suggested. It would indeed be better to have a primitive STM array, the only problem with this is the extra complexity. One simplifying assumption is that it should consider changes at the level of the whole array, rather than per-element (otherwise you'd use an array of TVars).
Actually, in that case it might be more useful to have a TMVar containing an array. But I suspect the need for this use case is small. I know a ton of uses for transactionally-updated arrays for which the goal is to permit concurrent access to independent array elements (concurrent hash tables come to mind as an obvious use case where transactions make life vastly simpler). You might ask Tim Harris whether there's a reasonably simple, clever way to do this using arrays + CAS. I believe such a trick exists---you might end up waking too many threads on a write, but you'd get read/write concurrency at least. -Jan
Cheers, Simon _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Dec 13, 2005, at 8:46 AM, Simon Marlow wrote:
[In response to another plea for TArrays]
In the past I have used arrays of TVars, as Thomasz suggested. It would indeed be better to have a primitive STM array, the only problem with this is the extra complexity. One simplifying assumption is that it should consider changes at the level of the whole array, rather than per-element (otherwise you'd use an array of TVars).
Actually, in that case it might be more useful to have a TMVar containing an array. But I suspect the need for this use case is small. I know a ton of uses for transactionally-updated arrays for which the goal is to permit concurrent access to independent array elements (concurrent hash tables come to mind as an obvious use case where transactions make life vastly simpler). You might ask Tim Harris whether there's a reasonably simple, clever way to do this using arrays + CAS. I believe such a trick exists---you might end up waking too many threads on a write, but you'd get read/write concurrency at least. -Jan
Cheers, Simon _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On 12/13/05, Simon Marlow <simonmar@microsoft.com> wrote:
On 13 December 2005 13:11, Sebastian Sylvan wrote:
On 12/13/05, Tomasz Zielonka <tomasz.zielonka@gmail.com> wrote:
On Tue, Dec 13, 2005 at 01:32:46PM +0100, Sebastian Sylvan wrote:
Are there plans to include a mutable array for use in the STM monad, or a good reason for why this is not needed? Also, an unboxed version would be nice.
Why not use an (Array idx (TVar a)) ?
Ah.. Good thinking! This should work for in the STM monad for anything you would IOArray for in the IO monad, if you write proper instances for MArray of course...
It's a bit inefficient, an extra indirection (compared to a primitive implementation) but that shouldn't matter too much for the general case. And the TVars themselves introduces some extra overhead, I would suppose (which could be per-array rather than per-element, without losing the property that only writes to the same element causes retries). It gets even trickier if you want an unboxed mutable array in the STM monad.
But still, it's useful and I think a mutable array for the STM monad should be in the libraries. It could be implemented as an Array at first, and perhaps later switch to a more efficient representation.
In the past I have used arrays of TVars, as Thomasz suggested. It would indeed be better to have a primitive STM array, the only problem with this is the extra complexity. One simplifying assumption is that it should consider changes at the level of the whole array, rather than per-element (otherwise you'd use an array of TVars).
There is no plan to provide an implementation of this (the Array-of-TVar approach) in the libs? With an MArray instance? It would be nice if you could just plug i into existing functions operating on MArray... /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862
On 12/13/05, Sebastian Sylvan <sebastian.sylvan@gmail.com> wrote:
There is no plan to provide an implementation of this (the Array-of-TVar approach) in the libs? With an MArray instance? It would be nice if you could just plug i into existing functions operating on MArray...
I hacked this up, see if it works: {-# OPTIONS -fglasgow-exts #-} module Control.Concurrent.STM.TMArray ( TArray ) where import Control.Monad (replicateM) import Data.Array (Array) import Data.Array.Base (listArray, arrEleBottom, unsafeAt, MArray(..), HasBounds(..)) import Data.Ix (rangeSize) import Control.Concurrent.STM (STM, TVar, newTVar, readTVar, writeTVar) newtype TArray i e = TArray (Array i (TVar e)) instance MArray TArray e STM where newArray b e = do a <- replicateM (rangeSize b) (newTVar e) return $ TArray (listArray b a) newArray_ b = do a <- replicateM (rangeSize b) (newTVar arrEleBottom) return $ TArray (listArray b a) unsafeRead (TArray a) i = readTVar $ unsafeAt a i unsafeWrite (TArray a) i e = writeTVar (unsafeAt a i) e instance HasBounds TArray where bounds (TArray a) = bounds a -- Taral <taralx@gmail.com> "Computer science is no more about computers than astronomy is about telescopes." -- Edsger Dijkstra
participants (4)
-
Jan-Willem Maessen -
Sebastian Sylvan -
Simon Marlow -
Taral