CollectionAssert.AllItemsAreUnique() very slow

[rvhuang]

Consider following simple test case:

// using NUnit.Framework;
        [TestCase(10000)]
        public void TestMethod1(int range)
        {
            CollectionAssert.AllItemsAreUnique(Enumerable.Range(0, range).ToArray());
        }

it takes about 14 seconds to complete.

However, applying MS Test Framework to same test case, it takes about 12 ms only to finish.

// using Microsoft.VisualStudio.TestTools.UnitTesting;
        [TestMethod]
        public void TestMethod1()
        {
            CollectionAssert.AllItemsAreUnique(Enumerable.Range(0, 10000).ToArray());
        }

The gap between two should not be that huge.

[ChrisMaddock]

NUnit uses a different way to test for uniqueness, than MSTest.

MSTest uses simple object equality. NUnit equality tests go through NUnitEqualityComparer - which has extra complexity.

Looking at that class however, there may be low hanging fruit. Before comparing for object equivalence, we create an empty List of FailurePoint objects, which doesn't seem to be used. We then do two null checks prior to object.ReferenceEquals(), which I think are unnecessary. This is incorrect - Resharper's 'find usages' failed me!

I wonder if initialising that list lazily is possible. I'll have a dig at some point.

[rvhuang]

@ChrisMaddock Thanks for looking into the issue. We have a test case which requires to check uniqueness of 10k strings and it cannot finish within one minute. The performance improvement shall help us a lot.

[CharliePoole]

@ChrisMaddock I'm not looking at the code but I believe we accept an IEnumerable rather than an ICollection. You. Might be able to create a special case for collections. Of course we are also doing a lot of boxing in the case of an int value.

[ChrisMaddock]

@CharliePoole - we do, but I'm not sure what sort of special case you're thinking of? Would love to hear, if you get a chance to look later!

[CharliePoole]

A simple thing to try would be (in Matches)

IList list = actual as IList ?? new List<object>(actual);

That way, if an IList were passed in, we would not create a new one.

UPDATE: We would then make the comparisons directly in the existing list.

Following that (if tests showed it necessary) I'd use a generic helper to eliminate boxing. I'm busy on parallelization stuff or I'd give it a try myself.

[ChrisMaddock]

This is a good candidate for Accidentally Quadratic! (If not purposefully quadratic...) Question is now, how we avoid that, whilst still using NUnitEqualityComparer.

Out of time for now, will come back to it. My first plan is to add some efficiencies to NUnitEqualityComparer.AreEqual() - this is low level so should be as efficient as possible - and there's some low hanging fruit here. After that, depending on the effect that has on runtime, I'll come back to look at UniqueItemsConstrant specifically, and see what can be done there.