FULL PRODUCT VERSION :
java version "1.8.0_77"
Java(TM) SE Runtime Environment (build 1.8.0_77-b03)
Java HotSpot(TM) 64-Bit Server VM (build 25.77-b03, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
Linux theta 3.13.0-71-generic #114-Ubuntu SMP Tue Dec 1 02:34:22 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux


EXTRA RELEVANT SYSTEM CONFIGURATION :
4 cores, 8 GB of RAM

A DESCRIPTION OF THE PROBLEM :
I have a program that uses Java streams and which does not take any import. It also does not explicitly request parallelism. The program shows varying runtimes - either 1.4seconds, or 5.3seconds, roughly 60%/40% of the time. With 1.8.0_20, the same behavior, but the longer run-time was 16seconds.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the included program multiple times using the /usr/bin/time command, e.g.

$ time /opt/jdk1.8.0_77/bin/java HotspotWeirdness
522367397240

real 0m1.052s
user 0m1.394s
sys 0m0.094s

$ time /opt/jdk1.8.0_77/bin/java HotspotWeirdness
522367397240

real 0m4.596s
user 0m4.975s
sys 0m0.056s




EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The runtime of this program should not vary by a factor of 4 if the conditions on which it runs did not change and if it does use any parallel APIs.
ACTUAL -
The runtime varies between 1 and 5 seconds, showing a bimodal distribution.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;
import java.io.*;
import java.util.stream.*;
import java.util.function.*;

public class HotspotWeirdness {
    static String input =
    "15 6\n"+
    "5055 1714 3285\n"+
    "9671 207 8459\n"+
    "9401 981 6906\n"+
    "1797 5262 9922\n"+
    "7599 9757 6767\n"+
    "7349 3753 4599\n"+
    "2095 7162 5062\n"+
    "4066 2683 5551\n"+
    "8754 8291 667\n"+
    "5371 9157 7853\n"+
    "8645 2910 6133\n"+
    "9651 9486 7444\n"+
    "2233 5924 9613\n"+
    "2179 5756 5749\n"+
    "4111 3811 9610\n";
public static long INF = 1L<<60;
    private static long[] cost;
public static void main (String[] args) {
Scanner in = new Scanner(new StringReader(input));
int n = in.nextInt(), k = in.nextInt();
int[] w = new int[n], h = new int[n];
        long []q = new long[n];
for (int i = 0; i < n; i++) {
w[i] = in.nextInt();
h[i] = in.nextInt();
q[i] = in.nextInt();
}

        cost = IntStream.range(0, 1<<n).mapToLong( mask -> {
            IntPredicate inSet = i -> (mask & (1<<i)) != 0;
            long maxw = IntStream.range(0, n).filter(inSet).map(i -> w[i]).max().orElse(0);
            long maxh = IntStream.range(0, n).filter(inSet).map(i -> h[i]).max().orElse(0);
            return IntStream.range(0, n).filter(inSet).mapToLong(i -> (maxw*maxh-w[i]*h[i])*q[i]).sum();
        }).toArray();
        
        int allcards = (1<<n) - 1;
        dp = new Long[1<<n][k+1];
        long answer = IntStream.range(0, k+1).mapToLong( _k -> compute(allcards, _k) ).min().getAsLong();
        System.out.println(answer);
        if (answer != 522367397240L)
            throw new Error();
    }

    static Long[][] dp;
    static long compute(int cardset, int k)
    {
        if (cardset == 0 && k == 0)
            return 0;

        if (cardset != 0 && k == 0)
            return INF;

        if (dp[cardset][k] != null)
            return dp[cardset][k];

        long best = INF;
        for (int subset = cardset; subset > 0; subset = (subset - 1) & cardset) {
            best = Math.min(best, compute(cardset ^ subset, k-1) + cost[subset]);
        }
        dp[cardset][k] = best;
        return best;
    }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
I did not find any, but it means I cannot use streams (the program must finish in under 3 seconds).

I'm intrigued. Is this a streams or a HotSpot issue?