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 stackoverflow.com/questions/1460634/… — Eric J.
– Eric J., Commented Oct 7, 2015 at 4: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
– Enigmativity, Commented Oct 7, 2015 at 6: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
– James South, Commented Oct 11, 2015 at 23:57

Roger Johansson · Accepted Answer · 2015-10-07 05:01:55Z

1

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.

answered Oct 7, 2015 at 5:01

Roger Johansson

23.3k18 gold badges108 silver badges206 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

James South Over a year ago

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

Roger Johansson Over a year ago

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

Yuval Itzchakov · Accepted Answer · 2015-10-07 04:39:06Z

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 7, 2015 at 4:39

answered Oct 7, 2015 at 4:32

Yuval Itzchakov

150k32 gold badges275 silver badges333 bronze badges

3 Comments

James South Over a year ago

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.

Yuval Itzchakov Over a year ago

@James Will you be updating the same indexes of the array from multiple threads?

James South Over a year ago

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.

Collectives™ on Stack Overflow

Increment an index within an array of running tasks

2 Answers 2

2 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related