CODEWITHSUNDEEP
rust
t348575
t348575

Reputation: 763

Lockless unsafe data sharing bus in rust

I am relatively new to rust, and I want to use Arc<> to give immutable access to some data to many threads, however I want to be able for the original owner of that Arc to have write access without introducing any kind of lock (mutex, rwlock etc). My application guarantees that there is only ever a single thread producing (writing) to the data inside the arc (so never a write data race to the arc). But there are many threads reading the data in the arc. (reading, not consuming). How do I implement this? Whenever I go near Arc and try to mutate I am not allowed to. Obviously I understand unsafe is needed for this.

The bus is created and cloned over to the reader threads.

use std::borrow::BorrowMut;
use std::sync::Arc;

type Data<T> = Arc<Vec<T>>;

pub struct Bus<T> {
    data: Data<T>
}

impl<T: Clone + Send + Sync + 'static> Bus<T> {
    pub fn new() -> Self {
        let data: Data<T> = Arc::new(Vec::new());
        
        {
            let mut data = data.clone();
            std::thread::spawn(move || {
                let a = data.borrow_mut();
                a.push(value); // write to vector
            }).join();
        }

        Bus {
            data
        }
    }

    pub fn read(&self, idx: usize) -> T {
        self.data[idx].clone()
    }
}

gives:

cannot borrow data in an Arc as mutable

Upvotes: 1

Views: 680

Answers (2)

Sprite
Sprite

Reputation: 3763

No, if a Vec<T> is written by one thread and read by multiple threads, here is a data race.

There are some other lock-free options, but they all different from your example.

  • If T is a simple type (a common integer type or a type with appropriate length and Copy trait implemented) and the Vec length is fixed, you can use a fixed-length array + atomic type. You can safely read and write each element, but cannot grow the array.

    Crate atomic provides a Atomic<T> type and you can check if it is lock-free at compile time.

  • AFAIK, a lock-free Vec is not possible, however some crates offer lock-free queues. But obviously a queue cannot be accessed by an index.

Upvotes: 0

cameron1024
cameron1024

Reputation: 10186

Disclaimer - Concurrent data structures are hard and I'm not an expert in them

The error message you get is essentially saying "you can't mutate the contents of an Arc, because other people could be reading it while you change it, causing a data race.

The typical solution is to use an Arc<Mutex<T>>. A Mutex allows you to go from an immutable reference to a mutable reference by first locking the mutex.

However, you've indicated you don't want to use locking.

So if Mutex (and similar things like RwLock are off the table, you'll need a Vec-like data structure that allows mutation via immutable reference.

However, my understanding is there's generally very little reason to prefer a "concurrent" or "lock free" Vec over a simple Arc<Mutex<Vec<T>> (or probably an Arc<RwLock<T>> in your case). In general, the performance will be similar.

This reddit thread has some insight into why such data structures don't really exist if you want some further reading.

There are also concurrent HashMap-like structures if you find that model is also suitable. Maps are generally more amenable to this kind of lock-free or highly concurrent workload.

For example, chashmap uses per-bin locking (i.e. each bin in the map has its own lock), so lock contention stays relatively low.

There is also evmap which is entirely lock-free, but comes at the cost of being only eventually consistent and using ~2x the memory. It essentially maintains 2 copies of your map, one of which is a "read map" and the other is a "write map". You can then "publish" the changes to apply the writes.

Upvotes: 2

Related Questions