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

Okoka

Can 'GetItem' be optimized to return a smaller set of data? – Melioration

yes that is possible but i need to perform calculations for each 20k items. – Okoka

Is MyMethod I/O intensive? Why is it taking 2-3 seconds? – Mev

because more than 1000 line of calculations are inside that method. we already optimized that part our level best. only thing remains before us is to reduce the time by parallel calculations. – Okoka

1000 lines of calcs? who are you sending to Mars? – Melioration

For CPU-intensive operatios, excessive concurrency may sometimes decresae performance. Right now you allow up to min(62, thread pool size) concurrent operations. Do you think it's optimal? – Concoct

Check if this helps: #2987939 – Somnambulate

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

Moiramoirai

How i can ensure that i am using all the CPU cores effectively? – Okoka

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?

Concoct

Ans1:i gave 62 because max size of wait handle is 64. i can increase it to 64 Ans2:It is not IO bound. but more than 1000 line of calc and taking 2 to 3 sec. – Okoka

But you don't really need to wait for all of them to finish before firing up new operations. I'll post some code in a bit. – Concoct

Answer 3

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

Numen

No, it won't make any significant difference in this case. – Moiramoirai

@icepack: Any specific reason for that? – Numen

@Sandeep: really it isn't, unless your loop code compiles down to a few instructions. This is obviously not the case here. – Somnambulate

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.

Dogtooth

what you have mentioned in the edit may reduce some more time. because now 20000/62=322 means around 322 times i am waiting and around 62 thread operations. it can be reduced to only once and around 40(20k/500=40) threads. – Okoka

@Okoka sorry, I meant in groups of 5000, not 500 (this was a typo). This would, however, change your equation to 20K/5K = 4 threads. – Dogtooth

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.

Spheno

I need to tryout this scenario and need to check how much i can reduce in time and performance. – Okoka

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 ?

Morril

I need to get the all results within 1 or 2 minutes. if it is reducing only 20% then there is no use for optimization. in that case i need to change my entire approach itself. – Okoka

yes i will do. but now i am trying with all the possible scenarios. – Okoka