Combining ST with STM

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Combining ST with STM

Thomas Koster
Hi friends,

I have an STM transaction that needs some private, temporary state.
The most obvious way is to simply pass pure state as arguments, but
for efficiency, I would like this state to be some kind of mutable
array, like STArray.

I know, STM has TVars and TArray, but since this state is private to
the transaction, I am wondering if using TVars/TArrays for private
state might be overkill that will unnecessarily slow down the STM
commit process. The private state is, by definition, not shared, so
including it in the STM log and commit process is, as far as I can
tell, pointless.

ST and STArray still appear to be the most appropriate tools for the
private state, because STRefs and STArrays really, really are private.

So this basically means I want to interleave ST and STM in a "safe"
way. That is, if the STM transaction retries, I want the ST state to
be vaporised as well.

Ideally, I would love to be able to say something like this:

-- | Copy the value from the shared TVar into the private STRef.
load :: TVar a -> STRef a -> STSTM s ()
load shared private = do
  value <- liftSTM (readTVar shared)
  liftST (writeSTRef private value)

Naturally, that STRef must originate from a call to newSTRef earlier
in the same transaction and is private to it, just like the real ST
monad. As far as I can tell, I am not trying to weaken either ST or
STM in any way here.

I found the STMonadTrans package on Hackage [1] that claims to
implement ST as a monad transformer, STT, which sounds close to what I
want. While its documentation does not mention STM, it does say that
some monads are unsafe to use as a base monad for STT.

Is STMonadTrans safe to use with STM?

[1] https://hackage.haskell.org/package/STMonadTrans

Thanks,
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Ryan Yates
I also have found need for what I think you are describing but only in the context of transactional arrays where there are multiple fields to initialize while I know that the array is private to the creating thread.  For now I'm adding the primitives I need as I go, but I would like to have better safer story.  You might be interested in how the stm-containers package uses ST to build internal nodes in transactions [1], [2].


Ryan

On Mon, Feb 8, 2016 at 10:43 PM, Thomas Koster <[hidden email]> wrote:
Hi friends,

I have an STM transaction that needs some private, temporary state.
The most obvious way is to simply pass pure state as arguments, but
for efficiency, I would like this state to be some kind of mutable
array, like STArray.

I know, STM has TVars and TArray, but since this state is private to
the transaction, I am wondering if using TVars/TArrays for private
state might be overkill that will unnecessarily slow down the STM
commit process. The private state is, by definition, not shared, so
including it in the STM log and commit process is, as far as I can
tell, pointless.

ST and STArray still appear to be the most appropriate tools for the
private state, because STRefs and STArrays really, really are private.

So this basically means I want to interleave ST and STM in a "safe"
way. That is, if the STM transaction retries, I want the ST state to
be vaporised as well.

Ideally, I would love to be able to say something like this:

-- | Copy the value from the shared TVar into the private STRef.
load :: TVar a -> STRef a -> STSTM s ()
load shared private = do
  value <- liftSTM (readTVar shared)
  liftST (writeSTRef private value)

Naturally, that STRef must originate from a call to newSTRef earlier
in the same transaction and is private to it, just like the real ST
monad. As far as I can tell, I am not trying to weaken either ST or
STM in any way here.

I found the STMonadTrans package on Hackage [1] that claims to
implement ST as a monad transformer, STT, which sounds close to what I
want. While its documentation does not mention STM, it does say that
some monads are unsafe to use as a base monad for STT.

Is STMonadTrans safe to use with STM?

[1] https://hackage.haskell.org/package/STMonadTrans

Thanks,
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Thomas Koster
On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:

> I have an STM transaction that needs some private, temporary state.
> The most obvious way is to simply pass pure state as arguments, but
> for efficiency, I would like this state to be some kind of mutable
> array, like STArray.
>
> I know, STM has TVars and TArray, but since this state is private to
> the transaction, I am wondering if using TVars/TArrays for private
> state might be overkill that will unnecessarily slow down the STM
> commit process. The private state is, by definition, not shared, so
> including it in the STM log and commit process is, as far as I can
> tell, pointless.
>
> ST and STArray still appear to be the most appropriate tools for the
> private state, because STRefs and STArrays really, really are private.
>
> So this basically means I want to interleave ST and STM in a "safe"
> way. That is, if the STM transaction retries, I want the ST state to
> be vaporised as well.
>
> Ideally, I would love to be able to say something like this:
>
> -- | Copy the value from the shared TVar into the private STRef.
> load :: TVar a -> STRef a -> STSTM s ()
> load shared private = do
>   value <- liftSTM (readTVar shared)
>   liftST (writeSTRef private value)
>
> Naturally, that STRef must originate from a call to newSTRef earlier
> in the same transaction and is private to it, just like the real ST
> monad. As far as I can tell, I am not trying to weaken either ST or
> STM in any way here.
>
> I found the STMonadTrans package on Hackage [1] that claims to
> implement ST as a monad transformer, STT, which sounds close to what I
> want. While its documentation does not mention STM, it does say that
> some monads are unsafe to use as a base monad for STT.
>
> Is STMonadTrans safe to use with STM?
>
> [1] https://hackage.haskell.org/package/STMonadTrans

On 9 February 2016 at 15:16, Ryan Yates <[hidden email]> wrote:

> I also have found need for what I think you are describing but only in the
> context of transactional arrays where there are multiple fields to
> initialize while I know that the array is private to the creating thread.
> For now I'm adding the primitives I need as I go, but I would like to have
> better safer story.  You might be interested in how the stm-containers
> package uses ST to build internal nodes in transactions [1], [2].
>
> [1]:
> https://github.com/nikita-volkov/stm-containers/blob/master/library/STMContainers/HAMT/Nodes.hs#L36
> [2]:
> https://github.com/nikita-volkov/stm-containers/blob/master/library/STMContainers/WordArray.hs#L118

Thank you Ryan.

Indeed, it is by experimenting with stm-containers that the need for
mixing ST and STM arose. Where the previous iteration of my program
used plain ST transactions serialized with an MVar, I am experimenting
with stm-containers with the hope that I will see improved throughput
for transactions that do not overlap, which, I believe, could complete
in parallel, at least some of the time.

It seems stm-containers itself uses unsafeFreezeArray from the
"primitive" package. One difference though is that while my private
array would be thawed, modified and refrozen regularly, the
stm-containers WordArray stays immutable (not thawed) once frozen, as
far as I can tell.

Since I am using only a single array for the entire private state,
sprinkling some runST calls with unsafeThawArray/unsafeFreezeArray in
my STM transaction may be enough for my needs, as long as I am
exceptionally careful not to leak one of these arrays into or out of
any STM transaction demarcated by the "atomically" block. If anybody
knows of any reason why I should abort this idea, please speak up.

I noticed also that Data.Array.Unsafe in base also has unsafe freezing
and thawing. Is there a reason to use one over the other?

--
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Jonas Scholl
On 02/09/2016 07:20 AM, Thomas Koster wrote:
> On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:
>> I have an STM transaction that needs some private, temporary state.
>> The most obvious way is to simply pass pure state as arguments, but
>> for efficiency, I would like this state to be some kind of mutable
>> array, like STArray.

This sounds like optimizing before you know what is really slow,
complicating your code for no good reason...

>>
>> I know, STM has TVars and TArray, but since this state is private to
>> the transaction, I am wondering if using TVars/TArrays for private
>> state might be overkill that will unnecessarily slow down the STM
>> commit process. The private state is, by definition, not shared, so
>> including it in the STM log and commit process is, as far as I can
>> tell, pointless.

The STM log allows you to revert a failed transaction. If you do not
record your writes to an array, you can not revert them and they can
leak outside an aborted transaction.

>>
>> ST and STArray still appear to be the most appropriate tools for the
>> private state, because STRefs and STArrays really, really are private.
>>
>> So this basically means I want to interleave ST and STM in a "safe"
>> way. That is, if the STM transaction retries, I want the ST state to
>> be vaporised as well.

So how should this work? Some log recording what you did would be good,
so the runtime knows which changes you did to the array... If you
however create the array in the same transaction, this would work by
just throwing away the whole array.

>>
>> Ideally, I would love to be able to say something like this:
>>
>> -- | Copy the value from the shared TVar into the private STRef.
>> load :: TVar a -> STRef a -> STSTM s ()
>> load shared private = do
>>   value <- liftSTM (readTVar shared)
>>   liftST (writeSTRef private value)
>>
>> Naturally, that STRef must originate from a call to newSTRef earlier
>> in the same transaction and is private to it, just like the real ST
>> monad. As far as I can tell, I am not trying to weaken either ST or
>> STM in any way here.
>>
>> I found the STMonadTrans package on Hackage [1] that claims to
>> implement ST as a monad transformer, STT, which sounds close to what I
>> want. While its documentation does not mention STM, it does say that
>> some monads are unsafe to use as a base monad for STT.
>>
>> Is STMonadTrans safe to use with STM?
It is not even safe to use with Maybe (for now), as it can share
different STRefs and STArrays. I filed a bug report. After the bug is
fixed, I see no reason, why it should not work with STM, as the complete
ST action should be repeated if the STM transaction aborts.

>>
>> [1] https://hackage.haskell.org/package/STMonadTrans
>
> On 9 February 2016 at 15:16, Ryan Yates <[hidden email]> wrote:
>> I also have found need for what I think you are describing but only in the
>> context of transactional arrays where there are multiple fields to
>> initialize while I know that the array is private to the creating thread.
>> For now I'm adding the primitives I need as I go, but I would like to have
>> better safer story.  You might be interested in how the stm-containers
>> package uses ST to build internal nodes in transactions [1], [2].
>>
>> [1]:
>> https://github.com/nikita-volkov/stm-containers/blob/master/library/STMContainers/HAMT/Nodes.hs#L36
>> [2]:
>> https://github.com/nikita-volkov/stm-containers/blob/master/library/STMContainers/WordArray.hs#L118
>
> Thank you Ryan.
>
> Indeed, it is by experimenting with stm-containers that the need for
> mixing ST and STM arose. Where the previous iteration of my program
> used plain ST transactions serialized with an MVar, I am experimenting
> with stm-containers with the hope that I will see improved throughput
> for transactions that do not overlap, which, I believe, could complete
> in parallel, at least some of the time.
>
> It seems stm-containers itself uses unsafeFreezeArray from the
> "primitive" package. One difference though is that while my private
> array would be thawed, modified and refrozen regularly, the
> stm-containers WordArray stays immutable (not thawed) once frozen, as
> far as I can tell.
So what happens if you thaw an array, write to it and then abort the
transaction? You have to revert the writes because they could be visible
to the transaction you just aborted. When this transaction restarts, the
array will still contain the values written prior to it. Even if nothing
else contains a reference to it, your array is garbage after you aborted
a transaction only once.

>
> Since I am using only a single array for the entire private state,
> sprinkling some runST calls with unsafeThawArray/unsafeFreezeArray in
> my STM transaction may be enough for my needs, as long as I am
> exceptionally careful not to leak one of these arrays into or out of
> any STM transaction demarcated by the "atomically" block. If anybody
> knows of any reason why I should abort this idea, please speak up.

Keep in mind that ST is only "safe IO" in a sense such that no side
effects are visible to the outside. You lose this if you start to modify
anything which you did not create yourself. I think this is not that
different from using
http://hackage.haskell.org/package/base-4.8.2.0/docs/GHC-Conc-Sync.html#v:unsafeIOToSTM.
To be safe, you should at least copy the arrays instead of unsafely
thawing them... but then it could be faster just to use TArrays from the
start.

>
> I noticed also that Data.Array.Unsafe in base also has unsafe freezing
> and thawing. Is there a reason to use one over the other?
>
> --
> Thomas Koster
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

signature.asc (484 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Alberto G. Corona
Why not use the state monad transformer?


atomically $   evalStateT  todo initialState

Seems Ok to me

evalStateT :: Monad m => StateT s m a -> s -> m a

in this case:

evalStateT :: StateT MyState STM a -> MyState -> STM a

2016-02-09 9:36 GMT+01:00 Jonas Scholl <[hidden email]>:
On 02/09/2016 07:20 AM, Thomas Koster wrote:
> On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:
>> I have an STM transaction that needs some private, temporary state.
>> The most obvious way is to simply pass pure state as arguments, but
>> for efficiency, I would like this state to be some kind of mutable
>> array, like STArray.

This sounds like optimizing before you know what is really slow,
complicating your code for no good reason...

>>
>> I know, STM has TVars and TArray, but since this state is private to
>> the transaction, I am wondering if using TVars/TArrays for private
>> state might be overkill that will unnecessarily slow down the STM
>> commit process. The private state is, by definition, not shared, so
>> including it in the STM log and commit process is, as far as I can
>> tell, pointless.

The STM log allows you to revert a failed transaction. If you do not
record your writes to an array, you can not revert them and they can
leak outside an aborted transaction.

>>
>> ST and STArray still appear to be the most appropriate tools for the
>> private state, because STRefs and STArrays really, really are private.
>>
>> So this basically means I want to interleave ST and STM in a "safe"
>> way. That is, if the STM transaction retries, I want the ST state to
>> be vaporised as well.

So how should this work? Some log recording what you did would be good,
so the runtime knows which changes you did to the array... If you
however create the array in the same transaction, this would work by
just throwing away the whole array.

>>
>> Ideally, I would love to be able to say something like this:
>>
>> -- | Copy the value from the shared TVar into the private STRef.
>> load :: TVar a -> STRef a -> STSTM s ()
>> load shared private = do
>>   value <- liftSTM (readTVar shared)
>>   liftST (writeSTRef private value)
>>
>> Naturally, that STRef must originate from a call to newSTRef earlier
>> in the same transaction and is private to it, just like the real ST
>> monad. As far as I can tell, I am not trying to weaken either ST or
>> STM in any way here.
>>
>> I found the STMonadTrans package on Hackage [1] that claims to
>> implement ST as a monad transformer, STT, which sounds close to what I
>> want. While its documentation does not mention STM, it does say that
>> some monads are unsafe to use as a base monad for STT.
>>
>> Is STMonadTrans safe to use with STM?

It is not even safe to use with Maybe (for now), as it can share
different STRefs and STArrays. I filed a bug report. After the bug is
fixed, I see no reason, why it should not work with STM, as the complete
ST action should be repeated if the STM transaction aborts.

>>
>> [1] https://hackage.haskell.org/package/STMonadTrans
>
> On 9 February 2016 at 15:16, Ryan Yates <[hidden email]> wrote:
>> I also have found need for what I think you are describing but only in the
>> context of transactional arrays where there are multiple fields to
>> initialize while I know that the array is private to the creating thread.
>> For now I'm adding the primitives I need as I go, but I would like to have
>> better safer story.  You might be interested in how the stm-containers
>> package uses ST to build internal nodes in transactions [1], [2].
>>
>> [1]:
>> https://github.com/nikita-volkov/stm-containers/blob/master/library/STMContainers/HAMT/Nodes.hs#L36
>> [2]:
>> https://github.com/nikita-volkov/stm-containers/blob/master/library/STMContainers/WordArray.hs#L118
>
> Thank you Ryan.
>
> Indeed, it is by experimenting with stm-containers that the need for
> mixing ST and STM arose. Where the previous iteration of my program
> used plain ST transactions serialized with an MVar, I am experimenting
> with stm-containers with the hope that I will see improved throughput
> for transactions that do not overlap, which, I believe, could complete
> in parallel, at least some of the time.
>
> It seems stm-containers itself uses unsafeFreezeArray from the
> "primitive" package. One difference though is that while my private
> array would be thawed, modified and refrozen regularly, the
> stm-containers WordArray stays immutable (not thawed) once frozen, as
> far as I can tell.

So what happens if you thaw an array, write to it and then abort the
transaction? You have to revert the writes because they could be visible
to the transaction you just aborted. When this transaction restarts, the
array will still contain the values written prior to it. Even if nothing
else contains a reference to it, your array is garbage after you aborted
a transaction only once.

>
> Since I am using only a single array for the entire private state,
> sprinkling some runST calls with unsafeThawArray/unsafeFreezeArray in
> my STM transaction may be enough for my needs, as long as I am
> exceptionally careful not to leak one of these arrays into or out of
> any STM transaction demarcated by the "atomically" block. If anybody
> knows of any reason why I should abort this idea, please speak up.

Keep in mind that ST is only "safe IO" in a sense such that no side
effects are visible to the outside. You lose this if you start to modify
anything which you did not create yourself. I think this is not that
different from using
http://hackage.haskell.org/package/base-4.8.2.0/docs/GHC-Conc-Sync.html#v:unsafeIOToSTM.
To be safe, you should at least copy the arrays instead of unsafely
thawing them... but then it could be faster just to use TArrays from the
start.

>
> I noticed also that Data.Array.Unsafe in base also has unsafe freezing
> and thawing. Is there a reason to use one over the other?
>
> --
> Thomas Koster
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe




--
Alberto.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Thomas Koster
In reply to this post by Jonas Scholl
Jonas,

On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:
> I have an STM transaction that needs some private, temporary state.
> The most obvious way is to simply pass pure state as arguments, but
> for efficiency, I would like this state to be some kind of mutable
> array, like STArray.

On 9 February 2016 at 19:36, Jonas Scholl <[hidden email]> wrote:
> This sounds like optimizing before you know what is really slow,
> complicating your code for no good reason...

From my wording it sounded like I was "only thinking about it". This is
not actually the case, sorry. Very early versions of my program did use
a plain, immutable array (Vector actually), but now it uses STArray. The
benefits to my program of ST are significant and proven by benchmarks.
Switching to ST did not significantly complicate the program.

By going back to immutable arrays and all that excessive copying and GC,
I could easily wipe out the small benefits of any extra parallelism I
might squeeze out of STM. If it turns out that what I want is
impossible, I will keep ST, drop STM, and say that my program is single-
threaded.

What *is* unknown is the cost of replacing the STArrays with TArrays as
proposed below.

On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:
> I know, STM has TVars and TArray, but since this state is private to
> the transaction, I am wondering if using TVars/TArrays for private
> state might be overkill that will unnecessarily slow down the STM
> commit process. The private state is, by definition, not shared, so
> including it in the STM log and commit process is, as far as I can
> tell, pointless.

On 9 February 2016 at 19:36, Jonas Scholl <[hidden email]> wrote:
> The STM log allows you to revert a failed transaction. If you do not
> record your writes to an array, you can not revert them and they can
> leak outside an aborted transaction.

The array is not shared between transactions or threads; it is local to
the transaction and is not referenced outside the transaction that
created it. Sorry if this was not clear. Like ST state, it is created
inside the transaction, invisible outside the transaction, and discarded
whenever the transaction commits or retries. There is no need to revert
it, ever. The closest thing to reverting it is to have the GC reclaim
it.

On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:
> ST and STArray still appear to be the most appropriate tools for the
> private state, because STRefs and STArrays really, really are private.
>
> So this basically means I want to interleave ST and STM in a "safe"
> way. That is, if the STM transaction retries, I want the ST state to
> be vaporised as well.

On 9 February 2016 at 19:36, Jonas Scholl <[hidden email]> wrote:
> So how should this work? Some log recording what you did would be good,
> so the runtime knows which changes you did to the array... If you
> however create the array in the same transaction, this would work by
> just throwing away the whole array.

The array is indeed created in same transaction, for that transaction.
Throwing away the whole array is exactly what *must* occur, just as it
does with ordinary ST. Otherwise, as you say, the invariants of STM are
violated.

On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:

> Ideally, I would love to be able to say something like this:
>
> -- | Copy the value from the shared TVar into the private STRef.
> load :: TVar a -> STRef a -> STSTM s ()
> load shared private = do
>   value <- liftSTM (readTVar shared)
>   liftST (writeSTRef private value)
>
> Naturally, that STRef must originate from a call to newSTRef earlier
> in the same transaction and is private to it, just like the real ST
> monad. As far as I can tell, I am not trying to weaken either ST or
> STM in any way here.

Please forgive the typo in the type signature of "load", which should
have been:

load :: TVar a -> STRef s a -> STSTM s ()

I will elaborate on this imagined STSTM monad in a separate reply,
shortly.

> I found the STMonadTrans package on Hackage [1] that claims to
> implement ST as a monad transformer, STT, which sounds close to what I
> want. While its documentation does not mention STM, it does say that
> some monads are unsafe to use as a base monad for STT.
>
> Is STMonadTrans safe to use with STM?

On 9 February 2016 at 19:36, Jonas Scholl <[hidden email]> wrote:
> It is not even safe to use with Maybe (for now), as it can share
> different STRefs and STArrays. I filed a bug report. After the bug is
> fixed, I see no reason, why it should not work with STM, as the complete
> ST action should be repeated if the STM transaction aborts.

I see. Thank you for evaluating STMonadTrans. I will propose an
implementation of the STSTM monad I mentioned above in a separate reply,
and would be very grateful if you could evaluate the Core of that one
too.

On 9 February 2016 at 17:20, Thomas Koster <[hidden email]> wrote:

> It seems stm-containers itself uses unsafeFreezeArray from the
> "primitive" package. One difference though is that while my private
> array would be thawed, modified and refrozen regularly, the
> stm-containers WordArray stays immutable (not thawed) once frozen, as
> far as I can tell.
>
> Since I am using only a single array for the entire private state,
> sprinkling some runST calls with unsafeThawArray/unsafeFreezeArray in
> my STM transaction may be enough for my needs, as long as I am
> exceptionally careful not to leak one of these arrays into or out of
> any STM transaction demarcated by the "atomically" block. If anybody
> knows of any reason why I should abort this idea, please speak up.

On 9 February 2016 at 19:36, Jonas Scholl <[hidden email]> wrote:

> So what happens if you thaw an array, write to it and then abort the
> transaction? You have to revert the writes because they could be visible
> to the transaction you just aborted. When this transaction restarts, the
> array will still contain the values written prior to it. Even if nothing
> else contains a reference to it, your array is garbage after you aborted
> a transaction only once.
>
> Keep in mind that ST is only "safe IO" in a sense such that no side
> effects are visible to the outside. You lose this if you start to modify
> anything which you did not create yourself. I think this is not that
> different from using
> http://hackage.haskell.org/package/base-4.8.2.0/docs/GHC-Conc-Sync.html#v:unsafeIOToSTM.
> To be safe, you should at least copy the arrays instead of unsafely
> thawing them... but then it could be faster just to use TArrays from the
> start.

No argument there, but as before, no revert is necessary because there
are no references to the array outside of the STM transaction that
created it (by abstinence, I concede, not by a ruling from the type
checker as with ST). Having it collected immediately after a retry or
commit is exactly what I want. The sooner the better!

--
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Thomas Koster
In reply to this post by Jonas Scholl
On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:

> I have an STM transaction that needs some private, temporary state.
> The most obvious way is to simply pass pure state as arguments, but
> for efficiency, I would like this state to be some kind of mutable
> array, like STArray.
>
> The private state is, by definition, not shared, so
> including it in the STM log and commit process is, as far as I can
> tell, pointless.
>
> ST and STArray still appear to be the most appropriate tools for the
> private state, because STRefs and STArrays really, really are private.
>
> So this basically means I want to interleave ST and STM in a "safe"
> way. That is, if the STM transaction retries, I want the ST state to
> be vaporised as well.
>
> Ideally, I would love to be able to say something like this:
>
> -- | Copy the value from the shared TVar into the private STRef.
> load :: TVar a -> STRef a -> STSTM s ()
> load shared private = do
>   value <- liftSTM (readTVar shared)
>   liftST (writeSTRef private value)
>
> Naturally, that STRef must originate from a call to newSTRef earlier
> in the same transaction and is private to it, just like the real ST
> monad. As far as I can tell, I am not trying to weaken either ST or
> STM in any way here.

Please forgive the typo in the type signature of "load", which should
have been:

load :: TVar a -> STRef s a -> STSTM s ()

Let me elaborate on STSTM, a monad I made up for this example that
combines the characteristics of ST and STM in the way that I want.
If my requirements were unclear from my prose, perhaps the code below
will illuminate them better.

An STSTM transaction is intended to be an STM transaction imbued with a
state token that encapsulates additional, transaction-local state in the
spirit of ST.

It is not intended to secretly perform IO inside STM, a la
GHC.Conc.unsafeIOToSTM.

It is not intended to facilitate the leaking of state into or out of an
STM transaction through STRefs, nor to communicate state between
successive retries of an STM transaction.

Thanks to hints from Ryan and Jonas, I made an attempt at implementing
it myself.

Below is my implementation of STSTM and associated operations. You will
need to link with the "primitive" and "stm" packages. I used versions
0.6 and 2.4.4, resp., and GHC 7.10.2.


{-# LANGUAGE GeneralizedNewtypeDeriving, Rank2Types #-}

module Control.Monad.STSTM
  (
    STSTM,
    liftST,
    liftSTM,
    atomicallyRunST,
    module Control.Monad.STM
  )
where

import Control.Monad.Primitive
import Control.Monad.ST
import Control.Monad.STM

-- | A computation of type @STSTM s a@ is an 'STM' computation that
-- also transforms a transaction-local internal state indexed by @s@, as
-- in the 'ST' monad, and returns a value of type @a@.
newtype STSTM s a = STSTM { unSTSTM :: STM a }
  deriving (Functor, Applicative, Monad)

-- | Lift an 'ST' computation into the 'STSTM' transaction.
liftST :: ST s a -> STSTM s a
{-# INLINE liftST #-}
liftST x = STSTM $
  let y = unsafeInlineST x
  in  y `seq` return y

-- | Lift an 'STM' computation into the 'STSTM' transaction.
liftSTM :: STM a -> STSTM s a
{-# INLINE liftSTM #-}
liftSTM = STSTM

-- | Perform a series of 'STSTM' actions atomically.
--
-- The 'ST' state is discarded when the 'STM' transaction commits or
-- retries.
atomicallyRunST :: (forall s. STSTM s a) -> IO a
{-# INLINE atomicallyRunST #-}
atomicallyRunST x = atomically (unSTSTM x)


Some commentary follows:

Some initial sanity testing with the GHC threaded runtime shows that it
does what I want, but I am not familiar enough with Core or the RTS to
predict whether or not it will launch nuclear missiles at the next
transit of Venus. I would be grateful for any feedback.

The use of rank-2 polymorphism in the type of atomicallyRunST is
intended to encapsulate the ST state exactly like it does for runST,
and that the ST state cannot leak into or out of the transaction.

STSTM is not a monad transformer (visibly or internally). I hope that
any potential problems that might afflict the STMonadTrans package are
irrelevant here.

I use seq in liftST to force the unsafe inline ST computation to occur
before bind proceeds to the next computation. Without seq, ST
computations returning () (or anything else that is not evaluated)
appear to stay as thunks and never transform any state. I suspect this
may cause problems with bottoms, but I am not sure if that is any
different from real ST/runST.

--
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Thomas Koster
In reply to this post by Alberto G. Corona
Alberto,

On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:
> I have an STM transaction that needs some private, temporary state.
> The most obvious way is to simply pass pure state as arguments, but
> for efficiency, I would like this state to be some kind of mutable
> array, like STArray.

On 9 February 2016 at 22:29, Alberto G. Corona <[hidden email]> wrote:

> Why not use the state monad transformer?
>
> http://hackage.haskell.org/package/transformers-0.5.1.0/docs/Control-Monad-Trans-State-Lazy.html#t:StateT
>
> atomically $   evalStateT  todo initialState
>
> Seems Ok to me
>
> evalStateT :: Monad m => StateT s m a -> s -> m a
>
> in this case:
>
> evalStateT :: StateT MyState STM a -> MyState -> STM a

Thank you for your suggestion.

Certainly, if the state was an immutable value, small or otherwise
cheaply modified, like a finger tree spine, StateT would be a much
cleaner alternative. But unfortunately it is the mutability of the
STArray that makes it valuable to my application.

"StateT (Vector Value) STM" would not help me much as the state would
need to be copied every time it was modified. In fact, I used a
variation of this in a very early version of my program, except that
the Vector was passed even more simply: as an argument, the way
ReaderT does, with no actual transformer in sight. Switching over to
ST and passing an STArray instead has improved the throughput of my
program greatly (far more than I expect to see from any extra
parallelism I might gain from using STM).

--
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Jonas Scholl
In reply to this post by Thomas Koster
On 02/09/2016 01:46 PM, Thomas Koster wrote:

> On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:
>> I have an STM transaction that needs some private, temporary state.
>> The most obvious way is to simply pass pure state as arguments, but
>> for efficiency, I would like this state to be some kind of mutable
>> array, like STArray.
>>
>> The private state is, by definition, not shared, so
>> including it in the STM log and commit process is, as far as I can
>> tell, pointless.
>>
>> ST and STArray still appear to be the most appropriate tools for the
>> private state, because STRefs and STArrays really, really are private.
>>
>> So this basically means I want to interleave ST and STM in a "safe"
>> way. That is, if the STM transaction retries, I want the ST state to
>> be vaporised as well.
>>
>> Ideally, I would love to be able to say something like this:
>>
>> -- | Copy the value from the shared TVar into the private STRef.
>> load :: TVar a -> STRef a -> STSTM s ()
>> load shared private = do
>>   value <- liftSTM (readTVar shared)
>>   liftST (writeSTRef private value)
>>
>> Naturally, that STRef must originate from a call to newSTRef earlier
>> in the same transaction and is private to it, just like the real ST
>> monad. As far as I can tell, I am not trying to weaken either ST or
>> STM in any way here.
>
> Please forgive the typo in the type signature of "load", which should
> have been:
>
> load :: TVar a -> STRef s a -> STSTM s ()
>
> Let me elaborate on STSTM, a monad I made up for this example that
> combines the characteristics of ST and STM in the way that I want.
> If my requirements were unclear from my prose, perhaps the code below
> will illuminate them better.
>
> An STSTM transaction is intended to be an STM transaction imbued with a
> state token that encapsulates additional, transaction-local state in the
> spirit of ST.
>
> It is not intended to secretly perform IO inside STM, a la
> GHC.Conc.unsafeIOToSTM.
>
> It is not intended to facilitate the leaking of state into or out of an
> STM transaction through STRefs, nor to communicate state between
> successive retries of an STM transaction.
I understand that, you just said, you wanted to sprinkle some runST
calls with unsafeThawArray and unsafeFreezeArray into your STM code. So
I assumed you wanted to share an (ST)Array between these STM actions.

>
> Thanks to hints from Ryan and Jonas, I made an attempt at implementing
> it myself.
>
> Below is my implementation of STSTM and associated operations. You will
> need to link with the "primitive" and "stm" packages. I used versions
> 0.6 and 2.4.4, resp., and GHC 7.10.2.
>
>
> {-# LANGUAGE GeneralizedNewtypeDeriving, Rank2Types #-}
>
> module Control.Monad.STSTM
>   (
>     STSTM,
>     liftST,
>     liftSTM,
>     atomicallyRunST,
>     module Control.Monad.STM
>   )
> where
>
> import Control.Monad.Primitive
> import Control.Monad.ST
> import Control.Monad.STM
>
> -- | A computation of type @STSTM s a@ is an 'STM' computation that
> -- also transforms a transaction-local internal state indexed by @s@, as
> -- in the 'ST' monad, and returns a value of type @a@.
> newtype STSTM s a = STSTM { unSTSTM :: STM a }
>   deriving (Functor, Applicative, Monad)
>
> -- | Lift an 'ST' computation into the 'STSTM' transaction.
> liftST :: ST s a -> STSTM s a
> {-# INLINE liftST #-}
> liftST x = STSTM $
>   let y = unsafeInlineST x
>   in  y `seq` return y
This is highly unsafe and will not do what you think it does!
unsafeInlineST provides an ST action with a realWorld# token out of thin
air and thus can float outside liftST, especially because you inline it.
This produces exactly the bug I reported against STMonadTrans.

A safe version could take the state token from the STM action, pass it
into the ST action and carry on with the returned state token (look at
GHC.Conc.Sync). Or convert the ST action to IO and then just run the IO
action in STM. This should be fine if you do not use unsafeThaw - any
garbage written to some STRef/STArray will be thrown away after the
runtime sees the STM action will fail and restarts it.

>
> -- | Lift an 'STM' computation into the 'STSTM' transaction.
> liftSTM :: STM a -> STSTM s a
> {-# INLINE liftSTM #-}
> liftSTM = STSTM
>
> -- | Perform a series of 'STSTM' actions atomically.
> --
> -- The 'ST' state is discarded when the 'STM' transaction commits or
> -- retries.
> atomicallyRunST :: (forall s. STSTM s a) -> IO a
> {-# INLINE atomicallyRunST #-}
> atomicallyRunST x = atomically (unSTSTM x)
>
>
> Some commentary follows:
>
> Some initial sanity testing with the GHC threaded runtime shows that it
> does what I want, but I am not familiar enough with Core or the RTS to
> predict whether or not it will launch nuclear missiles at the next
> transit of Venus. I would be grateful for any feedback.
>
> The use of rank-2 polymorphism in the type of atomicallyRunST is
> intended to encapsulate the ST state exactly like it does for runST,
> and that the ST state cannot leak into or out of the transaction.
What you still can not use is unsafeThaw. Consider this:

foo :: Array Int Val -> TVar Int -> IO someResult
foo arr var = atomicallyRunST $ do
    marr <- liftST $ unsafeThaw arr
    val <- liftSTM $ readTVar var
    liftST $ writeArray marr val someOtherVal
    ... do something more...

What happens if the transaction is restarted after the write? You've
written into arr (unsafeThaw did not copy it), but have no log to revert
the write. Now you see a different immutable array. This is bad.

So you can not use unsafeThaw. Even if only one transaction gets a hold
on this array and it would be safe to use unsafeThaw with plain ST (as
this can not retry), because the transaction has to depend on other
TVars etc, otherwise there would be no need for STM.

And now I am wondering what happens if a thread evaluates something like
runST ... unsafeThawArray ... unsafeFreezeArray ... and is hit by an
asynchronous exception... The computation is restated the next time the
thunk is demanded, but this could have already changed the array, right?
So can runST ... unsafeThawArray ... be used in a safe way or is this
combination inherently broken?

Anyway, I think the following holds true:
 - using STRefs: These must have been created in the transaction, so it
works.
 - using STArrays: unsafeThawing an incoming Array will break
referential transparency sooner or later. Thawing (and thus copying) the
incoming array or creating a fresh one should work.
 - using TArrays: You can return these from the STM action and start
another one later with them without breaking referential transparency as
always. If you have to modify incoming arguments, even if only one STM
action has a reference to them at a time, these can be faster as you do
not have to copy everything - instead they will have a log of the
writes, so you would have to benchmark copying against transaction logs.

>
> STSTM is not a monad transformer (visibly or internally). I hope that
> any potential problems that might afflict the STMonadTrans package are
> irrelevant here.

You won't have problems with lists as underlying monad, yes.

>
> I use seq in liftST to force the unsafe inline ST computation to occur
> before bind proceeds to the next computation. Without seq, ST
> computations returning () (or anything else that is not evaluated)
> appear to stay as thunks and never transform any state. I suspect this
> may cause problems with bottoms, but I am not sure if that is any
> different from real ST/runST.

Keep in mind that a `seq` b does not guarantee that a is evaluated
before b. I think this is not a problem here, as there are more severe
problems anyway (see above), but this is generally good to have in mind
when writing such code.

Jonas

>
> --
> Thomas Koster
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

signature.asc (484 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Combining ST with STM

Thomas Koster
Jonas,

Thank you for your swift response.

On 9 February 2016 at 14:43, Thomas Koster <[hidden email]> wrote:

> I have an STM transaction that needs some private, temporary state.
> The most obvious way is to simply pass pure state as arguments, but
> for efficiency, I would like this state to be some kind of mutable
> array, like STArray.
>
> The private state is, by definition, not shared, so
> including it in the STM log and commit process is, as far as I can
> tell, pointless.
>
> ST and STArray still appear to be the most appropriate tools for the
> private state, because STRefs and STArrays really, really are private.
>
> So this basically means I want to interleave ST and STM in a "safe"
> way. That is, if the STM transaction retries, I want the ST state to
> be vaporised as well.
>
> Ideally, I would love to be able to say something like this:
>
> -- | Copy the value from the shared TVar into the private STRef.
> load :: TVar a -> STRef a -> STSTM s ()
> load shared private = do
>   value <- liftSTM (readTVar shared)
>   liftST (writeSTRef private value)
>
> Naturally, that STRef must originate from a call to newSTRef earlier
> in the same transaction and is private to it, just like the real ST
> monad. As far as I can tell, I am not trying to weaken either ST or
> STM in any way here.

On 9 February 2016 at 23:46, Thomas Koster <[hidden email]> wrote:

> Please forgive the typo in the type signature of "load", which should
> have been:
>
> load :: TVar a -> STRef s a -> STSTM s ()
>
> Let me elaborate on STSTM, a monad I made up for this example that
> combines the characteristics of ST and STM in the way that I want.
> If my requirements were unclear from my prose, perhaps the code below
> will illuminate them better.
>
> An STSTM transaction is intended to be an STM transaction imbued with a
> state token that encapsulates additional, transaction-local state in the
> spirit of ST.
>
> It is not intended to secretly perform IO inside STM, a la
> GHC.Conc.unsafeIOToSTM.
>
> It is not intended to facilitate the leaking of state into or out of an
> STM transaction through STRefs, nor to communicate state between
> successive retries of an STM transaction.

On 10 February 2016 at 01:12, Jonas Scholl <[hidden email]> wrote:
> I understand that, you just said, you wanted to sprinkle some runST
> calls with unsafeThawArray and unsafeFreezeArray into your STM code. So
> I assumed you wanted to share an (ST)Array between these STM actions.

Sorry for the confusion. unsafeThawArray and unsafeFreezeArray were an
alternative solution for modifying the transaction-local Array in place,
directly in an STM action.

Rather than use unsafeThawArray, STSTM is intended to allow the safe
interleaving of safe STM actions with safe ST actions, where the ST
state is local and private to the STM transaction. I don't plan on using
any unsafe ST functions with STSTM at all. Naturally, the STSTM
implementation itself must use some kind of unsafe function, but
hopefully only in a safe way.

On 9 February 2016 at 23:46, Thomas Koster <[hidden email]> wrote:

> Thanks to hints from Ryan and Jonas, I made an attempt at implementing
> it myself.
>
> Below is my implementation of STSTM and associated operations. You will
> need to link with the "primitive" and "stm" packages. I used versions
> 0.6 and 2.4.4, resp., and GHC 7.10.2.
>
>
> {-# LANGUAGE GeneralizedNewtypeDeriving, Rank2Types #-}
>
> module Control.Monad.STSTM
>   (
>     STSTM,
>     liftST,
>     liftSTM,
>     atomicallyRunST,
>     module Control.Monad.STM
>   )
> where
>
> import Control.Monad.Primitive
> import Control.Monad.ST
> import Control.Monad.STM
>
> -- | A computation of type @STSTM s a@ is an 'STM' computation that
> -- also transforms a transaction-local internal state indexed by @s@, as
> -- in the 'ST' monad, and returns a value of type @a@.
> newtype STSTM s a = STSTM { unSTSTM :: STM a }
>   deriving (Functor, Applicative, Monad)
>
> -- | Lift an 'ST' computation into the 'STSTM' transaction.
> liftST :: ST s a -> STSTM s a
> {-# INLINE liftST #-}
> liftST x = STSTM $
>   let y = unsafeInlineST x
>   in  y `seq` return y

On 10 February 2016 at 01:12, Jonas Scholl <[hidden email]> wrote:
> This is highly unsafe and will not do what you think it does!
> unsafeInlineST provides an ST action with a realWorld# token out of thin
> air and thus can float outside liftST, especially because you inline it.
> This produces exactly the bug I reported against STMonadTrans.

Thank you for checking it out. I am not surprised that it does not do
what I think, because I don't even know what to think: unsafeInlineST
had no documentation. I wonder what its purpose is then.

So you are saying that because there is no data dependency on the *true*
state token (it evaluates the fake token instead), GHC is free to
rearrange, duplicate or elide the effects on the state with regard to
the other calls to liftST (and the STM actions too), causing those
effects on the state to be unpredictable?

Is this also why I thought I needed seq, when in fact what I needed to
do was thread the correct state token?

> A safe version could take the state token from the STM action, pass it
> into the ST action and carry on with the returned state token (look at
> GHC.Conc.Sync). Or convert the ST action to IO and then just run the IO
> action in STM.

This makes much more sense. I will look into these alternatives.

> This should be fine if you do not use unsafeThaw - any
> garbage written to some STRef/STArray will be thrown away after the
> runtime sees the STM action will fail and restarts it.

That's what I want.

On 9 February 2016 at 23:46, Thomas Koster <[hidden email]> wrote:

> -- | Lift an 'STM' computation into the 'STSTM' transaction.
> liftSTM :: STM a -> STSTM s a
> {-# INLINE liftSTM #-}
> liftSTM = STSTM
>
> -- | Perform a series of 'STSTM' actions atomically.
> --
> -- The 'ST' state is discarded when the 'STM' transaction commits or
> -- retries.
> atomicallyRunST :: (forall s. STSTM s a) -> IO a
> {-# INLINE atomicallyRunST #-}
> atomicallyRunST x = atomically (unSTSTM x)
>
>
> Some commentary follows:
>
> Some initial sanity testing with the GHC threaded runtime shows that it
> does what I want, but I am not familiar enough with Core or the RTS to
> predict whether or not it will launch nuclear missiles at the next
> transit of Venus. I would be grateful for any feedback.
>
> The use of rank-2 polymorphism in the type of atomicallyRunST is
> intended to encapsulate the ST state exactly like it does for runST,
> and that the ST state cannot leak into or out of the transaction.

On 10 February 2016 at 01:12, Jonas Scholl <[hidden email]> wrote:

> What you still can not use is unsafeThaw. Consider this:
>
> foo :: Array Int Val -> TVar Int -> IO someResult
> foo arr var = atomicallyRunST $ do
>     marr <- liftST $ unsafeThaw arr
>     val <- liftSTM $ readTVar var
>     liftST $ writeArray marr val someOtherVal
>     ... do something more...
>
> What happens if the transaction is restarted after the write? You've
> written into arr (unsafeThaw did not copy it), but have no log to revert
> the write. Now you see a different immutable array. This is bad.
>
> So you can not use unsafeThaw. Even if only one transaction gets a hold
> on this array and it would be safe to use unsafeThaw with plain ST (as
> this can not retry), because the transaction has to depend on other
> TVars etc, otherwise there would be no need for STM.
>
> And now I am wondering what happens if a thread evaluates something like
> runST ... unsafeThawArray ... unsafeFreezeArray ... and is hit by an
> asynchronous exception... The computation is restated the next time the
> thunk is demanded, but this could have already changed the array, right?
> So can runST ... unsafeThawArray ... be used in a safe way or is this
> combination inherently broken?

Agreed. This is a problem wherever unsafeThawArray is used. I understand
that nothing I do can make unsafeThawArray safer. Using unsafe functions
here would be at least as unsafe as using them in ST. But if the idea of
STSTM works and is safe, I will not be using any unsafe ST functions in
the ST actions at all.

> Anyway, I think the following holds true:
>  - using STRefs: These must have been created in the transaction, so it
> works.
>  - using STArrays: unsafeThawing an incoming Array will break
> referential transparency sooner or later. Thawing (and thus copying) the
> incoming array or creating a fresh one should work.
>  - using TArrays: You can return these from the STM action and start
> another one later with them without breaking referential transparency as
> always. If you have to modify incoming arguments, even if only one STM
> action has a reference to them at a time, these can be faster as you do
> not have to copy everything - instead they will have a log of the
> writes, so you would have to benchmark copying against transaction logs.

On 9 February 2016 at 23:46, Thomas Koster <[hidden email]> wrote:
> STSTM is not a monad transformer (visibly or internally). I hope that
> any potential problems that might afflict the STMonadTrans package are
> irrelevant here.

On 10 February 2016 at 01:12, Jonas Scholl <[hidden email]> wrote:
> You won't have problems with lists as underlying monad, yes.

On 9 February 2016 at 23:46, Thomas Koster <[hidden email]> wrote:
> I use seq in liftST to force the unsafe inline ST computation to occur
> before bind proceeds to the next computation. Without seq, ST
> computations returning () (or anything else that is not evaluated)
> appear to stay as thunks and never transform any state. I suspect this
> may cause problems with bottoms, but I am not sure if that is any
> different from real ST/runST.

On 10 February 2016 at 01:12, Jonas Scholl <[hidden email]> wrote:
> Keep in mind that a `seq` b does not guarantee that a is evaluated
> before b. I think this is not a problem here, as there are more severe
> problems anyway (see above), but this is generally good to have in mind
> when writing such code.

I hope that if I can fix the unsafety by threading the true state token
through, as per your suggestion above, seq will no longer be necessary.

--
Thomas Koster
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe