5
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ I'm not posting this as an answer because it doesn't address your actual question of performance but I notice that you are checking if the local parameter is null twice and not checking the remote parameter at all. Looks like a simple typo/copy and paste. \$\endgroup\$ – Stuart Leyland-Cole Oct 22 '13 at 8:44
  • \$\begingroup\$ How big do you expect local and remote to be? How many changes, insertions and deletions would you expect? \$\endgroup\$ – breischl Oct 23 '13 at 18:02
  • \$\begingroup\$ @breischl local and remote will be around 250.000 items, the nr. of changes may vary considerably, but should not be more than around 2%. \$\endgroup\$ – Magnus Oct 23 '13 at 19:52
1
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Shouldn't it be private readonly ReadOnlyCollection<T> _deleted;? \$\endgroup\$ – Mathieu Guindon Oct 23 '13 at 22:23
  • \$\begingroup\$ @retailcoder No? Why do you think it should? \$\endgroup\$ – Jesse C. Slicer Oct 23 '13 at 22:30
  • \$\begingroup\$ Because it's C# and it's a private field? It would mootinize usage of this in the constructor and enhance readability I find. \$\endgroup\$ – Mathieu Guindon Oct 23 '13 at 22:34
  • 1
    \$\begingroup\$ Hmm I guess I'm just used to ReSharper-style naming conventions for private fields. Code completion puts them all together that way, and it differenciates private fields from parameters and local variables. At the end of the day it's a matter of personal preference, I'll try real hard to stop twitching when I see private readonly SomeType field; ...nice review BTW (got my +1) :) \$\endgroup\$ – Mathieu Guindon Oct 24 '13 at 1:20
  • 2
    \$\begingroup\$ Thanks for the tips @JesseC.Slicer. So the only reason you convert local to a list is for the ability to set capacity for the lists? If that is done I would send in local to the constructor of the hashset also and avoid the lock/add in the loop. You are correct in that I don't care about the order and if we are going parallel the use of ConcurrentBag instead of lists would probably be a good idea to avoid the need for lock. Possibly create my own collection that inherits from ReadOnlyCollection but wraps IProducerConsumerCollection<T> instead if IList<T>. \$\endgroup\$ – Magnus Oct 24 '13 at 7:39
1
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Nice, what kind of speed improvement did you get compared to the original implementation? \$\endgroup\$ – Magnus Feb 21 at 11:02
  • \$\begingroup\$ I've made a simple benchmark implementation (gist.github.com/adospace/917429d2163a5435f5d19b9f092affce). Seems like that your implementation is pretty fast, actually faster of parallelized versions. Using a simple foreach in my code, I found it's a bit faster of your function (about 18% faster): I guess the point here is that lock contention in a parallel implementation degrades performance. \$\endgroup\$ – adospace Feb 21 at 14:34
  • \$\begingroup\$ I guess since there is no cpu intensive operation, this might not be an optimal case for palatalization. \$\endgroup\$ – Magnus Feb 21 at 14:51
  • \$\begingroup\$ Yes, I suppose that the parallel version could go better if local items are taken in chunks of many items (say local.Count()/10) so to give more work to each running thread and reduce lock contention. \$\endgroup\$ – adospace Feb 21 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.