Why is Fork/Join from JDK7 slow?

Question

Java

I am writing a simple program to generate a Farey series
At the beginning I wrote a simple recursion, a series of the 500th order generates in 100ms
Hidden text

public class NestedIntervals {
    private final int base;

    private NestedIntervals(int base) {
        this.base = base;
    }

    public static NestedIntervals base(int base) {
        return new NestedIntervals(base);
    }

    private List<Fraction> getFarey(Fraction left, Fraction right) {
        Fraction mediant = new Fraction(left.getNumerator()+right.getNumerator(), left.getDenominator()+right.getDenominator());
        if (mediant.getDenominator()>base) {
            return Collections.emptyList();
        }
        List<Fraction> result = new LinkedList<>();
        result.addAll(getFarey(left, mediant));
        result.add(mediant);
        result.addAll(getFarey(mediant, right));
        return result;
    }

    public List<Fraction> getFarey() {
        List<Fraction> result = new LinkedList<>();

        Fraction left = new Fraction(0, 1);
        Fraction right = new Fraction(1, 1);

        result.add(left);
        result.addAll(getFarey(left, right));
        result.add(right);

        return result;
    }

    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        List<Fraction> farey = NestedIntervals.base(500).getFarey();

        int max = 0;
        for (Fraction f: farey) {
            if (f.getDenominator()>max) {
                max = f.getDenominator();
            }
        }

        System.out.printf("Total %dms", System.currentTimeMillis()-time);
    }
}

On series of higher order, it works slowly. Conceived to rewrite on Fork/Join
Hidden text

public class FareyList extends RecursiveTask<List<Fraction>>{
    private final static int base = 500;

    private final Fraction left;
    private final Fraction right;

    private FareyList(Fraction left, Fraction right) {
        this.left = left;
        this.right = right;
    }

    @Override
    protected List<Fraction> compute() {
        Fraction mediant = new Fraction(left.getNumerator()+right.getNumerator(), left.getDenominator()+right.getDenominator());
        if (mediant.getDenominator()>base) {
            return Collections.emptyList();
        }

        FareyList leftList = new FareyList(left, mediant);
        FareyList rightList = new FareyList(mediant, right);
        leftList.fork();
        rightList.fork();

        List<Fraction> result = new LinkedList<>();
        result.addAll(leftList.join());
        result.add(mediant);
        result.addAll(rightList.join());
        return result;
    }

    public static List<Fraction> getFareyList() {
        List<Fraction> result = new LinkedList<>();

        Fraction left = new Fraction(0, 1);
        Fraction right = new Fraction(1, 1);

        FareyList task = new FareyList(left, right);

        new ForkJoinPool().invoke(task);

        result.add(left);
        result.addAll(task.join());
        result.add(right);

        return result;
    }

    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        List<Fraction> farey = FareyList.getFareyList();

        int max = 0;
        for (Fraction f: farey) {
            if (f.getDenominator()>max) {
                max = f.getDenominator();
            }
        }

        System.out.printf("Total %dms", System.currentTimeMillis()-time);
    }

}

This code runs in 12 seconds. A 4-core Xeon should be faster than the recursive version, but in practice the opposite is true. What am I doing wrong? Is Fork/Join suitable for such a task at all?

Answer 1

In-zero, you tried a startup, compilation and raising threads in FJP, with which I congratulate you.
First, make a transition to the sequential version, starting with some small threshold. Otherwise, the overhead of sawing and task management will gobble up everything.
Second, the way to join is worse than "t1.fork(); t2.fork(); t1.join(); t2.join () ”you can’t imagine. The best known way is doing "t1.fork(); t2.compute(); t1.join()".

Answer 2

This is expected behavior as java is slow.
But seriously, first read the presentation from TheShade on this topic (you may be especially interested in experimenting with the join method, from slide 30). In addition, there is an open source utility with which you can quite easily find plugs : github.com/shipilev/fjp-trace
compilation, class loading, but not FJP).

Answer 3

1) Do 2 runs of the calculation, and calculate the time in the 2nd run (the time should decrease due to the lack of class loading)
2) When splitting the task, do not reach the very end, do some number of forks, and then just call the recursive function

Answer 4

I rewrote your code avoiding unnecessary creation of objects and transferring objects from collection to collection. Parallel options are slower than recursive, but not dramatic - only a few times.
As already correctly pointed out, slower due to the overhead of maintaining subtasks. If we manage to enlarge the subtasks, we will get a real gain.

Answer 5

If you need it faster, try this thing habrahabr.ru/post/149552

Answer 6

I don’t understand the meaning of the task, so I can’t say anything about the code (some recursive creation of ForkJoinPools confuses me, which obviously goes beyond the number equal to 1), but there is a general rule. If you have calculations that need to be performed on the processor, then it makes sense to set the pool equal to the number of cores available to the JVM. Therefore, I would create 1 ForkJoinPool (the default constructor makes the parallelism equal to the number of cores), and submit tasks there. rather than creating a new pool each time for each split (or whatever you are doing there).

Answer 7

I forgot to ask, the sequential version is what?

Answer 8

In general, if you want to achieve optimal speed, then you need to manually control the threads. You create a fixed pool of threads (for example, one per core), and then you throw your calculations into this pool, which are queued and processed sequentially. I haven’t worked with this for a long time, so I couldn’t give you an example right here ...

Answer 9

And try to play around with new ForkJoinPool(nThreads), make nThreads = 2, for example.

Answer 10

Rewrote without using recursion, since the stack is not the strongest side of java, and also added a version with ExecutorService
My test results for BASE=5000
Total 14306ms (recursive implementation)
n Total 1725ms (non-recursive implementation)
m Total 1241ms (multi-threaded non-recursive implementation)

Source

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class NestedIntervals {
    private static ExecutorService executor;
    private final int base;

    private NestedIntervals(int base) {
        this.base = base;
    }

    public static NestedIntervals base(int base) {
        return new NestedIntervals(base);
    }

    public static class Fraction {
        private int denominator;
        private int numerator;

        public Fraction(int numerator, int denominator) {
            super();
            this.numerator = numerator;
            this.denominator = denominator;
        }

        public int getDenominator() {
            return denominator;
        }

        public void setDenominator(int denominator) {
            this.denominator = denominator;
        }

        public int getNumerator() {
            return numerator;
        }

        public void setNumerator(int numerator) {
            this.numerator = numerator;
        }

        @Override
        public String toString() {
            return numerator + "/" + denominator;
        }

    }

    private List<Fraction> getFarey(Fraction left, Fraction right) {
        Fraction mediant = new Fraction(left.getNumerator()
                + right.getNumerator(), left.getDenominator()
                + right.getDenominator());
        if (mediant.getDenominator() > base) {
            return Collections.emptyList();
        }
        List<Fraction> result = new LinkedList<Fraction>();
        result.addAll(getFarey(left, mediant));
        result.add(mediant);
        result.addAll(getFarey(mediant, right));
        return result;
    }

    public List<Fraction> getFarey() {
        List<Fraction> result = new LinkedList<Fraction>();

        Fraction left = new Fraction(0, 1);
        Fraction right = new Fraction(1, 1);

        result.add(left);
        result.addAll(getFarey(left, right));
        result.add(right);

        return result;
    }

    public List<Fraction> getFareyNonRecurcive() {
        LinkedList<Fraction> result = new LinkedList<Fraction>();
        Fraction left = new Fraction(0, 1);
        Fraction right = new Fraction(1, 1);
        Fraction mediant = null;
        result.add(left);
        result.add(right);
        ListIterator<Fraction> iterator = result.listIterator();
        left = iterator.next();
        while (iterator.hasNext()) {
            right = iterator.next();
            int denominator = left.getDenominator() + right.getDenominator();
            if (denominator <= base) {
                mediant = new Fraction(left.getNumerator()
                        + right.getNumerator(), denominator);
                iterator.previous();
                iterator.add(mediant);
                iterator.previous();
            } else {
                left = right;
            }
        }
        return result;
    }

    public List<Fraction> getFareyNonRecurciveMultiThread(int threads) {
        List<Fraction> result = null;
        if (threads <= 1) {
            result = getFareyNonRecurcive();
        } else {

            LinkedList<Fraction> ret = new LinkedList<Fraction>();
            List<Future<LinkedList<Fraction>>> futureList = new
                    ArrayList<Future<LinkedList<Fraction>>>();
            // fill params
            LinkedList<Fraction> params = fillParams(threads);
            ListIterator<Fraction> listIterator = params.listIterator();
            Fraction first = listIterator.next();
            while (listIterator.hasNext()) {
                Fraction second = (Fraction) listIterator.next();
                Future<LinkedList<Fraction>> future = executor
                        .submit(new FareyCallable(first, second, base));
                futureList.add(future);
                first = second;
            }
            try {
                for (int i = 0; i < futureList.size(); i++) {
                    if (i == 0) {
                        ret.addAll(futureList.get(i).get());
                    } else {
                        LinkedList<Fraction> linkedList = futureList.get(i)
                                .get();
                        linkedList.pollFirst();
                        ret.addAll(linkedList);
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }

            result = ret;
        }
        return result;
    }

    private LinkedList<Fraction> fillParams(int threads) {
        LinkedList<Fraction> params = new LinkedList<Fraction>();
        params.add(new Fraction(0, 1));
        params.add(new Fraction(1, 1));
        Fraction left = null;
        Fraction right = null;
        Fraction mediant = null;
        for (int j = 0; j < base; j++) {
            ListIterator<Fraction> listIterator = params.listIterator();
            left = listIterator.next();

            while (listIterator.hasNext()) {
                if (params.size() - 1 == threads) {
                    return params;
                }
                right = listIterator.next();
                int denominator = left.getDenominator()
                        + right.getDenominator();
                if (denominator <= base) {
                    mediant = new Fraction(left.getNumerator()
                            + right.getNumerator(), denominator);
                    listIterator.previous();
                    listIterator.add(mediant);
                    left = listIterator.next();
                } else {
                    left = right;
                }

            }
        }
        throw new RuntimeException();
    }

    public static class FareyCallable implements Callable<LinkedList<Fraction>> {
        private Fraction first;
        private Fraction last;
        private int base;

        public FareyCallable(Fraction first, Fraction last, int base) {
            super();
            this.first = first;
            this.last = last;
            this.base = base;
        }

        @Override
        public LinkedList<Fraction> call() throws Exception {
            LinkedList<Fraction> result = new LinkedList<Fraction>();
            Fraction left = first;
            Fraction right = last;
            Fraction mediant = null;
            result.add(left);
            result.add(right);
            ListIterator<Fraction> iterator = result.listIterator();
            left = iterator.next();
            while (iterator.hasNext()) {
                right = iterator.next();
                int denominator = left.getDenominator()
                        + right.getDenominator();
                if (denominator <= base) {
                    mediant = new Fraction(left.getNumerator()
                            + right.getNumerator(), denominator);
                    iterator.previous();
                    iterator.add(mediant);
                    iterator.previous();
                } else {
                    left = right;
                }
            }
            return result;
        }

    }

    public static void main(String[] args) {
        int threads = 20;
        int base = 5000;
        executor = Executors.newFixedThreadPool(threads);

        for (int i = 0; i < 1; i++) {
            long time = System.currentTimeMillis();
            List<Fraction> farey = NestedIntervals.base(base).getFarey();


            System.out.printf("Total %dms ", System.currentTimeMillis() - time);
            System.out.println(farey.size());

            farey = null;
            System.gc();
            time = System.currentTimeMillis();
            farey = NestedIntervals.base(base).getFareyNonRecurcive();


            System.out.printf("n Total %dms ", System.currentTimeMillis()
                    - time);
            System.out.println(farey.size());

            farey = null;
            System.gc();
            time = System.currentTimeMillis();
            farey = NestedIntervals.base(base).getFareyNonRecurciveMultiThread(threads);

            System.out.printf("m Total %dms ",
                    System.currentTimeMillis() - time);
            System.out.println(farey.size());
            farey = null;
            System.gc();
        }
        executor.shutdownNow();
    }
}

Answer 11

Hello. You can read here one more ://javarules.ru/java-8-parallel/ about creating fork/join