Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

atomic_init, compare_and_swap, atomic_add #7043

Closed
vicuna opened this issue Nov 15, 2015 · 5 comments · Fixed by #9570
Closed

atomic_init, compare_and_swap, atomic_add #7043

vicuna opened this issue Nov 15, 2015 · 5 comments · Fixed by #9570

Comments

@vicuna
Copy link

vicuna commented Nov 15, 2015

Original bug ID: 7043
Reporter: gerd
Status: acknowledged (set by @damiendoligez on 2017-04-13T11:07:14Z)
Resolution: open
Priority: normal
Severity: feature
Version: 4.02.3
Category: standard library
Monitored by: @gasche

Bug description

When developing a library, there are sometimes situations where you don't know whether it is used in a multi-threaded program or not. It would be nice to have some very basic primitives that work under these circumstances, in particular a version of compare_and_swap:

val atomic_init : 'a option ref -> 'a -> 'a

with the meaning: if the variable is None, it is atomically set to the new value and the value is returned. If the variable is Some x, the value x is returned.

A possible implementation with the current runtime is:

let atomic_init var new_val =
let new_val_opt = Some new_val in
match !var with
| None -> var := new_val_opt; new_val
| Some x -> x

Looks trivial, but it is not. It is exploiting that the code after "match" cannot be interrupted. If you e.g. move the new_val_opt allocation inside "match" the function would not be working anymore.

Because it is exploiting implementation details of the current runtime, it should be part of the standard library (Pervasives, not Thread, so you always have it).

atomic_init is useful for initializing variables only once. A generalization would be:

val compare_and_swap : 'a ref -> 'a -> 'a -> bool

with the meaning: if the variable has the old value it changed to the new value, and it is returned whether the update occurred:

let compare_and_swap var old_val new_val =
!var == old_val
&& ( var := new_val; true )

On the wish list is also atomic arithmetic, like

val atomic_add : int ref -> int -> int

which adds the number to the variable and returns the new value. (But this is not as important.)

These primitives seem to be safe to support even for alternate runtimes that permit more parallelization, because there is support for these operations in all modern CPUs.

@github-actions
Copy link

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

@github-actions github-actions bot added the Stale label May 11, 2020
@stedolan stedolan self-assigned this May 12, 2020
@stedolan stedolan removed the Stale label May 12, 2020
@stedolan
Copy link
Contributor

This already exists in the multicore branch, we could import it into the stdlib (with some cleanup and more documentation!)

Note that this would be a new type 'a Atomic.t of references with atomic operations - trying to define the precise semantics of atomic operations on ordinary refs gets very nasty.

@gasche
Copy link
Member

gasche commented May 12, 2020

I think it would be a good idea indeed to make these available in the standard library, so that when people start using Multicore in the future they can write most of their code in a way that is backward-compatible with older OCaml versions. (In particular library authors who may not need to control domains directly.)

We should probably focus on a subset of the API that we know is going to be very stable. (for example, in partial order: (make, get, set) > compare_and_set > (fetch_and_add, exchange) > (incr, decr))

@gasche
Copy link
Member

gasche commented May 13, 2020

(After sleeping on it, I would say the whole API is simple enough and can be kept whole.)

@gasche
Copy link
Member

gasche commented May 15, 2020

I proposed a PR in #9570. The implementation itself is simple (but still needs to be done and reviewed carefully), so it was mostly about pleasing the build system.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants