JqwikStreamSupport#concat(List<Stream<T>>) seem to be O(N^2)

[vlsi]

Testing Problem

See https://github.com/jlink/jqwik/blob/00185e2d52137ab12bff0b7dee180f96542fded4/engine/src/main/java/net/jqwik/engine/support/JqwikStreamSupport.java#L58-L68

The code is hard to follow, and it creates multiple temporary ArrayList objects (one per element).

Suggested Solution

Would .flatMap work?

For example:

 public static <T> Stream<T> concat(List<Stream<T>> streams) { 
 	int size = streams.size();
 	// No idea if the optimization for 0, 1, 2 is important, however, it should not hurt much
 	if (size == 0) {
 	 	return Streams.empty();
 	} else if (size = 1) {
 	 	return streams.get(0);
 	} else if (size = 2) {
 	 	return Streams.concat(streams.get(0), streams.get(1));
 	}
 	return streams.stream().flatMap(Function::identity);
 } 

[jlink]

At first glance

return streams.stream().flatMap(Function.identity());

should work. However, it breaks in recursive scenarios, probably due to the laziness of Java streams.
See e.g. ArbitrariesRecursiveTests.ShrinkingTests.complexShrinking.

I added a clarifying comment to the code.

Have you noticed any detrimental effects of the current solution?

BTW, the flat-map version will also be O(n^2) (I think), it's just that you don't see it at once from the code.

[jlink]

At the time I had read https://www.techempower.com/blog/2016/10/19/efficient-multiple-stream-concatenation-in-java/ and decided on the current implementation anyway. Probably for the reason mentioned above.

[vlsi]

Have you noticed any detrimental effects of the current solution?

The most significant effect was I spent noticeable time trying to understand the logic behind net.jqwik.engine.properties.stateful.ShrinkableActionSequence#shrinkActionsOneAfterTheOther.

It used JqwikStreamSupport.concat, and it was hard to understand what that means.

[vlsi]

BTW, the flat-map version will also be O(n^2) (I think)

Why?
I don't see why would it re-allocate the array again and again.

---

As per the article, flatMap has issues (however, it is still recommended for finite streams!), so a smaller change might be use subList(int fromIndex, int toIndex) rather than re-allocate new ArrayList and remove the head.

[jlink]

The code is hard to follow, and it creates multiple temporary ArrayList objects (one per element).

I don't think it does. rest.remove(0) changes the original list, so there's only a single list created. I'm not sure though if we're talking about the same thing.