Reducing runtime of method from 24 hours to 1 hour

Question

I have a 'For' loop I need to run from 0 to 2,147,483,647 (int.MaxValue). Inside the loop I'm calling a method that calculates a very complex equation and it returns the value for each parameter. I wish to get the highest return value.

The total runtime of my for loop takes about full 24 hours. How and can I reduce the runtime of my code to only one hour? Maybe 4 hours if I will use distributed computing?

    static void Main(string[] args)
    {
        CheckValuesZeroToMaxInt();
        Console.ReadLine();
    }

    private static void CheckValuesZeroToMaxInt()
    {
        for (int i = 0; i < int.MaxValue; i++)
        {
            ComplexMath(i);
        }
    }

I know how to use 'Parallel.For', but still this offers very little help. How can I take my c# code and run it on a cluster of computers to get the return value from my method in no time? Is there a site that offers this service for a low or free cost?

Well how many cores do you have access to? Is the problem genuinely embarrassingly parallelizable (as it appears)? It would be *simpler* to do this on one machine with several cores, but you could distribute it if necessary. — Jon Skeet, May 22 '14 at 17:10
If the calls are independent of one another, why not just use `Parallel.For()`? — 48klocs, May 22 '14 at 17:11
Without knowing what `ComplexMath` is doing, I don't see how we could possibly give a complete answer. An empty loop (without the function call) takes at most a few seconds. — Wonko the Sane, May 22 '14 at 17:14
Make `ComplexMath` run faster. It's a flip answer, but consider the question: Here's some code that takes .00001% of the execution time. I also have a function that takes 99.99999% of the time which I'm not showing. How do I make it 24 times faster? Well you could run it on a 30+ core computer and parallelize it, or run it on 30 different computers each doing a portion of the range. Or, you could optimize your function that takes all the time, and possibly speed it up by 100 or 1000 times. — hatchet - done with SOverflow, May 22 '14 at 17:25
Can you please show me how to run this code on 10 or more computers? Is there a site that give this service for free? — asker22, May 22 '14 at 17:34
As @hatchet said, make `ComplexMath` run faster, regardless of whether you exploit parallelism, because the speedup multiple you get will apply regardless of whatever else you do. [*This is the method I and many others use*](http://stackoverflow.com/a/378024/23771), to look for speedup opportunities. If your `ComplexMath` has any simple ways to be made faster, it will find them. — Mike Dunlavey, May 22 '14 at 19:26

peter · Answer 1 · 2014-05-22T19:38:15.580

The easiest way to do it on one machine would be with the Parallel.For-loop

private static void CheckValuesZeroToMaxInt()
{
    object maxValueLock = new object();
    int maxValue = int.MinValue;

    Parallel.For(0, int.MaxValue, i =>
    {
        int tmpMaxValue = ComplexMath(i);

        if (tmpMaxValue > maxValue)
        {
            lock(maxValueLock)
            {
                if (tmpMaxValue > maxValue)
                    maxValue = tmpMaxValue;
            }
        }
    }

    Console.WriteLine(maxValue);
}

However, since your ComplexMath function only takes ~0.04ms ((24 / (2^31)) * 3600 * 1000) to execute, you'd maybe get stuck with the constant locking and wouldn't get almost any improvement. To prevent this from happening, we can change the above function to execute more steps within a thread.

const long million = 1000*1000;

private static void CheckValuesZeroToMaxInt()
{
    object maxValueLock = new object();
    int maxValue = int.MinValue;

    Parallel.For(0, (int.MaxValue / million) + 1, i =>
    {
        int privateMaxValue = int.MinValue;

        for (long j = i * million; j < (i+1) * million && j < int.MaxValue; j++)
        {
            int tmpMaxValue = ComplexMath(j);

            if (tmpMaxValue > privateMaxValue)
            {
                privateMaxValue = tmpMaxValue;
            }
        }

        lock(maxValueLock)
        {
            if (privateMaxValue > maxValue)
                maxValue = privateMaxValue;
        }
    }

    Console.WriteLine(maxValue);
}

The second version should scale pretty much linearly with the number of processors, so if you run it on a machine with 24 cores, it will finish within 1h. Of course instead of Parallel.For you can use any kind of communication to distribute the computation between multiple machines.

Reducing runtime of method from 24 hours to 1 hour

1 Answers1