[Haskell-cafe] STM, orElse and timed read from a channel

[Tomasz Zielonka]

On Tue, Nov 29, 2005 at 12:29:55PM -0000, Simon Marlow wrote:
> 
> > Alternatively, it would be nice to have a new STM primitive:
> > 
> >     wailUntil :: ClockTime -> STM ()
> > 
> > so you would wait until some time-point passes, not for a number of
> > time-units (waiting for a number of time-units wouldn't work because
> > of retries). I think it could be efficiently implemented, wouldn't it?
> 
> But you could also implement this using registerTimeout, albeit with
> some more code and an extra thread, and waitUntil requires an
> implementation in the runtime which is not entirely trivial.

It is trivial to create a very inefficient implementation, in which all
STM transactions waiting on waitUntil will be retried on (almost) every
tick of the clock, let's say every second. You just create a TVar that
is updated with current time every second. But as I say, the efficiency
would be unacceptable.

But this can be improved. I found a simple solution that reduces the
number of transaction retries to O(log (t - t0)), where t0 is
transaction start time, and t is the parameter to waitUntil. I attached
a proof-of-concept implementation to this message.

I simply use the binary representation of time and wait only on the part
of bits, starting from most significant ones, that are enough to tell
that the waitUntil time has not come. To make it simple I used unix
epoch time in seconds, but the thing could be made more precise. I the
thread updating the time variable I make sure that I don't update the
bits that didn't change.

You can compile the Test module as a program. There are two kinds of
tests, some that show how many tries are made, and one that shows how
the thing works for many threads.

BTW, I tried to make the library interface simpler creating a default
top-level time variable

    {-# NOINLINE timeVar #-}
    timeVar :: TimeVar
    timeVar = unsafePerformIO initTimeVar

so I could export a waitUntil function with type

    waitUntil :: Time -> STM ()

but I tripped on something that was reported before, namely that STM
transactions can't be nested (as a result of unsafePerformIO or
unsafeInterleaveIO). Is there a plan to support such scenario?

Best regards
Tomasz

-- 
I am searching for a programmer who is good at least in some of
[Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Test.hs
Type: text/x-haskell
Size: 2311 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20051203/17190749/Test.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: TimeVar.hs
Type: text/x-haskell
Size: 1664 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20051203/17190749/TimeVar.bin