Multithreading and recursion together

Question

I have recursive code that processes a tree structure first. The code basically looks like this:

function(TreeNode curr) { if (curr.children != null && !curr.children.isEmpty()) { for (TreeNode n : curr.children) { //do some stuff function(n); } } else { //do some other processing } } 

I want to use threads to make it faster. Most of the time is spent going through, so I don’t want to just create a thread to handle “other processing”, because it doesn’t take so long. I think I want to fork threads to do something, but how will this work?

Answer 1

This is a good example for the Fork / Join framework , which should be included in Java 7. As a stand-alone library for use with Java 6, you can download it here .

Something like that:

 public class TreeTask extends RecursiveAction { private final TreeNode node; private final int level; public TreeTask(TreeNode node, int level) { this.node = node; this.level = leve; } public void compute() { // It makes sense to switch to single-threaded execution after some threshold if (level > THRESHOLD) function(node); if (node.children != null && !node.children.isEmpty()) { List<TreeTask> subtasks = new ArrayList<TreeTask>(node.children.size()); for (TreeNode n : node.children) { // do some stuff subtasks.add(new TreeTask(n, level + 1)); } invokeAll(subtasks); // Invoke and wait for completion } else { //do some other processing } } } ... ForkJoinPool p = new ForkJoinPool(N_THREADS); p.invoke(root, 0); 

The key point of the fork / join framework is the theft of work - when waiting for the completion of subtasks, the thread performs other tasks. This allows you to write the algorithm in a simple way, avoiding problems with thread depletion, as the naive apporach with ExecutorService will have.

Answer 2

In the // do some stuff code block, where you work with a separate Node, you can instead send the Node to some ExecutorService (in the Runnable form, which will work on Node).

You can configure the ExecutorService that you use to back up a pool of a certain number of threads, which allows you to separate the "processing" logic (along with the logic for creating threads, creation quantities, etc.) from your tree parsing logic.

Answer 3

This solution assumes that processing occurs only on leaf nodes and that the actual tree recursion does not take much time.

I would call the thread of the calling thread, and then the BlockingQueue workers who process leaves through the thread pool. I do not handle InterruptedException in several places here.

 public void processTree(TreeNode top) { final LinkedBlockingQueue<Runnable> queue = new LinkedBlockingQueue<Runnable>(MAX_NUM_QUEUED); // create a pool that starts at 1 threads and grows to MAX_NUM_THREADS ExecutorService pool = new ThreadPoolExecutor(1, MAX_NUM_THREADS, 0L, TimeUnit.MILLISECONDS, queue, new RejectedExecutionHandler() { public void rejectedExecution(Runnable r, ThreadPoolExecutor e) { queue.put(r); // block if we run out of space in the pool } }); walkTree(top, pool); pool.shutdown(); // i think this will join with all of the threads pool.awaitTermination(WAIT_TILL_CHILDREN_FINISH_MILLIS, TimeUnit.MILLISECONDS); } private void walkTree(final TreeNode curr, ExecutorService pool) { if (curr.children == null || curr.children.isEmpty()) { pool.submit(new Runnable() { public void run() { processLeaf(curr); } }); return; } for (TreeNode child : curr.children) { walkTree(child, pool); } } private void processLeaf(TreeNode leaf) { // ... }