SoftwareEntwicklung Beratung Schulung

A coders, hackers heaven.....Hm...I do not think so...

Stream.concat vs. New ArrayList Performance

During a code review I suggested a code improvement related to JDK8+ streams. The original code looked very similar like the following:

1
2
3
4
5
6
7
8

List<Element> result = content.getFancyStuffs().stream()
  .flatMap(item -> {
        List<Element> objects = new ArrayList<>();
        objects.add(item.getElement());
        objects.addAll(item.getElements());
        return objects.stream();
      })
  .collect(toList());

Some more details here. The getFancyStuffs() returns a list of FancyStuff elements. The FancyStuff class contains two getters where getElement() returns a single Element whereas the getElements() returns (Guess what?) a list of Element’s.

The interesting part was the lambda which creates a new ArrayList and adds a single element objects.add(item.getElement()) and the second part which adds several elements via objects.addAll(item.getElements).

My suggestion based on better readability was to use the following code instead:

1
2
3
4

List<Element> result = content.getFancyStuffs()
  .stream()
  .flatMap(fs -> Stream.concat(Stream.of(fs.getElement()), fs.getElements().stream()))
  .collect(Collectors.toList());

So far so good. But after a time I began to think about the two solutions. I asked myself: Which is the faster one? Which one uses more memory? (The usual questions a developer is asking? Don’t you?).

So what would you guess which is the faster solution? The first one or the second one? My guess was that the first solution will win, but based on some assumptions. This means the number of elements which are coming through content.getFancyStuffs().stream().. are more or less small (less than 20) and furthermore the number of elements wich are returned by item.getElements() are fairly small as well (less than 20).

The only thing which can help here to get a reliable answer is to measure it. No assumptions, no educated guesses etc. So I have to make a real performance measurement. So I created a separate project which really measures the performance.

So the first code part for performance measurement looks like this:

Solution 1

1
2
3
4
5
6
7
8
9

@Benchmark
public List<Element> with_new_arraylist(Container content) {
    return content.getFancyStuffs().stream().flatMap(item -> {
      ArrayList<Element> objects = new ArrayList<>();
      objects.add(item.getElement());
      objects.addAll(item.getElements());
      return objects.stream();
    }).collect(Collectors.toList());
}

and the second part:

Solution 2

1
2
3
4
5
6
7

@Benchmark
public List<Element> with_stream_concat(Container content) {
  return content.getFancyStuffs()
  .stream()
  .flatMap(fs -> Stream.concat(Stream.of(fs.getElement()), fs.getElements().stream()))
  .collect(Collectors.toList());
}

while writing the above code I thought about some parts of it and I got two other possible variations.

Solution 3

The following example where I put elements directly into the constructor of the ArrayList. This means it could only happen that in rarer cases the size of the array list must be resized which depends on the number of elements in item.getElements().

1
2
3
4
5
6
7
8

@Benchmark
public List<Element> with_new_arraylist_constructor(Container content) {
  return content.getFancyStuffs().stream().flatMap(item -> {
    ArrayList<Element> objects = new ArrayList<>(item.getElements());
    objects.add(item.getElement());
    return objects.stream();
  }).collect(Collectors.toList());
}

Solution 4

Finally this one where I already calculate the size of the final list by giving the number of elements via the constructor. This will prevent the resizing of the array list at all cause the size will fit always.

1
2
3
4
5
6
7
8
9

@Benchmark
public List<Element> with_new_arraylist_constructor_size(Container content) {
  return content.getFancyStuffs().stream().flatMap(item -> {
    ArrayList<Element> objects = new ArrayList<>(item.getElements().size() + 1);
    objects.add(item.getElement());
    objects.addAll(item.getElements());
    return objects.stream();
  }).collect(Collectors.toList());
}

Measurement

The measurement has been done on an Intel Xeon Machine with 3.50GHz with CentOS Linux release 7.6.1810 (Core). The full source code of the project can be found https://github.com/khmarbaise/performance-concat.

Basic Measurement

So I began very simple only with the first two solutions (1+2):

The following is only an excerpt of the above The detailed measurement result (I have remove the prefix BenchmarkStreamConcat from all results here in the post).

1
2
3

Benchmark           Mode  Cnt   Score   Error  Units
with_new_arraylist  avgt   15  22.350 ± 1.415  us/op
with_stream_concat  avgt   15  15.716 ± 2.561  us/op

So if you take a look at the results above you can already see that for a small amount of elements (49 getElements, 50 FanceStuff instances) the one with stream_concat is faster. Hm..is this really true? Not a measuring error or coincidence?

Parameterized Measurement

To reduce the likely of stumbling over a coincidence or a measuring error I changed the code which now takes a parameter and enhanced the number of elements. I stick with the two solutions (1+2).

The getElements() results always in 49 elements where as the number of FancyStuff elements varies (see count). The following result shows that the version with stream_concat is always faster.

1
2
3
4
5
6
7
8
9
10
11

Benchmark           (count)  Mode  Cnt     Score     Error  Units
with_new_arraylist       50  avgt   15    21.759 ±   0.797  us/op
with_new_arraylist      100  avgt   15    43.309 ±   1.449  us/op
with_new_arraylist     1000  avgt   15   498.693 ± 103.550  us/op
with_new_arraylist     2000  avgt   15   988.483 ±  80.574  us/op
with_new_arraylist     5000  avgt   15  3379.189 ± 376.885  us/op
with_stream_concat       50  avgt   15    17.695 ±   3.601  us/op
with_stream_concat      100  avgt   15    38.559 ±  13.014  us/op
with_stream_concat     1000  avgt   15   458.131 ±  95.578  us/op
with_stream_concat     2000  avgt   15   815.142 ± 183.491  us/op
with_stream_concat     5000  avgt   15  2682.883 ± 287.596  us/op

Interestingly this is not only the case for larger number of elements. It is also for a small number of elements the case.

Running all solutions

So finally I ran all solutions (1+2+3+4) with different numbers (count, elementCount) with different combinations. I honestly have to admit that I underestimated the time it took to finish that test (it took 13 hours+).

I just picked up some examples of the measured times here:

1
2
3
4
5
6
7
8
9
10

Benchmark                        (count)  (elementCount) Mode  Cnt      Score     Error  Units
with_new_arraylist                    10  1000           avgt   15     77,358 ±   2,957  us/op
with_new_arraylist_constructor        10  1000           avgt   15     76,431 ±   1,544  us/op
with_new_arraylist_constructor_size   10  1000           avgt   15     73,156 ±   0,118  us/op
with_stream_concat                    10  1000           avgt   15     68,461 ±   0,048  us/op
....
with_new_arraylist                  1000  1000           avgt   15  12864,161 ± 164,193  us/op
with_new_arraylist_constructor      1000  1000           avgt   15  12703,437 ± 346,234  us/op
with_new_arraylist_constructor_size 1000  1000           avgt   15  12401,783 ± 387,433  us/op
with_stream_concat                  1000  1000           avgt   15  11613,553 ± 632,684  us/op

Another run

So I ran also a solution with all possible options im JMH which took very long (1 day + 15 hours+).

So I will pick up some examples of the measured times here:

1
2
3
4
5
6
7
8
9
10

Benchmark                         (count) (elementCount) Mode Cnt Score          Error   Units
with_new_arraylist                   1000   500          ss   3   22169330,000 ± 25379203,013   ns/op
with_new_arraylist_constructor       1000   500          ss   3    6425606,000 ±  4699006,445   ns/op
with_new_arraylist_constructor_size  1000   500          ss   3   22911512,667 ± 13112575,975   ns/op
with_stream_concat                   1000   500          ss   3    5328312,333 ±  4162857,199   ns/op
...
with_new_arraylist                   1000  1000          ss   3   13283635,000 ±  7645310,577   ns/op
with_new_arraylist_constructor       1000  1000          ss   3   35622844,333 ± 49138969,434   ns/op
with_new_arraylist_constructor_size  1000  1000          ss   3   14122526,333 ±  4304061,268   ns/op
with_stream_concat                   1000  1000          ss   3   13405022,333 ± 17950218,966   ns/op

So finally the question comes: What do those numbers mean?

quote from the JMH output:

REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial experiments, perform baseline and negative tests that provide experimental control, make sure the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts. Do not assume the numbers tell you what you want them to tell.