Extended atomic types

[ghost]

The standard library offers several primitive atomic types: Atomic{Usize,Isize,Bool,Ptr}. Nightly Rust also has Atomic{U8,I8,U16,I16,U32,I32,U64,I64}.

Those are the primitive types, and then there are crates that expand a little bit. Crate atomic has type Atomic<T> where T can be any type (small Ts that are Copy use primitive atomics, and large or non-Copy Ts simply get wrapped in a mutex). crossbeam has AtomicOption<T> (atomic Option<Box<T>>) and ArcCell<T> (atomic Arc<T>). There's also crate atomic-option with a wider set of methods on AtomicOption<T>.

Taking a step back, I'd summarize and rename all those extended atomic types like this:

• AtomicBox<T> - atomic Option<Box<T>> (equivalent AtomicOption<T>)
• AtomicArc<T> - atomic Option<Arc<T>> (similar to ArcCell<T>)
• AtomicCell<T> - atomic Cell<T> (equivalent to Atomic<T>)

What do you think about including such AtomicBox<T>, AtomicArc<T>, and AtomicCell<T> in Crossbeam?

What I'm attempting to do here is to come up with a well-thought-out set of complementary atomic types that is a natural extension to the primitve atomic types in the standard library. Any thoughts or ideas? Any other nice-to-have atomic types I'm missing?

[jeehoonkang]

I think the proposed nomenclature is more consistent than that of the current implementation. May I ask why AtomicBox and AtomicArc correspond to Option<Box> and Option<Arc>, not Box and Arc?

Also, I wonder what will be the relation of crossbeam-utils and atomic-option crates. Do we want to subsume the functionality of atomic-option?

[ghost]

Well, atomic Option<Box>/Option<Arc> are strictly more powerful than atomic Box/Arc, and also more commonly used, I believe (for non-atomic variants this may not be true, though). It's like that argument why we have Ptr<'scope, T> and don't have non-nullable Ref<'scope, T>. Moreover, our Atomic<T> type is a nullable atomic pointer and we don't have a non-nullable variant.

We could have the whole palette of AtomicBox/AtomicArc/AtomicOptionBox/AtomicOptionArc, but my speculation is that the utility of having non-nullable variants will be low. Just my guess, though.

Yeah, I was thinking of subsuming the functionality of atomic and atomic-option crates. Pinging @Amanieu and @reem to see what they think about this.

[jeehoonkang]

I wonder if we can efficiently implement AtomicBox and AtomicArc. If they don't fit in a single word, we should resort to blocking implementation for portability, right? Can we ensure that they are fit into a single word?

[ghost]

// Accepts only `T: Sized`, pointers to which always fit into a single word.
struct AtomicBox<T> { inner: AtomicPtr<T> }

// Also accepts `T: !Sized`, pointers to which are fat (two words).
// We would need advanced specialization for this (not yet implemented).
struct AtomicBox<T: ?Sized> { inner: ??? }

I don't think we can easily support fat pointers at all, at least not until full specialization gets into Rust.

[arthurprs]

AtomicArc and AtomicBox should probably support Option, even if the name desn't say so :+1:

I don't have a strong opinion on supporting arbitrary sized stuff (?Sized and AtomicCell).

[ghost]

Another primitive we might want is something like Pinboard. This is basically just an epoch-protected Box. The interface would be along the lines of:

impl<T: Send + 'static> EpochBox<T> {
    fn new(t: T) -> Self;
    fn remove(&self);
    fn set(&self, t: T);
}

impl<T: Send + Sync + 'static> EpochBox<T> {
    fn get<'scope>(&self, scope: &'scope Scope) -> Option<&'scope T>;
    fn take<'scope>(&self, scope: &'scope Scope) -> Option<&'scope T>;
    fn swap<'scope>(&self, t: T, scope: &'scope Scope) -> Option<&'scope T>;
}

impl<T: Send + Sync + Clone + 'static> EpochBox<T> {
    fn get_clone(&self) -> Option<T>;
    fn take_clone(&self) -> Option<T>;
    fn swap_clone(&self, t: T) -> Option<T>;
}

[arthurprs]

~The second group of functions are too easy to misuse (as in holding the pin for too long). This was one of the reasons we preferred the closure api instead of handle.~ edit: nevermind, I just saw that you need to be in a scope to use them.

EpochArc also works well.

[jeehoonkang]

To my eyes, https://github.com/crossbeam-rs/crossbeam-utils/issues/2 suggests that we should not allow users to specify Ordering for atomic types, at least for AtomicBox and AtomicArc.

For AtomicCell<T>, the only implementation I can think of for big T (of size > 2 words) is just locking: we cannot effectively guarantee atomicity for a big type. @stjepang Is it the implementation you thought of?

[ghost]

@jeehoonkang Yeah, I'm thinking of AtomicCell<T> as similar to std::atomic in C++, where it uses atomic instructions for small types and mutexes for bigger types.

[Amanieu]

You may want to have a look at this crate, which does exactly that.

[Amanieu]

The disadvantage of using a mutex is that the crate won't work with no_std any more. This is why I used spinlocks in the atomic crate.

[spacejam]

What do folks think about supporting double-word atomics?

[Amanieu]

@spacejam It should be exposed as AtomicU128 / AtomicI128 on platforms that support it.

[spacejam]

@Amanieu in particular I'm interested in dw cas that runs on ARM 32 (6k+) for the equivalent of AtomicU64 so that sled can easily support that architecture.

[Amanieu]

AtomicU64 should already work on some ARM targets (v6 and above). These targets are v6 and above:

• arm-unknown-linux-gnueabi
• arm-unknown-linux-gnueabihf
• armv7-unknown-linux-gnueabihf

[jeehoonkang]

@spacejam I'm also waiting for DWCAS to land in Rust. It will enable a whole new class of concurrent algorithms, e.g. LCRQ for starters. It was not possible even in C++, as DWCAS is not supported in its standard library!

[spacejam]

@jeehoonkang there is a bunch of code I'm looking forward to refactoring once DWCAS is available! Super excited for it :)

[Amanieu]

@jeehoonkang DWCAS is supported in C++ through the generic std::atomic<T> type. Just make T a 2-word struct.