How to use LCell in a multithreaded context

[jrmoulton]

Continuation from the discussion on pull request #4.
Yep. This attempt is coming because of the talk surrounding the ghostcell and the paper talking about it. From what I understand the LCell in this crate is essentially an implementation of those same principles. I could totally just be misunderstanding the paper but in section 1.2 in the design section it seems to suggest that it would be possible to avoid the overhead of waiting in a lock introduced by an RwLock (or a mutex) by letting the control of mutability of individual nodes of a linked list (or in my case indices of a vector) be controlled at a higher level and letting different elements of a data type have exclusive mutable access without a lock. Is that a correct understanding?

The section of my code using LCell is the following:

let image = Arc::new(LCell::new(vec![0; (LENGTH * HEIGHT * 3) as usize]));
LCellOwner::scope(|mut owner| {
        let handles: Vec<_> = (0..num_threads)
            .map(|thread| {
                let image_clone = Arc::clone(&image);
                thread::Builder::new()
                    .name(thread.to_string())
                    .spawn(move || {
                        for x in (thread * cols_p_t)..((cols_p_t * thread) + cols_p_t) {
                            for y in 0..HEIGHT {
                                mandelbrot(x, y, &mut owner, &Arc::clone(&image_clone));
                            }
                        }
                    })
                    .expect("couldn't build thread")
            })
            .collect();
        for handle in handles {
            handle.join().unwrap();
        }

If this could avoid the overhead of a thread lock, the error that I'm dealing with has to do with lifetimes inside of a closure.

cannot infer an appropriate lifetime for lifetime parameter 'id in function call due to conflicting requirements
expected &mut LCellOwner<'>
found &mut LCellOwner<'>
but, the lifetime must be valid for the static lifetime...

Is there any way to use the LCell in a multithreaded context (instead of a mutex) with the goal of avoiding thread locks?

[uazu]

What GhostCell provides (or TCell or QCell for that matter) is the ability to move the ownership from the cell itself to the 'owner' (which is called a 'token' in the GhostCell paper). So to make this work for your code, you'd need to divide the image into num_threads parts before spawning all the threads. Each part needs to have its own owner. Then one owner would be passed to each thread.

The fundamental problem with this code as it stands is that it only has one owner, and the threads can't all share the same owner mutably. In that section 1.2 it does actually say "To achieve the same for our doubly-linked list, we would use RwLock<GhostToken<'id>>." So you could do that, but that isn't going to be any more efficient than just putting a RwLock or Mutex around the whole Vec. Where GhostCell provides an advantage in section 1.2 is converting N rw-locks into 1 rw-lock, but in your case you already have just 1 rw-lock.

However if you're going to split up the image into num_threads parts, then I think you don't actually need to use GhostCell at all. You could just use slice::split_at_mut to break it up into mutable slices, and pass a mutable slice to each thread. To make that work you'd have to use scoped threads, though, because there is a borrow going on.

[jrmoulton]

Ahhh I see now. Ok this makes sense. And thanks for the suggestion!

[uazu]

Also, I should add that starting with LCell and LCellOwner (or equivalently GhostCell) makes things a lot more complicated, because the lifetime errors can be very confusing. If you had started with QCell, the errors would have been clearer and you might have figured out all this for yourself. QCell and TCell have the same borrowing characteristics as LCell and GhostCell. (TLCell is different)