How long will this take to run and how can I speed it up

Question

I'm running some code to test Brownian Motion and divergence, I was curious how long this code will take to run as well as any ways to speed up the process. I am relatively new to java, so the code at the present time is relatively basic. The arguments that I am running are 1000000 1000000.

public class BrownianMotion {

    public static void main(String[] args) {

    /**starts vars for program*/

    int N = Integer.parseInt(args[0]);
    int T = Integer.parseInt(args[1]);
    double sqtotal = 0;
    double r;
    double avg;

    /**number of trials loop*/

    for (int count=0;count<T;count++) {

        /**started here so that x & y reset at each trial*/

        int x = 0;
        int y = 0;

        /**loop for steps*/
        for (int steps=0;steps<N;steps++) {

        r = Math.random();
        if      (r < 0.25) x--;
        else if (r < 0.50) x++;
        else if (r < 0.75) y--;
        else if (r < 1.00) y++;

        }
        /**squared total distance after each trial*/
        sqtotal = sqtotal + (x*x+y*y);

    }

    /**average of squared total*/

    avg = sqtotal/T;
    System.out.println(avg);

    }
}

Thanks in advance for the help.

Answer 1

As I understand your code, you could run each trial in parallel. If your CPU has multiple cores it would run faster accordingly.

(EDIT ADDED)

Normally, I'd convert the algorithm into a Callable, create tens of them, (one per dimension, per state, etc.) then use Executors.newFixedThreadPool() to create a thread pool of reasonable size (say, for my might Intel i3 laptop, 4 threads) and call invokeAll(). More details in this blog post

However, in your example of 100,000 this doesn't work so well. The ideal way would be to use a CompletionService to resubmit jobs as they finish. This starts getting complicated.

A simpler, not as efficient method (but still faster) might be to

1. Create a collection containing, say, 10 BrownianWalkers. Note that if they set x and y = 0 at the start they can be reused. So you only need to create this list once
2. Create the fixedThreadPool
3. In a loop for i=0...10000 {
4. call submitAll().
5. Loop over the results (the Futures) and add them to your sum.
   }

You will waste a bit of time waiting for all to finish, but there should still be a significant speedup. Since most processors have cores in 2,4,8 etc..., a slight improvement would be to make the collection a power of 2 (instead of 10 which makes the math easy)

Answer 2

There are at least three ways in which you can make your code go faster, listed from more effective to least effective:

1. Reduce the complexity of the algorithm. Right now, your algorithm has a O(N^2) time complexity: that means that the time needed to complete the processing is proportional to the square of the length of the input. You might need to revisit the algorithm to reduce unnecessary computations or apply optimizations on intermediate results.

2. Introduce parallelism in the algorithm. Your algorithm is currently implemented as a big block of code that executes sequentially; that is (barring instruction pipelining at the hardware level) every instruction can be executed only when the previous one is completed. You might rewrite the code to use threads to split the work across multiple processors or you could use parallelization frameworks that do most of the work for you. This is less efficient than point 1. because the number of processors in your machine is constant, so it will not scale when the size of the input that you feed to the algorithm increases.

3. Use a faster machine. If the algorithm is not improved in other ways, well, the only way to speed it up is to run it faster.

Answer 3

This should be a working parallel implementation:

public class BrownianMotionThread extends Thread
{
    int i;
    int T;
    int N;
    int numberOfProcessors;
    double sqtotal;

    BrownianMotionThread(int i, int T, int N, int numberOfProcessors)
    {
        this.i = i;
        this.T = T;
        this.N = N;
        this.numberOfProcessors = numberOfProcessors;

    }

    public void run()
    {
        double r;
        for (int count=i;count<T;count+= numberOfProcessors) {

            /**started here so that x & y reset at each trial*/

            int x = 0;
            int y = 0;
                /**loop for steps*/
            for (int steps=0;steps<N;steps++) {
                r = Math.random();
            if      (r < 0.25) x--;
            else if (r < 0.50) x++;
            else if (r < 0.75) y--;
            else if (r < 1.00) y++;
                }
            /**squared total distance after each trial*/
            sqtotal = sqtotal + (x*x+y*y);
            }
    }
}

public class BrownianMotion {
    static double sqtotal;
    public static void main(String[] args) {

    /**starts vars for program*/

    final int N = Integer.parseInt(args[0]);
    final int T = Integer.parseInt(args[1]);
    final int numberOfProcessors = Runtime.getRuntime().availableProcessors();
    BrownianMotionThread[] threads = new BrownianMotionThread[numberOfProcessors];
    double avg;

    /**number of trials loop*/
    for(int i = 0; i < numberOfProcessors; i++)
    {
        threads[i] = new BrownianMotionThread(i,T,N,numberOfProcessors);
        threads[i].start();
    }
    for(int i = 0; i < numberOfProcessors; i++)
    {
        try 
        {
            threads[i].join();
        } 
        catch (InterruptedException e) 
        {
            e.printStackTrace();
        }
    }

    for(int i = 0; i < numberOfProcessors; i++)
    {
        sqtotal += threads[i].sqtotal;
    }


    /**average of squared total*/

    avg = sqtotal/T;
    System.out.println(avg);

    }

}

Answer 4

In order to find how long this will run, is to find the run complexity of the function, O(N^2). I believe.