On Thu, 2009-02-12 at 22:58 -0500, David Menendez wrote:

On Thu, Feb 12, 2009 at 6:26 PM, Don Stewart <dons@galois.com> wrote:

...

bugfact:

...

Consider the following code

stamp v x = do t <- getCurrentTime putMVar v (x,t)

Is it possible - with GHC - that a thread switch happens after the t <- getCurrentTime and the putMVar v (x,t)?

Yes. if 't' is heap allocated, there could be a context switch.

...

If so, how would it be possible to make sure that the operation of reading the current time and writing the pair to the MVar is an "atomic" operation, in the sense that no thread switch can happen between the two? Would this require STM?

Using 'atomically' and TVars in STM, perhaps? Else, use withMVar? Or a modifyMVar in IO?

As I understand it, withMVar or modifyMVar will protect you from extraneous exceptions, but they won't prevent another thread from writing to the MVar between the take and the put.

You have to cooperate with the other users of the MVar. If each thread is using readMVar, withMVar or modifyMVar then it's fine. The read/with/modify actions do a takeMVar followed by a putMVar. If one thread is using withMVar and another is doing putMVar directly then the exclusion scheme does not work. Duncan

If you have two streams of time/value pairs - using MVars as write-once sampling variables - and both streams are fed from another thread (e.g. timers firing), and you want to merge these two streams into a single stream with monotonic time stamps, then you want to be able to check if at time t an occurrence exists in a stream. In the case an old time was read but not yet written to an mvar, this could lead to the merged stream not being monotonic. At least in my C# prototype that was the case, I used many very high frequency timers to stress test the merger, and this bug popped up. I found similar code in the Reactive library, but Reactive is much more clever operationally (and semantically) than my little prototype so it might not be a problem. But if it is, I guess it can be solved by introducing another MVar to indicate "I'm reading time", at least I solved it in the C# prototype in that way. On Sat, Feb 14, 2009 at 8:01 PM, Paul Johnson <paul@cogito.org.uk> wrote:

I'm not entirely sure what you are trying to achieve here. Presumably you want v to contain the (value, time) pair as soon as possible after time "t". Of course it won't be instantaneous. So another thread could observe that at time (t+delta) the variable "v" does not yet contain (x,t). Is this a problem?

Atomic transactions won't work because "getCurrentTime" is of type "IO Time", whereas anything inside "atomic" has to be of type "STM a".

In theory you could lock out context switches by messing around with the GHC runtime, but if you are running on a multicore machine then that won't work either.

Paul.

I'm not sure what you mean with "Time on different cores does not progress monotonically". Time could come from a dedicated clock device. E.g. in the broadcast television sector a time signal is distributed across all hardware components to keep them all in sync within some margin, or you could use the clock from a local sound card, etc. I guess each operating system provides such a clock. I'm also not sure about the performance penalty. One would surely get a penalty with a global lock on the clock (serializing time), but I think the problem can be solved with a local lock per stream. But I would have to think about this more before claiming such things :-) Maybe you could elaborate a bit more on your claims? On Sun, Feb 15, 2009 at 5:38 AM, Bryan O'Sullivan <bos@serpentine.com>wrote:

2009/2/14 Peter Verswyvelen <bugfact@gmail.com>

...

If you have two streams of time/value pairs - using MVars as write-once sampling variables - and both streams are fed from another thread (e.g. timers firing), and you want to merge these two streams into a single stream with monotonic time stamps, then you want to be able to check if at time t an occurrence exists in a stream.

What you want to do isn't actually achievable on multi-processor machines without some form of mutual exclusion. Time on different cores does not progress monotonically, and you'll pay an enormous performance penalty to do what you want to do (the nature of which is somewhat unclear).