Improve performance of small tests that use rejection sampling #2030
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This was referenced Jul 2, 2019
DRMacIver
force-pushed
the
DRMacIver/rejection-sampling-performance
branch
2 times, most recently
from
7040de6
to
be14bad
Compare
|
Despite the failing build, this should actually pass and be ready for review. It's just failing because Cloudflare issues are breaking most of the internet right now. |
DRMacIver
force-pushed
the
DRMacIver/rejection-sampling-performance
branch
from
be14bad
to
7579868
Compare
Zac-HD
reviewed
Jul 4, 2019
| @@ -70,6 +70,7 @@ def test_unsat_sets_of_samples(x): | |||
| assert False | |||
|
|
|||
|
|
|||
| @settings(suppress_health_check=[HealthCheck.too_slow, HealthCheck.filter_too_much]) | |||
There was a problem hiding this comment.
I'm not really comfortable with this since it seems to defeat the purpose of the test, but after merging #2031 and rebasing I don't think it will be needed.
There was a problem hiding this comment.
Yup, agreed. I think it's not totally defeating the point of the test, but it definitely weakens it. Either way, it's no longer necessary.
DRMacIver
force-pushed
the
DRMacIver/rejection-sampling-performance
branch
from
7579868
to
903e1cc
Compare
DRMacIver
force-pushed
the
DRMacIver/rejection-sampling-performance
branch
from
903e1cc
to
1b0867c
Compare
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Fixes #1864.
I think this problem must always have been latent in Hypothesis but the previous implementation of the tree had a bug which masked it somehow, because the issue is actually intrinsic to what we were doing: The rejection sampling on small state spaces forces the necessary novel prefix to be progressively longer and longer, creating an accidentally quadratic problem where generating the Nth example takes O(N) time.
This PR fixes it by implicitly capping all rejection sampling loops to 20 iterations by building logic for marking longer sequences of consecutive discards as invalid into
ConjectureData.Earlier versions of this PR had an independent performance improvement to
generate_novel_prefixwhich turned out to change the distribution enough that I decided to pull it out for now (it causes us to miss some branches in coverage that we were previously hitting).