Shrinking stateful chain yields OutOfMemoryError

[vlsi]

Testing Problem

Shrinking stateful chain causes the following. I'll attach details from the heap dump soon

java.lang.OutOfMemoryError: Java heap space
Dumping heap to java_pid6286.hprof ...
Heap dump file created [920534673 bytes in 4.318 secs]
MappingApply2Properties > mapping change works STANDARD_ERROR
    мая 19, 2022 8:05:21 PM net.jqwik.engine.JqwikTestEngine execute
    SEVERE: Java heap space
    java.lang.OutOfMemoryError: Java heap space
    	at java.base/java.util.ArrayList.iterator(ArrayList.java:977)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:21)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.restIterator(CombinedIterator.java:28)
    	at net.jqwik.engine.support.combinatorics.CombinedIterator.<init>(CombinedIterator.java:22)

[jlink]

Need a reproducible example for that.

[vlsi]

It looks like one of the streams within ShrinkableChainShrinker has been buffered (e.g. like in https://stackoverflow.com/questions/29229373/why-filter-after-flatmap-is-not-completely-lazy-in-java-streams).

There were 721601 instances of ShrinkableChain in the heap.

Unfortunately, jqwik did not print the seed to reproduce before failing 🤷‍♂️

[vlsi]

Just for reference, there's jdk.internal.lambda.dumpProxyClasses=/path/to/dir (see https://stackoverflow.com/a/30944839/1261287 ) to dump lambda classes. Hope it would narrow down the reason for the failure.

[vlsi]

[jlink]

@vlsi Which JDK version did you use. The SO answer suggests that the problem was fixed in JDK 10, which would narrow down if it really is the same problem.

[jlink]

@vlsi Did the OME occur more than once? Have you a way to replicate it?

[jlink]

As far as I can see, the current implementation of JqwikStreamSupport.concat(..) does not use flatMap under the hood, so the SO issue wouldn't apply.

[vlsi]

I tried both 11 and 17 -- both crash at will. I can reproduce the crash consistently, however, the test code involves lots of code which I would like keep private.

It might be a new JDK bug though. I did examine a lot the shrinking code that breaks, and it looked fine to me.

I can probably build something similar if you consider merging that to jqwik. Basically I need to randomize database table structure, however, my current jqwik code relies on my model DSL a lot, so I can't easily extract a small sample

[jlink]

I can probably build something similar if you consider merging that to jqwik.

For clarification: Something similar to what? A new implementation of Stream.concat()?

[vlsi]

Something similar to a "stateful testing" I am working on (==a use-case for stateful testing).

[jlink]

Would be something for the examples section then?

[jlink]

I close since I cannot reproduce. Feel free to reopen if you can provide a reproducible example.

[vlsi]

One more idea: it looks like Stream.sorted(...) might collect all the data in memory and trigger OOM.

See https://stackoverflow.com/a/31580392/1261287

WDYT of adding https://github.com/amaembo/streamex for least(int n) collector so the stream could collect "top n" without buffering everything at once?

An alternative option could probably stop using .sorted(..) method in streams that might contain many elements.

[jlink]

WDYT of adding https://github.com/amaembo/streamex for least(int n) collector so the stream could collect "top n" without buffering everything at once?

It looks like a trustworthy lib. Thing is that I want to forgo any hard depencency until jqwik cannot solve a pressing issue without it. What about:

1. Find out if least(..) will really solve the problem.
2. If it does, check if a similiar idea / implementation can't be implemented directly in jqwik.

[vlsi]

I tried "proper sort limit" in https://github.com/jlink/jqwik/pull/436/files#diff-24f2363e5b549d73b76a697390516a86b444e6f9962c24032fb71a4dc7ce12ceR48-R49, however, it does not really solve the issue.

The cause might be "some other shrinker producing too many shrink candidates".

[jlink]

I tried "proper sort limit" in https://github.com/jlink/jqwik/pull/436/files#diff-24f2363e5b549d73b76a697390516a86b444e6f9962c24032fb71a4dc7ce12ceR48-R49, however, it does really solve the issue.

You mean, it does NOT really solve the issue?

[vlsi]

It does NOT solve the issue of "too long shrinking duration", however, I tried it only for the newly added EagerShrinkable when it eagerly creates N shrinkable values.

However, it might still help for other usages in jqwik.

[vlsi]

Thing is that I want to forgo any hard depencency until jqwik cannot solve a pressing issue without it.

In fact, Stream#sorted is used in core places of jqwik. For instance, ShrinkableBigInteger#shrinkTowardsTarget does use sorted, so it easily triggers materialization of the full stream for the sorting purposes.

For instance, here's a sample stacktrace during net.jqwik.engine.properties.shrinking.ShrinkableProperties#allShrinkingShrinksToSmallerValues

"Test worker" #1 prio=5 os_prio=31 cpu=3422.79ms elapsed=3.57s tid=0x0000000122010800 nid=0x1503 runnable  [0x000000016fb7d000]
   java.lang.Thread.State: RUNNABLE
	at net.jqwik.engine.properties.shrinking.ShrinkableBigInteger.distanceFor(ShrinkableBigInteger.java:67)
	at net.jqwik.engine.properties.shrinking.ShrinkableBigInteger.distance(ShrinkableBigInteger.java:63)
	at net.jqwik.engine.properties.shrinking.ShrinkableBigInteger$$Lambda$516/0x0000000800263c40.apply(Unknown Source)
	at java.util.Comparator.lambda$comparing$77a9974f$1([email protected]/Comparator.java:469)
	at java.util.Comparator$$Lambda$490/0x000000080025e440.compare([email protected]/Unknown Source)
	at java.util.TimSort.binarySort([email protected]/TimSort.java:296)
	at java.util.TimSort.sort([email protected]/TimSort.java:221)
	at java.util.Arrays.sort([email protected]/Arrays.java:1515)
	at java.util.stream.SortedOps$SizedRefSortingSink.end([email protected]/SortedOps.java:353)
	at java.util.stream.Sink$ChainedReference.end([email protected]/Sink.java:258)
	at java.util.stream.StreamSpliterators$AbstractWrappingSpliterator.fillBuffer([email protected]/StreamSpliterators.java:210)
	at java.util.stream.StreamSpliterators$AbstractWrappingSpliterator.doAdvance([email protected]/StreamSpliterators.java:161)
	at java.util.stream.StreamSpliterators$WrappingSpliterator.tryAdvance([email protected]/StreamSpliterators.java:300)
	at java.util.stream.Streams$ConcatSpliterator.tryAdvance([email protected]/Streams.java:720)
	at java.util.stream.Streams$ConcatSpliterator.tryAdvance([email protected]/Streams.java:723)
	at java.util.stream.StreamSpliterators$WrappingSpliterator.lambda$initPartialTraversalState$0([email protected]/StreamSpliterators.java:294)
	at java.util.stream.StreamSpliterators$WrappingSpliterator$$Lambda$513/0x0000000800264040.getAsBoolean([email protected]/Unknown Source)
	at java.util.stream.StreamSpliterators$AbstractWrappingSpliterator.fillBuffer([email protected]/StreamSpliterators.java:206)
	at java.util.stream.StreamSpliterators$AbstractWrappingSpliterator.doAdvance([email protected]/StreamSpliterators.java:161)
	at java.util.stream.StreamSpliterators$WrappingSpliterator.tryAdvance([email protected]/StreamSpliterators.java:300)
	at net.jqwik.engine.support.JqwikStreamSupport$1.lambda$tryAdvance$1(JqwikStreamSupport.java:31)
	at net.jqwik.engine.support.JqwikStreamSupport$1$$Lambda$511/0x0000000800264840.accept(Unknown Source)
	at java.util.stream.StreamSpliterators$WrappingSpliterator.tryAdvance([email protected]/StreamSpliterators.java:302)
	at net.jqwik.engine.support.JqwikStreamSupport$1.tryAdvance(JqwikStreamSupport.java:31)
	at java.util.stream.ReferencePipeline$7$1.accept([email protected]/ReferencePipeline.java:278)
	at java.util.ArrayList$ArrayListSpliterator.tryAdvance([email protected]/ArrayList.java:1632)

As you see, there's Arrays.sort which implies there was a materialized stream.sorted() somewhere.

I'm inclined all the shrinkables must have a hard limit on the number of produced elements. This would significantly improve shrinking the collections, especially long ones like 1000 elements.

For instance, net.jqwik.engine.properties.shrinking.ShrinkableProperties#allShrinkingShrinksToSmallerValues executes MUCH faster if net.jqwik.engine.properties.shrinking.ShrinkableContainer#shrinkElementsOneAfterTheOther is commented-out. At the same time, replacing element.shrink() with element.shrink().limit(100) makes the test much faster as well (e.g. 8 sec -> 1.5 sec).

[jlink]

At the same time, replacing element.shrink() with element.shrink().limit(100) makes the test much faster as well (e.g. 8 sec -> 1.5 sec).

Limiting the search space will improve shrinking times but potentially make shrinking results worse.

I tend to review such changes against the samples in https://github.com/jlink/shrinking-challenge but I haven't done so in a while.