nunit: CollectionAssert.AreEquivalent is extremely slow
var lines1 = new List<string> { };
var lines2 = new List<string> { };
for (int i = 0; i < 10000; i++)
{
lines1.Add(i.ToString());
lines2.Add(i.ToString());
}
CollectionAssert.AreEquivalent(lines1, lines2);
Verification of 10000 string elements takes 10 seconds. Verification of 100k elements may take more than 30 minutes (cannot wait until it finishes). This behavior takes a place in NUnit 3.10 and not reproducible in 3.9
About this issue
- Original URL
- State: closed
- Created 6 years ago
- Comments: 34 (30 by maintainers)
Commits related to this issue
- Fix for #2799 and #2826: slow collection equivalence tests. — committed to ggeurts/nunit by ggeurts 6 years ago
- Fix for #2799 and #2826: slow collection equivalence tests. — committed to ggeurts/nunit by ggeurts 6 years ago
- Fix for #2799 and #2826: slow collection equivalence tests. Extended NUnitEqualityComparer with hash code calculations to speed up collection equivalence tests Fix spelling mistake — committed to ggeurts/nunit by ggeurts 6 years ago
- Fix for #2799 and #2826: slow collection equivalence tests. Extended NUnitEqualityComparer with hash code calculations to speed up collection equivalence tests Fix spelling mistake — committed to ggeurts/nunit by ggeurts 6 years ago
- Fix for #2799 and #2826: slow collection equivalence tests. Extended NUnitEqualityComparer with hash code calculations to speed up collection equivalence tests Fix spelling mistake — committed to ggeurts/nunit by ggeurts 6 years ago
- Fix for #2799 and #2826: slow collection equivalence tests. Extended NUnitEqualityComparer with hash code calculations to speed up collection equivalence tests Fix spelling mistake — committed to ggeurts/nunit by ggeurts 6 years ago
- Fix for #2799 and #2826: Modified NUnitEqualityComparer and CollectionTally to perform collection equivalence tests with O(log(N)) instead of O(n*m) comparison operations where possible. — committed to ggeurts/nunit by ggeurts 6 years ago
- Fix for #2799 and #2826: Modified NUnitEqualityComparer and CollectionTally to perform collection equivalence tests with O(log(N)) instead of O(n*m) comparison operations where possible. — committed to ggeurts/nunit by ggeurts 6 years ago
I will break down the changes into smaller commits to simplify review. However, my spare time is limited as well. It may take a short while to get there.
I have extended NUnitEqualityComparer and related classes (such as chain comparers and equalityadapter) with hash code generation. For most collection equivalence tests the complexity is now O(log(n)) instead of O(n*m). The exception is where external comparers are used that are based on IComparer or Comparison delegates, because it is not possible to calculate unique hash codes for those cases.
It is possible to speed up collection equivalence tests further by providing CollectionTally with an optimized IEqualityComparer<T> implementation rather than it always using NUnitEqualityComparer for comparisons. However, I prefer to first wait for review of the changes committed so far.
I’m wondering if the various collection constraints should possibly be separated in their implementation, separately optimized and only then possibly recombined to remove duplication.
Actually, I think that my change in nunit/nunit#2600 has caused the problem (I’ve not had time to check it yet, as I’m halfway a VS upgrade). In the case above we will have to run through the entire remaining collection for every match we want to remove. Before my change we would find each match immediately as the first element.