Java Collection performance

Question

I just tried a test example on codility. The task was: " ... given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.".

Plus:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].

my firts attempt was a typical Java 8 solution:

public int solution(int[] A) {

     Set<Integer> l = Arrays
            .stream(A)
            .boxed()
            .filter(i -> i > 0)
            .collect(Collectors.toSet());

    return IntStream
            .iterate(1, a -> a + 1)
            .filter(i -> !l.contains(i))
            .findFirst()
            .getAsInt();
}

All correct, but the tests for intermediate size test arrays, ran into a timeout.

Second try (plain old java):

public int solution(int[] A) {

    boolean[] B = new boolean[1000001];

    for (int a : A) {
        if (a > 0) {
            B[a] = true;
        }
    }

    for (int i = 1; i <= 1000000; i++) {
        if (!B[i]) {
            return i;
        }
    }

    return 1;
}

This version was incedibly much faster, especially for short arrays A.

Questions:

Am I missing something with my first attempt?
Are there tweaking options?
Is the test on codility premature, and in reallity the difference is expected to disappear, almost entirely?
Does anyone have a better Java 8 solution?

Test results first version:

▶ example1 first example test ✔OK 1. 0.108 s OK

▶ example2 second example test ✔OK 1. 0.104 s OK

▶ example3 third example test ✔OK 1. 0.104 s OK

▶ extreme_single a single element ✔OK 1. 0.100 s OK 2. 0.104 s OK 3. 0.104 s OK 4. 0.100 s OK

▶ simple simple test ✔OK 1. 0.100 s OK 2. 0.104 s OK 3. 0.100 s OK

▶ extreme_min_max_value minimal and maximal values ✔OK 1. 0.100 s OK 2. 0.104 s OK

▶ positive_only shuffled sequence of 0...100 and then 102...200 ✔OK 1. 0.100 s OK 2. 0.104 s OK

▶ negative_only shuffled sequence -100 ... -1 ✔OK 1. 0.100 s OK

▶ medium chaotic sequences length=10005 (with minus) ✘TIMEOUT ERROR running time: 0.136 sec., time limit: 0.100 sec. 1. 0.136 s TIMEOUT ERROR, running time: 0.136 sec., time limit: 0.100 sec. 2. 0.128 s TIMEOUT ERROR, running time: 0.128 sec., time limit: 0.100 sec. 3. 0.144 s TIMEOUT ERROR, running time: 0.144 sec., time limit: 0.128 sec.

▶ large_1 chaotic + sequence 1, 2, ..., 40000 (without minus) ✔OK 1. 0.588 s OK

▶ large_2 shuffled sequence 1, 2, ..., 100000 (without minus) ✔OK 1. 0.748 s OK 2. 0.660 s OK

▶ large_3 chaotic + many -1, 1, 2, 3 (with minus) ✔OK 1. 0.444 s OK

Test results second version:

▶ example1 first example test ✔OK 1. 0.004 s OK

▶ example2 second example test ✔OK 1. 0.004 s OK

▶ example3 third example test ✔OK 1. 0.004 s OK

▶ extreme_single a single element ✔OK 1. 0.004 s OK 2. 0.008 s OK 3. 0.004 s OK 4. 0.008 s OK

▶ simple simple test ✔OK 1. 0.004 s OK 2. 0.004 s OK 3. 0.008 s OK

▶ extreme_min_max_value minimal and maximal values ✔OK 1. 0.008 s OK 2. 0.004 s OK

▶ positive_only shuffled sequence of 0...100 and then 102...200 ✔OK 1. 0.008 s OK 2. 0.004 s OK

▶ negative_only shuffled sequence -100 ... -1 ✔OK 1. 0.008 s OK

▶ medium chaotic sequences length=10005 (with minus) ✔OK 1. 0.024 s OK 2. 0.024 s OK 3. 0.032 s OK

▶ large_1 chaotic + sequence 1, 2, ..., 40000 (without minus) ✔OK 1. 0.220 s OK

▶ large_2 shuffled sequence 1, 2, ..., 100000 (without minus) ✔OK 1. 0.244 s OK 2. 0.244 s OK

▶ large_3 chaotic + many -1, 1, 2, 3 (with minus) ✔OK 1. 0.172 s OK

Bottom line: Especially the tests with small sized arrays are two orders of magnitude faster with just plain java. For large arrays its 'only' a factor of 3.

EDIT:

Accoring to the comments I just tried to get deeper into the problem and tried:

public int solution(int[] A) {

boolean[] B = new boolean[1000001];

for (int a : A) {
    if (a>0){
        B[a] = true;
    }
}

 return IntStream
        .iterate(1, a -> a + 1)
        .filter(i -> !B[i])
        .findFirst()
        .getAsInt();

}

Result:

▶ example1 first example test ✔OK 1. 0.096 s OK

▶ example2 second example test ✔OK 1. 0.096 s OK

▶ example3 third example test ✔OK 1. 0.096 s OK collapse allCorrectness tests

▶ extreme_single a single element ✔OK 1. 0.096 s OK 2. 0.096 s OK 3. 0.096 s OK 4. 0.096 s OK

▶ simple simple test ✔OK 1. 0.100 s OK 2. 0.096 s OK 3. 0.100 s OK

▶ extreme_min_max_value minimal and maximal values ✔OK 1. 0.096 s OK 2. 0.100 s OK

▶ positive_only shuffled sequence of 0...100 and then 102...200 ✔OK 1. 0.096 s OK 2. 0.096 s OK

▶ negative_only shuffled sequence -100 ... -1 ✔OK 1. 0.096 s OK collapse allPerformance tests

▶ medium chaotic sequences length=10005 (with minus) ✘TIMEOUT ERROR running time: 0.116 sec., time limit: 0.112 sec. 1. 0.116 s TIMEOUT ERROR, running time: 0.116 sec., time limit: 0.112 sec. 2. 0.116 s TIMEOUT ERROR, running time: 0.116 sec., time limit: 0.100 sec. 3. 0.124 s OK

▶ large_1 chaotic + sequence 1, 2, ..., 40000 (without minus) ✔OK 1. 0.340 s OK

▶ large_2 shuffled sequence 1, 2, ..., 100000 (without minus) ✔OK 1. 0.408 s OK 2. 0.372 s OK

▶ large_3 chaotic + many -1, 1, 2, 3 (with minus) ✔OK 1. 0.272 s OK

Conclusion:

For small sized test arrays it is almost equally slow like the first version, thus here the IntStream seems to be the bottle neck.
For large test arrays the speed seems to be intemediate. Thus I'm not really sure what it should tell me.

Edit 2:

I actually just found an article describing the issue partly: https://jaxenter.com/java-performance-tutorial-how-fast-are-the-java-8-streams-118830.html . Therein, the author claims the difference between streams and for loop running over arrays is due to the fact that streams are quite new. However the article is dated 4 years ago.

why are you assuming that streams should outperform plain old loops? — Andrew Tobilko, Aug 09 '19 at 12:08
There's a lot of boxing/unboxing going on in your stream solution. — assylias, Aug 09 '19 at 12:12
@AndrewTobilko I didn't claim, I expect the stream to faster. However, I expected a difference of maybe some percentage, thus not interesting for most real world applications. But two orders of magnitude, and even a factor of three is way more than I expected. — PeMa, Aug 09 '19 at 12:13
@LutzHorn I don't have acces to the backing java process. It is run by codility. — PeMa, Aug 09 '19 at 12:14
@Nexevis To be true, not even sure, what makes the difference here ... that's why I'm asking the experts. — PeMa, Aug 09 '19 at 12:18
It's hard to write an appropriate answer here. There's some speculation, and probably *several* possible reasons for the performance differences. One reason might also be that this "codility"-Page is likely to do some sort of "one-shot" execution: It does not do a warmup, and the JIT does not have a chance to kick in. If you executed the stream-based variant multiple times, it's likely to become faster (but how much...? That's hard to say, considering that unboxing etc. still have to happen...) — Marco13, Aug 09 '19 at 21:28
@Marco13 I was asking since I wanted to get a deeper understanding about what really makes a difference, when performance matters. After the two edits, it seems that the main difference here are the streams compared to for loops. So, I think an accepted answer maybe to explain what causes this difference, what is really behind streams, and how to improve. Or a reasoning that all this is just due to bad performance testing practice. I can't do performance tests reliably myself, since I don't know, how to "warm up" the JVM appropriately, e.g. how to make the JIT decide to compile the streams. — PeMa, Aug 10 '19 at 23:35

MikeFHay · Answer 1 · 2019-08-09T14:08:24.297

3

You're not missing anything. Boxing integers and checking HashSets is slower than iterating a primitive array. The only change I would make to your second solution is to replace the boolean[] with a BitSet, which is similar to a boolean[] but more space-efficient as it uses just one bit per element.

edited Aug 09 '19 at 14:08

answered Aug 09 '19 at 12:27

MikeFHay

8,562
4
31
52

I made an edit to my question accordingly. It seems like, the search in the HashSet doesn't make the big difference far small test arrays. – PeMa Aug 09 '19 at 12:42
And yes, I remember the BitSet (from long in the past). True, this should help. But it's not related to my point in the question. – PeMa Aug 09 '19 at 12:43
@PeMa it’s not clear, what the point of your question is. You are creating two code snippets doing entirely different things, which has nothing to do with the Stream API (setting boolean entries of an array *is* an entirely different thing than populating a `HashSet`, further, the loops stop at `1000000` whereas the stream is infinite, rather than an equivalent `IntStream.rangeClosed(1, 1000000)`). You didn’t document your measuring method. – Holger Aug 12 '19 at 15:45
1

@MikeFHay Using a `BitSet` for this task is more than just “more space-efficient”, as searching for the smallest number via `.nextClearBit(1)` will test 64 bits at a time. – Holger Aug 12 '19 at 15:54

Lars Christian Jensen · Answer 2 · 2019-08-09T14:07:42.683

0

There are many differences between those two pieces of code. I suspected that the largest difference comes from using Set<Integer> vs boolean[], so I wrote a little test:

        Set<Integer> set = new HashSet<>();
        for (int n : numbs) {
            set.add(n);
        }

vs

        boolean[] arr = new boolean[numbs.length];
        for (int n : numbs) {
            arr[n] = true;
        }

The difference was 20x with 1000000 numbers in range [0, 1000000).

edited Aug 09 '19 at 14:07

answered Aug 09 '19 at 13:00

Lars Christian Jensen

1,407
1
13
14

Well I actually suspected the same had the same. But as seen in the edit, for small test arrays this is not what makes the large real difference. – PeMa Aug 09 '19 at 13:06
1

The problem with this solution at the end of the post is that it doesn't test to see whether the result, `.getAsInt() - 1` is in `A` (which it could be). – scottb Aug 09 '19 at 13:27
@scottb; My solution was wrong. I removed it. – Lars Christian Jensen Aug 09 '19 at 14:08

Java Collection performance

2 Answers2