Performance and scalability: concat

I started working on the performance of EnumJ library, as I wrote in my previous post. The term of comparison is the Java 8 sequential streams despite the fact that Java 8 streams are not highly composable.

How the performance tests look like

The test pattern is simple:

1. create a simple enumerator/stream
2. modify the enumerator/stream by applying the same operation repeatedly – in our case concat() 
3. consume the elements from the enumerator/stream via forEach()

I took great care to choose only extremely simple operations so that the statistics do not get distorted by extraneous operations: the original enumerator/stream contains one element only, the same for the concatenated enumerators/streams and no allocation takes place: the enumerated element is always the same constant string.

Considering the above operations, there are three types of tests derived from the steps above:

1. construction tests – they measure only steps 1) and 2) from above
2. consumption tests – they apply stepts 1) and 2) and then measure only 3)
3. combined (both) tests – they measure 1), 2) and 3) as a single operation

Regarding the number of operations applied, the tests fall in two categories:

1. comparison tests – less than 10000 concatenations, where enumerators can be compared against Java 8 streams
2. scalability tests – where enumerators go beyond what streams can handle (from 10000 to 10 million concatenations)

Creation speed

When comparing the speed of creating the pipeline, enumerators are clearly the winner: their creation time compared to Java 8 streams is between under 50% and 0.2% (see the chart above). Moreover, their performance improves as the number of concatenations grows – as expected, they have been designed with scalability in mind.

Going beyond the limit of 10000 concatenations,  which Java 8 streams cannot handle, the statistics look good, too: performance stays low and flat up to 5 million concatenations and then it degrades somewhat linearly (clearly non-exponentially) – see the image to the right.

Consumption speed

Things look differently when consuming the elements from the concatenated enumerator/stream. Here Java 8 streams offer superior performance.

This is expected, since Stream.concat() does not do much more than calling the concatenated streams in succession – thus overflowing the stack when we have more than 10000 concatenations.

By contrast, enumerators create an internal pipeline for concatenation, handling concat() in a manner similar to flatMap(). This allows massive scalability but with the price of lower performance when extracting elements. OBS: we will see that the overall picture is quite different.

As one can easily notice, the performance of enumerator consumption is at least one order of magnitude worse than that of Java 8 streams, but the ratio stays quite flat – sign that the algorithm is still O(N), just the constant differs (see the image to the left).

When we move large scale, the picture is different: the performance degrades well (linearly) and the ratio time/num. of concatenations stays flat. This means that enumerators hold well under high pressure yielding consistently a linear performance.

For an illustration of scalability performance, see the image below.

Combined speed

We get a clear picture only when we measure creation, concatenation and consumption together – just like in real life. In this case we can see that enumerators are the winner when we have a large number of concatenations, at least 300. Moreover, performance improves as the number of concatenations grows:

Going beyond what Java 8 streams can handle shows the resilience of enumerators: their performance stays virtually flat up to 5 million concatenations, when the large number of objects in the pipeline starts to take a toll:

Conclusion

As I shown in my short talk given at LJC a while ago, enumerators are powerful tool designed for high scalability. With their help the programmer can build large, complex, intricate graphs of inter-connected computations similar to what one can find in high-level programming languages.

Future posts will detail the performance of other functions in the Enumerator<E> interface.