Lazy and Threads

Lazy and Threads

[victor-caml-list]

Hello, 

I'm working with both lazy expressions and threads, and noticed that the 
evaluation of lazy expressions is not thread-safe:

  let expr = lazy (Thread.delay 1.0)

  let _ =
    let thread = Thread.create (fun () -> Lazy.force expr) () in
      Lazy.force expr; 
      Thread.join thread

The second thread to attempt an evaluation dies with Lazy.Undefined. The 
source of this appears to be the standard Lazy.force behavior, which 
replaces the closure in the lazy-block with a raise_undefined closure in 
order to detect self-recursing lazy expressions.

Aside from handling a mutex myself (which I don't find very elegant for 
a read operation in a pure functional program) is there a solution I can 
use to manipulate lazy expressions in a pure functional multi-threaded 
program?

-- 
Victor Nicollet

Re: [Caml-list] Lazy and Threads

[Yaron Minsky]

[-- Attachment #1: Type: text/plain, Size: 1716 bytes --]

At a minimum, this seems like a bug in the documentation. The documentation
states very clearly that Undefined is called when a value is recursively
forced.  Clearly, you get the same error when you force a lazy value that is
in the process of being forced for the first time....

It does seem like fixing the behavior to match the current documentation
would be superior to fixing the documentation to match the current behavior.

I'd suggest adding a bug report to the bug tracker.

y

On Tue, Feb 17, 2009 at 10:54 AM, <victor-caml-list@nicollet.net> wrote:

> Hello,
>
> I'm working with both lazy expressions and threads, and noticed that the
> evaluation of lazy expressions is not thread-safe:
>
>  let expr = lazy (Thread.delay 1.0)
>
>  let _ =
>    let thread = Thread.create (fun () -> Lazy.force expr) () in
>      Lazy.force expr;
>      Thread.join thread
>
> The second thread to attempt an evaluation dies with Lazy.Undefined. The
> source of this appears to be the standard Lazy.force behavior, which
> replaces the closure in the lazy-block with a raise_undefined closure in
> order to detect self-recursing lazy expressions.
>
> Aside from handling a mutex myself (which I don't find very elegant for
> a read operation in a pure functional program) is there a solution I can
> use to manipulate lazy expressions in a pure functional multi-threaded
> program?
>
> --
> Victor Nicollet
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 2464 bytes --]

Re: [Caml-list] Lazy and Threads

[Xavier Leroy]

Victor Nicollet wrote:
>     I'm working with both lazy expressions and threads, and noticed that the
>     evaluation of lazy expressions is not thread-safe:

Yaron Minsky wrote:
> At a minimum, this seems like a bug in the documentation. The
> documentation states very clearly that Undefined is called when a value
> is recursively forced.  Clearly, you get the same error when you force a
> lazy value that is in the process of being forced for the first time....
> It does seem like fixing the behavior to match the current documentation
> would be superior to fixing the documentation to match the current behavior.

It's not just the Lazy module: in general, the whole standard library
is not thread-safe.  Probably that should be stated in the
documentation for the threads library, but there isn't much point in
documenting it per standard library module.

As to making the standard library thread-safe by sprinkling it with
mutexes, Java-style: no way.  There is one part of the stdlib that is
made thread-safe this way: buffered I/O operations.  (The reason is
that, owing to the C implementation of some of these operations, a
race condition in buffered I/O could actually crash the whole program,
rather than just result in unexpected results as in the case of pure
Caml modules.)  You (Yaron) and others recently complained that such
locking around buffered I/O made some operations too slow for your
taste.  Wait until you wrap a mutex around all Lazy.force
operations...

More generally speaking, locking within a standard library is the
wrong thing to do: that doesn't prevent race conditions at the
application level, and for reasonable performance you need to lock at
a much coarser grain, again at the application level.  (That's one of
the things that make shared-memory programming with threads and locks
so incredibly painful and non-modular.)

Coming back to Victor's original question:

>     Aside from handling a mutex myself (which I don't find very elegant for
>     a read operation in a pure functional program) is there a solution I can
>     use to manipulate lazy expressions in a pure functional multi-threaded
>     program?

You need to think more / tell us more about what you're trying to
achieve with sharing lazy values between threads.

If your program is really purely functional (i.e. no I/O of any kind),
OCaml's multithreading is essentially useless, as you're not going to
get any speedup from it and would be better off with sequential
computations.  If your program does use threads to overlap computation
and I/O, using threads might be warranted, but then what is the
appropriate granularity of locking that you'd need?

A somewhat related question is: what semantics do you expect from
concurrent Lazy.force operations on a shared suspension?  One thread
blocks while the other completes the computation?  Same but with busy
waiting?  (if the computations are generally small).  Or do you want
speculative execution?  (Both threads may evaluate the suspended
computation.)

There is no unique answer to these questions: it all depends on what
you're trying to achieve...

- Xavier Leroy

Re: [Caml-list] Lazy and Threads

[Yaron Minsky]

You're totally right. I withdraw my complaint.

y

Yaron Minsky

On Feb 20, 2009, at 1:36 PM, Xavier Leroy <Xavier.Leroy@inria.fr> wrote:

> Victor Nicollet wrote:
>>    I'm working with both lazy expressions and threads, and noticed  
>> that the
>>    evaluation of lazy expressions is not thread-safe:
>
> Yaron Minsky wrote:
>> At a minimum, this seems like a bug in the documentation. The
>> documentation states very clearly that Undefined is called when a  
>> value
>> is recursively forced.  Clearly, you get the same error when you  
>> force a
>> lazy value that is in the process of being forced for the first  
>> time....
>> It does seem like fixing the behavior to match the current  
>> documentation
>> would be superior to fixing the documentation to match the current  
>> behavior.
>
> It's not just the Lazy module: in general, the whole standard library
> is not thread-safe.  Probably that should be stated in the
> documentation for the threads library, but there isn't much point in
> documenting it per standard library module.
>
> As to making the standard library thread-safe by sprinkling it with
> mutexes, Java-style: no way.  There is one part of the stdlib that is
> made thread-safe this way: buffered I/O operations.  (The reason is
> that, owing to the C implementation of some of these operations, a
> race condition in buffered I/O could actually crash the whole program,
> rather than just result in unexpected results as in the case of pure
> Caml modules.)  You (Yaron) and others recently complained that such
> locking around buffered I/O made some operations too slow for your
> taste.  Wait until you wrap a mutex around all Lazy.force
> operations...
>
> More generally speaking, locking within a standard library is the
> wrong thing to do: that doesn't prevent race conditions at the
> application level, and for reasonable performance you need to lock at
> a much coarser grain, again at the application level.  (That's one of
> the things that make shared-memory programming with threads and locks
> so incredibly painful and non-modular.)
>
> Coming back to Victor's original question:
>
>>    Aside from handling a mutex myself (which I don't find very  
>> elegant for
>>    a read operation in a pure functional program) is there a  
>> solution I can
>>    use to manipulate lazy expressions in a pure functional multi- 
>> threaded
>>    program?
>
> You need to think more / tell us more about what you're trying to
> achieve with sharing lazy values between threads.
>
> If your program is really purely functional (i.e. no I/O of any kind),
> OCaml's multithreading is essentially useless, as you're not going to
> get any speedup from it and would be better off with sequential
> computations.  If your program does use threads to overlap computation
> and I/O, using threads might be warranted, but then what is the
> appropriate granularity of locking that you'd need?
>
> A somewhat related question is: what semantics do you expect from
> concurrent Lazy.force operations on a shared suspension?  One thread
> blocks while the other completes the computation?  Same but with busy
> waiting?  (if the computations are generally small).  Or do you want
> speculative execution?  (Both threads may evaluate the suspended
> computation.)
>
> There is no unique answer to these questions: it all depends on what
> you're trying to achieve...
>
> - Xavier Leroy