Optimization of comparing two collections and get the changes

Question

I use the following code to get the changes between two collections. Objects are "joined" using a primary key. Any tips on performance issues or other optimizations appreciated.

/// <summary>
/// Gets the changes [Deleted, changed, inserted] comparing this collection to another.
/// </summary>
/// <param name="local">The source collection.</param>
/// <param name="remote">The remote collection to comare agains.</param>
/// <param name="keySelector">The primary key selector function</param>
/// <returns></returns>
public static ChangeResult<TSource> CompareTo<TSource, TKey>(this IEnumerable<TSource> local, IEnumerable<TSource> remote, Func<TSource, TKey> keySelector)
{
    if (local == null)
        throw new ArgumentNullException("local");
    if (remote == null)
        throw new ArgumentNullException("remote");
    if (keySelector == null)
        throw new ArgumentNullException("keySelector");

    var remoteKeyValues = remote.ToDictionary(keySelector);

    var deleted = new List<TSource>();
    var changed = new List<TSource>();
    var localKeys = new HashSet<TKey>();

    foreach (var localItem in local)
    {
        var localKey = keySelector(localItem);
        localKeys.Add(localKey);

        /* Check if primary key exists in both local and remote 
         * and if so check if changed, if not it has been deleted
         */
        TSource changeCandidate;
        if (remoteKeyValues.TryGetValue(localKey, out changeCandidate))
        {
            if (!changeCandidate.Equals(localItem))
                changed.Add(changeCandidate);
        }
        else
        {
            deleted.Add(localItem);
        }
    }
    var inserted = remoteKeyValues
                    .Where(x => !localKeys.Contains(x.Key))
                    .Select(x => x.Value)
                    .ToList();

    return new ChangeResult<TSource>(deleted, changed, inserted);
}

/// <summary>
/// Immutable class containing changes
/// </summary>
public class ChangeResult<T>
{
    public ChangeResult(IList<T> deleted, IList<T> changed, IList<T> inserted)
    {
        Deleted = new ReadOnlyCollection<T>(deleted);
        Changed = new ReadOnlyCollection<T>(changed);
        Inserted = new ReadOnlyCollection<T>(inserted);
    }

    public IList<T> Deleted { get; private set; }
    public IList<T> Changed { get; private set; }
    public IList<T> Inserted { get; private set; }
}

Usage

var changes = Col1.CompareTo(Col2, x => x.UniqueId);

Answer 1

I think it looks like good, clear, general purpose code. I don't see any really significant changes to make, but there might be some minor improvements available.

First, allocating default size collections and letting them grow naturally may not work well for large collections. IIRC they start at 10 elements, and then double each time they top out. But each doubling requires a reallocation and a copy, which can add up when you're adding thousands of items. You should initialize them with the proper size if you know what it is. If you can take a decent guess, even that will help: starting at (for example) 200 elements instead of 10 will save you a lot of allocations. But avoid calling Count() on your input IEnumerable objects since that could cause them to be enumerated an extra time, depending on the underlying implementation.

Second, if you commonly have no insertions in remote and no deletions in local, you could add some code to skip the final enumeration of remoteKeyValue. As you're enumerating local, keep a count of how many items were found in remoteKeyValues. If the number you end up with is equal to remoteKeyValues.Count then you know there are no insertions, because you already matched all the items in that collection.

As always with performance tweaking, profile it before and after any changes.

Answer 2

I would first make ChangeResult<T> truly immutable using sealed and readonly. It's unfortunate that we don't have true immutable syntax for automatic properties, but space is cheap, they say:

/// <summary>
/// Immutable class containing changes
/// </summary>
public sealed class ChangeResult<T> : IChangeResult<T>
{
    private readonly ReadOnlyCollection<T> deleted;

    private readonly ReadOnlyCollection<T> changed;

    private readonly ReadOnlyCollection<T> inserted;

    public ChangeResult(IList<T> deleted, IList<T> changed, IList<T> inserted)
    {
        this.deleted = new ReadOnlyCollection<T>(deleted);
        this.changed = new ReadOnlyCollection<T>(changed);
        this.inserted = new ReadOnlyCollection<T>(inserted);
    }

    public IList<T> Deleted
    {
        get
        {
            return this.deleted;
        }
    }

    public IList<T> Changed
    {
        get
        {
            return this.changed;
        }
    }

    public IList<T> Inserted
    {
        get
        {
            return this.inserted;
        }
    }
}

and because it's good design to program to interfaces, I extracted one:

public interface IChangeResult<T>
{
    IList<T> Deleted
    {
        get;
    }

    IList<T> Changed
    {
        get;
    }

    IList<T> Inserted
    {
        get;
    }
}

Then, in your CompareTo<TSource, TKey>() method, I have it return said interface. Also, I expand the deleted and changed lists to the capacity of the local enumerable (converted to a list locally so an expensive enumerable doesn't get iterated multiple times). This may be overkill in some cases, but in the worst cases, you wind up eliminating potentially expensive list expansion reallocations. A classic speed-vs-space tradeoff. I would then posit that this is actually a great algorithm to go parallel with, as long as you don't care about the order in the three lists:

/// <summary>
/// Gets the changes [Deleted, changed, inserted] comparing this collection to another.
/// </summary>
/// <typeparam name="TSource"></typeparam>
/// <typeparam name="TKey"></typeparam>
/// <param name="local">The source collection.</param>
/// <param name="remote">The remote collection to compare against.</param>
/// <param name="keySelector">The primary key selector function</param>
/// <returns></returns>
public static IChangeResult<TSource> CompareTo<TSource, TKey>(
    this IEnumerable<TSource> local,
    IEnumerable<TSource> remote,
    Func<TSource, TKey> keySelector)
{
    if (local == null)
    {
        throw new ArgumentNullException("local");
    }

    if (remote == null)
    {
        throw new ArgumentNullException("remote");
    }

    if (keySelector == null)
    {
        throw new ArgumentNullException("keySelector");
    }

    local = local.ToList();

    var remoteKeyValues = remote.ToDictionary(keySelector);
    var deleted = new List<TSource>(local.Count());
    var changed = new List<TSource>(local.Count());
    var localKeys = new HashSet<TKey>();

    Parallel.ForEach(
        local,
        localItem =>
        {
            var localKey = keySelector(localItem);

            lock (localKeys)
            {
                localKeys.Add(localKey);
            }

            /* Check if primary key exists in both local and remote
             * and if so check if changed, if not it has been deleted
             */
            TSource changeCandidate;

            if (remoteKeyValues.TryGetValue(localKey, out changeCandidate))
            {
                if (changeCandidate.Equals(localItem))
                {
                    return;
                }

                lock (changed)
                {
                    changed.Add(changeCandidate);
                }
            }
            else
            {
                lock (deleted)
                {
                    deleted.Add(localItem);
                }
            }
        });

    var inserted = remoteKeyValues
        .AsParallel()
        .Where(x => !localKeys.Contains(x.Key))
        .Select(x => x.Value)
        .ToList();

    return new ChangeResult<TSource>(deleted, changed, inserted);
}

Answer 3

I tried to make a parallelized implementation without full locks (use collections from Concurrency namespace). Also, I've added an optional compareFunc function useful if you want to test object equality without override Equals on TSource.

This is my version:

    /// <summary>
    /// Gets the changes [Deleted, changed, inserted] comparing this collection to another.
    /// </summary>
    /// <param name="local">The source collection.</param>
    /// <param name="remote">The remote collection to comare agains.</param>
    /// <param name="keySelector">The primary key selector function</param>
    /// <param name="compareFunc">Optional camparing function between 2 objects of type TSource</param>
    /// <returns>List of changes as Added, Removed and Changed items of type TSource</returns>
    public static ChangeResult<TSource> CompareTo<TSource, TKey>(
        this IEnumerable<TSource> local, IEnumerable<TSource> remote, Func<TSource, TKey> keySelector, Func<TSource, TSource, bool> compareFunc = null)
    {
        if (local == null)
            throw new ArgumentNullException("local");
        if (remote == null)
            throw new ArgumentNullException("remote");
        if (keySelector == null)
            throw new ArgumentNullException("keySelector");

        var remoteKeyValues = new ConcurrentDictionary<TKey, TSource>(remote.ToDictionary(keySelector));
        var localKeyValues = new ConcurrentDictionary<TKey, TSource>(local.ToDictionary(keySelector));
        var changed = new ConcurrentBag<Tuple<TSource, TSource>>();

        Parallel.ForEach(
           local,
           localItem =>
           {
               var localItemKey = keySelector(localItem);

               //1. Check if item is both in local and remote
               if (remoteKeyValues.TryRemove(localItemKey, out var remoteItemValue))
               {
                   //1.a item is in both collections -> check if they are different
                   var isItemChanged = compareFunc != null ? !compareFunc(localItem, remoteItemValue) :
                        !localItem.Equals(remoteItemValue);

                   if (isItemChanged)
                   {
                       //1.b are different -> mark a change
                       changed.Add(new Tuple<TSource, TSource>(localItem, remoteItemValue));
                   }

                   //1.c remove the item from local list as it's prensent in remote list too
                   //this should never return false
                   localKeyValues.TryRemove(localItemKey, out var localItemValue);
               }

               //2. if item is not in remote list means it has been removed
           });

        var deleted = localKeyValues.Values;
        var inserted = remoteKeyValues.Values;

        return new ChangeResult<TSource>(deleted, changed, inserted);
    }

and ChangeResult class slightly modified:

    /// <summary>
/// Immutable class containing changes
/// </summary>
public sealed class ChangeResult<T>
{
    public ChangeResult(IEnumerable<T> deleted, IEnumerable<Tuple<T, T>> changed, IEnumerable<T> inserted)
    {
        Deleted = deleted;
        Changed = changed;
        Inserted = inserted;
    }

    public IEnumerable<T> Deleted { get; }

    public IEnumerable<Tuple<T, T>> Changed { get; }

    public IEnumerable<T> Inserted { get; }
}

end this is a test

[TestClass]
public class ListUtilsTests
{
    class User
    {
        public string Key { get; set; }

        public string Name { get; set; }
    }

    [TestMethod]
    public void ListUtilsCompare()
    {
        var local = new[] { new User() { Key = "A", Name = "John" }, new User() { Key = "B", Name = "Red" } };
        var remote = new[] { new User() { Key = "B", Name = "Red (edited)" }, new User() { Key = "C", Name = "Tizio" } };

        var changes = local.CompareTo(remote, _ => _.Key, (i1, i2) => i1.Name == i2.Name);

        Assert.IsNotNull(changes);
        Assert.AreEqual(1, changes.Inserted.Count());
        Assert.AreEqual("Tizio", changes.Inserted.First().Name);
        Assert.AreEqual(1, changes.Deleted.Count());
        Assert.AreEqual("John", changes.Deleted.First().Name);
        Assert.AreEqual(1, changes.Changed.Count());
        Assert.AreEqual("Red (edited)", changes.Changed.First().Item2.Name);
    }
}

Edit: After further investigations, I found that actually going without parallel threads it runs much faster (see https://gist.github.com/adospace/917429d2163a5435f5d19b9f092affce for a comparison chart).

So just replace the Parallel code above with foreach (var localItem in local)