How to optimize large size for loop

Question

I have a for loop with more than 20k iterations,for each iteration it is taking around two or three seconds and total around 20minutes. how i can optimize this for loop. I am using .net3.5 so parallel foreach is not possible. so i splited the 200000 nos into small chunks and implemented some threading now i am able reduce the time by 50%. is there any other way to optimize these kind of for loops.

My sample code is given below

    static double sum=0.0;
    public double AsyncTest()
    {
            List<Item> ItemsList = GetItem();//around 20k items
            int count = 0;
            bool flag = true;
            var newItemsList = ItemsList.Take(62).ToList();
            while (flag)
            {
                int j=0;
                WaitHandle[] waitHandles = new WaitHandle[62];
                foreach (Item item in newItemsList)
                {
                    var delegateInstance = new MyDelegate(MyMethod);
                    IAsyncResult asyncResult = delegateInstance.BeginInvoke(item.id, new AsyncCallback(MyAsyncResults), null);
                    waitHandles[j] = asyncResult.AsyncWaitHandle;
                    j++;
                }
                WaitHandle.WaitAll(waitHandles);
                count = count + 62;
                newItemsList = ItemsList.Skip(count).Take(62).ToList();  
            }
            return sum;
    }

    public double MyMethod(int id)
    {
        //Calculations
        return sum;
    }

    static public void MyAsyncResults(IAsyncResult iResult)
    {
        AsyncResult asyncResult = (AsyncResult) iResult;
        MyDelegate del = (MyDelegate) asyncResult.AsyncDelegate;
        double mySum = del.EndInvoke(iResult);
        sum = sum + mySum;
    }

Answer 1

It's possible to reduce number of loops by various techniques. However, this won't give you any noticeable improvement since the heavy computation is performed inside your loops. If you've already parallelized it to use all your CPU cores there is not much to be done. There is a certain amount of computation to be done and there is a certain computer power available. You can't squeeze from your machine more than it can provide.

You can try to:

1. Do a more efficient implementation of your algorithm if it's possible
2. Switch to faster environment/language, such as unmanaged C/C++.

Answer 2

1. Is there a rationale behind your batches size (62)?
2. Is "MyMethod" method IO bound or CPU bound?

What you do in each cycle is wait till all the batch completes and this wastes some cycles (you are actually waiting for all 62 calls to complete before taking the next batch). Why won't you change the approach a bit so that you still keep N operations running simultaneosly, but you fire a new operation as soon as one of the executind operations completes?

Answer 3

According to this blog, for loops are more faster than foreach in case of collections. Try looping with for. It will help.

Answer 4

Correct me if I'm wrong, but it looks to me like your threading is at the individual item level - I wonder if this may be a little too granular.

You are already doing your work in blocks of 62 items. What if you were to take those items and process all of them within a single thread? I.e., you would have something like this:

void RunMyMethods(IEnumerable<Item> items)
{
    foreach(Item item in items)
    {
        var result = MyMethod(item);
        ...
    }
}

Keep in mind that WaitHandle objects can be slower than using Monitor objects: http://www.yoda.arachsys.com/csharp/threads/waithandles.shtml

Otherwise, the usual advice holds: profile the performance to find the true bottlenecks. In your question you state that it takes 2-3 seconds per iteration - with 20000 iterations, it would take a fair bit more than 20 minutes.

Edit:

If you are wanting to maximise your usage of CPU time, then it may be best to split your 20000 items into, say, four groups of 5000 and process each group in its own thread. I would imagine that this sort of "thick 'n chunky" concurrency would be more efficient than a very fine-grained approach.

Answer 5

It sounds like you have a CPU intensive MyMethod. For CPU intensive tasks, you can gain a significant improvement by parallelization, but only to the point of better utilizing all CPU cores. Beyond that point, too much parallelization can start to hurt performance -- which I think is what you're doing. (This is unlike I/O intensive tasks where you pretty much parallelize as much as possible.)

What you need to do, in my opinion, is write another method that takes a "chunk" of items (not a single item) and returns their "sum":

double SumChunk(IEnumerable<Item> items)
{
    return items.Sum(x => MyMethod(x));
}

Then divide the number of items by n (n being the degree of parallelism -- try n = number of CPU cores, and compare that to x2) and pass each chunk to an async task of SumChunk. And finally, sum up the sub-results.

Also, watch if any of the chunks is completed much before the other ones. If that's the case, then your task distributions is not homogen. You'd need to create smaller chunks (say chunks of 300 items) and pass those to SumChunk.

Answer 6

To start with, the numbers just don't add:

20k iterations,for each iteration it is taking around two or three seconds and total around 20minutes

That's a x40 'parallelism factor' - you can never achieve that running on a normal machine.

Second, when 'optimizing' a CPU intensive computation, there's no sense in parallelizing beyond the number of cores. Try dropping that magical 62 to 16 and bench test - it will actually run faster.

I ran a deformed malversion of your code on my laptop, and got some 10-20% improvement using Parallel.ForEach

So maybe you can make it run 17 minutes instead of 20 - does it really matter ?