Processing trees in parallel in Rust

Question

I have a tree structure in Rust which I would like to process in parallel. My real problem is more complicated, but this is essentially the serial version I have now:

#[derive(Debug)]
enum BinaryTree {
    Node(Box<BinaryTree>, Box<BinaryTree>),
    Leaf(i32),
}

use BinaryTree::*;

impl BinaryTree {
    /// Applies the given function to every leaf in the tree
    fn map<F: Fn(i32) -> i32>(&mut self, f: &F) {
        match *self {
            Node(ref mut tree1, ref mut tree2) => {
                tree1.map(f);
                tree2.map(f);
            }
            Leaf(ref mut n) => *n = f(*n),
        }
    }
}

I'd like to parallelize this using:

• No locks
• A thread pool, or otherwise not having to re-create threads
• (Preferably) no unsafe code

The problem seems very natural to parallelize: At every node, process each child node concurrently, potentially falling back to the serial version at some point. However, this requires scoped threads, which aren't in the standard library yet. I settled for the scoped-pool crate, and arrived at this solution:

extern crate scoped_pool;

impl BinaryTree {
/// Applies the given function to every leaf in the tree
    fn map_parallel<F>(&mut self, f: &F, scope: &scoped_pool::Scope)
        where F: Fn(i32) -> i32 + Send + Sync
    {
        match self {
            &mut Node(ref mut tree1, ref mut tree2) => {
                // Create new, smaller scope
                scope.zoom(|scope2| {
                    // Concurrently process child nodes
                    scope2.recurse(|scope3| {
                        tree1.map_parallel(f, scope3);
                    });
                    scope2.recurse(|scope3| {
                        tree2.map_parallel(f, scope3);
                    });
                }
                           );},
            &mut Leaf(ref mut n) => *n = f(*n),
        }
    }
}
fn main() {
    let mut tree = Node(
        Box::new(Node(
            Box::new(Node(
                Box::new(Node(
                    Box::new(Node(
                        Box::new(Leaf(11)),
                        Box::new(Leaf(15)))),
                    Box::new(Leaf(13)))),
                Box::new(Leaf(19)))),
            Box::new(Leaf(5)))),
        Box::new(Leaf(10)));

    let thread_pool = scoped_pool::Pool::new(4);
    tree.map_parallel(&|n| n + 1, &scoped_pool::Scope::forever(thread_pool));
    println!("{:?}", tree);
}

However, this appears to get stuck in a deadlock, and I don't understand why. What is the idiomatic way to process trees in parallel in Rust?

Answer 1

in a deadlock, and I don't understand why

You have 4 threads, then call map_parallel once, which ties up a thread, which calls map_parallel itself before it exits, which ties up a thread, and so on. You ran out of threads before any thread could finish. Switching to 5 threads "fixes" the deadlock in this example. Obviously, switching the number of threads depending on the depth of the tree is not ideal.

---

I'd recommend splitting up your code into separate concerns. Since you are already handling things in parallel, each node needs to be independent from each other. That means you can implement an iterator:

impl BinaryTree {
    fn iter_mut(&mut self) -> IterMut {
        IterMut { queue: vec![self] }
    }
}

struct IterMut<'a> {
    queue: Vec<&'a mut BinaryTree>,
}

impl<'a> Iterator for IterMut<'a> {
    type Item = &'a mut i32;

    fn next(&mut self) -> Option<Self::Item> {
        match self.queue.pop() {
            Some(tree) => {
                match *tree {
                    Leaf(ref mut n) => Some(n),
                    Node(ref mut left, ref mut right) => {
                        self.queue.push(right);
                        self.queue.push(left);
                        self.next() // bad recursive, see note
                    }
                }
            }
            None => None,
        }
    }
}

This is nice because it removes any entanglement of the threading library with the data structure. With this, you can then choose to do single-threaded mutation:

for node in tree.iter_mut() {
    *node += 1;
}

Or threaded:

let thread_pool = scoped_pool::Pool::new(2);
thread_pool.scoped(|scope| {
    for node in tree.iter_mut() {
        scope.execute(move || {
            *node += 1;
        })
    }
});

---

You'll note that I used tail-recursive code in the iterator. Rust doesn't optimize this, so you should change it to the imperative equivalent.

You may also want to investigate using a zipper for the iterator.