How can I maximize the performance of element-wise operation on an big array in C#

Question

The operation is to multiply every i-th element of a array (call it A) and i-th element of a matrix of the same size(B), and update the same i-th element of A with the value earned.

In a arithmetic formula, A'[i] = A[i]*B[i] (0 < i < n(A))

What's the best way to optimize this operation in a multi-core environment?

Here's my current code;

var learningRate = 0.001f;
var m = 20000;
var n = 40000;
var W = float[m*n]; 
var C = float[m*n];

//my current code ...[1]
Parallel.ForEach(Enumerable.Range(0, m), i =>
{
    for (int j = 0; j <= n - 1; j++)
    {
         W[i*n+j] *= C[i*n+j];
    }
});

//This is somehow far slower than [1], but I don't know why ... [2]
Parallel.ForEach(Enumerable.Range(0, n*m), i =>
{
    w[i] *= C[i]
});


//This is faster than [2], but not as fast as [1] ... [3]
for(int i = 0; i < m*n; i++)
{
    w[i] *= C[i]
}

Tested the following method. But the performance didn't get better at all. http://msdn.microsoft.com/en-us/library/dd560853.aspx

   public static void Test1()
    {
        Random rnd = new Random(1);

        var sw1 = new Stopwatch();
        var sw2 = new Stopwatch();
        sw1.Reset();
        sw2.Reset();

        int m = 10000;
        int n = 20000;
        int loops = 20;

        var W = DummyDataUtils.CreateRandomMat1D(m, n);
        var C = DummyDataUtils.CreateRandomMat1D(m, n);

        for (int l = 0; l < loops; l++)
        {
            var v = DummyDataUtils.CreateRandomVector(n);
            var b = DummyDataUtils.CreateRandomVector(m);

            sw1.Start();

            Parallel.ForEach(Enumerable.Range(0, m), i =>
            {
                for (int j = 0; j <= n - 1; j++)
                {
                    W[i*n+j] *= C[i*n+j];
                }
            });
            sw1.Stop();

            sw2.Start();
            // Partition the entire source array. 
            var rangePartitioner = Partitioner.Create(0, n*m);

            // Loop over the partitions in parallel.
            Parallel.ForEach(rangePartitioner, (range, loopState) =>
            {
                // Loop over each range element without a delegate invocation. 
                for (int i = range.Item1; i < range.Item2; i++)
                {
                    W[i] *= C[i];
                }
            });

            sw2.Stop();

            Console.Write("o");
        }

        var t1 = (double)sw1.ElapsedMilliseconds / loops;
        var t2 = (double)sw2.ElapsedMilliseconds / loops;

        Console.WriteLine("t1: " + t1);
        Console.WriteLine("t2: " + t2);
    }

---

Result:

t1: 119

t2: 120.4

Answer 1

The problem is that while invoking a delegate is relatively fast, it adds up when you invoke it many times and the code inside the delegate is very simple.

What you could try instead is to use a Partitioner to specify the range you want to iterate, which allows you to iterate over many items for each delegate invocation (similar to what you're doing in [1]):

Parallel.ForEach(Partitioner.Create(0, n * m), partition =>
    {
        for (int i = partition.Item1; i < partition.Item2; i++)
        {
            W[i] *= C[i];
        }
    });