Does Java automatically parallelize recursive functions?

Viewed 214

I am parallelizing a recursive function and I measured poor speedup. While debugging the code, I noticed that in the sequential version all cores are working.

I have reproduced this behavior in a minimal example, and again, all my cores have a workload of about 90%. I'm using Java 8 (OpenJDK).

Is Java automatically doing parallelism without my knowledge? How is Java doing this?

import java.util.Random;
import java.util.ArrayList;

class Node
{
    float value;
    ArrayList<Node> children;

    public Node()
    {
        children = new ArrayList<Node>();
    }

    public Node(float value)
    {
        this.value = value;
    }

    public int count()
    {
        int count = 1;

        if (children != null)
            for (Node c : children)
                count += c.count();

        return count;
    }
}

public class ProofOfConcept {
    final static int N_NODES = 10000000;
    final static int MAX_CHILDREN = 6;

    final static Random RAND = new Random();

    static Node generateTree(int nNodes)
    {
        if (nNodes > 1)
        {
            Node result = new Node();
            int nChildren = 1 + RAND.nextInt(Math.min(MAX_CHILDREN, nNodes) - 1);
            int nNodesPerChild = (nNodes - 1) / nChildren;

            for (int i = 0; i < nChildren; ++i)
            {
                Node t = generateTree(nNodesPerChild);
                result.children.add(t);
            }

            return result;
        }
        else
            return new Node(RAND.nextFloat());
    }

    public static void main(String[] args)
    {
        Node t = generateTree(N_NODES);
        System.out.println(t.count());
    }
}

EDIT: This is also really weird for me. I'm attaching a screenshot of htop; as you can see, we have the main process and eight threads (one for each one of my logic cores).

htop

EDIT 2: It seems like GC is doing its job in parallel. For those who do not understand why GC is triggered if apparently no objects are being freed, you should read the following reference:

When a garbage collection is triggered by an allocation failure, but the garbage collection does not free enough space, the Garbage Collector expands the storage heap. During heap expansion, the Garbage Collector takes storage from the maximum amount of storage reserved for the heap (the amount specified by the -Xmx option), and adds it to the active part of the heap (which began as the size specified by the -Xms option). Heap expansion does not increase the amount of storage required for the JVM, because the maximum amount of storage specified by the -Xmx option has already been allocated to the JVM at startup. If the value of the -Xms option provides sufficient storage in the active part of the heap for your applications, the Garbage Collector does not have to carry out heap expansion at all.

1 Answers

No, Java is not magically making your code parallel.

If you see 90% utilization on all core it's either operating system, other processes or JVM doing background work. It could be JVM using Parallel GC utilizing all cores to collect garbage.

Related