Mutating data behind references stored in a Vec?

1

I'm working on today's Advent of Code puzzle and it involves modeling how a few processes run, feeding input into the next process in a circular chain, and getting a result out of it once all the processes halt. I've been working in Rust for this, and have come to a problem with the borrowchecker that I don't understand how to get past.

A prior level modeled only a single pass of this chaining shape, forwarding the result from one process to the next one, and eventually stopping with the last process and waiting for it to finish:

A -> B -> C -> {answer}

Now I have to forward the output from one process to the next, looping back into the first process many times until the whole system stops

+-> A -> B -> C -+
^                |
+---<----<-------+ = = => {answer, when system stops}

When I was modelling the one-way chain, I could use vectors for the pipes and advance the process by calling a function that mutates the vectors, pulling data off the input pipe and pushing data onto the output pipe, which would become the input pipe for the next process:

    // run processes piping in a line, a -> b -> c
    next_step(&mut process_a_state, &mut stdin_a, &mut stdin_b);
    next_step(&mut process_b_state, &mut stdin_b, &mut stdin_c);
    next_step(&mut process_c_state, &mut stdin_c, &mut stdin_a);

My plan for modelling the ring of processes is to keep a Vec of tuples that contain references to the process states and pipes, and then iterate over them until the processes signal that they should no longer be called:

    // run processes piping ring:   +-> a -> b -> c -+
    //                              |                |
    //                              +---<----<----<--+
    let mut schedule_ring = vec![
     (process_a_state, &stdin_a, &stdin_b),
     (process_b_state, &stdin_b, &stdin_c),
     (process_c_state, &stdin_c, &stdin_a),
    ];
    loop {
        let (mut current_state, mut pipe_in, mut pipe_out) = schedule_ring.remove(0);
        let should_we_stop = next_step(&mut current_state, &mut pipe_in, &mut pipe_out);
        schedule_ring.push((current_state, pipe_in, pipe_out));
        if should_we_stop {
            break;
        }
    }

However, this throws a lot of compiler errors about references and mutable references. I haven't figured out the right way to throw in Rc's or mutable references into my ring of processes to get this to compile. I'm not sure what is available for me to use, nor if I should be changing the design of my model to avoid the tricky memory stuff I'm trying to accomplish in Rust right now.

I have what I think is a minimal toy example that demonstrates how process state can be advanced, and how I've currently designed my pipes. This should be able to all run in a single thread, although processes may need to skip if they are blocked reading from their stdin pipe if the process in front of them does not currently have input for it to consume. I was hoping that since this is all single threaded I could store my process states and pipe references in a queue that cycles through all the processes, but I'm missing how to use Rust correctly here.

2

Sounds like a case where you'd need to store multiple references at once, which is not allowed statically. Consider replacing the raw references with RefCell in order to opt in to dynamic borrow checking.

1 Like
3

I solved the first part of this problem just using VecDeques - there's no need for cells or anything because you can just run one amplifier at a time.

For the second part the amplifiers run in parallel and all communicate with each other, so I created mpsc::channels for communication between the amplifiers, and then ran each amplifier on a separate thread. I still didn't need any Arcs, cells or other synchronisation primitive.

1 Like
4

Good tip! I've updated my code from using raw references to using RefCell. Here's what it used to look like, with raw references:

    let mut stdin_a = vec![];
    let mut process_a_state = vec!["a".to_string()];
    let mut stdin_b = vec![];
    let mut process_b_state = vec!["b".to_string()];
    let mut stdin_c = vec![];
    let mut process_c_state = vec!["c".to_string()];
    stdin_a.push(0); // seed the chain of inputs

    let mut schedule_ring = vec![
     (process_a_state, &stdin_a, &stdin_b),
     (process_b_state, &stdin_b, &stdin_c),
     (process_c_state, &stdin_c, &stdin_a),
    ];
    loop {
        let (mut current_state, mut pipe_in, mut pipe_out) = schedule_ring.remove(0);
        let should_we_stop = next_step(&mut current_state, &mut pipe_in, &mut pipe_out);
        schedule_ring.push((current_state, pipe_in, pipe_out));
        if should_we_stop {
            break;
        }
    }

And now re-written to put the mutable stdin/stdout pipes behind RefCell's

    use std::cell::RefCell;
    let mut stdin_a = vec![];
    let process_a_state: Vec<String> = vec!["a".to_string()];
    let stdin_b = vec![];
    let process_b_state = vec!["b".to_string()];
    let stdin_c = vec![];
    let process_c_state = vec!["c".to_string()];
    stdin_a.push(0);  // seed the chain of inputs
    
    let stdin_a_ptr = RefCell::new(stdin_a);
    let stdin_b_ptr = RefCell::new(stdin_b);
    let stdin_c_ptr = RefCell::new(stdin_c);

    let mut schedule_ring = vec![
     (process_a_state, &stdin_a_ptr, &stdin_b_ptr),
     (process_b_state, &stdin_b_ptr, &stdin_c_ptr),
     (process_c_state, &stdin_c_ptr, &stdin_a_ptr),
    ];
    loop {
        let (mut current_state, pipe_in, pipe_out) = schedule_ring.remove(0);
        let should_continue = next_step(&mut current_state, &mut pipe_in.borrow_mut(), &mut pipe_out.borrow_mut());
        schedule_ring.push((current_state, pipe_in, pipe_out));
        if !should_continue {
            break;
        }
    }

Updated my broken example to work with RefCells here

Ah -- yeah that is clever. Relying on threads and channels to synchronize the amplifier processes means you don't need to worry about coming up with your own scheduling strategy like I did. As it turns out, the 'schedule ring' approach I designed had a bug in that I was reusing some of the same variable names, and ended up accidentally copying a process's prior state back into the job queue while the FIFO pipes between processes were still getting read from. As a result, when I first got my solution to compile with RefCell's, all of my processes immediately halted because they consumed their input but their internal state did not advance forwards.

If I relied on the OS to schedule my processes for me I probably would not have run into this bug, because each process would not need to spit its state out for my home-grown scheduler to put back on the queue.

5

Hah! That's exactly what I ended up doing, too. I think it says a lot about Rust that a multi-threaded solution was a good, safe option. If I'd been writing C or C++ I'd almost certainly not gone the multi-threaded route. Or at the very lease it probably wouldn't have worked on the first try... :wink:

1 Like
6

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.