Channels ▼
RSS

Tools

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, 
               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;
        }
    }
}

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

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<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

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video