Refactor code into mutlithreaded

[Maciej Kowalski]

Hi

In terms of multi-threading i am noob. I have written some programs which uses Java thread but nothing special.

Current code is single-threaded. It reads data from file, generate random numbers and check if that numbers belong to given inteval.

import java.io.*;
import java.util.*;

class Generator {
    private double mean;
    private double variance;
    private long amountOfNumbersToGenerate;

    public Generator(double mean, double variance, long amountOfNumbersToGenerate) {
        this.mean = mean;
        this.variance = variance;
        this.amountOfNumbersToGenerate = amountOfNumbersToGenerate;
    }

    double getMean() {
        return mean;
    }

    double getVariance() {
        return variance;
    }

    long getAmountOfNumbersToGenerate() {
        return amountOfNumbersToGenerate;
    }
}

class Interval {
    private double start;
    private double end;

    public Interval(double start, double end) {
        this.start = start;
        this.end = end;
    }

    double getStart() {
        return start;
    }

    double getEnd() {
        return end;
    }
}

class ParsedData {
    private Vector<Generator> generators;
    private Vector<Interval> intervals;

    public ParsedData(Vector<Generator> generators, Vector<Interval> intervals) {
        this.generators = generators;
        this.intervals = intervals;
    }

    Vector<Generator> getGenerators() {
        return generators;
    }

    Vector<Interval> getIntervals() {
        return intervals;
    }
}

class Worker extends Thread {

    public Worker() {

    }

}

class Start {
    static ParsedData readDataFromFile(String path) throws IOException {
        File file = new File(path);
        BufferedReader br = new BufferedReader(new FileReader(file));
        String line;
        line = br.readLine();
        String delimiter = "\\s+";

        // generators
        long generatorSize =  Long.parseLong(line);
        Vector<Generator> generators = new Vector<Generator>();
        for(long i =0; i < generatorSize; i++) {
            line = br.readLine();

            Scanner f = new Scanner(line);
            f.useLocale(Locale.US); //without this line the program wouldn't work on machines with different locales
            f.useDelimiter(delimiter);

            Generator g = new Generator(f.nextDouble(), f.nextDouble(), f.nextInt());
            generators.add(g);
        }

        line = br.readLine();
        long intervalSize = Long.parseLong(line);
        Vector<Interval> intervals = new Vector<Interval>();
        for(long i = 0; i < intervalSize; i++) {
            line = br.readLine();
            System.out.println(line);

            Scanner f = new Scanner(line);
            f.useLocale(Locale.US); //without this line the program wouldn't work on machines with different locales
            f.useDelimiter(delimiter);

            Interval interval = new Interval(f.nextDouble(), f.nextDouble());
            intervals.add(interval);
        }
        br.close();

        return new ParsedData(generators, intervals);
    }

    static double boxMullerMarsagliaPolarRand(double mean, double variance) {
        double micro = mean;
        double sigma = Math.sqrt(variance);
        double y, x, omega;
        Random random = new Random();

        do {
            x = random.nextDouble();
            y = random.nextDouble();
            omega = x * x + y * y;
        } while (!(0.0 < omega && omega < 1.0));
        double sigma_sqrt = sigma * Math.sqrt(-2.0 * Math.log(omega) / omega);
        double g = micro + x * sigma_sqrt;
        // float h = micro + y * sigma_sqrt;
        return g;
    }

    /////////////////////////////////////////
    // TODO: refactor code into multithreaded
    static Vector<Double> generateRandomNumbers(ParsedData parsedData) {
        Vector<Double> generatedNumbers = new Vector<Double>();

        for(int i = 0; i < parsedData.getGenerators().size(); i++) {
            Generator g = parsedData.getGenerators().get(i);
            for(long j = 0; j < g.getAmountOfNumbersToGenerate(); j++) {
                double random = boxMullerMarsagliaPolarRand(g.getMean(), g.getVariance());
                generatedNumbers.add(random);
            }
        }
        return generatedNumbers;
    }

    /////////////////////////////////////////
    // TODO: refactor code into multithreaded
    static int[] checkIntervals(ParsedData parsedData, Vector<Double> generatedNumbers) {
        int[] numberOfHits = new int[parsedData.getIntervals().size()];
        for(int j = 0; j < parsedData.getIntervals().size(); j++) {
            Interval interval = parsedData.getIntervals().get(j);
            for(int i = 0; i < generatedNumbers.size(); i++) {
                if (interval.getStart() < generatedNumbers.get(i) && generatedNumbers.get(i) < interval.getEnd()) {
                    numberOfHits[j]++;
                }
            }
        }
        return numberOfHits;
    }

    public static void main(String args[]) {
        int amountOfThreads = Integer.parseInt(args[0]);
        String path = System.getProperty("user.dir") + "/input.dat";
        ParsedData parsedData = null;

        try {
            parsedData = readDataFromFile(path);
        } catch (IOException e) {
            e.printStackTrace();
        }

        System.out.println(parsedData.getGenerators().size());
        System.out.println(parsedData.getIntervals().size());

        Vector<Double> generatedNumbers = generateRandomNumbers(parsedData);

        int[] numberOfHits = checkIntervals(parsedData, generatedNumbers);

        for (int i = 0; i < numberOfHits.length; i++) {
            Interval interval = parsedData.getIntervals().get(i);
            System.out.println("" + (i+1) + " " + interval.getStart() + " " + interval.getEnd() + " " + numberOfHits[i]);
        }

        System.out.println(generatedNumbers.size());
    }
}

here goes the input file:

30
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
10.0 5.0 1000000
50.0 2.0 1000000
-8.0 1.0 1000000
25
8.881966011250105  11.118033988749895
7.76393202250021  12.23606797749979
6.645898033750315  13.354101966249685
5.52786404500042  14.47213595499958
4.4098300562505255  15.590169943749475
3.2917960675006306  16.70820393249937
1.0557280900008408  18.94427190999916
-1.180339887498949  21.18033988749895
49.292893218813454  50.707106781186546
48.58578643762691  51.41421356237309
47.878679656440355  52.121320343559645
47.17157287525381  52.82842712474619
46.46446609406726  53.53553390593274
45.757359312880716  54.242640687119284
44.34314575050762  55.65685424949238
42.928932188134524  57.071067811865476
-8.5  -7.5
-9.0  -7.0
-9.5  -6.5
-10.0  -6.0
-10.5  -5.5
-11.0  -5.0
-12.0  -4.0
-13.0  -3.0
-1000.0 1000.0

I don't expect for anyone to write code for me.

But I don't know how to make this methods multi-threaded

   /////////////////////////////////////////
    // TODO: refactor code into multithreaded
    static Vector<Double> generateRandomNumbers(ParsedData parsedData) {
        Vector<Double> generatedNumbers = new Vector<Double>();

        for(int i = 0; i < parsedData.getGenerators().size(); i++) {
            Generator g = parsedData.getGenerators().get(i);
            for(long j = 0; j < g.getAmountOfNumbersToGenerate(); j++) {
                double random = boxMullerMarsagliaPolarRand(g.getMean(), g.getVariance());
                generatedNumbers.add(random);
            }
        }
        return generatedNumbers;
    }

    /////////////////////////////////////////
    // TODO: refactor code into multithreaded
    static int[] checkIntervals(ParsedData parsedData, Vector<Double> generatedNumbers) {
        int[] numberOfHits = new int[parsedData.getIntervals().size()];
        for(int j = 0; j < parsedData.getIntervals().size(); j++) {
            Interval interval = parsedData.getIntervals().get(j);
            for(int i = 0; i < generatedNumbers.size(); i++) {
                if (interval.getStart() < generatedNumbers.get(i) && generatedNumbers.get(i) < interval.getEnd()) {
                    numberOfHits[j]++;
                }
            }
        }
        return numberOfHits;
    }

Any help (links, info etc) would be great.

Best.

[Jayesh A Lalwani]

Your problem is a good candidate for java.util.concurrent.ThreadPoolExecutor. The ThreadPoolExecutor contains a thread pool and a queue. You create instances of class that implement Callable and add it to the queue. All the threads wait for callable objects to appear on the queue. When an object appears, one thread pops it out, executes it and then goes back to waiting. You can set up a executor to have a pool of 5-10 threads, and put 100 objects in the queue, and they will execute them one by one. When you submit a task to the queue, the execute returns a Future object. The Future object encapsulates the result of the task. It provides methods that allow your main thread to check if the task is done and also to get the result of the task

So, in your case, you need to decide how you want to break up your processing into tasks. In both methods you have 2 for loops. Do you want to have a task for each iteration of outer loop, or have a task per iteration of the inner loop. More tasks mean smaller tasks, and that means you can have better progress tracking (if you need in the future). However, more tasks also means that you will have to do some sort of processing after tasks are complete to merge the results. so depending on how much work it is to merge the results, you might to have bigger tasks.

I would split generateRandomNumbers to have a task per iteration of inner loop. Since, all you do is add the result to a list. I would split checkIntervals to have a task per iteration of outerloop, since the inner loop counts the number of hits.

[Maciej Kowalski]

Jayesh A Lalwani wrote:Your problem is a good candidate for java.util.concurrent.ThreadPoolExecutor. The ThreadPoolExecutor contains a thread pool and a queue. You create instances of class that implement Callable and add it to the queue. All the threads wait for callable objects to appear on the queue. When an object appears, one thread pops it out, executes it and then goes back to waiting. You can set up a executor to have a pool of 5-10 threads, and put 100 objects in the queue, and they will execute them one by one. When you submit a task to the queue, the execute returns a Future object. The Future object encapsulates the result of the task. It provides methods that allow your main thread to check if the task is done and also to get the result of the task

So, in your case, you need to decide how you want to break up your processing into tasks. In both methods you have 2 for loops. Do you want to have a task for each iteration of outer loop, or have a task per iteration of the inner loop. More tasks mean smaller tasks, and that means you can have better progress tracking (if you need in the future). However, more tasks also means that you will have to do some sort of processing after tasks are complete to merge the results. so depending on how much work it is to merge the results, you might to have bigger tasks.

I would split generateRandomNumbers to have a task per iteration of inner loop. Since, all you do is add the result to a list. I would split checkIntervals to have a task per iteration of outerloop, since the inner loop counts the number of hits.

Wooooow! This forum is better than StackOverflow.

Thanks for so detailed explanation.

[Henry Wong]

A few points to consider (assuming that you are considering threading to go faster)...

1. It takes time to start and coordinate threads. You will be paying a time cost for this, so short tasks are not a good candidate for threading... meaning that the multithreaded version can take longer to run than the single threaded version.

2. It takes time to synchronize between threads -- so consider distributing work as coarse as possible. The optimal case is to have each thread get all its sub-tasks once. Of course, if the sub-tasks have different execution times, then you will need to get more finer.... however, if you get too fine, then, again, the multithreaded version can take longer to run than the single threaded version.

3. If order matters, then it will be much harder. If order matters, then you will need synchronization between threads. In the extreme case, it simply isn't possible to go multithreaded. In the other cases, this synchronization takes time (and the threads will be effectively single threaded while this is happening)... and again, the multithreaded version can take longer to run than the single threaded version.

4. Threads is only useful when there are resources to run the threads. Lots of threads running on lots of cores is the best case. If you are running on a single core processor box, then you have lots of threads trying to share the one available core ... and again, the multithreaded version can take longer to run than the single threaded version.


Henry

[Jeff Verdegan]

Henry Wong wrote:
4. Threads is only useful when there are resources to run the threads. Lots of threads running on lots of cores is the best case. If you are running on a single core processor box, then you have lots of threads trying to share the one available core ... and again, the multithreaded version can take longer to run than the single threaded version.

That's an important point, excellently stated. (Emphasis added by me.) I think a lot of beginners don't realize this.

It's like you have 10 tasks written down on a piece of paper. You can hand that paper to one minion and tell him to go off and do those tasks. But if you have 10 minions, you can tear that paper into 10 pieces (one for each task--like starting 10 threads) and hand each piece to one minion, and they can go off and each can do one task. Since all 10 tasks are now being executed at the same time, by 10 different minions, they get done faster. But if you have just one minion, tearing the paper into 10 separate pieces (threads) doesn't help, because he can still only do one tasks at a time.

Another possible breakdown of resources and threads to use them is one thread to read the data from the file or network and stick it into a work queue, and then one or more threads (depending on how many cores you have) to read from that queue and process the data. If you're reading from multiple input sources, other than multiple files on the same physical disk, you might also benefit from multiple reader threads rather than just one.