Fix HashSetAssert contains/containsAll O(n²) on large sets - #4355
Open
kalayciburak wants to merge 1 commit into
Open
kalayciburak wants to merge 1 commit into
kalayciburak wants to merge 1 commit into
Conversation
When checking membership against the HashSet under test, use HashSet#contains (O(1)) instead of also scanning with StandardComparisonStrategy. Align assertContainsAll with assertContains so Collection actuals keep their identity for strategy-backed lookups. Fixes assertj#4233
This branch has not been deployed
This file contains hidden or 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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
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.
Summary
assertThat(hashSet).contains(...)/.containsAll(...)scanned the whole set for every checked element, so both were O(n²) —containsAllof 50k elements against a 100kHashSettook several seconds (#4233).InHashSetComparisonStrategyalready holds the set under test, andHashSet#containsanswers membership in O(1) viahashCode. Two small changes restore that:HashSetAssert.InHashSetComparisonStrategy#iterableContains— when the iterable being checked is the set under test, returnoriginalSet.contains(value)only (skip the redundant linear scan).Iterables#assertContainsAll— reuseensureActualCanBeReadMultipleTimeslikeassertContainsso aCollectionactual keeps its identity; the previousnewArrayList(actual)copy forced the slow scan path for every element.When the iterable is a different collection (e.g. after intermediate processing), behavior is unchanged: still
originalSet.contains(value) && super.iterableContains(...).Fixes #4233
Test plan
HashSetAssert_contains_performance_Test(RED→GREEN; 100k/50k under 2s timeout)org.assertj.core.api.hashset.**— 110 tests GREEN./mvnw -pl assertj-core spotless:apply license:format