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[IU]size: Supply a generic CAS loop #48655

Open
llogiq opened this issue Mar 2, 2018 · 8 comments

Comments

Projects
None yet
10 participants
@llogiq
Copy link
Contributor

commented Mar 2, 2018

Rationale: Writing an optimal CAS loop is time-consuming and risks errors (e.g.
mis-setting Orderings). On the other hand, there are two general operations:
fetch_and_update which is useful for things like random number generators,
and update_and_fetch which is the usual operation when you want to e.g. keep
a maximum stat over a series of concurrently produced values.

Adding those two operations as methods has little cost. Conversely, requiring
an extra crate means that the methods would have to either be implemented as
functions instead of methods, or that an extension trait would have to be
imported to use them. Both of those options are suboptimal.

Prior art: Java has an getAndUpdate / updateAndGet method on its
AtomicInteger class since version 1.8. Due to the fact that Java lambdas are
more restricted w.r.t. mutability of their arguments than Rust's, there's also
accumulateAndGet / getAndAccumulate.

llogiq added a commit to llogiq/rust that referenced this issue Mar 2, 2018

Add a gerneic CAS loop to std::sync::Atomic?size
This adds two new methods to both `AtomicIsize` and `AtomicUsize`
with optimized safe compare-and-set loops, so users will no longer
need to write their own, except in *very* strange circumstances.

`update_and_fetch` will apply the function and return its result,
whereas `fetch_and_update` will apply the function and return the
previous value.

This solves rust-lang#48384 with `x.update_and_fetch(|x| x.max(y))`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now)..

*note* This *might* need a crater run because the functions could
clash with third party extension traits.
@stjepang

This comment has been minimized.

Copy link
Contributor

commented Mar 3, 2018

This method would definitely be useful. However, I wonder if it's a better fit for something like crossbeam_atomic::AtomicCell rather than std::sync::atomic::AtomicUsize?

Note that Java's AtomicInteger would be more similar to AtomicCell (they're both high-level atomic primitives), while AtomicUsize is more low-level (it's essentially just a thin wrapper around LLVM atomics).

llogiq added a commit to llogiq/rust that referenced this issue Mar 26, 2018

Add a gerneic CAS loop to std::sync::Atomic?size
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 26, 2018

Add a gerneic CAS loop to std::sync::Atomic?size
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 26, 2018

Add a gerneic CAS loop to std::sync::Atomic?size
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 26, 2018

Add a gerneic CAS loop to std::sync::Atomic?size
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 26, 2018

Add a gerneic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 27, 2018

Add a generic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 27, 2018

Add a generic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 27, 2018

Add a generic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 27, 2018

Add a generic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 28, 2018

Add a generic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 28, 2018

Add a generic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 30, 2018

Add a generic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

llogiq added a commit to llogiq/rust that referenced this issue Mar 30, 2018

Add a generic CAS loop to std::sync::Atomic*
This adds a new method to all numeric `Atomic*` types with a
safe compare-and-set loop, so users will no longer need to write
their own, except in *very* strange circumstances.

This solves rust-lang#48384 with `x.fetch_max(_)`/`x.fetch_min(_)`. It
also relates to rust-lang#48655 (which I misuse as tracking issue for now).

*note* This *might* need a crater run because the functions could
clash with third party extension traits.

kennytm added a commit to kennytm/rust that referenced this issue Apr 5, 2018

Rollup merge of rust-lang#48658 - llogiq:no-more-cas, r=kennytm
Add a generic CAS loop to std::sync::Atomic*

This adds two new methods to both `AtomicIsize` and `AtomicUsize` with optimized safe compare-and-set loops, so users will no longer need to write their own, except in *very* strange circumstances.

`update_and_fetch` will apply the function and return its result, whereas `fetch_and_update` will apply the function and return the previous value.

This solves rust-lang#48384 with `x.update_and_fetch(|x| x.max(y))`. It also relates to rust-lang#48655 (which I misuse as tracking issue for now)..

*note* This *might* need a crater run because the functions could clash with third party extension traits.
@stbuehler

This comment has been minimized.

Copy link

commented Apr 8, 2018

I think the current doc could be read as "on success returns Ok(new_value)"; afaict the implementation always returns the "previous" value passed to the last invocation of f; as Ok(_) on success and as Err(_) if f returned None. Perhaps the wording could be improved?

@llogiq

This comment has been minimized.

Copy link
Contributor Author

commented Apr 8, 2018

Agreed, the wording can certainly be improved. I had a lot of back-and-forth and frankly at one point almost closed the PR, I'm just happy it's landed.

If you like, you may submit a doc improvement PR. Otherwise I can do it, citing you as the source.

@nagisa

This comment has been minimized.

Copy link
Contributor

commented Jul 21, 2018

Documentation for the functions should specify which orderings are valid or not (e.g. fetch_order for fetch_update does not permit AcqRel or Release).

@RalfJung

This comment has been minimized.

Copy link
Member

commented Aug 7, 2018

The ordering argument names are also not entirely correct -- set_order is also used for the the successful load. The two modes should probably be called success and failure, with failure also used for the load.

EDIT: Oh, the argument order is the wrong way around compared to compare_exchange. Dang :/

EDIT2: Also see #53106.

@RalfJung

This comment has been minimized.

Copy link
Member

commented Aug 7, 2018

Is it worth mentioning that for the case where f always returns Some and never panics, there really is no reason not to use Relaxed as load ordering? A final successful CAS is going to happen, which is sufficient for synchronization. No need to use anything stronger for all the loads and failed CASes.

@nikolads

This comment has been minimized.

Copy link

commented Sep 3, 2018

Is Result the correct return type? Unlike the compare_exchange functions here an Err result doesn't indicate that the function failed to do something, it indicates that f returned None.

My concern is that Result is marked as #[must_use] and here a common use case will be that you are not interested in the result value. So you will write code like let _ = x.fetch_update(...);.

Maybe a custom enum with Updated and NotUpdated variants can be used. But then you will have to import an additional type if you are interested in the result and want to pattern match it.

@Centril Centril added the T-lang label Dec 20, 2018

@mystor

This comment has been minimized.

Copy link
Contributor

commented May 26, 2019

Stumbled across this method today, and figured I'd prod this issue & drop in my bikeshed 2¢.

I pulled the Weak::upgrade method as an example from the stdlib, and translated it roughly to the new API, formatted with rustfmt, as an example:

// We use a CAS loop to increment the strong count instead of a
// fetch_add because once the count hits 0 it must never be above 0.
let inner = self.inner()?;

// Relaxed load because any write of 0 that we can observe leaves the
// field in a permanently zero state (so a "stale" read of 0 is fine),
// and any other value is confirmed via the CAS.
inner
    .strong
    .fetch_update(
        |n| {
            if n == 0 {
                return None;
            }

            // See comments in `Arc::clone` for why we do this (for `mem::forget`).
            if n > MAX_REFCOUNT {
                unsafe {
                    abort();
                }
            }

            Some(n + 1)
        },
        Relaxed,
        Relaxed,
    )
    .ok()
    .map(|_| Arc {
        // null checked above
        ptr: self.ptr,
        phantom: PhantomData,
    })

A few things I've noticed:

  1. This particular usecase has a fairly textually long update parameter, which forces the method into the multi-line format used by rustfmt. If we moved the ordering parameters before the lambda parameter, it would end up looking a bit cleaner:
inner
    .strong
    .fetch_update(Relaxed, Relaxed, |n| {
        if n == 0 {
            return None;
        }

        // See comments in `Arc::clone` for why we do this (for `mem::forget`).
        if n > MAX_REFCOUNT {
            unsafe {
                abort();
            }
        }

        Some(n + 1)
    })
  1. The ordering parameters are in the opposite order to compare_exchange (although this doesn't come up in this particular case). It might be more straightforward for code to move over if the order was consistent.

  2. The return value being a Result doesn't bother me, as I don't have any use cases currently which wouldn't want to match on it in some way. If we'd like to make it non-essential to match on, a tuple return type could potentially be used, like (usize, Option<usize>), where the first is the previous value, and the second is the new value returned by the last call to the passed-in lambda.

  3. I also noticed that this method doesn't appear to exist for AtomicBool or AtomicPtr. It may be nice to add this method to those types too before stabilization.

In summary, I think I'd move the lambda parameter after the two ordering parameters, and make them match the parameter order used by the compare_exchange method.

Other than that, this seems like a handy API which makes writing CAS loops much cleaner, and I'd be happy to see it stabilized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.