Iterative Fork-Join for base case of divide-and-conquer

Question

I have a recursive divide and conquer algorithm that requires two computationally intensive base case tasks before starting the dividing. The initial base cases are independent tasks, so I want to do them in parallel. After the base cases, the dividing runs the same tasks with different inputs between 0 and 1, and based on the output decides whether or not to split again. I got the base cases to work by creating a task wrapper object that fakes the recursion, but this feels like a kludge, as follows:

public static void doSomething () {
    ForkJoinPool pool = new ForkJoinPool();
    private ArrayList<Object> al = new ArrayList<Object>();
    TaskWrapper tw = new TaskWrapper(true,-1);

    al.addAll(pool.invoke(tw));
}

@SuppressWarnings("serial")
public static class TaskWrapper extends RecursiveTask<ArrayList<Object>> {
    private ArrayList<Object> al = new ArrayList<Object>();
    private boolean arg;
    private double input;
    private Object out;

    TaskWrapper(boolean ar, double in){
        arg = ar;
        input = in;
    }

    @Override
    public ArrayList<Object> compute() {
        if (arg == false) {
            out = new Object(runIntensiveTask(input));
            al.add(out);
        }
        else {
            // Right Base Case
            TaskWrapper right = new TaskWrapper(false, 1);
            right.fork();

            // Left Base Case
            TaskWrapper left = new TaskWrapper(false, 0);
            al.addAll(left.compute());

            // Join with Right result
            al.addAll(right.join());
        }
        return al;
    }
}

Is there a simpler way to accomplish the same thing?

This is my first StackOverflow post, so please forgive any formatting or protocol errors. Thank you for the help.

Divide

With Java 8 you may be able to express the operations as a stream and make it parallel. – Shiftless

Answer 1

It never surprises me the way people use this framework. In a nutshell: The framework was devised to process balanced tree structures (D.A.G) When you use it for other than that, there are problems. You are not processing a balanced tree.

What Java needs is a general-purpose parallel engine, but what it has is this framework. So, you're doing the best you can. If it works, good. I can't see any alternative in Java7 but i"ll look more deeply. I would like to know how this performs under a profiler (say visualVM.) Since I don't have the intensiveTask class there is no way for me to proceed. The join() in Java7 creates "continuation threads" which can be really impact an application. Let us know what the profiler says.

Mystery

Indeed, and the rest of the time I use the algoithm after the base cases it is for a D.A.G. work breakdown. FWIW, the intensiveTask class is just Dijkstra's shortest path algorithm, using a binary heap priority queue, running on a graph of a million nodes and 16 million arcs. I appreciate the response, and any insight you find to do this base case stuff more elegantly. – Divide

Why bother with F/J for the base cases? Just create two independent threads and let them do the intensive work putting their results in slots 0, 1 respectively. You can run it all concurrently. – Mystery

True. I'm kind of new to concurrency, and hadn't tried out straight-up threads yet. I figured it out with not too much trouble though, and certainly is more straightforward than my fork/join trick. Since it's only two iterations, there isn't much of a performance difference between the two methods. – Divide