Channels ▼


Custom Parallel Partitioning With .NET 4

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, 
        _source = source; 

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

        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>> 
        return GetOrderableDynamicPartitionsCore(
            _source, new StrongBox<Int32>(0));

    private static IEnumerable<KeyValuePair<long, T>> 
            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;

Listing 1: A Load-Balancing Orderable Partitioner for IList<T>

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.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags


<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags


<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

