[Caml-list] Threads and "transaction isolation" in OCaml

[Caml-list] Threads and "transaction isolation" in OCaml

[Markus Mottl]

Hi,

I just wondered how much we can rely on current OCaml-semantics where
context-switches are impossible as long as there are no allocations.

E.g. pattern-matches, array and record field assignments, etc., can be
safely chained together in one "transaction" without having to fear
that another thread will interrupt them.  This is extremely useful for
optimizing certain applications where lock acquisitions might just be
too expensive.

There already are some corner cases where things may be
platform-dependent, e.g. calling functions tail-recursively that take
more arguments than there are available CPU-registers.  In that case
the compiler may pass arguments by allocating blocks on the heap.  But
I think people that care about such obviously brittle semantics know
where to be careful.

Anyway, is it considered reasonably future-safe to write code of that
sort?  I'd rather not have new compiler optimizations, etc., interfere
with these assumptions in the near future.

Regards,
Markus

-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com

Re: [Caml-list] Threads and "transaction isolation" in OCaml

[John F Carr]

Do you mean allocation or garbage collection?

Generational garbage collectors can collect without allocation when you 
assign a
young object to a field of an older object.  There is (or may be) a list of
intergenerational (older to younger) references.  When that list exceeds a
threshold, the GC may do a minor collection.

I have not checked what the current implementation of OCaml does in this case.

let x = ref (ref 0) in
let y = ref 1 in (* allocation triggers GC; x is old and y is young *)
... work here ...
x := y (* may cause GC *)


> Hi,
>
> I just wondered how much we can rely on current OCaml-semantics where
> context-switches are impossible as long as there are no allocations.
>
> E.g. pattern-matches, array and record field assignments, etc., can be
> safely chained together in one "transaction" without having to fear
> that another thread will interrupt them.  This is extremely useful for
> optimizing certain applications where lock acquisitions might just be
> too expensive.
>
> There already are some corner cases where things may be
> platform-dependent, e.g. calling functions tail-recursively that take
> more arguments than there are available CPU-registers.  In that case
> the compiler may pass arguments by allocating blocks on the heap.  But
> I think people that care about such obviously brittle semantics know
> where to be careful.
>
> Anyway, is it considered reasonably future-safe to write code of that
> sort?  I'd rather not have new compiler optimizations, etc., interfere
> with these assumptions in the near future.
>
> Regards,
> Markus
>
> --
> Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Threads and "transaction isolation" in OCaml

[Markus Mottl]

That's a good point.  I had never seen a problem with this, but wasn't
sure whether this is just due to my particular use cases in the past
(may have involved atomic values only) so I've verified this in the
source now to be sure.  The "caml_ref_table", which contains all
fields on the major heap that refer to the minor heap, will be
reallocated if it runs out of space, but I don't see any place where
this would actually run the GC.  The same seems to be true of the
"gray_vals" table that may also get involved.  I guess such
reallocations are exceedingly rare in practice, because the GC will
usually run before the tables get full and clear them out.

I'm sure the OCaml team will let us know if I missed anything, but I
think assignments are safe in all circumstances (including your
example), no matter what the source or destination values are.

On Thu, Aug 15, 2013 at 9:28 PM, John F Carr <jfc@mit.edu> wrote:
> Do you mean allocation or garbage collection?
>
> Generational garbage collectors can collect without allocation when you
> assign a
> young object to a field of an older object.  There is (or may be) a list of
> intergenerational (older to younger) references.  When that list exceeds a
> threshold, the GC may do a minor collection.
>
> I have not checked what the current implementation of OCaml does in this
> case.
>
> let x = ref (ref 0) in
> let y = ref 1 in (* allocation triggers GC; x is old and y is young *)
> ... work here ...
> x := y (* may cause GC *)
>
>
>> Hi,
>>
>> I just wondered how much we can rely on current OCaml-semantics where
>> context-switches are impossible as long as there are no allocations.
>>
>> E.g. pattern-matches, array and record field assignments, etc., can be
>> safely chained together in one "transaction" without having to fear
>> that another thread will interrupt them.  This is extremely useful for
>> optimizing certain applications where lock acquisitions might just be
>> too expensive.
>>
>> There already are some corner cases where things may be
>> platform-dependent, e.g. calling functions tail-recursively that take
>> more arguments than there are available CPU-registers.  In that case
>> the compiler may pass arguments by allocating blocks on the heap.  But
>> I think people that care about such obviously brittle semantics know
>> where to be careful.
>>
>> Anyway, is it considered reasonably future-safe to write code of that
>> sort?  I'd rather not have new compiler optimizations, etc., interfere
>> with these assumptions in the near future.
>>
>> Regards,
>> Markus
>>
>> --
>> Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs



-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com

Re: [Caml-list] Threads and "transaction isolation" in OCaml

[Török Edwin]

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

On 08/16/2013 12:57 AM, Markus Mottl wrote:
> Hi,
> 
> I just wondered how much we can rely on current OCaml-semantics where
> context-switches are impossible as long as there are no allocations.

I wrote a little test program and this is not true for bytecode -vmthread, but seems to work for bytecode -thread and native -thread:
$ ocamlfind ocamlc race.ml -package threads -vmthread -linkpkg -o race && ./race
started
Check OK
worker 2 OK
worker 3 OK
worker 4 OK
worker 5 OK
worker 7 OK
worker 8 OK
worker 9 OK
worker 10 OK
worker 11 OK
worker 12 OK
worker 13 OK
worker 14 OK
worker 0 OK
worker 1 OK
worker 6 OK
worker 15 OK
Array sum inconsistent: -33


> 
> Anyway, is it considered reasonably future-safe to write code of that
> sort?  I'd rather not have new compiler optimizations, etc., interfere
> with these assumptions in the near future.

I'd consider this very fragile as you'd need to know the implementation details of every function you call (or only calling your own safe functions). I was surprised to find out that even Array.fold_left creates a temporary ref for example.

Best regards,
--Edwin

[-- Attachment #2: race.ml --]
[-- Type: text/x-ocaml, Size: 1254 bytes --]

let n = 10000000
let global = Array.init n (fun i -> 0)
let cond = Condition.create ()
let mutex = Mutex.create ()

let rec check_consistent accum i =
  if i >= 0 then
    check_consistent (accum + global.(i)) (i-1)
  else if accum <> 0 then begin
    Printf.eprintf "Array sum inconsistent: %d\n" accum;
    flush stderr;
    exit 1
  end

let rec update_array x i =
  if i < n then begin
    if i mod 2 = 0 then
      global.(i) <- x
    else
      global.(i) <- -x;
    update_array x (i+1)
  end

let start = ref false

let barrier () =
  (* start all threads at same time *)
  Mutex.lock mutex;
  while !start = false do
    Condition.wait cond mutex
  done;
  Mutex.unlock mutex

let worker i =
  barrier ();
  while true; do
    (* the transaction *)
    update_array i 0;
    (* end of transaction *)
    Printf.printf "worker %d OK\n" i;
    flush stdout;
  done

let verifier () =
  barrier ();
  while true; do
    check_consistent 0 (n-1);
    Printf.printf "Check OK\n";
    flush stdout;
  done

let () =
  let a = Array.init 16 (fun i -> Thread.create worker i) in
  let t = Thread.create verifier () in
  start := true;
  Condition.broadcast cond;
  Printf.eprintf "started\n";
  flush stderr;
  Array.iter Thread.join a;
  Thread.join t

Re: [Caml-list] Threads and "transaction isolation" in OCaml

[Markus Mottl]

On Fri, Aug 16, 2013 at 4:46 AM, Török Edwin <edwin+ml-ocaml@etorok.net> wrote:
> I wrote a little test program and this is not true for bytecode -vmthread, but seems to work for bytecode -thread and native -thread:

Thanks for this example.  It's not surprising that this trick does not
work with VM-threads, but I have never seen anybody use them for
anything so I'm not bothered by this.

But, surprisingly to me, I did manage to get a failure with byte code
+ POSIX threads when running this example on Linux (Centos 6.4) via
VMware Fusion (Mac OS X).  I admittedly have never thoroughly tested
these "transactions" with any sort of byte code, since I practically
exclusively run native code.  Still, I would have expected the runtime
to work identically here.  Interestingly, I couldn't replicate the
error on a VPS running the same OS and compiler, but using Xen (via
Linode) instead of VMware Fusion for virtualization.

Note that some open source libraries, e.g. the Nano_mutex module in
Jane Street Core, depend on this trick so it seems important to figure
out how safe and portable it really is.  It would be a huge pity to do
without, since it can offer quite dramatic performance improvements
for certain applications.

Does anybody know a reason why byte code + POSIX threads might fail
with this trick?

> I'd consider this very fragile as you'd need to know the implementation details of every function you call (or only calling your own safe functions). I was surprised to find out that even Array.fold_left creates a temporary ref for example.

It would certainly be unwise to call any function whose implementation
is not fixed and fully understood wrt. transaction isolation.  This
trick is obviously low-level and its use should be clearly documented
by the developer.  Most of the time it will only consist of a few
assignments or pattern-matches anyway.

Regards,
Markus

-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com

Re: [Caml-list] Threads and "transaction isolation" in OCaml

[Yaron Minsky]

I'd like to second Markus' request here.  We definitely take advantage
of this behavior in the compiler, and I hadn't realized that it didn't
hold in byte-code.  I do think this is a rather valuable hack, and it
would be good to make the bounds of its applicability more explicit.

y

On Fri, Aug 16, 2013 at 12:07 PM, Markus Mottl <markus.mottl@gmail.com> wrote:
> On Fri, Aug 16, 2013 at 4:46 AM, Török Edwin <edwin+ml-ocaml@etorok.net> wrote:
>> I wrote a little test program and this is not true for bytecode -vmthread, but seems to work for bytecode -thread and native -thread:
>
> Thanks for this example.  It's not surprising that this trick does not
> work with VM-threads, but I have never seen anybody use them for
> anything so I'm not bothered by this.
>
> But, surprisingly to me, I did manage to get a failure with byte code
> + POSIX threads when running this example on Linux (Centos 6.4) via
> VMware Fusion (Mac OS X).  I admittedly have never thoroughly tested
> these "transactions" with any sort of byte code, since I practically
> exclusively run native code.  Still, I would have expected the runtime
> to work identically here.  Interestingly, I couldn't replicate the
> error on a VPS running the same OS and compiler, but using Xen (via
> Linode) instead of VMware Fusion for virtualization.
>
> Note that some open source libraries, e.g. the Nano_mutex module in
> Jane Street Core, depend on this trick so it seems important to figure
> out how safe and portable it really is.  It would be a huge pity to do
> without, since it can offer quite dramatic performance improvements
> for certain applications.
>
> Does anybody know a reason why byte code + POSIX threads might fail
> with this trick?
>
>> I'd consider this very fragile as you'd need to know the implementation details of every function you call (or only calling your own safe functions). I was surprised to find out that even Array.fold_left creates a temporary ref for example.
>
> It would certainly be unwise to call any function whose implementation
> is not fixed and fully understood wrt. transaction isolation.  This
> trick is obviously low-level and its use should be clearly documented
> by the developer.  Most of the time it will only consist of a few
> assignments or pattern-matches anyway.
>
> Regards,
> Markus
>
> --
> Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Threads and "transaction isolation" in OCaml

[Mark Shinwell]

On 17 August 2013 01:06, Yaron Minsky <yminsky@janestreet.com> wrote:
> I'd like to second Markus' request here.  We definitely take advantage
> of this behavior in the compiler, and I hadn't realized that it didn't
> hold in byte-code.  I do think this is a rather valuable hack, and it
> would be good to make the bounds of its applicability more explicit.

I have wondered in the past if we should introduce a syntactic
construct to delimit areas of code that rely on the no-thread-switch
property.  I think it would probably be reasonable to actually
check that the expression inside the construct was guaranteed under
the current runtime not to cause a context switch (such expressions are
likely to be, and should be, straightforward).  At runtime, the
construct would have no semantic effect.  For the scenario described
with bytecode, the construct could just cause a compiler error, at
least at present.

Mark

Re: [Caml-list] Threads and "transaction isolation" in OCaml

[Xavier Leroy]

On 2013-08-16 18:07, Markus Mottl wrote:
> I just wondered how much we can rely on current OCaml-semantics where
> context-switches are impossible as long as there are no allocations.
> [...]
> But, surprisingly to me, I did manage to get a failure with byte code
> + POSIX threads when running this example on Linux (Centos 6.4) via
> VMware Fusion (Mac OS X).

Bytecode and native code poll for asynchronous events (context
switches, pending signals, etc) at different program points:

- Bytecode:
    . at every function call
    . at the beginning of every iteration of a while or for loop
    . at the end of "b" in "try b with ...".

- Native:
    . at every allocation in the minor heap.

Your example has a function call in the "transaction", hence the
behavior you observe.

> Anyway, is it considered reasonably future-safe to write code of that
> sort?  I'd rather not have new compiler optimizations, etc., interfere
> with these assumptions in the near future.

There is no short-term plan to change this behavior, but no guarantee
that it will be here forever.  Caveat emptor.

- Xavier Leroy

Re: [Caml-list] Threads and "transaction isolation" in OCaml

[Markus Mottl]

On Mon, Aug 19, 2013 at 2:10 AM, Mark Shinwell <mshinwell@janestreet.com> wrote:
> I have wondered in the past if we should introduce a syntactic
> construct to delimit areas of code that rely on the no-thread-switch
> property.  I think it would probably be reasonable to actually
> check that the expression inside the construct was guaranteed under
> the current runtime not to cause a context switch (such expressions are
> likely to be, and should be, straightforward).  At runtime, the
> construct would have no semantic effect.  For the scenario described
> with bytecode, the construct could just cause a compiler error, at
> least at present.

This might just require adding two new primitives
(enter/leave_transaction) to the standard library.  If e.g. the native
code compiler sees that there is no allocation in-between, these could
even become no-ops.  Otherwise the runtime system might just need to
check one extra flag when deciding whether to do a context switch,
which would have negligible cost and apparently low complexity.  Of
course, using these primitives requires great care so maybe they
should be prefixed with "unsafe_".

Regards,
Markus

-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com