Significantly speed up BeEquivalentTo for large unordered collections#3188
Merged
dennisdoomen merged 6 commits intofluentassertions:mainfrom Apr 12, 2026
Merged
Conversation
Qodana for .NETIt seems all right 👌 No new problems were found according to the checks applied 💡 Qodana analysis was run in the pull request mode: only the changed files were checked Contact Qodana teamContact us at qodana-support@jetbrains.com
|
9973452 to
75ccee2
Compare
d141c65 to
e0e1ef5
Compare
…collections Replace the O(n! * n) permutation search in FindClosestMismatches with a two-strategy approach: - For n <= 8 items remaining, keep the exact permutation search (globally optimal; factorial(8) = 40,320, well within cost). - For n > 8, use a greedy O(n^2 log n) assignment that sorts all n^2 (expectation, subject) pairs by failure count and picks the closest unassigned pair first. Ties are broken by expectation index then subject index to preserve deterministic, natural-order error messages. Also extract ReferentialComparer to its own file and bump Reflectify to 1.9.0. Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
AsCollectionItem<T>(int) now returns a pre-computed string for indices 0-1023 instead of calling ToString() on every comparison. For large collections this avoids repeated short-lived string allocations in hot paths. Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Add UseDryRun flag to AssertionScope. When set, AssertionChain.FailWith() increments a counter instead of formatting and storing the full message. LooselyOrderedEquivalencyStrategy uses a dry-run scope in TryToMatchCount to count failures cheaply, split caches (countCache for counts, fullFailuresCache for strings), and updates FindClosestMismatches to take separate getFailureCount and getFullFailures delegates — deferring string allocation to the winning assignment only. Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
…k overflows Dry-run comparisons in TryToMatchCount and TryToMatch share the parent context's CyclicReferenceDetector by default. When the same object appears in multiple positions in an unordered collection, the detector could flag subsequent dry-runs as cyclic references and skip them — producing wrong failure counts and potential stack overflows. Fix by cloning the detector before each dry-run invocation. Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
GetFailureCount() was only counting direct RegisterFailure() calls. Failures from nested assertion scopes (e.g. via AssertionRuleEquivalencyStep) are stored in assertionStrategy.FailureMessages rather than the local counter, so they were invisible to TryToMatchCount — causing mismatches to look like matches (count=0) and corrupting the optimal assignment. Also call scope.Discard() after GetFailureCount() so that the dry-run scope does not propagate its failure messages to the parent scope on disposal. Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
e0e1ef5 to
4883856
Compare
jnyrup
approved these changes
Apr 12, 2026
Member
jnyrup
left a comment
There was a problem hiding this comment.
Looks good - and what a pleasure to review with the focused commits
Did you do a benchmark on Compare_complex_collection to get before and after cpu/mem numbers?
For later work, I'm wondering if we might be able to utilize UseDryRun more places?
Member
Author
I'm using Copilot CLI heavily, so thanks to Copilot ;-)
Most likely. But haven't investigated that yet. |
Member
Author
Added all the benchmarks. |
The strategy already owns TryToMatchCount and TryToMatch, so keeping the closest-match helper chain static forced delegate plumbing without adding value. Make those helpers instance methods so they can use the existing instance members directly while preserving the matching logic, scoring, and caches. Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
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
2 participants
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
This PR significantly improves the performance of
BeEquivalentTowhen comparing large unordered collections (usingWithoutStrictOrdering()). Focus benchmark: 500 complex objects vs 500 completely different objects.The work is split across five focused commits.
Changes
1. Replace O(n!) permutation search with O(n^2 log n) greedy assignment (Phase 3)
For n > 8 subjects, the original brute-force permutation search was replaced with a greedy strategy: compute all n^2 failure-count pairs, sort ascending, pick closest unassigned pair. n <= 8 keeps the exact search.
Also extracts
ReferentialComparerinto its own file and updates the benchmark target.2. Pre-cache collection index strings 0-1023
AsCollectionItem<T>(int index)calledindex.ToString()on every invocation. A static string[] cache for indices 0-1023 eliminates millions of small string allocations.3. Skip failure message formatting in dry-run comparisons
Phases 1 and 2 only need to count failures, not format them. Three-part change:
AssertionScope: newUseDryRunflag,RegisterFailure()counter,GetFailureCount()methodAssertionChain: whenUseDryRunis set, callRegisterFailure()instead of formattingLooselyOrderedEquivalencyStrategy: newTryToMatchCount()for counting; split caches (countCachefor ints,fullFailuresCachefor strings);FindClosestMismatchestakes separate count/full-failures delegatesEliminates ~3.25M FailureMessageFormatter calls and ~6.5M Regex.Replace calls from Phases 1+2.
4. Clone CyclicReferenceDetector per dry-run comparison
Dry-runs shared the parent context's
CyclicReferenceDetector. When the same object appears in multiple positions, the detector incorrectly flagged subsequent dry-runs as cyclic -- causing wrong counts and stack overflows. Fix: clone the detector for each dry-run call. Exposes the setter asinternal.5. Include nested scope failures in dry-run failure count
GetFailureCount()was missing failures from nested assertion scopes (they go intoassertionStrategy.FailureMessagesnot the local counter). Fix: returnfailureCount + assertionStrategy.FailureMessages.Count(). Also callscope.Discard()after counting to prevent leaking into the outer scope.Combined effect
Microbenchmark
BeEquivalentToWithDeeplyNestedStructuresBefore
After
PerformanceSpecs /
Compare_complex_collectionBefore
37-39 seconds
After
12-13 seconds