2

I have been studying the new feature in JDK 7, namely Fork and Join. In the Javadoc it states that in a ForkJoinTask one can not do fork only in the context of a ForkJoinPool. But it does not mention if the fork() method call creates a new thread or not.

The ForkJoinPool uses a work-stealing algorithm to balance the work between threads, but nowhere mentions how many threads are actually created.

I have a task which I should break up in a divide-et-impera manner but I am worried that ForkJoinPool creates too many threads and would decrease the performance of the execution because of the overhead of managing these threads.

Can someone help me with this?

yatskevich
  • 2,085
  • 16
  • 25
Szilard Mandici
  • 33
  • 3
  • 1
    I would assume that the whole point of Fork-Join is to free the developer from this calculation, and automagically determine the ideal number of threads given typical overheads and 100% parallel execution. Probably one-per-core. But I do not know for sure. – tucuxi Jul 16 '12 at 09:19
  • That is what I think too, but I am not sure and can't find any decent resource that would clear it to me and without confirmation I can't use it. – Szilard Mandici Jul 16 '12 at 09:22
  • 1
    The cost of extra threads is so close to zero as to not be worth worrying about. It is so many orders of magnitude less than the penalty for creating too few threads that creating a few extra threads is common. You shouldn't assume the people who developed your platforms are idiots and you should use the tools they gave you for the purposes they intended them. If they are idiots, you're screwed anyway. – David Schwartz Jul 16 '12 at 09:29
  • You have plenty to worry about. [What determines the number of threads a Java ForkJoinPool creates?][1] [1]: http://stackoverflow.com/questions/10797568/what-determines-the-number-of-threads-a-java-forkjoinpool-creates – edharned Jul 16 '12 at 18:29

1 Answers1

0

Fork does not (necessarily) create new threads. In my benchmark, it only creates 1 thread per available core + 1 extra thread. Attaching benchmark; call from main() as Factorizer.factorize(71236789143834319L), say. 

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class Factorizer extends RecursiveTask<Long> {

static ForkJoinPool fjPool = new ForkJoinPool();
static final int sequentialThreshold = 10000;

private long number, low, high;

Factorizer(long number, long low, long high) {
    this.number = number; this.low = low; this.high = high;
}

private long factorize() {
    if ((number % 2) == 0) {
        return 2;
    }
    // ensures i is odd (we already know number is not even)
    long i = ((low % 2) == 0) ? low + 1: low;
    for (/**/; i < high; i+=2) {
        if ((number % i) == 0) {
            return i;
        }
    }
    return number;
}

@Override
protected Long compute() {

    // ugly debug statement counts active threads
    System.err.println(Thread.enumerate(
            new Thread[Thread.activeCount()*2]));

    if (high - low <= sequentialThreshold) {
        return factorize();
    } else {
        long mid = low + (high - low) / 2;
        Factorizer left = new Factorizer(number, low, mid);
        Factorizer right = new Factorizer(number, mid, high);
        left.fork();
        return Math.min(right.compute(), left.join());
    }
}

static long factorize(long num) {
    return fjPool.invoke(new Factorizer(num, 2, (long)Math.sqrt(num+1)));
}
}

Note - this was only a test. Do not use this code to seriously try to factor anything big.

tucuxi
  • 17,561
  • 2
  • 43
  • 74