Strange dead-lock with Streams API

Question

I was working a program, and decided to use the new Streams API for Java 8. However, my program stopped working when I introduced .parallel(). Here's the relevant code:

import java.math.BigInteger;
import java.util.Objects;
import java.util.stream.Stream;

import com.google.common.cache.*;

public class Alg196 {

    public static void main(String[] args) {
        // Add .parallel() where suitable
        long c = Stream
                .iterate(BigInteger.valueOf(101), i -> i.add(BigInteger.ONE))
                .limit(100000000).map(BigInteger::toString).map(Alg196::alg196)
                .filter(Objects::nonNull).count();
        System.err.println(c);
    }

    private static final String reverse(String n) {
        return new StringBuilder(n).reverse().toString();
    }

    private static final boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
            if (s.charAt(i) != s.charAt(j))
                return false;
        }
        return true;
    }

    private static final String alg196(String n) {
        System.err.println("PROCESSING " + n);
        int loops = 0;
        while (!isPalindrome(n)) {
            n = new BigInteger(n).add(new BigInteger(reverse(n))).toString();
            loops++;
            if (loops >= 100) {
                return null;
            }
        }
        if (loops <= 10) {
            return null;
        }
        return n;
    }
}

The output will contain many PROCESSING <x> lines when working correctly, but that never happens with .parallel(). Why is this?

Answer 1

Your program didn't stop - it's working hard trying to generate requested range of BigIntegers (in your case it is 100000000) before submitting map tasks to executors (try to put breakpoint at BigInteger::add() method - and you'll see)

it's also easy to see from thread dump

"ForkJoinPool.commonPool-worker-2@710" daemon prio=5 tid=0xe nid=NA runnable java.lang.Thread.State: RUNNABLE
at java.util.stream.Stream$1.next(Stream.java:1033)
  at java.util.Spliterators$IteratorSpliterator.trySplit(Spliterators.java:1784)
  at java.util.stream.AbstractShortCircuitTask.compute(AbstractShortCircuitTask.java:114)
  at java.util.concurrent.CountedCompleter.exec(CountedCompleter.java:731)
  at java.util.concurrent.ForkJoinTask.doExec(ForkJoinTask.java:289)
  at java.util.concurrent.ForkJoinPool$WorkQueue.runTask(ForkJoinPool.java:902)
  at java.util.concurrent.ForkJoinPool.scan(ForkJoinPool.java:1689)
  at java.util.concurrent.ForkJoinPool.runWorker(ForkJoinPool.java:1644)
  at java.util.concurrent.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:157)`

Also please be careful submitting many long-running tasks to the common ForkJoin pool, as you may block all threads in the pool - you can check this thread (Custom thread pool in Java 8 parallel stream) for solution

Answer 2

Turns out that limit is a short-circuiting operation, which means it will generate all 100,000,000 BigIntegers before running anything else. Not a dead-lock after all!