Increment an index within an array of running tasks

Question

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";

As long as each thread accesses only its own section of the array (which I understand is your intent, you should be fine directly accessing the array by index http://stackoverflow.com/questions/1460634/are-c-sharp-arrays-thread-safe — Eric J., Oct 07 '15 at 04:25
I don't understand why you are passing `yStart` as a `ref` as `yStart` is a local variable that is not used past the call to `this.Apply(...)`. — Enigmativity, Oct 07 '15 at 06:26
@HenkHolterman Sorry, I should have been more specific. I meant that the assignment of value to the location in the array was incorrect. — James South, Oct 11 '15 at 23:57

score 1 · Accepted Answer · answered Oct 07 '15 at 05:01

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.

I think you're on to something here but there's an error once you begin processing on each thread. If you change your `int[]` to a string and assign `y + x` to that index as a string you'll see a difference once you hit 10. Single = `output[10] = "1+0`, multiple `output[10] = "0+10"`. — James South, Oct 07 '15 at 05:21
That is not because of the incrementing counter, your for y and for x overlaps.. 1+0 = 1 , 0+1 = 1 etc.. make a test for `if(x == y) {...}` and you will see that the issue is in the loops. the counter is correct — Roger Johansson, Oct 07 '15 at 10:46

Yuval Itzchakov · Answer 2 · 2015-10-07T04:39:06.153

0

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.

edited Oct 07 '15 at 04:39

answered Oct 07 '15 at 04:32

Yuval Itzchakov

146,575
32
257
321

Hi thanks for the answer. I've tried to give a further example of the output I am trying to achieve. I need to assign a specific value at he given index with the result the same in both single and multi-threaded environments. – James South Oct 07 '15 at 04:53
@James Will you be updating the same indexes of the array from multiple threads? – Yuval Itzchakov Oct 07 '15 at 04:55
I'd like to assign the value at the correct index for each part of the array within each thread. The tricky bit for me is figuring out what value to assign to the indexer to ensure the correct position. I may have been staring at this for too long. – James South Oct 07 '15 at 04:59

Increment an index within an array of running tasks

2 Answers2