Optimizing this method (HashSet.RemoveWhere performance issue)

Question

I have the following method:

public static HashSet<PathDetails> GetDeletedPaths(HashSet<PathDetails> old, HashSet<PathDetails> current)
{
 var deleted = new HashSet<PathDetails>(old);
 deleted.RemoveWhere(x => current.Any(y => y.Path == x.Path));
 return deleted;
}

PathDetails is a struct that, among other things, contains Path of type String. This method takes the longest in my application and I was wondering if there were any good ways of improving its performance. These hash sets are used elsewhere in a more hashset-friendly way, so the method must take in two sets and return a set.

Answer 1

Instead of using the RemoveWhere() method together with the Any() method you should consider to just use ExceptWith() method.

public static HashSet<PathDetails> GetDeletedPaths(HashSet<PathDetails> old, HashSet<PathDetails> current)
{
 var deleted = new HashSet<PathDetails>(old);
 deleted.ExceptWith(current);
 return deleted;
}

Your approach calls for each item in deleted the Any() of current whereas ExceptWith() just calls for each item in current the Remove() method of deleted.

• Alexandru: This approach is still problematic because the structure contains more than just Path, and I only want to match on the Path of each PathDetails structure, not all of its members.
• Heslacher: Then add an IEqualityComparer which only targets the Path property.
• Alexandru: So basically, var deleted = new HashSet<PathDetails>(old, _pathOnlyEqualityComparer); and (after calling ExceptWith on the other hash sets) I would return new HashSet<PathDetails>(deleted); in order to revert to the default equality comparer for PathDetails for this object? The performance boost is excellent, by the way. Thank you!
• Alexandru: I also implemented my equality comparer's Equals method using return (x.Path.Equals(y.Path, StringComparison.OrdinalIgnoreCase)); in case anyone is interested, as ordinal is what I care about and it is much more performant in O(1) time.

Answer 2

I would recommend making a set containing the paths in current. Then instead of adding and removing PathDetails, just add them instead.

var paths = new HashSet<string>(current.Select(x => x.Path));
return new HashSet<PathDetails>(old.Where(x => !paths.Contains(x.Path)));

---

Since PathDetails is a struct, make sure you're overriding Equals and GetHashCode, as it can lead to improved performance.