CODEWITHSUNDEEP
c#multithreading
James South
James South

Reputation: 10635

Increment an index within an array of running tasks

Given the following code. 

int i = 0;    
int width = 100;
int height = 100;
int[] output = new int[width * height];

for (int y = 0; y < height; y++)
{
    for (int x = 0; x < width; x++)
    {
        output[i++] = y+x;
    }
}

I can be assured that both the index and the assigned sum are incremental.

With the following code I am splitting the job into several sub-tasks

int width = 100;
int height = 100;
int[] output = new int[width * height];
int partitionCount = this.Parallelism;

Task[] tasks = new Task[partitionCount];

for (int p = 0; p < partitionCount; p++)
{
    int current = p;
    tasks[p] = Task.Run(() =>
    {
        int batchSize = height / partitionCount;
        int yStart = current * batchSize;
        int yEnd = current == partitionCount - 1 ? height : yStart + batchSize;

        this.Apply(output, width, height, yStart, yEnd, ref yStart);
    });
}

Task.WaitAll(tasks);


void Apply(int[] output, int width, int height, int startY, int endY, ref int index)
{
    for (int y = startY; y < endY; y++)
    {
        for (int x = 0; x < width; x++)
        {
            // How do I increment the index within output.
            // Interlocked.Increment(ref index);                
            // output[index] = y+x; doesn't work
        }
    }
}

How can I ensure that the index is incremented appropriately and ensure that the assigned output at each index of the multi-threaded approach matches the single-threaded approach?

Edit: I've added an expected output to further explain what I am trying to do.

e.g. 

output[0] = "0+1";
output[1] = "0+1";
output[2] = "0+2";
output[3] = "0+3";

Upvotes: 0

Views: 457

Answers (2)

Roger Johansson
Roger Johansson

Reputation: 23214

You can wrap your index in an object and pass that object, like so:

class Counter
{
    public int Index;
}

class Program
{
    static void Main(string[] args)
    {
        int width = 100;
        int height = 100;
        int[] output = new int[width * height];
        int partitionCount = 10;

        Task[] tasks = new Task[partitionCount];
        var counter = new Counter();
        for (int p = 0; p < partitionCount; p++)
        {
            int current = p;
            tasks[p] = Task.Run(() =>
            {
                int batchSize = height / partitionCount;
                int yStart = current * batchSize;
                int yEnd = current == partitionCount - 1 ? height : yStart + batchSize;

                Apply(output, width, height, yStart, yEnd, counter);
            });
        }

        Task.WaitAll(tasks);
    }

    static void Apply(int[] output, int width, int height, int startY, int endY, Counter counter)
    {
        for (int y = startY; y < endY; y++)
        {
            for (int x = 0; x < width; x++)
            {
                output[Interlocked.Increment(ref counter.Index) -1] = y + x;
            }
        }
    }
}

This will let you increment the index and still pass it by reference to the worker threads.

This could ofc be cleaned up so that there is a method on the counter that both increments and returns the new value to remove the interlocked logic from your worker just to hide the concurrency aspects of it.

This would work for both the single threaded and multi threaded version.

Upvotes: 1

Yuval Itzchakov
Yuval Itzchakov

Reputation: 149538

How can I ensure that the index is incremented appropriately and ensure that the assigned output at each index of the multi-threaded approach matches the single-threaded?

Two things to notice:

First, As long as the variables you're closing over in your lambda aren't being modified, you shouldn't have a problem there.

Regarding Apply, given each batch works on a separate part of the array, you should be fine as long as that guideline is followed. If you are updating a shared location concurrently, you will need a memory barrier while updating, perhaps a lock, which will have an effect on performance.

Upvotes: 0

Related Questions