Implementing a List Partitioner

With an understanding of the base types, we can now implement a simple custom partitioner. We'll implement an orderable partitioner for IList<T>, including supporting both a static and a dynamic number of partitions. Our partitioner will force all partitions to synchronize on every element retrieval: While this increases the cost of partitioning, it also provides the best possible load-balancing, at least without having a-priori knowledge of the contents of the data source and the work being performed on every element. If you're familiar with OpenMP, this behavior is similar in nature to OpenMP's dynamic(1). Listing 1 provides the full implementation.

public sealed class SingleItemIListPartitioner<T> : OrderablePartitioner<T>
{
    private readonly IList<T> _source;

    public SingleItemIListPartitioner(IList<T> source) 
        : base(keysOrderedInEachPartition:true, 
               keysOrderedAcrossPartitions:false, 
               keysNormalized:true) 
    { 
        if (source == null) throw new ArgumentNullException("source");
        _source = source; 
    }

    public override bool SupportsDynamicPartitions { get { return true; } }

    public override IList<IEnumerator<KeyValuePair<long, T>>> 
        GetOrderablePartitions(int partitionCount)
    {
        if (partitionCount < 1) 
            throw new ArgumentOutOfRangeException("partitionCount");
        var dynamicPartitioner = GetOrderableDynamicPartitions();
        return (from i in Enumerable.Range(0, partitionCount) 
                select dynamicPartitioner.GetEnumerator()).ToList();
    }

    public override IEnumerable<KeyValuePair<long, T>> 
        GetOrderableDynamicPartitions()
    {
        return GetOrderableDynamicPartitionsCore(
            _source, new StrongBox<Int32>(0));
    }

    private static IEnumerable<KeyValuePair<long, T>> 
        GetOrderableDynamicPartitionsCore(
            IList<T> source, StrongBox<Int32> nextIteration)
    {
        while (true)
        {
            var iteration = 
                Interlocked.Increment(ref nextIteration.Value) - 1;
            if (iteration >= 0 && iteration < source.Count) 
                yield return new KeyValuePair<long, T>(iteration, source[iteration]);
            else yield break;
        }
    }
}

An instance of the SingleItemIListPartitioner is initialized with the target IList<T>, and the constructor simply squirrels this reference away for access by the main methods on the type. Since our type supports dynamic numbers of partitions, we can also easily implement SupportsDynamicPartitions to always return True. That leaves GetOrderablePartitions and GetOrderableDynamicPartitions; we'll start with the latter.

Again, GetOrderableDynamicPartitions is responsible for returning an IEnumerable<KeyValuePair<long,TSource>>, and every call to this enumerable's GetEnumerator method will return an enumerator that represents another partition. We can take advantage of the C# compiler's iterator support to implement this enumerator. The GetOrderableDynamicPartitionsCore method contains a while loop that atomically increments an integral value representing the next index into the list owned by this partition. It yields that index and the associated value from the list, and then loops around to do it again, continuing this process until the index exceeds the length of the loop. Since multiple partitions must share a reference to the same integral index value (every index from the list should be processed once, and only once), and since Int32 is a value type, we take advantage of the System.Runtime.CompilerServices.StrongBox<T> type to create a strongly-typed object wrapper for the Int32. That wrapper is shared with each partition. With GetOrderableDynamicPartitions implemented, implementing GetOrderablePartitions becomes easy: we simply create an enumerable of partitions using GetOrderableDynamicPartitions, retrieve partitionCount enumerators from it, and return that set of enumerators as our static set.

Finally, note the parameters we pass down to the base OrderablePartitioner<TSource>'s constructor. These are the contracts/guarantees mentioned earlier that help a consumer to optimize based on key pieces of knowledge about the partitioning. We've specified that keys are ordered in each partition, because each partition is using Interlocked.Increment, and thus the indices are only increasing in value. And we've specified that keys are normalized, since each index in the range 0 through N-1 will be yielded once and only once from one of the partitions. However, we've specified that keys are not ordered across partitions because of the load-balancing being employed and the lack of strict range partitioning.