Java – multithreading and recursion together
I have recursive code that deals with tree structures in a depth first manner The code is basically as follows:
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 speed up completion Most of the time is spent on traversal, so I don't want to create only one thread to handle "other processing" because it doesn't take that long I think I want to fork threads when "doing something", but how does it work?
Solution
This is a good example of fork / join framework, which will be included in Java 7 As a separate library for use with Java 6, you can download it here
Something like this:
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 fork / join framework is work stealing - executing other tasks while waiting for the subtask thread to complete As a naive application of executorservice, it allows you to write algorithms directly while avoiding thread exhaustion