Shrinking stateful chain yields OutOfMemoryError #338

vlsi · 2022-05-19T17:49:50Z

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)

The text was updated successfully, but these errors were encountered:

jlink · 2022-05-19T19:22:12Z

Need a reproducible example for that.

vlsi · 2022-05-19T21:23:59Z

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 · 2022-05-20T05:52:01Z

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 · 2022-05-20T05:53:31Z

jlink · 2022-06-04T08:20:39Z

@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 · 2022-06-04T08:25:32Z

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

jlink · 2022-06-04T08:28:27Z

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 · 2022-06-04T08:36:41Z

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 · 2022-06-04T08:38:57Z

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 · 2022-06-04T08:42:14Z

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

jlink · 2022-06-04T09:10:02Z

Would be something for the examples section then?

jlink · 2022-09-25T09:29:56Z

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

vlsi · 2022-12-14T15:30:04Z

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 · 2022-12-23T14:39:25Z

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:

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

vlsi · 2022-12-23T14:50:18Z

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 · 2022-12-23T15:53:52Z

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 · 2022-12-23T16:07:35Z

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 · 2022-12-27T09:28:31Z

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(java.base@11.0.13/Comparator.java:469)
	at java.util.Comparator$$Lambda$490/0x000000080025e440.compare(java.base@11.0.13/Unknown Source)
	at java.util.TimSort.binarySort(java.base@11.0.13/TimSort.java:296)
	at java.util.TimSort.sort(java.base@11.0.13/TimSort.java:221)
	at java.util.Arrays.sort(java.base@11.0.13/Arrays.java:1515)
	at java.util.stream.SortedOps$SizedRefSortingSink.end(java.base@11.0.13/SortedOps.java:353)
	at java.util.stream.Sink$ChainedReference.end(java.base@11.0.13/Sink.java:258)
	at java.util.stream.StreamSpliterators$AbstractWrappingSpliterator.fillBuffer(java.base@11.0.13/StreamSpliterators.java:210)
	at java.util.stream.StreamSpliterators$AbstractWrappingSpliterator.doAdvance(java.base@11.0.13/StreamSpliterators.java:161)
	at java.util.stream.StreamSpliterators$WrappingSpliterator.tryAdvance(java.base@11.0.13/StreamSpliterators.java:300)
	at java.util.stream.Streams$ConcatSpliterator.tryAdvance(java.base@11.0.13/Streams.java:720)
	at java.util.stream.Streams$ConcatSpliterator.tryAdvance(java.base@11.0.13/Streams.java:723)
	at java.util.stream.StreamSpliterators$WrappingSpliterator.lambda$initPartialTraversalState$0(java.base@11.0.13/StreamSpliterators.java:294)
	at java.util.stream.StreamSpliterators$WrappingSpliterator$$Lambda$513/0x0000000800264040.getAsBoolean(java.base@11.0.13/Unknown Source)
	at java.util.stream.StreamSpliterators$AbstractWrappingSpliterator.fillBuffer(java.base@11.0.13/StreamSpliterators.java:206)
	at java.util.stream.StreamSpliterators$AbstractWrappingSpliterator.doAdvance(java.base@11.0.13/StreamSpliterators.java:161)
	at java.util.stream.StreamSpliterators$WrappingSpliterator.tryAdvance(java.base@11.0.13/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(java.base@11.0.13/StreamSpliterators.java:302)
	at net.jqwik.engine.support.JqwikStreamSupport$1.tryAdvance(JqwikStreamSupport.java:31)
	at java.util.stream.ReferencePipeline$7$1.accept(java.base@11.0.13/ReferencePipeline.java:278)
	at java.util.ArrayList$ArrayListSpliterator.tryAdvance(java.base@11.0.13/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 · 2022-12-29T10:23:01Z

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.

jlink closed this as completed Sep 25, 2022

vlsi mentioned this issue Dec 14, 2022

Cache several shrink results for every chain step, so it does not re-access state model state during shrink phase #436

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Shrinking stateful chain yields OutOfMemoryError #338

Shrinking stateful chain yields OutOfMemoryError #338

vlsi commented May 19, 2022

jlink commented May 19, 2022

vlsi commented May 19, 2022

vlsi commented May 20, 2022

vlsi commented May 20, 2022

jlink commented Jun 4, 2022

jlink commented Jun 4, 2022

jlink commented Jun 4, 2022

vlsi commented Jun 4, 2022

jlink commented Jun 4, 2022

vlsi commented Jun 4, 2022 •

edited

Loading

jlink commented Jun 4, 2022

jlink commented Sep 25, 2022

vlsi commented Dec 14, 2022 •

edited

Loading

jlink commented Dec 23, 2022

vlsi commented Dec 23, 2022 •

edited

Loading

jlink commented Dec 23, 2022

vlsi commented Dec 23, 2022 •

edited

Loading

vlsi commented Dec 27, 2022

jlink commented Dec 29, 2022

Shrinking stateful chain yields OutOfMemoryError #338

Shrinking stateful chain yields OutOfMemoryError #338

Comments

vlsi commented May 19, 2022

Testing Problem

jlink commented May 19, 2022

vlsi commented May 19, 2022

vlsi commented May 20, 2022

vlsi commented May 20, 2022

jlink commented Jun 4, 2022

jlink commented Jun 4, 2022

jlink commented Jun 4, 2022

vlsi commented Jun 4, 2022

jlink commented Jun 4, 2022

vlsi commented Jun 4, 2022 • edited Loading

jlink commented Jun 4, 2022

jlink commented Sep 25, 2022

vlsi commented Dec 14, 2022 • edited Loading

jlink commented Dec 23, 2022

vlsi commented Dec 23, 2022 • edited Loading

jlink commented Dec 23, 2022

vlsi commented Dec 23, 2022 • edited Loading

vlsi commented Dec 27, 2022

jlink commented Dec 29, 2022

vlsi commented Jun 4, 2022 •

edited

Loading

vlsi commented Dec 14, 2022 •

edited

Loading

vlsi commented Dec 23, 2022 •

edited

Loading

vlsi commented Dec 23, 2022 •

edited

Loading