Assume I have below cyclic data structure below, which requires using reference counting type.
First idea is that I create two independent Rc<Block>, and want to compute them in two indepedent threads, without locking, but because Rc is !Send, I cannot move the result out of a thread.
Then I have to use Arc and Mutex/RwLock instead, which requires lock operations.
I wonder if any solution to have cyclic strucutre being able to be computed in parallel without locking.
If you can ensure that there is only one reference to the Block (not sure if that's the case in your scenario), you can unwrap the Rc prior to sending the data:
use std::rc::Rc;
use std::thread::spawn;
#[derive(PartialEq, Eq, Debug)]
struct X(i32);
fn calculate() -> Rc<X> {
Rc::new(X(99))
}
fn main() {
let thread = spawn(move || {
let inner_rc = calculate();
// this only works if `inner_rc` has no clones:
Rc::try_unwrap(inner_rc).expect("more than one RC clone")
});
let outer_rc = Rc::new(thread.join().expect("thread failed"));
assert_eq!(*outer_rc, X(99));
}
Ah, I didn't understand your post properly. Unwrapping the Rc would also drop the inner value of the rc::Weak, I suppose. You could assert that the structure is cyclic (and has no other clones) by unwrapping it (which will make the parent field to become None inside), then just send the value part, and then reconstruct the Block outside the thread.
If you can make sure absolutely no Rc/Weak remains on the spawned thread. You can just opt into (super duper) unsafe with force-send-sync.
This also requires no reference to the cyclic structure is left on the main thread when you spawned worker thread. Basically, if you somehow can prove you are moving the whole cyclic structure through threads without any Rc/Weak pointing to it, then it's fine.
You don't need an Option. The Weak will be "invalidated" automatically because it's a "weak" reference (edit: and you can send only the value, which is Send).
What I mean is something like this:
use std::cell::RefCell;
use std::rc::{self, Rc};
use std::thread::spawn;
#[derive(Debug)]
struct Block {
value: RefCell<u32>,
parent: RefCell<rc::Weak<Block>>,
}
impl Block {
fn new(
value: u32,
) -> Rc<Self> {
Rc::new_cyclic(|block| Self {
value: RefCell::new(value),
parent: RefCell::new(block.clone()),
})
}
}
fn calculate() -> Rc<Block> {
Block::new(99)
}
fn main() {
let thread = spawn(move || {
let inner_rc = calculate();
// this only works if `inner_rc` has no clones:
Rc::try_unwrap(inner_rc).expect("more than one RC clone").value
});
let outer_rc = Rc::new_cyclic(|block| Block {
value: thread.join().expect("thread failed"),
parent: RefCell::new(block.clone()),
});
assert_eq!(*outer_rc.value.borrow(), 99);
let parent = rc::Weak::upgrade(&*outer_rc.parent.borrow());
assert!(Rc::ptr_eq(&outer_rc, &parent.unwrap()));
}
But not sure if that's worth the hassle. Maybe you would just want to calculate the value in the first place, instead of creating the cyclic Rc, then unwrapping it, and then recomposing it.
@jbe I see, the example data strcuture I given is just a simplied case, my use case has both a parent and some childrens, need to construct the whole tree, and send back after computation.
@zirconium-n , my thinking is that create a worker thread, construct the cyclic data structure, I can gurantee to compute it only inside the thread, then move the resulted tree out of thread
While I like @zirconium-n's solution, I would like to add that Rc is specifically meant for data structures which are not synchronized and which do not need to be sent to other threads. I believe the idiomatic way is to use Arcs whenever multithreading is involved. In the general case, I don't think the overhead of Arcs is really that big, since they don't lock (i.e. Arcsare lock-free).
However:
You could replace the Rc with an Arc, and this wouldn't introduce locks. The problem isn't using Arc, I believe, but the underlying problem is the following:
RefCell<_> is !Sync, thus Block is !Sync. This, in turn, means that sync::Weak<Block> would be !Send, which, in turn, makes Block being !Send. (PlaygroundPlayground)
So the underlying problem isn't Rc being !Send but that RefCell is !Sync. Not sure if that helps somehow, but I suppose this was already clear to you (but I wasn't aware of it until now).
Maybe a solution could be to create some sort of (integrated) RefCellArc / RefCellWeak type, which is lock-free and Send, but !Sync. (Not sure though.)
I'm thinking on something like that:
(edit: This is a bad example, don't use it.)
use std::cell::RefCell;
use std::sync::Arc;
pub struct RefCellArc<T>(pub RefCell<Arc<T>>);
unsafe impl<T: Send> Send for RefCellArc<T> {}
Is this sound? Edit: Probably it's not sound because it allows me to send an Arc where I shouldn't be allowed to do that (and thus effectively create a &T in another thread even if T: !Sync).
The example I gave there is very bad. I thought it might be sound, but it's not. Don't use it, please. If you want to use unsafe (which is often a bad idea anyway), then use @zirconium-n's code instead. Their code requires you to type unsafe when using it.
Unless I'm mistaken, my code above allows you to cause Undefined Behavior (UB) from safe Rust, which is unsound.
My idea was to somehow use the fact that you know the inner value is Send. But the inherent problem is that a RefCell allows mutation while having a shared reference. If you wrap a RefCell in an Arc, it can't be Send, because if the Arc was Send, then you could send a &RefCell to another thread, which can cause race conditions and UB.
I feel like to solve this problem in a clean way, you need something like sendable, which @SkiFire13 mentioned in the very beginning of this thread (possibly with Weak support though).
The only alternative I see is to convert the cyclic graph into a different structure for sending it, and then recreating it in the receiving thread.
I think this is an interesting problem, and I wonder if there is any better or easier (safe?) solution.
P.S. / Side note: If you decide to use unsafe, I think it is a good idea to always add SAFETY comments where you explain why each use of unsafe is sound. I also like to use #![deny(unsafe_op_in_unsafe_fn)] so that the compiler forces me to type unsafe even when I'm in unsafe functions.