Single thread :: cell = multi thread ::?

1

I would strongly prefer a lock-free solution.

Is there some struct Magic<T> with the following property:

for any T: Copy, m: Magic<T> we have the following property:

if thread1 executes m.write(t1); and thread2 executes m.write(t2);

it is guaranteed that the answer is is either t1 or t2. I.e. it fully writes one or the other, not part of one, part of other.

We do not have the guarantee that sizeof(T) <= sizeof(u64).

2

Maybe you're looking for AtomicCell in crossbeam::atomic - Rust

3

This is interesting. Quoting atomic_cell.rs - source :

const fn atomic_is_lock_free<T>() -> bool {
    // HACK(taiki-e): This is equivalent to `atomic! { T, _a, true, false }`, but can be used in const fn even in Rust 1.36.
    let is_lock_free = can_transmute::<T, AtomicUnit>()
        | can_transmute::<T, atomic::AtomicU8>()
        | can_transmute::<T, atomic::AtomicU16>()
        | can_transmute::<T, atomic::AtomicU32>();
    #[cfg(not(crossbeam_no_atomic_64))]
    let is_lock_free = is_lock_free | can_transmute::<T, atomic::AtomicU64>();
    // TODO: AtomicU128 is unstable
    // let is_lock_free = is_lock_free | can_transmute::<T, atomic::AtomicU128>();
    is_lock_free
}

I am not familiar with this code, but it looks like: up to u32, it is lock free, u64 may or may not be lock free, and beyond u64 it uses locks. Is that correct ?

4

For an arbitrarily-large value, your processor can't do it lock-free. There's nothing Rust can do about that.

(Well, unless you make your data smaller -- perhaps by putting it inside a Box, so you can cmpxchg the pointer instead.)

2 Likes
5

Is the best we can do here: add a level of indirection.

I.e. we have a Vec<T>, have different threads write to different locations of this Vec. Then, we overwrite a usize atomically, which points to which entry of the Vec<T> we want.

6

But you'll need to lock the Vec sometimes -- to reallocate it, if nothing else.

7

Suppose we can bound the number of threads as N, and then we create a vec![T; 2 * N]. Each thread is assigned 2 locs, ensuring it never writes to the one being read.

8

At this point, I am no longer sure if Lock is cheaper.

9

How about the arc-swap crate?

1 Like
10

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.